文档介绍：该【图论29电子科大杨春】是由【闰土】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【图论29电子科大杨春】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Email:******@
图论及其应用
任课教师:杨春
数学科学学院
2021/9/12
1
本次课主要内容
(二)、边独立集与边覆盖
拉姆齐问题简介
(一)、独立集与覆盖
(四)、拉姆齐数r(m,n)
(三)、点临界图与边临界图
2021/9/12
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的一个最大独立集
2021/9/12
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的一个最小点覆盖
2021/9/12
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的一个点独立集,于是有:
2021/9/12
5
α(G)≥|V-K|=n-β(G)
由上面两个不等式,得到:
α(G)+β(G)=n
(二)、边独立集与边覆盖
1、概念
定义3设G=(V,E)是一个图。E的一个边子集E1称为G的一个边独立集,如果E1中的边互不邻接;
G的一个包含边数最多的边独立集称为G的最大边独立集。最大边独立集包含的边数,称为G的边独立数,记为α‵(G)。
2021/9/12
6
注:一个边独立集实际上就是图的一个匹配,一个最大边独立集就是图的一个最大匹配。
G的一个边独立集
G的一个最大边独立集
定义4设G=(V,E)是一个图。E的一个边子集L称为G的一个边覆盖,如果G中的每个顶点均是L中某条边的端点。
G的一个包含边数最少的边覆盖称为G的最小边覆盖。最小边覆盖包含的边数,称为G的边覆盖数,记为β‵(G)。
2021/9/12
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。
2021/9/12
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)个分支。
2021/9/12
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。
2021/9/12
10