CHAP11平面图教学讲解教学课件

图中的边不要交叉实际中的很多问题都涉及到一个图中的边是否会交叉的问题。例如：单面印刷电路板，集成电路的布线，交通设计问题；等等。由此便抽象出平面图的概念：没有交叉(这里当然不是指在端点处的相互邻接）的边的图。一个有交叉的边的图能不能转换成与之同构的平面图，显然是人们所关注的问题。本章就是介绍平面图以及平面图的性质。7/20/20231离散数学§11.1平面图的概念7/20/20232离散数学平面图定义11.1.1：设G是平面上由有限个点及以这些点为端点的有限连续曲线所组成的图形，如果G中任意两条线最多只在它们的端点处相交，称G为平面图。例1，⑴图不是平面图，⑵和⑶是平面图。⑴⑵⑶7/20/20233离散数学可平面图上例中的图⑴虽然不是平面图，但是却和图⑵和图⑶是同构的，这样的图称为可平面图。可平面图：如果一个图G与一个平面图H同构，称G是可平面图；而称H是G的一个平面嵌入。上例中的图⑴是可平面图，图⑵和图⑶是图⑴的两个平面嵌入。7/20/20234离散数学平面图的面定义11.1.2：设G是一个平面图，平面被G的边所围成的区域称为面，这些边称为该面的边界；其中有限区域对应的面称为内部面，无限区域对应的面称为外部面(用f0表示)。用G(p,q,r)表示一个p个顶点，q条边以及r个面的平面图。一个面f所包含的边数称为f的次数，记为d(f)，若边为割边，则计算两次。7/20/20235离散数学计算下图中各面的次数：d(f0)=3;d(f1)=5。2431f1f0(a)f1f0(b)f2d(f0)=8;d(f1)=3;d(f2)=3.7/20/20236离散数学面的总次数为边数的两倍定理11.1.1：对任何平面图G(p,q,r),有d(fi)=2q,(i=1,2,,r).证明：由于G的每条非割边恰属于两个面，所以，在计算这两个面的次数时，该边计算两次，而割边只属于一个面，但由规定也计算了两次，故上式成立，即所有面的总次数为边数的两倍。对比：d(vi)=2q，(i=1,2,,p)，即所有顶点的总度数为边数的二倍。7/20/20237离散数学平面图的同构定义11.1.3：设G和H是两个平面图。如果并且f是G中一个由途径uvwu围成的面当且仅当(u)(v)(w)(u)围成H的一个面f’,则称G与H同构。有时可省略。例1中图⑵与图⑶就是平面图同构。7/20/20238离散数学图的同构与平面图的同构如果两个图是平面图同构，则必是两个同构的图。可是两个同构的图不一定是平面图同构。例1中图⑴与图⑵和图⑶是同构的图，但图⑴却不是平面图，因而不可能和它们平面图同构。下面两个平面图是图同构，但不是平面图同构：GH1’3’4’5’1234566’2’7/20/20239离散数学外平面图定义11.1.4：图G称为外可平面图，如果它有一个平面嵌入H，使得G的所有顶点均在H的同一个面的边界上，这时，称H为外平面图。f1f1这是外平面图这不是外平面图这是外可平面图7/20/202310离散数学极大平面图定义11.1.5设G是一个可平面图，如果对G中任意两个互不邻接的顶点u,v,G+uv成为一个不可平面图，则称G是一个极大可平面图，极大可平面图的一个平面嵌入称为极大平面图。说明：对一个不是极大的可平面图，可以添加一些边以得到一个极大可平面图。(如图)7/20/202311离散数学G是极大平面图当且仅当G的每个面都是三角形(必要性)极大简单平面图的任何一个面都是三角形K3。证明：(反证)设G是极大简单平面图。若G的某个面f不是K3，不妨设f由闭途径v1v2vnv1围成，且d(f)=n4。为简单起见，不妨设n=4，即f由闭途径v1v2v3v4v1围成。则f只有以下三种情况：⑴v1与v3不邻接；⑵v1与v3邻接，而v2与v4不邻接；⑶v1与v3邻接，而v2与v4也邻接。下面我们对这三种情况分别予以讨论：7/20/202312离散数学极大平面图的面都是三角形证明：…⑴若v1与v3不邻接，则v1v2v3v4v1所围成内部面，v1v2v3v4于是在该面内联结v1和v3不破坏G的平面性，此与G的假设矛盾；⑵若v1与v3邻接，v2与v4不邻接，则v1v2v3v1围成内部面，边v1v4及顶点v4必在此面的外部，v1v2v3v4故联结v2和v4不破坏G的平面性，此与G的假设矛盾；7/20/202313离散数学极大平面图的面都是三角形证明：…⑶若v1与v3邻接，且v2与v4邻接，则v1v2v3v4v1所围成的区域是内部面。因此边v1v3，v2v4都在此面之外，因而必相交,此与G的可平面性矛盾。v1v2v3v4综合以上，知结论成立。7/20/202314离散数学(充分性)若平面图G的每个面都是三角形，

则是G是极大平面图。证明：设平面图G的每个面都是K3，若G不是极大平面图.则G中存在u、vV(G)，使得uvE(G)，且G+uv仍为平面图。设uv是G+uv中两个面fi和fj的公共边界.于是，G中fi和fj的面是一个面fk，显然，d(fk)3,由此G与的每个面是K3矛盾！7/20/202315离散数学§11.2欧拉公式7/20/202316离散数学欧拉公式定理:对任何一个简单平面图G(p,q,r)均满足：p–q+r=2.证明：对面数r作归纳证明。当r=1时，G是树，此时q=p–1，结论成立。假设对G(p,q,r-1)，r2，结论成立，设G是有r个面的平面图，G至少有一条回路。设e是某回路上的边，G–e仍是连通平面图，它有p个顶点，q–1条边和r–1个面，由归纳假设有，p–(q–1)+(r–1)=2。整理即得p–q+r=2。由归纳法原理，欧拉公式成立。7/20/202317离散数学面等次平面图中边与点的关系推论11.2.1：若简单平面图G(p,q,r)的每个面的次数均为m,则

q=m(p–2)/(m–2)证明：由定理11.1.1，2q=d(fi)=mr，解出r，代入欧拉公式,得p–q+(2/m)q=2整理上式即得证。7/20/202318离散数学简单平面图边数的上界推论11.2.2对任何简单平面图G(p,q,r)(p3),q3p–6.证明：由于极大简单平面图的每个面都是K3,故将m=3代入推论11.2.1中的式q=m(p–2)/(m–2)

有q=3(p–2)=3p–6.故对一般简单平面图有q3p–6.7/20/202319离散数学K5是不可平面图推论11.2.3K5是不可平面图。证明：若K5是可平面图，则由推论11.2.2知q3p–6，于是10=q3p–6=35–6=9,即：109，矛盾。故结论成立。7/20/202320离散数学无3次面的平面图边数的上界推论11.2.4：若简单平面图G(p,q,r)的每个面均不是K3，则q2p–4.证明：由假设每个面的次数至少不小于4

2q=d(fi)4r即rq/2,从而由欧拉公式有2=p–q+rp–q+q/2=p–q/2

整理后得q2p–4.7/20/202321离散数学K3,3是不可平面图推论11.2.5：K3,3是不可平面图。证明：因K3,3是二分图，故它不含K3，假设K3,3是可平面图，则由推论11.2.4知9=q2p–4=26–4=8,即：98，矛盾。故结论成立。7/20/202322离散数学简单平面图的最小度小于6推论11.2.6：任何简单平面图G(p,q,r)均有(G)

＜6。证明：若(G)6，则q=(1/2)d(vi)(2q=d(vi))(1/2)p(G)(6/2)p>3p–6,此与推论11.2.2(对任何简单平面图G(p,q,r)(p3)，都有q3p–6)矛盾。故结论成立。7/20/202323离散数学极大平面图的五个性质定理11.2.2：设简单平面图G(p,q,r)是极大平面图(p4)，于是①q=3p–6;②r=2p–4;

④(G)3;⑤G中至少有4个顶点的度不超过5.7/20/202324离散数学极大平面图的边数证明：由定理11.1.2(极大简单平面图的任何一个面都是三角形K3)，将推论11.2.1中的式q=m(p–2)/(m–2)中的m用m=3代入，即可得q=3p–6;7/20/202325离散数学极大平面图的面数证明：由性质①有q=3p–6，将其代入欧拉公式得：

p–q+r=p–(3p–6)+r=2,

整理即得r=2p–4；7/20/202326离散数学极大平面图连通度不小于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的两个不同分支。7/20/202327离散数学极大平面图连通度不小于3证明：…S是顶点割，…ui和ui+1分别属于G–S的两个不同分支。uvui+1uif1由ui和ui+1的取法可知，在uui和uui+1之间没有其它与u邻接的边，依据定理11.1.2，在G中uuiui+1是一个K3面，故ui和ui+1邻接。从而在G–S中，ui也和ui+1邻接，这与S是顶点割相矛盾。所以(G)3。7/20/202328离散数学极大平面图最小度不小于3证明：由定理7.1.1可知图的连通度不大于边连通度，而边连通度又不大于最小度，即(G)(G)(G)；又由性质③即可得极大平面图最小度不小于3，即(G)(G)3。7/20/202329离散数学至少有4个顶点的度不超过5证明：设G的顶点集V={v1,v2,,vp}。

若对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=2q2q–d(vj)(这里j=p–2,p-1,p)=d(vi)(这里i=1,2,,p–3)6(p–3)=6p–18.此为矛盾，故结论成立。习题7/20/202330离散数学§11.3可平面性判定7/20/202331离散数学剖分图定义11.3.1：设G是一个图，e=uv∈E(G)，在G–uv中增加一个新点w及边wu,wv.称此过程为对图G的一次剖分运算。如果H是由G经过有限次剖分运算得到的，则称H是G的剖分图。直观地说，剖分就是在图的某边上加个顶点。右边就是K4的剖分。7/20/202332离散数学可平面图的充要条件定理11.3.1(Kuratowski定理)一个图是可平面图的充分必要条件是它不包含K5或K3,3的剖分图.该定理亦可描述为：一个图是可平面的当且仅当它没有一个可以收缩到K5或K3,3的子图。7/20/202333离散数学Petersen图的收缩和剖分Petersen图例如：Petersen图不是可平面图，因为它含有K3,3的剖分。Petersen图含有K3,3的剖分Petersen图收缩为K5它也可以收缩为K5。7/20/202334离散数学§11.4平面图的面着色7/20/202335离散数学给平面图着色对简单图G(p,q)只考虑顶点和边，其着色也只有点着色和边着色。对简单平面图G(p,q,r)则还需要考虑面，其着色还由相应的面着色。平面图着色的一个直接的重要的应用:地图着色

。用颜色来区分地图中的区域，需要多少种颜色呢？这就是著名的四色问题。7/20/202336离散数学面的邻接定义1.4.1：设f1和f2是平面图G的两个面。若f1和f2的边界至少有一条公共边，则称f1与f2是邻接的，否则称f1与f2不邻接。三种邻接：⑴点邻接：两个顶点有边相关联；⑵边邻接：两条边有共同的端点；⑶面邻接：两个面有共同的边。7/20/202337离散数学有公共顶点的面不是邻接的面注意：两个面如果在边界上只有一个或有限个公共点，则它们是不邻接的。如下左图中的面A与E,A与C,A与D都不是邻接的面。下右图中的面A与C，B与D也都不是邻接的面ABCDEFABCD7/20/202338离散数学面着色定义11.4.2：设G是平面图，S={1,2,,k}，k1。若存在面集R(G)到S的满射r，则称r为G的k面着色，S为面色集。若对G中任意两个邻接面f1和f2

，均有r(f1)≠r(f2)，则称r是正常k面着色，并称G是k面可着色的。图G的正常k面可着色中最小的k称为G的面色数，记为*(G)

。对比：色数(G)

：最小正常k(顶点)着色；

边色数’(G)

：最小正常k边着色；面色数*(G)：最小正常k面着色。7/20/202339离散数学对偶图如果把每个面看作一个顶点，若两个面的边界有一条公共边，则看作两个顶点之间有一条边关联。这样就可以把一个平面图G中面与面之间邻接关系描述为另一个图G*中顶点与顶点之间的邻接关系。这样对一个平面图G进行转换，所得到的图G*称为图G的对偶图于是可将对平面图G的面着色转换为对其对偶图G*的点着色问题。7/20/202340离散数学对偶图的构造对偶图的构造：在G的每个面内放一个顶点f*，这些顶点就构成了G*的顶点集V(G*)。若G的两个面f和g有一条公共边e，则画一条以f*和g*为端点的边e*，e*仅穿过e一次，对于G中仅属于一个面的割边e，则画一条以f*为端点的环，穿过e一次。如果一个图的对偶图就是它自己，则称为自对偶图。7/20/202341离散数学对偶图的举例自对偶图7/20/202342离散数学G与G*的关系对任何一个平面图G，G*是唯一确定的：p(G)*=r(G),q(G*)=q(G);G*中的顶点f*

和g*

邻接当且仅当G中与f*

和g*对应的两个面f和g邻接；G*有多重边当且仅当G的某两个面至少有两条公共边；G*有环当且仅当G中有割边。可将对平面图G的面着色转换为对其对偶图G*的点着色问题：(G*)=*(G)。7/20/202343离散数学四色问题定理11.4.1：所有平面图都是4面可着色的当且仅当所有平面图都是4可着色的.与四色问题等价的问题：对一个简单平面图G，是否(G)4?

1976年,美国的Appel,Haken,Koch借助计算机证明了四色问题.7/20/202344离散数学五色问题(一)定理11.4.2(Headhood,1890)：对任何平面图G,(G)5.证明：对顶点数p作归纳证明。归纳基础：当p5时，结论显然成立。归纳步骤：假设对所有顶点数小于p的平面图，结论成立。设G为p+1个顶点的平面图，由推论11.2.6,(G)

5。

考虑(p–1)阶平面图G–v，由归纳假设G–v有正常5着色。7/20/202345离散数学五色问题(二)证明：…G–v有正常5着色。若d(v)<5，则中至少