圖論導引（第二版）

《圖論導引（第二版）》是2014年電子工業出版社出版的圖書。

內容簡介

本書系統地介紹了圖論的基本概念、基本定理和算法，同時還介紹了一些懸而未決的圖論問題和圖論的新研究成果，旨在幫助讀者理解並掌握圖的結構和解決圖論問題的技巧。

全書包含8章和7個附錄。第1～4章介紹圖的概念、樹和距離、匹配問題和圖的分解問題、圖的連通性等基本內容；第5～8章分別介紹了組合圖論、拓撲圖論的知識，圖論中的邊和環，以及圖論的其他主題。書中配有大量例題和超過1200道習題，使讀者容易理解書中的概念和定理，並掌握證明技巧。本書內容豐富，具有很多可選擇閱讀的章節，可以供不同層次的讀者使用。

目　錄

第1章 基本概念

11 什麼是圖

1.1.1 定義

1.1.2 圖模型

1.1.3 矩陣與同構

1.1.4 分解和特殊圖

1.1.5 習題

12 路徑、 環和跡

1.2.1 圖的連通

1.2.2 二分圖

1.2.3 歐拉迴路

1.2.4 習題

13 頂點度和計數

1.3.1 計數和雙射

1.3.2 極值問題

1.3.3 圖解序列

1.3.4 習題

14 有向圖

1.4.1 定義和例子

1.4.2 頂點度

1.4.3 歐拉有向圖

1.4.4 定向圖和競賽圖

1.4.5 習題

第2章 樹和距離

21 基本性質

2.1.1 樹的性質

2.1.2 樹和圖中的距離

2.1.3 不相交生成樹（選學）

2.1.4 習題

22 生成樹和枚舉

2.2.1 樹的枚舉

2.2.2 圖的生成樹

2.2.3 分解和優美標記

2.2.4 分叉與歐拉有向圖

（選學）

2.2.5 習題

23 最佳化和樹

2.3.1 最小生成樹

2.3.2 最短路徑

2.3.3 計算機科學中的樹

（選學）

2.3.4 習題

第3章 匹配和因子

31 匹配與覆蓋

3.1.1 最大匹配

3.1.2 Hall匹配條件

3.1.3 最小最大定理

3.1.4 獨立集與覆蓋

3.1.5 支配集(選學)

3.1.6 習題

32 算法及套用

3.2.1 最大二分匹配

3.2.2 加權二分匹配

3.2.3 穩定匹配（選學）

3.2.4 快速二分匹配（選學）

3.2.5 習題

33 一般圖中的匹配

3.3.1 Tutte 1因子定理

3.3.2 圖的f因子（選學）

3.3.3 Edmonds開花算法

（選學）

3.3.4 習題

第4章 連通度和路徑

41 割與連通度

4.1.1 連通度

4.1.2 邊連通度通常

4.1.3 塊

42 k通圖

4.2.1 2連通圖

4.2.2 有向圖的連通度

4.2.3 k通圖與k邊連通圖

4.2.4 Menger定理的套用

4.2.5 習題

43 網路流問題

4.3.1 最大網路流

4.3.2 整數流

4.3.3 供應與需求(選學)

4.3.4 習題

第5章 圖的著色

51 頂點著色和上界

5.1.1 定義和實例

5.1.2 上界

5.1.3 Brooks定理

5.1.4 習題

52 k色圖的構造

5.2.1 大色數圖

5.2.2 極值問題與Turn

定理

5.2.3 顏色臨界圖

5.2.4 強制細分

5.2.5 習題

53 計數方面的問題

5.3.1 真著色的計數

5.3.2 弦圖

5.3.3 完美圖點滴

5.3.4 無環定向的計數

(選學)

5.3.5 習題

第6章 可平面圖

61 嵌入與歐拉公式

6.1.1 平面作圖

6.1.2 對偶圖

6.1.3 歐拉（Euler）公式

6.1.4 習題

62 可平面圖的特徵

6.2.1 Kuratowski定理的

預備知識

6.2.2 凸嵌入

6.2.3 可平面性的測試

(選學)

6.2.4 習題

63 可平面性的參數

6.3.1 可平面圖的著色

6.3.2 交叉數

6.3.3 具有更高虧格的表面

(選學)

6.3.4 習題

第7章 邊和環

71 線圖與邊著色

7.1.1 邊著色

7.1.2 線圖的性質(選學)

7.1.3 習題

72 哈密頓環

7.2.1 必要條件

7.2.2 充分條件

7.2.3 有向圖中的環(選學)

7.2.4 習題

73 可平面性、 著色與環

7.3.1 Tait定理

7.3.2 Grinberg定理

7.3.3 鯊魚圖(選學)

7.3.4 流與環覆蓋(選學)

7.3.5 習題

第8章 其他主題

81 完美圖

8.1.1 完全圖定理

8.1.2 弦圖的再研究

8.1.3 其他完美圖類

8.1.4 非完美圖

8.1.5 強完美圖猜想

8.1.6 習題

82 擬陣

8.2.1 遺傳系統及示例

8.2.2 擬陣的性質

8.2.3 生成函式

8.2.4 擬陣的對偶

8.2.5 擬陣的子式與可

平面對偶

8.2.6 擬陣的交

8.2.7 擬陣的並

8.2.8 習題

83 拉姆齊理論

8.3.1 鴿巢原理的再研究

8.3.2 拉姆齊(Ramsey)定理

8.3.3 拉姆齊數

8.3.4 圖的拉姆齊理論

8.3.5 Sperner引理和頻寬

8.3.6 習題

84 其他極值問題

8.4.1 圖的編碼

8.4.2 分叉和流言

8.4.3 序列著色和可選擇性

8.4.4 由路徑和環構成的

劃分

8.4.5 周長

8.4.6 習題

85 隨機圖

8.5.1 存在性和數學期望

8.5.2 幾乎所有圖均具有的

性質

8.5.3 閾值函式

8.5.4 圖的演變和圖的參數

8.5.5 連通度、 團和著色

8.5.6 鞅

8.5.7 習題

86 圖的特徵值

8.6.1 特徵多項式

8.6.2 線性代數和實對稱陣

8.6.3 特徵值和圖參數

8.6.4 正則圖的特徵值

8.6.5 特徵值與擴張圖

8.6.6 強正則圖

8.6.7 習題

附錄A 數學基礎

附錄B 最最佳化和複雜度

附錄C 部分習題提示

附錄D 術語表

附錄E 補充閱讀

附錄F 參考文獻

附錄G 術語對照表