《圖論及其在計算機科學中的套用》是1995年中國礦業大學出版社出版的圖書，作者是周強等。
基本介紹
- 作者：周強 / 等
- ISBN：9787810404600
- 頁數：170
- 定價：8.00
- 出版社：中國礦業大學出版社
- 出版時間：1995-12
- 裝幀：平裝
內容介紹,作品目錄,
內容介紹
內容提要
本書分成兩部分。第一部分對圖論的基本概念做了簡明論述和深入討論，包括圖、通路和迴路、樹、割集和割點、有向圖和二分圖等。
第二部分是圖論在計算機科學中的套用，包括最小支撐樹、最短通路、最大匹配、網路流、中國郵遞員問題和旅行售貨員等問題的算法和計算機實現。
書中穿插著一些有名的圖論問題和生動的例子，使讀者能理解和掌握如何用圖論的基本知識解決實際問題。每章後面編排了適量習題，幫助讀者通過練習掌握書本內容。既是一本好教材，又是一本好的科技讀物。
本書可作為理工各科高年級本科生和研究生教材和參考書，也可供教師和有關工程技術人員及科研人員參考。
作品目錄
目錄
前言
第一章 引論
第一節 幾個有名的圖論問題
第二節 什麼是圖？
第三節 哥尼斯堡七橋問題的解
習題
第二章 通路和迴路
第一節 同構圖
第二節 子圖
第三節 邊鏈、通路和迴路
第四節 連通圖、非連通和成分
第五節 歐拉圖
第六節 圖的運算
第七節 歐拉圖的進一步討論
第八節 哈密爾頓通路和迴路
習題
第三章 有向圖
第一節 什麼是有向圖？
第二節 有向圖的種類
第三節 成對比較和競賽
第四節 在邏輯上的套用
習題
第四章 樹
第一節 樹的概念和認識
第二節 樹的性質
第三節 根樹和二元樹
第四節 支撐樹
第五節 基本迴路
第六節 怎樣找出所有的生成樹
習題
第五章 割集和割點
第一節 割集
第二節 割集的性質
第三節 圖中所有的割集
第四節 基本迴路和割集
習題
第六章 圖的矩陣表示
第一節 關聯矩陣
第二節 迴路矩陣
第三節 基本迴路矩陣和迴路矩陣的秩
第四節 割集矩陣
第五節 Af、Bf和Cf之間的關係
第六節 在開關網路中的套用
第七節 鄰接矩陣
第八節 最小支撐樹
習題
第七章 平面圖
第一節 公用設備問題
第二節 平面圖概念
第三節 地圖四色問題
第四節 歐拉公式
第五節 分塊問題
第六節 兩個典型的非平面圖
第七節 五色定理
習題
第八章 最短通路算法
第一節 最短通路問題
第二節 Dijkstra算法
第三節 任意兩點間的最短通路
習題
第九章 覆蓋和匹配
第一節 二分圖
第二節 覆蓋
第三節 匹配
第四節 匈牙利算法
第五節 庫恩－蒙克萊斯算法
習題
第十章 網路的最大流問題
第一節 網路流的基本概念
第二節 最大流基本定理
第三節 標號法
第四節 最小費用流問題
習題
第十一章 中國郵遞員問題
習題
第十二章 旅行售貨員問題
第一節 TSP 的表示
第二節 分支和界限方法
第三節 快速TSP 算法
習題
參考文獻
前言
第一章 引論
第一節 幾個有名的圖論問題
第二節 什麼是圖？
第三節 哥尼斯堡七橋問題的解
習題
第二章 通路和迴路
第一節 同構圖
第二節 子圖
第三節 邊鏈、通路和迴路
第四節 連通圖、非連通和成分
第五節 歐拉圖
第六節 圖的運算
第七節 歐拉圖的進一步討論
第八節 哈密爾頓通路和迴路
習題
第三章 有向圖
第一節 什麼是有向圖？
第二節 有向圖的種類
第三節 成對比較和競賽
第四節 在邏輯上的套用
習題
第四章 樹
第一節 樹的概念和認識
第二節 樹的性質
第三節 根樹和二元樹
第四節 支撐樹
第五節 基本迴路
第六節 怎樣找出所有的生成樹
習題
第五章 割集和割點
第一節 割集
第二節 割集的性質
第三節 圖中所有的割集
第四節 基本迴路和割集
習題
第六章 圖的矩陣表示
第一節 關聯矩陣
第二節 迴路矩陣
第三節 基本迴路矩陣和迴路矩陣的秩
第四節 割集矩陣
第五節 Af、Bf和Cf之間的關係
第六節 在開關網路中的套用
第七節 鄰接矩陣
第八節 最小支撐樹
習題
第七章 平面圖
第一節 公用設備問題
第二節 平面圖概念
第三節 地圖四色問題
第四節 歐拉公式
第五節 分塊問題
第六節 兩個典型的非平面圖
第七節 五色定理
習題
第八章 最短通路算法
第一節 最短通路問題
第二節 Dijkstra算法
第三節 任意兩點間的最短通路
習題
第九章 覆蓋和匹配
第一節 二分圖
第二節 覆蓋
第三節 匹配
第四節 匈牙利算法
第五節 庫恩－蒙克萊斯算法
習題
第十章 網路的最大流問題
第一節 網路流的基本概念
第二節 最大流基本定理
第三節 標號法
第四節 最小費用流問題
習題
第十一章 中國郵遞員問題
習題
第十二章 旅行售貨員問題
第一節 TSP 的表示
第二節 分支和界限方法
第三節 快速TSP 算法
習題
參考文獻
