1 图论概述
1.1 发展历史
- 第一阶段：
1736：欧拉发表首篇关于图论的文章，研究了哥尼斯堡七桥问题，被称为图论之父
1750：提出了拓扑学的第一个定理，多面体欧拉公式：V-E+F=2
- 第二阶段（19~20世纪）：
1852: Francis Guthrie提出四色问题
1856: Thomas P. Kirkman & William R.Hamilton研究了哈密尔顿图
1878: Alfred Kempe给出给出四色定理证明
1890: 希伍德（Heawood）推翻原有四色定理证明
1891: 彼得森（Petersen 丹麦）给出关于图论的理论知识的第一篇论文
1936: 哥尼格(Dénes Kőnig Hungarian), 写出第一本图论专著《有限图与无限图的理论》，图论成为了一门独立学科
- 第三阶段（现代图论）：
1941: F. P. Ramsey开创 Extremal graph theory
1959: Erd˝os and Rényi 引入随机图理论 （边的存在的概率为p）
1976: Kenneth Appel & Wolfgang Haken使用计算机最终证明了四色问题
1.2 参考教材
Graph Theory with Application - J.A. Bondy and U.S.R. Murty, Elsevier, 1976
《图论及其应用》 经典教材，吴望名译，有电子版
Graph theory - J.A. Bondy and U.S.R. Murty, Springer, 2008
《图论》GTM244，可以认为是 “Graph Theory with Application” 的第二版，推荐教材
Graph Theory, 5th - Reinhard Diestel, Springer, 2017
《图论》GTM173，有电子版
Introduction to Graph Theory, 2nd- Douglas B. West, 2017
入门教材
2 ，图的初步知识
（注：一般考虑simple graph (no graph loops or multiple edges), 且阶大于等于2）
2.1 规则图
Definition: 所有顶点的度相同的图叫不规则图 (irregular graph)
Definition: 只有一对顶点的度相同的图叫几乎不规则图 (almost irregular graph)
Theorem:
1）不规则图不存在
2）恰好存在两个阶数相同的几乎不规则图，且互为补图（顶点相同，边合起来是完全图）
3）对于任意最大值为n的正整数集合，存在n+1阶的图，使其顶点数正好等于这些整数
（以上结论不适用于多重图和加权图）
2.2 正则图
Definition: 所有顶点的度为r的图叫 r-正则图 (r-regular graph)
e.g. 单连通的0-regular是单个点，单连通的1-regular是一条边的图，单连通的2-regular是一个圈，单连通的3-regular称为立方图
Theorem: n阶r正则图存在，只要r, n不都是奇数，且r<=n-1
常用正则图：
Kn: n阶完全图，r = n-1
Cn: n(n>=3)阶圈， r = 2
Qn: 2^n阶的超立方体(n-cube), r = n
Kr,r: 2r阶的二分图
2.3 二分图（bipartite graph）
Definition：顶点被分为两个集合，所有边只在两个集合之间连接的图叫二分图
Theorem：图G是二分图 <=> G中无奇圈
2.4 子图
图G，子图（subgraph）H
subgraph ---> spanning subgraph
---> induced subgraph ---> vertex-delete subgraph
spanning subgraph: 生成子图，H和G的顶点相同
induced subgraph: 诱导子图，H = G[S] (从图中去除1个或多个顶点)
vertex-delete subgraph: 去顶点子图，从图中去除1个顶点
Theorem：任意图都可以表示为某个正则图的导出子图
未解问题：给定某一图G的所有去顶点子图，是否能够重构出唯一的图G（同构意义上是唯一的）？该
2.5 距离
Definition：连通图（connected），由多个连通分支（component）构成的图为不连通图（disconnected）。
G-v 比 G有更多的连通分支，则v称为G的割点（cut-vertex）
G-e 比 G有跟多的连通分支，则e称为G的桥（bridge）
Theorem:
连通图G，e是桥 <=> e不属于G的任何一个圈 <=> 存在顶点u，v，使得任意路径u-v的路径经过e
连通图G，w是割点 <=> 存在顶点u，v，使得任意路径u-v的路径经过w
Definition：
顶点x-y之间的距离（distance）：所有x-y路径的最小长度。
顶点v的离心率（eccentricity）：v到距离v最远顶点u的距离，u被称为v的离心顶点（eccentric vertix）
中心顶点：G中离心率最小的顶点
2.6 Tree
Definition：不包含圈的连通图为树（Tree）
Theorem：图G是树 <=> G中任意两个顶点都有且只有一条连通路径
n阶树有n-1条边
在G内添加任意一条边，就会形成一个回路。
去掉任意一条边，就不再连通。
G内的任意两个顶点能被唯一路径所连通。
一颗树的每一个节点都可以作为根
Definition：叶子（leaf）：树中度为1的节点
Theorem：树至少有两个节点
Definition：生成树（spanning graph）：图G的生成子图T是树，则T称为G的生成树
最小生成树：加权边之和最小的生成树
克鲁克斯算法：依次选择最小权的边，但保证不形成圈，可以生成最小生成树
3，图的遍历
Definition：
对于某个顶点序列（v1，v2，..., vk）
通路 (walk) ---> 路径 (path) ---> 圈 (circle)
| |
v v
---> 迹 (trail) ---> 回路 (circuit)
闭合的含义：v1=vk
walk: 所有 vi-vi+1 都是图的边
path: 所有的顶点不重复，闭合path为circle
trail: 所有边不重复. 闭合trail为circuit
注：path -> trail, circle -> circuit
3.1 欧拉图问题（遍历所有边不能重复，一笔画问题）
欧拉回路 (Eulerian circuit): 包含G中所有边的回路
欧拉迹 (Eulerian trail or Eulerian tour): 包含G中所有边的迹
包含一个欧拉回路的连通图为欧拉图
Theorem：
连通图G是欧拉的 <=> 每个顶点的度是偶数，（注：G可以是多重图）
连通图G含有欧拉迹 <=> 图G中恰好有两个顶点是奇数度 （注：G可以是多重图，欧拉迹从这两个奇数度的顶点开始和结束）
3.2 中国邮递员问题（遍历所有边可以重复）
Definition：欧拉通路：经过G的所有边的最短闭通路
找到欧拉通路的方法：对奇数度的顶点添加多重边，使每个顶点的度都是偶数
Theorem：欧拉通路一定经过G中的桥两次 （注：也即是是说讲桥复制为欧拉多重图）
注：加权图也可以用类似思路解决
3.3，哈密尔顿问题 (遍历所有点不能重复)
Definition：经过图中所有顶点的圈为哈密尔顿圈，包含哈密尔顿的圈为哈密尔顿图。
还没有任何理论可以精确判定一个图是否是哈密尔顿图，但已有如下结论
Theorem:
设G是一个n阶图，每个顶点的度>=n/2, 则G为哈密尔顿图；
（奥尔定理）如果n阶图G中任意一对不相邻的顶点的度数和大于等于n，则G是哈密尔顿图；
如果G是哈密尔顿图，那么任意去掉G的k个顶点，剩余的图最多含有k个连通分支；
3.4 旅行商问题 （遍历所有点可以重复）(TSP)
TSP（Traveling Salesman Problem），通过优化算法求解
4，图的匹配和分解
4.1 匹配（Matching）
（研究二分图中两个集合中元素的配对问题）
Definition: 一组互不相邻的边组成的集合叫做匹配（matching）（匹配的概念可以用于所有的图）
相异代表系：n个非空集合，每个集合挑出一个元素，这n个元素互不相同。因此，集合系有相异代表系，等价于对应的二分图（集合系和元素组成二分图的顶点集合）含有大小为n的匹配。
（霍尔定理 Philip-Hall's Theorem）n个非空集合存在相异代表系 <=> 任意k个集合的并，含有不少于k个元素 （k=1,…,n）。
Definition: G中包含边最多的匹配为最大匹配
Definition: 匹配覆盖了图中所有的顶点的匹配为完美匹配 (n阶图的完美匹配的大小为n/2)
(塔特定理) 图G有完美匹配 <=> 对于任意一个顶点的真子集S，都有 k0(G-S) <= |S|, 其中k0(G)表示G中奇数阶连通分支的数量
1-regular graph有完美匹配
2-regular graph有完美匹配 <=> G中每个连通分支都是一个偶阶圈
3-regular graph（立方图） （彼得森定理）每个无桥立方图含有一个完美匹配
4.2 正则图的1-因子分解
Definition：
图G的1-正则生成子图称为1-因子图 （1-因子图的边为图G的完美匹配）
图G的边集合可以表示为多个1-因子图的划分，则G称为1-因子分解图
由定义可知，每个1-因子分解图必定是一个偶数阶的r-正则图
注：反之不成立，例如彼得森图（10阶3-正则图）不是1-因子分解图
Theorem：偶数阶完全图是1-因子分解图；
猜想：若G是n阶r-正则图，且r>=n/2，则G是1-因子分解图。可分解为r个1-因子图
4.3 正则图的2-因子分解（圈分解）
Theorem：
（彼得森给出证明）图G是2-因子分解图 <=> G是r-正则，r为偶数；
完全图的分解定理（2012年证明，之前为阿尔斯波猜想）
（布莱恩特-霍斯利-彼得森定理）
1，n为奇数 (n>=3)，m1+m2+…+mt = n(n-1)/2, Kn可以分解为Cm1, Cm2, … , Cmt；
2，n为偶数 (n>=4)，m1+m2+…+mt = n(n-2)/2, Kn-M可以分解为Cm1, Cm2, … , Cmt ，其中M是Kn中的一个完美匹配；
推论：n为奇数，且m可以整除n(n-1)/2，那么Kn为Cm-可分解图；
再推论：n为奇数，Kn是哈密尔顿因子分解图（每个圈是哈密尔顿圈）
应用：
斯坦纳三元系（Steiner triple systems）问题
n个元素，每3个元素为一组（称为三元组）， 每一对元素恰好落在一个三元组中，这个分组称为斯坦纳三元系
等价于将Kn分解为多个C3
5，图的画法（可平面图，交叉点数）
Definition：如果图G能在平面上画出来，且任何两条边不相交，则称G为可平面图（planar graph），将可平面图在平面上画出得到的图为平面嵌入图（planar embedding）或平面图；
Three Houses and Three Utilities Problem等价为K3,3 是不是可平面图
最大平面图的区域都是三角形
欧拉多面体公式：V-E+F=2
多面体可以投影到平面上形成多面体的平面图
欧拉恒等式：G是连通的平面嵌入图，有n个顶点、m条边、r个区域，则n-m+r=2
Theorem：平面图G，则m<=3n-6，其中n为阶数，m为边数
推论：每个平面图都包含一个不超过5度的顶点；
（以下两个定理等价）
库拉托夫斯基定理：图G是可平面图 <=> G不包含K5和K3,3的剖分子图作为其子图
注：在图G的边上插入任意个（可以是0个）2度的顶点得到的图称为G的剖分子图
瓦格纳定理：图G是可平面图 <=> K5和K3,3都不是G的缩图
注：将图G中的某条边收缩为一个顶点，并删除重叠的顶点和边，形成的图为缩图（剖分图，则H是G的缩图）
缩图定理：对于任意一个含有无限个图的图集合，必定有一个图是另一个图的缩图
Definition：把图G画在平面上，产生的最少交叉点数目称为图G的交叉数cr(G) （crossing number）
Definition：把图G用直线画在平面上，产生的最少交叉点数目称为图G的直线段交叉数cr_(G) （rectilinear crossing number）
Theorem：cr(G) >= m-3n+6
cr(Kn) <= ¼ floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2), 其中，当n<=12，上式中的等号成立
（法里定理）可平面图可以用直线画法无交叉点，即cr_(G) = 0
6，图的着色（顶点着色，边着色）
四色定理：每个可平面图的顶点能够以四种或更少的颜色被着色，且每两个相邻顶点的颜色不同