![离散生期末题集合论与图论gra_第1页](http://file4.renrendoc.com/view/fa0a99a12eb5bafa45978a78225df301/fa0a99a12eb5bafa45978a78225df3011.gif)
![离散生期末题集合论与图论gra_第2页](http://file4.renrendoc.com/view/fa0a99a12eb5bafa45978a78225df301/fa0a99a12eb5bafa45978a78225df3012.gif)
![离散生期末题集合论与图论gra_第3页](http://file4.renrendoc.com/view/fa0a99a12eb5bafa45978a78225df301/fa0a99a12eb5bafa45978a78225df3013.gif)
![离散生期末题集合论与图论gra_第4页](http://file4.renrendoc.com/view/fa0a99a12eb5bafa45978a78225df301/fa0a99a12eb5bafa45978a78225df3014.gif)
![离散生期末题集合论与图论gra_第5页](http://file4.renrendoc.com/view/fa0a99a12eb5bafa45978a78225df301/fa0a99a12eb5bafa45978a78225df3015.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第三章连通度和匹配 基本内容 顶点连通度和边连通度 门格尔定理 匹配、霍尔定理3.3 霍尔定理(相异性条件)定理1 设G=(V1V2,E)是一个偶图,|V1|V2|。G中存在从V1到V2的完全匹配充分必要条件是V1中任意k个顶点(k=1,2, |V1|)至少与V2中的k个顶点相连接。该条件称为相异性条件例4 现有4名教师:张、王、李、赵,要求他们去教4门课程:数学、物理、电工和计算机科学。已知张能教数学和计算机科学;王能教物理和电工;李能教数学、物理和电工;赵只能教电工。如何安排才能使4位教师都能教课,并且每门课都有人教?共有几种方案? 用相异性条件判断一个偶图是否存在完全匹配常常很不方便,下
2、面的充分条件比较便于实际应用。定理2 设G=(V1V2,E)是一个偶图,|V1|V2|。G中存在从V1到V2的完全匹配的充分条件是存在正整数t,使得V1中每个顶点的度大于等于t,V2中每个顶点的度小于等于t。该条件称为t条件。 定理3 从t条件可以推出相异性条件。 证: 对于V1中的任意的v1,v2,vr,与它们关联的顶点个数m,从v1,v2,vr到V2的边数为e。根据t条件:v1中的每个顶点至少和t个顶点相关联,则ert。V2中的每个顶点至多和V1中的t个顶点相关联,则emt。故有,mtrt,即mt,结论成立。注意:定理3中反过来不能推出t条件。推论1 任何r-正则偶图G(V1V2,E)必有
3、一个完美匹配,其中r1。例某年级共开设7门课程,由7位教师承担。已知每位教师都能担任其中的3门课程。他们将自己能担任的课程报到教务处后,教务处人员发现每门课都恰好有3位教师能担任。问教务处人员能否安排这7位教师每人担任1门课,并且每门课都有人承担。第四章 平面图和图的着色本章内容:平面图及其欧拉公式 非哈密顿平面图(不要求) 和图的着色 库拉托斯基定理、对偶图 图的顶点着色 图的边着色(不要求)第一节 平面图及其欧拉公式内容:背景、平面图、面、偶拉公式、推论1.1 背景 在图论的理论研究和实际应用中,需要考虑一个图能否画在平面上使得它的边仅在端点相交的问题。若一个图能画在平面上使得它的边仅可能
4、在端点相交,则这个图称为平面图。于是在实际问题中,判断一个图是否是一个平面图是非常重要的。 例1在印刷电路的布线中,感兴趣的是知道一个特定的电网络是否可以嵌入平面上。 例2 如图所示(书上)H1,H2,H3表示三座楼房,W,G和E分别表示自来水厂、煤气管道和地下电缆。为了安全起见,要求这些管道不能直接接触交叉。书上图显然不是个好的设计方案。但工程设计要求能达到吗? 这就提出了这个图是否为平面图的问题。 例3 地图的着色(四色问题) 一个图可以用它的图解来表示,把一个图的图解就看成是这个图本身。但对一个给定的图,其图解的画法并不唯一,即从几何图形上看可以很不一样。一个图的图解不仅可以画在一个平面
5、上,还可以画在球面上或任一给定的曲面上。 下面将考虑这样一类图,其图解画在一个平面上时,有一种画法能使其边仅可能在顶点相交,而在边的内部不相交,这种图称为平面图。1.2 平面图、面定义1 若G的图解已画在平(曲)面S上,而且任何两条边均不相交(除可能在端点相交外),则图G称为嵌入平(曲)面S内。已嵌入平面S内的图称为平面图。若一个图可以嵌入平面,则称此图是可平面的 说明:可平面图:能画在平面上 ,但还没有画;平面图:已经画在平面上了。以后这两个概念不加区分。例如:图K4是可平面的,因为K4的一种平面嵌入法 ;图K5没有平面嵌入法; K5画不出来,并不等于就是非平面图,必须证明。实际上,K5是典
6、型的不可平面图,还有K3,3。定义2 平面图G把平面分成了若干个区域,这些区域都是连通的,称之为G的面,其中无界的那个连通区域称为G的外部面,其余的单连通区域称为G的内部面。说明:(1)平面图的每个内部面都是G的某个回路围成的单连通区域; (2)一个平面图可以没有内部面,但必有外部面,而且外部面唯一;例如:树作为平面图就没有内部面。(3)图K4所示的图有4个面,f4是外部面,f1,f2,f3都是内部面。 1.3 欧拉公式定理1(欧拉公式)设G=(p,q)是平面连通图,有f个面,则p-q+f=2。证:用数学归纳法证明,施归纳于面f的个数:注意:定理中的连通性是重要的。若G不连通,则定理不成立。但
7、却有下面的结论。推论:设G=(p,q)是一个具有f个面、k个分支的平面图,则p-q+f=k+11.4 欧拉公式的推论这些推论都是平面图的必要条件,不是充分条件。推论1 若G=(p,q)是平面连通图且每个面都是由长为n的回路围成的,则q=n(p-2)/(n-2) 一个最大可平面图是一个可平面图,对此可平面图中不能再加入边而不破坏可平面性。推论2 设G=(p,q)是一个最大可平面图,则G的每个面都是三角形,而且q=3p-6。推论3 若G=(p,q)是一个可平面连通图,而且G的每个面都是一个长为4的回路围成的,则q=2p-4推论4 若G=(p,q)是一个连通的平面图,p3,则q3p6。 若G是2连通
8、的且没有三角形,则q2p4。推论5 证明K5和K3,3都不是可平面图。 推论6 每个平面图G的顶点度的最小值不超过5,即(G)5 。 第二节 库拉托斯基定理、对偶图 内容:细分图、收缩图、二度结点内的同构、初等收缩、对偶替已经证明:(1) K5和K3,3不是平面图,而K5和K3,3的每个真子图显然都是平面图;( (2)显然,平面图的每个子图是平面图。因此,平面图中不含子图K5和K3,3。2.1 细分图定义1 设G=(V,E)是一个图,则(1)若x=uv是图G一条边,又w不是G的顶点,则当用uw和wv代替边x时,就称边x被细分。(2)若G的某些条边被细分,产生的图称为G的细分图,也称为二度顶点内
9、细分图。定义2 若两个图可以从一个图通过一系列的边细分得到,这两个图称为同胚的(homeomorphism),也称为二度顶点内同胚。例如:两个回路是同胚的。于是,一个图若含有同胚于K5或K3,3的子图,它就不是平面图。库拉托斯基指出,这个必要条件也是充分的。定理1(库拉托斯基,1930)一个图是可平面的充分必要条件是它没有同胚于K5或K3,3的子图。 平面图还存在着若干其他特征。 为了描述另外的特征,引入下面定义。2.2 收缩图定义3 设G=(V,E)是一个图,则(1)若uw和wv是图G的两条边且deg(w)=2,用一条边uv代替uw和wv时,则称uw和wv被缩减。(2)若G的某些条边被缩减,
10、产生的图称为G的缩减图,也称二度顶点内缩减图。1937年,瓦格纳(K.W.agner)证明了:定理2 一个图是可平面的当且仅当它没有一个可以收缩到K5或K3,3的子图。2.3 二度结点内的同构定义4 给定两个图G1和G2,若它们是同构的,或者通过反复插入或除去度为2的顶点后,使得G1和G2同构,则称这两个图是2度顶点内同构。定理3 一个图是可平面图充分必要条件是图G不包含与K5或K3,3在二度顶点内同构的子图。2.4 初等收缩定义5 一个图G的一个初等收缩由等同两个邻接的顶点u和v得到,即从G中去掉u和v,然后再加上一个新的顶点w,使得w邻接于所有邻接于u和v的顶点。一个图G可收缩到图H,若H
11、可以从G经一系列的初等收缩得到。2.5 对偶图定义6 设G=(V,E)是一个平面图,由G按如下方法构造一个图G*,G*称为G的对偶图: (1)对G的每个面f对应地有G*的一个顶点f*; (2)对G的每条边e对应地有G*的一条边e*:G*的两个顶点f*与g*由边e*联结,当且仅当G中与顶点f*与g*对应的面f与g有公共边e,若某条边x仅在一个面中出现而不是两个面的公共边,则在G*中这个面对应的顶点有一个环。 (3)当平面G已画在平面上时,G的对偶图如下构造:在G的每个面内放一个顶点,若两个面有一条公共边x,则用一条仅仅穿过边x的边x*来联相应的顶点。这样总产生一个平面伪图。在图中,G的边是实线,
12、顶点是小圆圈,而G的对偶图G*的边用虚线画出,顶点用实心黑点画出。说明:(1)显然,G*有一个环当且仅当G有一条桥;而G*有多重边当且仅当G的两个面至少有两条公共边。(2) 若G是一个有p个顶点和q条边及f个面的平面连通图,则G的对偶图G*也是一个平面图;若G不是平面连通图, G的对偶图G*也是一个平面图。(3)若G*是连通平面图:顶点数、边数和面数分别记为p*,q*和f*,则 p*=f,q*=q,f*=p。 若G不是连通平面图:则 p*=f ,q*=q,f*=p-k+1。 (4) 由于一个抽象的可平面图嵌入平面上时,可能有不只一种嵌入方法,因而产生了不只一个对偶图。尽管G的不同嵌入法得到的平
13、面图是同构的,但不同嵌入产生的平面图的对偶图可能不同构。例如(书上)图(a)和(b)是同一个可平面图G的两种不同方法嵌入平面,G中的顶点和边分别用小圆圈和实圆圈画出,而它们的对偶图G*分别在同一图上用黑点和虚线画出顶点和边。由于(a)中有一面是五条边围成的,而(b)没有这样的面,所以(a)产生的对偶图中有一个顶点度为5,而(b)产生的对偶图中没有度为5的顶点,所以这两个对偶图不同构。 定义7 若一个平面图与它的对偶图同构,则称这个平面图是自对偶的。 2.6 例题:例1 判断下面命题的对错,并说明理由。任何平面图G的对偶图G*的对偶图G*与G同构。分析:这个题目应该仔细钻研,结论也值得记忆。证:
14、非连通的平面图G的对偶图G*的对偶图G*与G不同构因为G不连通,而G*连通和G*连通,所以非连通的平面图G的对偶图G*的对偶图G*与G不同构例7 把平面分成n个区域,每两个区域都相邻,问n最大为多少?证:在每个区域放一个顶点,当两区域相邻时,就在相邻的两个顶点间连一条边,如此构造了一个平面图且是完全平面图,而最大的完全平面图为K,所以n最大为4。例给出平面图G的对偶图G*为欧拉图的一个充分必要条件。并证明之。分析:当且仅当G中每个面均由偶数条边围成,因为平面图G的每个面对应G*的每个顶点,而G*为欧拉图的充要条件是G*每个顶点的度数为偶数,围成G每个面的边数与对应的G*中的顶点的度数相等,所以
15、一个平面图G的对偶图G*是欧拉图.证:当且仅当G中每个面均由偶数条边围成,一个平面图G的对偶图G*是欧拉图。显然G*是连通图。设v*为G*中任意一顶点,v*处于G的面R中,因为R由偶数条边围成,所以v*的度数为偶数。由于v*的任意性可知。G*为欧拉图。反之也成立。例设G为连通的简单平面图,顶点数为n,面数为r,证明:若n3,则r2n-4;(2)若G中顶点最小的度为4,则G中至少有6个顶点的度数小于等于5。 证:(1)根据欧拉公式n-m+r=2,其中n,m,r分别是G的顶点数、边数和G的面数。得r=m+2-n,而对于顶点数n3的连通的简单的平面图G,有m3n-6。所以,r2n-4; (2) 假设
16、G中至多含有5个顶点的度数小于等于5。又因为(G)=4,所以由degvim,得m=degvi54+6(n-5),所以m3n-5。从而 3n-53n-6,矛盾;所以,G中至少有6个顶点的度数小于等于5。例 设无向图G是n(n2)个顶点的极大平面图,证明:G的对偶图G*的边连通度(G)2,并且G*是3-正则图。分析:要证明图G的对偶图G*的边连通度(G)2,也就是说任意删去G*的一条边,G*还是连通的。任意图G的对偶图G*都是连通的,并且对于任意顶点数大于等于3的极大平面图所有面的边数均为3。所以图G*是3-正则图。 证:因为无向图G是n2个顶点的极大平面图,所以图G的所有面的边数均为。根据平面图
17、的对偶图定义,对偶图G*的每个顶点的度数degv*=3,所以G*是-度正则图。 要证明图G的对偶图G*的边连通度(G)2,等价于证明:任意删去G*的一条边e*(设图为G1*),G1*还是连通的。设e*的两端点分别为u*,v*。并设图G中u*和v*对应的平面分别为r1,r2。显然r1和r2 是相邻的,因为图G的平面数是有限的,且所有的面都由三条边围成,所以不走e*,从r1一定存在到r2的路。所以G1*也是连通的,即G的对偶图G*的边连通度(G)2。例10设简单平面图G中顶点数n=7,边数m=15,证明G是连通的。证:用反证法。设G不是连通的,则G至少包含两个连通分支G1,G2,Gk,k2。设Gi
18、 的顶点数为ni,边数为mi,i=1,2,k 。 若存在ni=1,则k必为2,因为只有此时G为一个平凡图并上一个K6才能使其边数为15,可是K6不是平面图(它的子图K5已不是平面图),这与G是平面图矛盾,所以ni1。 若存在ni=2,则Gi中至多有一条边(因为G为简单图),另外5个顶点构成K5时边数最多,但充其量为10条边,这与G有15条边矛盾。综上所述,ni3,于是由mi3ni-6 ,i=1,2,k,求和得: m3n-6k (1)将n=7,m=15代入(1)得:1521-6k。即k1,这与k2矛盾。因此G必为连通图。例12 设G是面数r12的简单平面图,G中每个顶点的度数至少为3。(1) 证
19、明G中存在至多由4条边围成的面;(2) 给出一个例子说明,若G中的面数为12,且每个顶点的度至少为3,则(1)的结论不成立。证:(1)不妨设G是连通的,否则可以对它的每个连通分支进行讨论。因而由欧拉公式有: n-m+r=2 (1)又由已知条件知道r12 且 n2m/3 (2)将式(2)的结果代入式(1)得22m/3m+12 得m30 (3)若所有的面均至少由5条边围成,则5r2m 得 r2m/5 (4)将式(2),(4)的结果代入式(1)得22m/3-m+2m/5 得 m30 (5)式(3)与式(5)矛盾,因而必存在至多由4条边围成的面。 (2)十二面体图有12个面,每个顶点均为3度,每个面由5条边围成,并没有4条边围成的面。 例14 证明:当每个顶点的度数大于等于3时,不存在有7条边的简单连通平面图。 证:设G=(n,m)为简单连通平面图,有r个面。 若m=7,由欧拉公式知n+r=m+2=9 (1
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论