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