內容介紹
內容簡介
本書介紹了有關圖論的基本概念和典型的圖論算法，結合曆屆賽題分析如何把一個實際問題
抽象化為數學中的圖論問題，並給出了程式解法。本書的特點是既有基本概念的講解及對所解問
題的分析，又有編程的思路與參考程式。是參加國際和全國奧林匹克競賽學生的必讀書，也可作為
大學生的參考書。
作品目錄
目錄
第一章 基本概念
1.1 引言
1.2 圖的定義
1.3 道路與迴路
1.4 樹
第二章求最短路徑的算法及套用
2.1 求最短路
2.2 服務點設定問題1――求圖的中心
2.3 服務點設定問題2――求圖的P中心
2.4 服務點設定問題3――求圖的中央點
第三章 求最小生成樹
3.1 求無向圖的最小生成樹
3.2 求有向圖的最小樹形圖
第四章 圖的連通性
4.1 連通性的基本概念和定義
4.2 深度優先搜尋（dfs）
4.3 求割頂和塊
4.4 求極大強連通子圖
4.5 求最小點基
4.6 可靠通訊網的構作
第五章 支配集與獨立集
5.1 求支配集
5.2 求獨立集
第六章 網路流及其套用
6.1 求網路的最大流
6.2 求容量有上下界的網路的最大流和最小流
6.2.1 求容量有上下界的網路的最大流
6.2.2 求容量有上下界的網路的最小流
6.3 最小費用最大流問題
6.4 求容量有上下界的網路的最小費用最小流和套用實例
6.4.1 求容量有上下界的網路的最小費用最小流
6.4.2 一個套用實例――餐廳問題
6.5 求有供需約束的可行流
6.6 求圖的連通度
6.7 求圖的邊連通度
第七章 匹配問題
7.1 匹配的基本概念
7.2 求二分圖的最大匹配
7.3 求二分圖的完備匹配
7.4 求二分圖的最佳匹配
7.5 求任意圖的最大匹配
7.6 求最小邊的覆蓋
第八章 著色問題
8.1 求頂色數
8.2 求邊色數
8.2.1 邊色數
8.2.2 邊色數的一個實際套用
第九章 可行遍性問題
9.1 中國郵路問題
9.2 貨郎問題1
9.3 貨郎問題2
9.4 工作的最佳排序問題
