《图论新论》

1图和子图1

1.1 图和简图1

1.2 图的同构5

1.3 关联矩阵和相邻矩阵8

1.4 子图9

1.5 点的阶数11

1.6 路和相连13

1.7 循环16

2树18

2.1 树18

2.2 割裂边和边结集20

2.3 割裂点24

2.4 凯耒公式25

3连通图29

3.1 连通度29

3.2 块32

4欧拉环路和哈密顿循环36

4.1 欧拉环路36

4.2 哈密顿循环38

5匹配集49

5.1 匹配集49

5.2 二部图的匹配集和覆盖52

5.3 完全匹配集56

6边上色法62

6.1 边色数62

6.2 维申克定理65

7无关集和完整集70

7.1 无关集70

7.2 拉姆西定理73

7.3 杜拉恩定理应用80

7.4 舒尔定理83

7.5 一个几何问题84

8点上色法89

8.1 色数89

8.2 布鲁克斯定理94

8.3 哈琼斯猜想95

8.4 色多项式98

8.5 围长和色数103

9平面图106

9.1 平面上图和平面图106

9.2 对偶图111

9.3 欧拉公式115

9.4 桥117

9.5 库拉拓夫斯基定理124

9.6 五色定理和四色问题129

10有向图132

10.1有向图132

10.2 有向路136

10.3 有向循环139

11网络145

11.1流145

11.2 割集149

11.3 最大流－最小割集定理应用152

11.4 萌格定理155

12循环空间和边结集空间160

12.1环流和势差160

12.2 同顶树的棵数167