第 1 章 圖的基本概念 1.1 圖論發(fā)展歷史與特點(diǎn) 1.1.1 圖論 1.1.2 圖論的起源與發(fā)展（不同階段的經(jīng)典圖論問題案例） 1.1.3 圖論特點(diǎn) 1.2 圖的定義 1.2.1 定義 1.2.2 度 1.2.3 同構(gòu) 1.3 子圖和連通分支 1.3.1 子圖 1.3.2 導(dǎo)出子圖 1.3.3 連通分支 1.3.4 距離和中心 習(xí)題一 第 2 章 重要圖類與圖運(yùn)算 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 強(qiáng)連通分支 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 可達(dá)矩陣 2.5 運(yùn)算 2.5.1 刪去、添加和補(bǔ)圖 2.5.2 交和并 2.5.3 收縮和剖分 2.5.4 笛卡爾積 2.5.5 克羅內(nèi)克積 習(xí)題二 第 3 章 樹及其算法 3.1 樹和森林 3.1.1 樹的基本概念 3.1.2 破圈法和避圈法 3.1.3 六個等價命題 3.1.4 割邊 3.1.5 邊割 3.1.6 割點(diǎn) 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 強(qiáng)九龍樹猜想 3.5.3 Erd？s-Sós猜想 習(xí)題三 第 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 最小費(fèi)用最大流 4.3.1 問題描述 4.3.2 F增廣圈 4.3.3 Klein算法 習(xí)題四 第 5 章 遍歷性及其算法 5.1 Euler圖和有向Euler圖 5.1.1 定義 5.1.2 Fleury算法 5.1.3 編碼盤設(shè)計 5.2 中國郵遞員問題 5.2.1 問題描述 5.2.2 奇偶點(diǎn)圖上作業(yè)法 5.3 Hamilton圖 5.3.1 定義 5.3.2 閉包 5.3.3 格雷碼與立方體的Hamilton圈 5.4 有向Hamilton圖 5.4.1 強(qiáng)連通的充要條件 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猜想 習(xí)題五 第 6 章 獨(dú)立集及其算法 6.1 獨(dú)立集和覆蓋 6.1.1 獨(dú)立數(shù)和覆蓋數(shù) 6.1.2 性質(zhì) 6.1.3 極大獨(dú)立集的計算 6.1.4 獨(dú)立集與連通度的聯(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 頂點(diǎn)著色 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)猜想 習(xí)題六 第 7 章 匹配及其算法 7.1 邊獨(dú)立集和邊覆蓋 7.1.1 邊獨(dú)立數(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飽和頂點(diǎn) 7.3.2 增廣鏈 7.3.3 Hall定理 7.3.4 匈牙利算法 7.4 最優(yōu)匹配 7.4.1 最優(yōu)匹配的概念 7.4.2 可行頂標(biāo) 7.4.3 Kuhn-Munkres算法 7.5 相關(guān)猜想 習(xí)題七 第 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ù)學(xué)描述 8.5.2 五色定理 8.6 平面性檢測算法 8.6.1 DMP算法 8.6.2 DMP算法的證明 習(xí)題八 第9章 應(yīng)用案例拓展 9.1 拉普拉斯矩陣在網(wǎng)絡(luò)中的應(yīng)用 9.1.1 隨機(jī)游走與電網(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 圖能量在化學(xué)與網(wǎng)絡(luò)中的應(yīng)用 9.3.3 相關(guān)猜想 習(xí)題九 參考文獻(xiàn) 名詞索引