第 1 章 圖的基本概念 1.1 圖論發(fā)展歷史與特點 1.1.1 圖論 1.1.2 圖論的起源與發(fā)展（不同階段的經(jīng)典圖論問題案例） 1.1.3 圖論特點 1.2 圖的定義 1.2.1 定義 1.2.2 度 1.2.3 同構(gòu) 1.3 子圖和連通分支 1.3.1 子圖 1.3.2 導出子圖 1.3.3 連通分支 1.3.4 距離和中心 習題一 第 2 章 重要圖類與圖運算 2.1 重要圖類 2.1.1 完全圖 2.1.2 正則圖 2.1.3 二部圖 2.1.4 常見圖類 2.2 有向圖 2.2.1 定義 2.2.2 基礎(chǔ)圖 2.2.3 出度和入度 2.2.4 有向途徑 2.2.5 強連通分支 2.3 網(wǎng)絡(luò) 2.3.1 無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò) 2.3.2 Dijkstra算法 2.4 矩陣表示 2.4.1 鄰接矩陣 2.4.2 Laplace矩陣 2.4.3 關(guān)聯(lián)矩陣 2.4.4 可達矩陣 2.5 運算 2.5.1 刪去、添加和補圖 2.5.2 交和并 2.5.3 收縮和剖分 2.5.4 笛卡爾積 2.5.5 克羅內(nèi)克積 習題二 第 3 章 樹及其算法 3.1 樹和森林 3.1.1 樹的基本概念 3.1.2 破圈法和避圈法 3.1.3 六個等價命題 3.1.4 割邊 3.1.5 邊割 3.1.6 割點 3.2 支撐樹的計數(shù) 3.2.1 遞推公式 3.2.2 矩陣-樹定理 3.3 最小支撐樹 3.3.1 定義 3.3.2 Prim算法 3.3.3 Kruskal算法 3.4 二元樹與前綴碼 3.4.1 二元樹 3.4.2 有序二元樹的個數(shù) 3.4.3 前綴碼 3.4.4 Huffman樹 3.5 與樹有關(guān)的猜想 3.5.1 優(yōu)美樹猜想 3.5.2 強九龍樹猜想 3.5.3 Erd？s-Sós猜想 習題三 第 4 章 最大流及其算法 4.1 網(wǎng)絡(luò)模型 4.1.1 容量網(wǎng)絡(luò) 4.1.2 流 4.1.3 流值 4.1.4 最大流 4.2 最大流算法 4.2.1 增廣鏈 4.2.2 最大流Ford-Fulkerson算法 4.2.3 最大流最小截定理 4.2.4 最短增廣鏈算法 4.3 最小費用最大流 4.3.1 問題描述 4.3.2 F增廣圈 4.3.3 Klein算法 習題四 第 5 章 遍歷性及其算法 5.1 Euler圖和有向Euler圖 5.1.1 定義 5.1.2 Fleury算法 5.1.3 編碼盤設(shè)計 5.2 中國郵遞員問題 5.2.1 問題描述 5.2.2 奇偶點圖上作業(yè)法 5.3 Hamilton圖 5.3.1 定義 5.3.2 閉包 5.3.3 格雷碼與立方體的Hamilton圈 5.4 有向Hamilton圖 5.4.1 強連通的充要條件 5.4.2 回路 5.4.3 有向Hamilton圖的充分條件 5.5 連通度和邊連通度 5.5.1 連通度和邊連通度 5.5.2 2連通圖 5.5.3 3連通圖 5.6 堅韌度 5.6.1 堅韌度 5.6.2 邊堅韌度 5.7 相關(guān)猜想 5.7.1 關(guān)于Hamilton圖的Graffiti.PC猜想 5.7.2 Chvàtal猜想 習題五 第 6 章 獨立集及其算法 6.1 獨立集和覆蓋 6.1.1 獨立數(shù)和覆蓋數(shù) 6.1.2 性質(zhì) 6.1.3 極大獨立集的計算 6.1.4 獨立集與連通度的聯(lián)系 6.2 Ramsey數(shù) 6.2.1 Ramsey數(shù) 6.2.2 Ramsey數(shù)的上界 6.2.3 Ramsey數(shù)的下界 6.2.4 廣義Ramsey數(shù) 6.2.5 類似Ramsey數(shù)的問題 6.2.6 Turán定理 6.3 頂點著色 6.3.1 色數(shù) 6.3.2 色數(shù)上界 6.3.3 色數(shù)的下界 6.3.4 色多項式 6.4 支配集 6.4.1 定義 6.4.2 性質(zhì) 6.4.3 極小支配集的計算 6.5 相關(guān)猜想 習題六 第 7 章 匹配及其算法 7.1 邊獨立集和邊覆蓋 7.1.1 邊獨立數(shù)和邊覆蓋數(shù) 7.1.2 完美匹配 7.1.3 Tutte定理 7.2 邊著色 7.2.1 邊色數(shù) 7.2.2 Vizing定理 7.2.3 第一類圖和第二類圖 7.3 二部圖的最大匹配 7.3.1 M飽和頂點 7.3.2 增廣鏈 7.3.3 Hall定理 7.3.4 匈牙利算法 7.4 最優(yōu)匹配 7.4.1 最優(yōu)匹配的概念 7.4.2 可行頂標 7.4.3 Kuhn-Munkres算法 7.5 相關(guān)猜想 習題七 第 8 章 平面性及其算法 8.1 平面圖 8.1.1 平面圖和平圖 8.1.2 對偶圖 8.2 平面圖必要條件和Euler公式 8.2.1 平面圖的必要條件 8.2.2 Euler公式 8.3 極大平面圖和極大外平面圖 8.3.1 極大平面圖 8.3.2 極大外平面圖 8.4 Kuratowski定理 8.4.1 剖分圖和H分枝 8.4.2 Kuratowski定理 8.5 四色問題 8.5.1 四色問題的三種數(shù)學描述 8.5.2 五色定理 8.6 平面性檢測算法 8.6.1 DMP算法 8.6.2 DMP算法的證明 習題八 第9章 應(yīng)用案例拓展 9.1 拉普拉斯矩陣在網(wǎng)絡(luò)中的應(yīng)用 9.1.1 隨機游走與電網(wǎng)絡(luò) 9.1.2 圖聚類與圖分割 9.1.3 相關(guān)猜想 9.2 智能集群控制中的圖論問題 9.2.1 Kalman可控性 9.2.2 支配集在最小領(lǐng)航集中的應(yīng)用 9.2.3 相關(guān)猜想 9.3 圖能量的概念與應(yīng)用 9.3.1 圖能量的定義 9.3.2 圖能量在化學與網(wǎng)絡(luò)中的應(yīng)用 9.3.3 相關(guān)猜想 習題九 參考文獻 名詞索引