chap13平面图.

1第十三章平面图2图中的边不要交叉实际中的很多问题都涉及到一个图中的边是否会交叉的问题。例如：单面印刷电路板，集成电路的布线，交通设计问题；等等。由此便抽象出平面图的概念：没有交叉(这里当然不是指在端点处的相互邻接）的边的图。一个有交叉的边的图能不能转换成与之同构的平面图，显然是人们所关注的问题。本章就是介绍平面图以及平面图的性质。3§13.1平面图的概念4平面图定义13.1.1：设G是平面上由有限个点及以这些点为端点的有限条连续曲线所组成的图形，如果G中任意两条线最多只在它们的端点处相交，称G为平面图，否则称为非平面图。⑴⑵⑶下例中，⑴图不是平面图，⑵和⑶是平面图。5可平面图上例中的图⑴虽然不是平面图，但是却和图⑵和图⑶是同构的，这样的图称为可平面图。可平面图：如果一个图G与一个平面图H同构，称G是可平面图；而称H是G的一个平面嵌入；否则称为不可平面图。上例中的图⑴是可平面图，图⑵和图⑶是图⑴的两个平面嵌入。可平面图的例子6上面的都是可平面图，下面的是它们的平面嵌入。7平面图的面定义13.1.2：设G是一个平面图，平面被G的边所围成的区域称为面，这些边称为该面的边界；其中有限区域对应的面称为内部面，无限区域对应的面称为外部面(用f0表示)。显然，任何一个平面图恰有一个外部面。用G(p,q,r)表示一个p个顶点，q条边以及r个面的平面图。一个面f所包含的边数称为f的次数，记为d(f)，若边为割边，则计算两次。8计算下图中各面的次数：d(f0)=3;d(f1)=5。2431f1f0(a)f1f0(b)f2d(f0)=8;d(f1)=3;d(f2)=3.练一练指出平面图的面、面的边界及面的次数9e6e1e2e3e4e5e7e8e10e9f0f1f2f3f4d(f0)=6.d(f1)=5.d(f2)=3.d(f3)=3.d(f4)=3.面的总次数为20，边数为10，正好两倍？！10面的总次数为边数的两倍定理13.1.1：对任何平面图G(p,q,r),有d(fi)=2q,(i=1,2,,r).证明：由于G的每条非割边恰属于两个面，所以，在计算这两个面的次数时，该边计算两次，而割边只属于一个面，但由规定也计算了两次，故上式成立，即所有面的总次数为边数的两倍。对比：d(vi)=2q，(i=1,2,,p)，即所有顶点的总度数为边数的二倍。11平面图的同构定义13.1.3：设G和H是两个平面图。如果G≌H(关于),并且f是G中一个由途径uvwu围成的面当且仅当(u)(v)(w)(u)围成H的一个面f’,则称G与H同构，记为G≅H。例1中图⑵与图⑶就是平面图同构。⑵⑶12图的同构与平面图的同构平面图同构一定是⇌不一定同构图。①同构的图不一定都是平面图，如例1。②同构的图都是平面图，但不是平面图同构：G12345H1’2’3’4’5’66’13外平面图定义13.1.4：图G称为外可平面图，如果它有一个平面嵌入H，使得G的所有顶点均在H的同一个面的边界上，这时，称H为外平面图。f1f1这是外平面图。这不是外平面图。G:红色顶点在外部面的边界上,蓝色的在内部面的H:所有点在外部面边界上14极大平面图定义13.1.5设G是一个可平面图，如果对G中任意两个互不邻接的顶点u,v,G+uv成为一个不可平面图，则称G是一个极大可平面图，极大可平面图的一个平面嵌入称为极大平面图。说明：对一个不是极大的可平面图，可以添加一些边以得到一个极大可平面图。(如图)15极大平面图的面都是三角形定理13.1.2极大简单平面图的任何一个面都是三角形K3。证明：(反证)设G是极大简单平面图。若G的某个面f不是K3，不妨设f由闭途径v1v2vnv1围成，且d(f)=n4。为简单起见，不妨设n=4，即f由闭途径v1v2v3v4v1围成。则f只有以下三种情况：⑴v1与v3不邻接；⑵v1与v3邻接，而v2与v4不邻接；⑶v1与v3邻接，而v2与v4也邻接。下面我们对这三种情况分别予以讨论：即每个面的次数均为3。16极大平面图的面都是三角形证明：…⑴若v1与v3不邻接，则v1v2v3v4v1围成内部面，v1v2v3v4于是在该面内联结v1和v3不破坏G的平面性，此与G是极大简单平面图的假设矛盾；⑵若v1与v3邻接，v2与v4不邻接，则v1v2v3v1围成内部面，边v1v4及顶点v4必在此面的外部，v1v2v3v4故联结v2和v4不破坏G的平面性，此与G的假设矛盾；17极大平面图的面都是三角形证明：…⑶若v1与v3邻接，且v2与v4邻接，则由于v1v2v3v4v1所围成的区域是内部面。v1v2v3v4因此边v1v3，v2v4都在此面之外，因而必相交,此与G的可平面性矛盾。综合以上，知结论成立。此定理可作为极大平面图的判定定理。极大平面图的判定判断下面各图是否为极大平面图18G1G2G3只有G3为极大平面图。因为只有该图每个面的次数都为3。19§13.2欧拉公式可平面性的必要条件欧拉在研究凸多面体时得到了它们的顶点数、棱数和面数之间的一个简单关系，将这个关系应用到平面图上，就有了欧拉公式。本节主要介绍若干可平面性的必要条件2021欧拉公式定理13.2.1(欧拉公式)：任何一个简单连通平面图G(p,q,r)均满足：p–q+r=2.证明：对面数r作归纳证明。当r=1时，G是树，此时q=p–1，结论成立。假设对G(p,q,r-1)，r2，结论成立，设G是有r个面的平面图，G至少有一条回路。设e是某回路上的边，G–e仍是连通平面图，它有p个顶点，q–1条边和r–1个面，由归纳假设有，p–(q–1)+(r–1)=2。整理即得p–q+r=2。由归纳法原理，欧拉公式成立。22面等次平面图中边与点的关系推论13.2.1：若简单平面图G(p,q,r)的每个面的次数均为m,则q=m(p–2)/(m–2)证明：由定理13.1.1，2q=d(fi)=mr，解出r，代入欧拉公式,得p–q+(2/m)q=2整理上式即得证。23简单平面图边数的上界推论13.2.2对任何简单平面图G(p,q,r)(p3),q3p–6.证明：由于极大简单平面图的每个面都是K3,故将m=3代入推论13.2.1中的式q=m(p–2)/(m–2)有q=3(p–2)=3p–6.故对一般简单平面图有q3p–6.24K5是不可平面图推论13.2.3K5是不可平面图。证明：若K5是可平面图，则由推论13.2.2知q3p–6，于是10=q3p–6=35–6=9,即：109，矛盾。故结论成立。25无3次面的平面图边数的上界推论13.2.4：若简单平面图G(p,q,r)的每个面均不是K3，则q2p–4.证明：由假设每个面的次数不小于4。∴2q=d(fi)4r即rq/2,从而由欧拉公式有2=p–q+rp–q+q/2=p–q/2整理后得q2p–4.26K3,3是不可平面图推论13.2.5：K3,3是不可平面图。证明：因K3,3是二分图，故它不含K3，假设K3,3是可平面图，则由推论13.2.4知9=q2p–4=26–4=8,即：98，矛盾。故结论成立。27简单平面图的最小度小于6推论13.2.6：任何简单平面图G(p,q,r)均有(G)＜6。证明：若(G)6，则q=(1/2)d(vi)(2q=d(vi))(1/2)p*(G)(6/2)p3p–6,此与推论13.2.2(对任何简单平面图G(p,q,r)(p3)，都有q3p–6)矛盾。故结论成立。小结：简单平面图的性质任何简单连通平面图G(p,q,r)均满足：p-q+r=2（欧拉公式）任何简单平面图G(p,q,r)均满足：①q≤3p-6②(G)6（重要的平面图着色理论）28后面两个条件都是根据欧拉公式，由式𝟐𝒒=𝒅𝒇𝒊=𝒅(𝒗𝒋)𝒑𝒋=𝟏𝒓𝒊=𝟏和极大平面图任意面𝒅𝒇𝒊=3推导而得的。K5、K3,3是不可平面图29极大平面图的五个性质定理13.2.2：设简单平面图G(p,q,r)是极大平面图(p4)，于是①q=3p–6;②r=2p–4;③(G)3;④(G)3;⑤G中至少有4个顶点的度不超过5.30极大平面图的边数证明：由定理13.1.2(极大简单平面图的任何一个面都是三角形K3)，将推论13.2.1中的式q=m(p–2)/(m–2)中的m用m=3代入，即可得q=3p–6;31极大平面图的面数证明：由性质①有q=3p–6，将其代入欧拉公式得：p–q+r=p–(3p–6)+r=2,整理即得r=2p–4；32极大平面图连通度不小于3证明：∵G的面都是K3，∴(G)2。假设(G)=2，则有顶点割S={u,v}。其中的u和v都应该与G–S的至少两个连通分支中的顶点在G中邻接。不妨设在G的一个平面嵌入G中与u邻接的点按环绕u的顺序依次为u1,…,ut。而u1,…,ut中除可能有一点是v外，其余的点分别属于G–S的至少两个分支，必有两点ui和ui+1分属G–S的两个不同分支。33极大平面图连通度不小于3图示图示1uv分支1分支2S={u,v}ui+1ui+2..utui..u2u1图示2uvG’34极大平面图连通度不小于3证明：…S是顶点割，…ui和ui+1分别属于G–S的两个不同分支。uvui+1uif1由ui和ui+1的取法可知，在uui和uui+1之间没有其它与u邻接的边，依据定理13.1.2，在G中uuiui+1是一个K3面，故ui和ui+1邻接。从而在G–S中，ui也和ui+1邻接，这与S是顶点割相矛盾。所以(G)3。35极大平面图最小度不小于3证明：由定理7.1.1可知图的连通度不大于边连通度，而边连通度又不大于最小度，即(G)(G)(G)；又由性质③即可得极大平面图最小度不小于3，即(G)(G)3。36至少有4个顶点的度不超过5证明：设G的顶点集V={v1,v2,…,vp}。若最多只有三个顶点的度不超过5，即对i=1,2,…,p–3，均有d(vi)6，则由性质④，对i=p–2,p–1,p，有d(vi)(G)3。于是，6p–21=2q–9？因为由性质①，q=3p–6，于是6p–12=2q2q–d(vj)(这里j=p–2,p-1,p)=d(vi)(这里i=1,2,…,p–3)6(p–3)=6p–18.此为矛盾，故结论成立。37§13.3可平面性判定38剖分图定义13.3.1：设G是一个图，e=uv∈E(G)，在G–uv中增加一个新点w及边wu,wv.称此过程为对图G的一次剖分运算。如果H是由G经过有限次剖分运算得到的，则称H是G的剖分图。直观地说，剖分就是在图的某边上加个顶点。右边就是K4的剖分。39可平面图的充要条件定理13.3.1(Kuratowski定理)一个图是可平面图的充分必要条件是它不包含K5或K3,3的剖分图.该定理亦可描述为：一个图是可平面的当且仅当它没有一个可以收缩到K5或K3,3的子图。40Petersen图的收缩和剖分Petersen图例如：Petersen图不是可平面图，因为它含有K3,3的剖分。Petersen图含有K3,3的剖分Petersen图收缩为K5它也可以收缩为K5。41§13.4平面图的面着色42给平面图着色对简单图G(p,q)只考虑顶点和边，其着色也只有点着色和边着色。对简单平面图G(p,q,r)则还需要考虑面，其着色还有相应的面着色。平面图着色的一个直接的重要的应用:地图着色。用颜色来区分地图中的区域，最少需要多少种颜色呢？这就是著名的四色问题。43面的邻接定义13.4.1：设f1和f2是平面图G的两个面。若f1和f2的边界至少有一条公共边，则称f1与f2是邻接的，否则称f1与f2不邻接。区分三种邻接：⑴点邻接：两个顶点有边相关联；⑵边邻接：两条边有共同的端点；⑶面邻接：两个面有共同的边。44有