图论重点复习

冷不防 2021-09-26 18:36 1135阅读 0赞

# 一、重点概念 #

1、图：一个图是一个序偶（V，E），记为G=( V , E),其中：  
（1） V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；  
（2） E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。  
2、简单图：无环无重边的图称为简单图。  
3、图的度序列： 一个图G的各个点的度d1, d2,…, dn构成的非负整数组（d1, d2,…, dn）称为G的度序列 。  
4、图的图序列：一个非负数组如果是某简单图的度序列，我们称它为可图序列，简称图序列。  
5、联图：设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为 ：G1∨G2  
6、偶图： 所谓具有二分类（X, Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在中，另一个端点在Y中。  
7、树： 不含圈的图称为无圈图，树是连通的无圈图。  
8、森林： 称无圈图G为森林。  
9、生成树： 图G的一个生成子图T如果是树，称它为G的一棵生成树；若T为森林，称它为G的一个生成森林。  
10、最小生成树：在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。  
11、根树： 一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点。  
12、完全m元树： 对于根树T，若每个分支点至多m个儿子，称该根树为m元根树；若每个分支点恰有m个儿子，称它为完全m元树。  
13、迹：边不重复的途径称为迹  
14、 路：顶点不重复的途径称为库  
15、起点与终点重合的途径称为闭途径；起点与终点重合的迹称为闭迹；起点与重点重合的路称为圈，长度为k的圈称为k圈。  
16、连通图： 若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径），则称vi和vj是连通的。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图  
17、欧拉图与欧拉环游： 对于连通图G，如果G中存在经过每条边的闭迹，则称G为欧拉图，简称G为E图。欧拉闭迹又称为欧拉环游，或欧拉回路。  
18、 欧拉迹： 对于连通图G，如果G中存在经过每条边的迹，则称该迹为G的一条欧拉迹。  
19、哈密尔顿图与哈密尔顿圈：如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈，称为G的哈密尔顿圈。  
20、 哈密尔顿路：图G的经过每个顶点的路称为哈密尔顿路。  
21、匹配： 如果M是图G的边子集(不含环），且M中的任意两条边没有共同顶点，则称M是G的一个匹配或对集或边独立集。  
22、最大匹配 M： 如果M是图G的包含边数最多的匹配，称M是G的一个最大匹配。特别是，若最大匹配饱和了G的所有顶点，称它为G的一个完美匹配。  
23、最优匹配： 设G=(X, Y)是边赋权完全偶图，G中的一个权值最大的完美匹配称为G的最优匹配。  
24、因子分解： 所谓一个图G的因子分解，是指把图G分解为若干个边不重的因子之并。  
25、平面图：如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称为平面图。  
26、极大平面图：设G是简单可平面图，如果G是Ki (1≦i≦4),或者在G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称G是极大可平面图。  
27、边色数： 设G是图，对G进行正常边着色需要的最少颜色数，称为G的边色数，记为：X’（G）  
28、点色数：对图G正常顶点着色需要的最少颜色数，称为图G的点色数。图G的点色数用 X（G）表示。  
29、色多项式：对图进行正常顶点着色，其方式数Pk(G)是k的多项式，称为图G的色多项式。

# 二、重要结论 #

1、握手定理：图G= (V, E)中所有顶点的度的和等于边数m的2倍：  
![这里写图片描述][70]  
推论1 在任何图中，奇点个数为偶数。  
推论2 正则图的阶数和度数不同时为奇数  
2、托兰定理：若n阶简单图G不包含Kl+1，则G度弱于某个完全 l 部图 H，且若G具有与 H 相同的度序列，则:  
![这里写图片描述][70 1]  
3、树的性质：设T是( n , m )树，则：m = n - 1  
4、偶图判定定理： 图G是偶图当且仅当G中没有奇回路。  
5、欧拉图、欧拉迹的判定： 定理6 下列陈述对于非平凡连通图G是等价的：  
（1）G是欧拉图  
（2）G的顶点度数为偶数  
（3）G的边集合能划分为圈  
推论：连通非欧拉图G存在欧拉迹当且仅当G中只有两个顶点度数为奇数  
6、H图的判定  
（1） (必要条件) 若G为H图，则对V(G)的任一非空顶点子集S，有：  
![这里写图片描述][70 2]  
（2）(充分条件) 对于n≧3的单图G，如果G中有：  
![这里写图片描述][70 3]  
（3）(充分条件) 对于n≧3的单图G，如果G中的任意两个不相邻顶点u与v，有：  
![这里写图片描述][70 4]  
（4）(帮迪——闭包定理) 图G是H图当且仅当它的闭包是H图。  
（5）(Chvátal——度序列判定法) 设简单图G的度序列是(d1,d2,…,dn), 这里，d1≦d2≦…≦dn,并且n≧3.若对任意的m < n / 2,或者 dm > m,或者dn-m ≧ n-m,则G是H图。  
7、偶图匹配与因子分解  
（1）(Hall定理）设G=(X, Y)是偶图，则G存在饱和X每个顶点的匹配的充要条件是：  
![这里写图片描述][70 5]  
推论：若G是k (k>0)正则偶图，则G存在完美匹配。  
（2） (哥尼，1931) 在偶图中，最大匹配的边数等于最小覆盖的顶点数。  
（3）K2n可一因子分解。  
（4）具有H圈的三正则图可一因子分解。  
（5）K2n+1可2因子分解。  
（6）K2n可分解为一个1因子和n-1个2因子之和。  
（7）每个没有割边的3正则图是一个1因子和1个2因子之和。  
8、平面图及其对偶图  
（1）平面图的次数公式  
设G=(n, m)是平面图，则：  
![这里写图片描述][70 6]  
（2）平面图的欧拉公式  
( 欧拉公式 ) 设G=(n, m)是连通平面图，ф是G的面数，则：  
![这里写图片描述][70 7]  
几个重要推论：  
推论1：设G是具有n个点m条边ф个面的连通平面图，如果对G的每个面f ,有：deg (f) ≥ l ≥3,则：  
![这里写图片描述][70 8]  
推论2：设G是具有n个点m条边ф个面的简单平面图，则：  
![这里写图片描述][70 9]  
推论3 设G是具有n个点m条边的简单平面图，则：  
![这里写图片描述][70 10]  
（3）对偶图的性质  
平面图G的对偶图必然连通  
（4）极大平面图的性质  
设G是至少有3个顶点的平面图，则G是极大平面图，当且仅当G的每个面的次数是3且为单图。  
9、着色问题  
（1）边着色  
![这里写图片描述][70 11]  
【2】若G是偶图，则：  
![这里写图片描述][70 12]  
【3】(维津定理，1964) 若G是单图，则：  
![这里写图片描述][70 13]  
【4】设G是单图且Δ(G)>0。若G中只有一个最大度点或恰有两个相邻的最大度点，则：  
![这里写图片描述][70 14]  
【5】设G是单图。若点数n=2k+1且边数m>kΔ,则：  
![这里写图片描述][70 15]  
【6】设G是奇数阶Δ正则单图,若Δ>0,则：  
![这里写图片描述][70 16]

# 三、图论应用 #

1、 偶图匹配问题  
例1 有7名研究生 A, B, C, D, E, F, G毕业寻找工作。就业处提供的公开职位是：会计师(a) ,咨询师(b),编辑(c ),程序员(d), 记者(e), 秘书(f)和教师(g)。每名学生申请的职位如下：  
A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ;  
E : a, c, d, f ; F : c, e ; G : d, e, f, g ;  
问：学生能找到理想工作吗？  
解：如果令X=｛A, B, C, D, E, F, G｝,Y=｛a, b, c, d, e, f , g｝,X中顶点与Y中顶点连线当且仅当学生申请了该工作。于是，得到反映学生和职位之间的状态图：  
![这里写图片描述][70 17]  
问题转化为是否有饱和X每个顶点的一个匹配。  
当S取X中四元点集时，若取S=｛A,C,D,F｝,则有3=|N(S)|<|S|=4，所以，不存在饱和X每个顶点的匹配。  
2、着色问题  
（1）边着色问题  
例2 (排课表问题) 在一个学校中，有7个教师12个班级。在每周5天教学日条件下，教课的要求由如下矩阵给出：  
![这里写图片描述][70 18]  
其中，pij表示xi必须教yj班的节数。求：  
（1） 一天分成几节课，才能满足所提出的要求？  
（2）若安排出每天8节课的时间表，需要多少间教室？  
解：问题可模型为一个偶图。  
一节课对应边正常着色的一个色组。由于G是偶图，所以边色数为G的最大度35。这样，最少总课时为35节课。平均每天要安排7节课。  
如果每天安排8节课，因为G的总边数为240，所以需要的教室数为240/40=6  
例3 （比赛安排问题） Alvin (A)曾邀请3对夫妇到他的避暑别墅住一个星期。他们是：Bob和Carrie , David和Edith, Frank和Gena。由于这6人都喜欢网球运动，所以他们决定进行网球比赛。6位客人的每一位都要和其配偶之外的每位客人比赛。另外，Alvin将分别和David， Edith， Frank， Gena进行一场比赛。若没有人在同一天进行2场比赛，则要在最少天数完成比赛，如何安排？  
解：用点表示参赛人，两点连线当且仅当两人有比赛。这样得到比赛状态图。  
问题对应于求状态图的一种最优边着色(用最少色数进行正常边着色)。  
![这里写图片描述][70 19]  
由于n=2×3+1, 所以k=3。而Δ=5 ，m=16>3×5=kΔ,所以由定理5知：X’(G) = 6  
（2）点着色问题  
例4 课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数(MA)。现有10名学生(如下所示)需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。(学生用Ai表示）  
A1: LA, S ; A2: MA, LA, G ; A3: MA, G, LA;  
A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC;  
A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA;  
A10: GT, S。  
解：把课程模型为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。  
![这里写图片描述][70 20]  
如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求对应于点色数的着色。  
(1) 求点色数  
一方面，因图中含有奇圈(红色边), 所以，点色数至少为3。又因为点LA与该圈上每一个点均邻接，所以，点色数至少为4.  
![这里写图片描述][70 21]  
另一方面，我们用4种色实现了G的正常点着色，所以，图的点色数为4.  
（2）求安排—-具体着色  
![这里写图片描述][70 22]

[70]: /images/20210923/c06414ade3884a90aa08176fb08c7175.png
[70 1]: /images/20210923/e24f64f038af42cf8c92b1c57c3d3cf3.png
[70 2]: /images/20210923/b2e37533f3034e14880e2fbea7b16b2e.png
[70 3]: /images/20210923/ce6634ead0ef4b909bd5ebac4f0d1d99.png
[70 4]: /images/20210923/555a2228c4874df9ab38830f77318e69.png
[70 5]: /images/20210923/bcf3fa20ce354e40af74b93d65c65758.png
[70 6]: /images/20210923/6105358cff794d36b980c75127e64286.png
[70 7]: /images/20210923/c2d08b28f64d430cb968134e483064b3.png
[70 8]: /images/20210923/13e3e225c21949d0bf4983524b85cd24.png
[70 9]: /images/20210923/7e76ff551f894434a7a42dd51eb456ad.png
[70 10]: /images/20210923/a8bf0c4a901845808d84cbcd654c2406.png
[70 11]: /images/20210923/22b5779d93f8447a91b0b87715c197b4.png
[70 12]: /images/20210923/eb4277a3c6034313a655ad4c518b6986.png
[70 13]: /images/20210923/e5c6357ef7a448d6b87b2375ea2ec52a.png
[70 14]: /images/20210923/e79adff06fbb4952a8a574ccc16c3edc.png
[70 15]: /images/20210923/76a93c55b75f472cae1d3b481de1be1d.png
[70 16]: /images/20210923/5e18e90e3c284c3380108b1fbf209a12.png
[70 17]: /images/20210923/e7398093765749c4bcb57c71eb9deeb2.png
[70 18]: /images/20210923/7e16de1b8e864d78a1f6c316f345234e.png
[70 19]: /images/20210923/151e31d896ff4786b3bf1f61aefcff2e.png
[70 20]: /images/20210923/17a5f5ccd4e34013b40e5840a379ec3a.png
[70 21]: /images/20210923/5801a23f284b4f62bf6379998ac8e97f.png
[70 22]: /images/20210923/4367a01c335b4852847240efd3d22b0d.png