文档介绍：Email: yc517922@
图论及其应用
任课教师:杨春
数学科学学院
1
本次课主要内容
(二)、边独立集与边覆盖
拉姆齐问题简介
(一)、独立集与覆盖
(四)、拉姆齐数r (m, n)
(三)、点临界图与边临界图
2
1、概念
定义1 设G=(V ,E)是一个图。V的一个顶点子集V1称为G的一个点独立集,如果V1中的顶点互不邻接;
(一)、独立集与覆盖
G的一个包含顶点数最多的独立集称为G的最大独立集。最大独立集包含的顶点数,称为G的点独立数,记为α(G)。
v2
v1
v6
v5
v4
v3
v8
v7
G的一个独立集
v2
v1
v6
v5
v4
v3
v8
v7
G的一个最大独立集
3
定义2 设G=(V ,E)是一个图。V的一个顶点子集K称为G的一个点覆盖,如果E中的每条边至少有一个端点在K中。
G的一个包含顶点数最少的点覆盖称为G的最小点覆盖。最小点覆盖包含的顶点数,称为G的点覆盖数,记为β(G)。
v2
v1
v6
v5
v4
v3
v8
v7
G的一个点覆盖
v2
v1
v6
v5
v4
v3
v8
v7
G的一个最小点覆盖
4
定理1 (加莱) 对任意不含孤立点的n阶图G,有:
2、加莱恒等式
α(G)+ β(G)= n
证明:一方面,设V1是G的最大点独立集。因为G中每条边的端点最多一个在V1中,所以G中每条边的端点至少有一个在V-V1中。即V-V1构成G的一个点覆盖,于是有:
β(G)≦|V-V1|=n - α(G)
另一方面,设K是G的最小点覆盖。因为G中每条边的端点至少有一个在K中,所以G中每条边的端点至多有一个在V-K中。即V-K构成G的一个点独立集,于是有:
5
α(G) ≥|V-K|=n - β(G)
由上面两个不等式,得到:
α(G)+ β(G)= n
(二)、边独立集与边覆盖
1、概念
定义3 设G=(V ,E)是一个图。E的一个边子集E1称为G的一个边独立集,如果E1中的边互不邻接;
G的一个包含边数最多的边独立集称为G的最大边独立集。最大边独立集包含的边数,称为G的边独立数,记为α‵(G) 。
6
注:一个边独立集实际上就是图的一个匹配,一个最大边独立集就是图的一个最大匹配。
G的一个边独立集
G的一个最大边独立集
定义4 设G=(V ,E)是一个图。E的一个边子集 L 称为G的一个边覆盖,如果G中的每个顶点均是L中某条边的端点。
G的一个包含边数最少的边覆盖称为G的最小边覆盖。最小边覆盖包含的边数,称为G的边覆盖数,记为β‵(G) 。
7
G的一个边覆盖
G的一个最小边覆盖
2、加莱恒等式
定理2 (加莱) 对任意不含孤立点的n阶图G,有:
α‵(G)+ β‵(G)= n
证明:一方面, 设α‵(G)= k ,则G的最大匹配由k条边组成,且覆盖了2k个顶点。
所以,余下的n-2k个顶点至多需要n-2k条边就可以被覆盖,于是: β‵(G)≦k+(n-2k)=n-k。
8
所以,α‵(G)+ β‵(G)≦ k+ (n - k)= n
另一方面, 设X是G的一个最小边覆盖,则|X|= β‵(G)。
考虑导出子图F = G[X]。可以证明F中不会包含长度为3的迹。
若不然,设F中包含长度为3的迹。取该迹的中间边e,显然,X-e仍然构成G的边覆盖,与X的最小性矛盾。
所以,F中不包含长度为3和大于3的迹。也不包含圈。
所以,F中的每个连通分支必然为星图。F是森林。
因为,阶数为n,边数为n-k的森林包含k个连通分支。而F的边数为n - (n- β‵(G)) ,所以F有n- β‵(G)个分支。
9
从F的每个分支中选取一条边,可作成G的一个匹配,所以α‵(G) ≥ n- β‵(G)。
由上面两个不等式,得到: α‵(G)+ β‵(G)= n。
例1 确定下图G的α(G), β(G), α‵(G) , β‵(G)。
1
4
3
2
5
6
7
G
解:顶点2的左右两部分均是K4, 所以可以推知α(G)=2,再由加莱恒等式得: β(G) = 5 。
10