图论介绍(Graph Theory)

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(Traveling Salesman Problem),通过优化算法求解

4,图的匹配和分解

4.1 匹配(Matching)

(研究二分图中两个集合中元素的配对问题)

Definition: 一组互不相邻的边组成的集合叫做匹配(matching)(匹配的概念可以用于所有的图)

相异代表系:n个非空集合,每个集合挑出一个元素,这n个元素可以互不相同。因此,集合系有相异代表系,等价于对应的二分图(集合系和元素组成二分图的顶点集合)含有大小为n的匹配。

(霍尔定理)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,图的着色(顶点着色,边着色)

四色定理:每个可平面图的顶点能够以四种或更少的颜色被着色,且每两个相邻顶点的颜色不同

上一篇:Codeforces 1109D. Sasha and Interesting Fact from Graph Theory


下一篇:An Introduction to Measure Theory and Probability