离散数学 第四章平面图与图完全强烈公开课一等奖课件省赛课获奖课件

第四章平面图与图着色

4.1平面图定义4.1.1若能把图G画在一种平面上，使任何两条边都不相交,就称G可嵌入平面，或称G是可平面图.可平面图在平面一种嵌入称为平面图.假如G是可平面图,那么它任何导出子图也是可平面图.第1页平面图定义4.1.2设G是一种平面图,由它若干条边所组成一种区域内假如不含任何结点及边，就称该区域为G一种面或域.包围这个域诸边称为该域边界.为了讨论方便,我们把平面图G外边无限区域称为无限域,其他域都叫做内部域.假如两个域有共同边界，就说它们是相邻,不然是不相邻.假如e不是割边,它一定是某两个域共同边界.第2页平面图定理4.1.1设G是平面连通图,则G域数目是d=m–n+2.证明:G是连通图,有支撑树T,它包括n-1条边，不产生回路,因此对T来说只有一种无限域.由于G是平面图,每加入一条余树边,它一定不与其他边相交,也就是说一定是跨在某个域内部,把该区域提成两部分.这样,加入Gm-n+1条余树边,就生成了m-n+2个域.第3页平面图推论4.1.1若平面图G有k个连通支,则n–m+d=k–1.推论4.1.2对一般平面图G,恒有n–m+d>=2.第4页平面图定理4.1.2设平面连通图G没有割边,且每个域边界数最少是t,则m<=t*(n-2)/(t–2)证明:设G有d个区域,每个域边界树最少是t,且每条边都与两个不一样域相邻.因此td<=2m.代入欧拉公式:(2m/t)>=m-n+2,即,m<=t*(n-2)/(t–2).第5页4.3非平面图假如图G不能嵌入平面,满足任意两边只能在结点处相交,那么G就称为非平面图这样,按平面性质进行划分,图G分为两大类:可平面图和非平面图.第6页非平面图定理4.3.1是非平面图.证明:在中,n=5,m=10.假如它是可平面图,应当有m<=3n-6.而此时3n-6=9,矛盾.定理4.3.2是非平面图.证明:假定是可平面图,由于n=6,m=9.由欧拉公式,d=5.但G中没有子图,因此4d<=2m,亦即20<=18,矛盾.第7页非平面图商定和分别记为和图.定义4.3.1在和图上任意任意增加某些度为2结点之后得到图象为型和型图,统称为K型图.定理4.3.3G是可平面图充要条件是G不存在K型图.第8页4.5对偶图定义4.5.1满足如下条件图G*称为G对偶图.G中每个确定域内设置一种结点.对域和共同边界,有一条边,并与相交一次.若处于域之内,则有一自环与相交一次.

第9页对偶图性质4.5.1假如G是平面图,G一定有对偶图G*,并且G*是唯一.由D过程即可得证.性质4.5.2G*是连通图.在平面G里,每个域f都存在相邻域,并且对G任何部分域来说，都存在与它们之中某个域相邻域.这样由对偶图定义可知G*连通.第10页对偶图性质4.5.3若G是平面连通图,那么性质4.5.4平面连通图G与其对偶图G*结点,边和域之间存在如下对应关系:m=m*,n=d*,d=n*.第11页对偶图性质4.5.5若G是平面连通图一种初级回路,S*是G*中与C各边 对应集合,那么S*是G*一种割集.证明：Ｃ把Ｇ域提成两部分，因此把G*结点提成不连通两部分，由性质4.5.2，G*两部分是分别连通，因此那么S*是G*一种割集．

第12页对偶图定理4.5.1G有对偶图充要条件是G为平面图.证明:充足性直接由4.5.1得证.先证必要性:即非平面图没有对偶图.由库拉图斯基定理，非平面图一定具有和型子图；而，型子图是和图中增加

定理4.5.2每一种平面图G都是5-可着色.第13页对偶图定理4.5.3假如平面图G有哈密顿回路,则四色猜想成立.定理4.5.4若任何一种3-正则平面图域可四着色,则任何一种平面域也能够四着色.第14页4.6色数与色数多项式定义4.6.1给定图G,满足相邻点结点着以不一样颜色最少颜色数为G色数,记为γ(G).定义4.6.2给定图G,满足相邻边着以不一样颜色最少颜色数目称为G边色数,记为β(G).第15页色数与色数多项式定理4.6.1一种非空图,γ(G)=2,当且仅当它没有奇回路.证明：充足性：在Ｇ中确定一种林，其每个连通子图都是树Ｔ，．由于每个回路都是偶回路．因此加入每一条余树边都不会使结点着色发生变化，因此．必要性：假如Ｇ中有奇回路，则．矛盾．第16页色数与色数多项式定理4.6.2对于任意一种图G,其中证明：对Ｇ结点进行归纳，n＝１时成立．设n＝k－１时成立，当n＝k时，从Ｇ中任意移去一点得，．于是，其中是结点最大度，由于，因此．即种颜色能够对结点着色，放回结点恢复成Ｇ，由于，因此比有一种与邻点都不一样颜色可对着色．第17页色数与色数多项式定理4.6.3对于任意一种图G.

γ(G)<=1+maxδ(G’)其中δ(G’)是G导出子图G’中结点最小度,极大是对所有G’而言.第18页色数与色数多项式定义4.6.3设i,j是简单图G不相邻两个结点.令也是一种简单图,其结点集边集第19页色数与色数多项式定理4.6.4设i,j是简单图G不相邻结点,则证明：对Ｇ中结点任何着色，i和j或者将着以同色，或者异色．设i，j着以异色情况下Ｇ最少着色数为，i，j着以同色情况下最少着色数是．这样，显然式中因此定理得证第20页色数与色数多项式定理4.6.5定理4.6.6

第21页色数与色数多项式定理