CHAP11平面图ppt课件

1、第十一章 平面图图中的边不要交叉4实际中的很多问题都涉及到一个图中的边是否会交叉的问题。例如：单面印刷电路板，集成电路的布线，交通设计问题；等等。4由此便抽象出平面图的概念：没有交叉 (这里当然不是指在端点处的相互邻接的边的图。4一个有交叉的边的图能不能转换成与之同构的平面图，显然是人们所关注的问题。4本章就是介绍平面图以及平面图的性质。11.1 平面图的概念平面图4定义11.1.1：设G是平面上由有限个点及以这些点为端点的有限连续曲线所组成的图形，如果G中任意两条线最多只在它们的端点处相交，称G为平面图。4例1，图不是平面图， 和是平面图。可平面图4上例中的图虽然不是平面图，但是却和图和图是

2、同构的，这样的图称为可平面图。4可平面图：如果一个图G与一个平面图H同构，称G是可平面图；而称H是G的一个平面嵌入。4上例中的图是可平面图，图和图是图的两个平面嵌入。平面图的面4定义11.1.2：设G是一个平面图，平面被G的边所围成的区域称为面，这些边称为该面的边界；其中有限区域对应的面称为内部面，无限区域对应的面称为外部面(用f0表示)。4用G(p, q, r)表示一个p个顶点，q条边以及r个面的平面图。4一个面 f 所包含的边数称为 f 的次数，记为d( f ) ，若边为割边，则计算两次。计算下图中各面的次数：4d( f0 ) = 3 ; 4d( f1 ) = 5 。2431f1f0(a)

3、f1f0(b)f24d( f0 ) = 8 ;4d( f1 ) = 3 ;4d( f2 ) = 3 .面的总次数为边数的两倍4定理11.1.1：对任何平面图G(p, q, r) ,有4 d( fi ) =2q , (i =1 , 2 , ,r).4证明：由于G的每条非割边恰属于两个面，所以，在计算这两个面的次数时，该边计算两次，而割边只属于一个面，但由规定也计算了两次，故上式成立，即所有面的总次数为边数的两倍。4对比：d( vi ) =2q，(i =1 , 2 , , p)，即所有顶点的总度数为边数的二倍。平面图的同构4定义11.1.3：设G和H是两个平面图。如果并且 f 是G中一个由途径uv

4、wu围成的面当且仅当(u)(v) (w)(u)围成H的一个面 f , 则称G与H同构。有时可省略。4例1中图与图就是平面图同构。图的同构与平面图的同构4如果两个图是平面图同构，则必是两个同构的图。可是两个同构的图不一定是平面图同构。4例1中图与图和图是同构的图，但图却不是平面图，因而不可能和它们平面图同构。4下面两个平面图是图同构，但不是平面图同构：GH134512345662外平面图4定义11.1.4：图G称为外可平面图，如果它有一个平面嵌入H，使得G的所有顶点均在H的同一个面的边界上，这时，称H为外平面图。f1f1这是外平面图这不是外平面图这是外可平面图极大平面图4定义11.1.5 设G是

5、一个可平面图，如果对G中任意两个互不邻接的顶点u , v , G+uv成为一个 不可平面图，则称G是一个极大可平面图，极大可平面图的一个平面嵌入称为极大平面图。4说明：对一个不是极大的可平面图，可以添加一些边以得到一个极大可平面图。(如图)G是极大平面图当且仅当G的每个面都是三角形4(必要性) 极大简单平面图的任何一个面都是三角形K3。 4证明： (反证)设G是极大简单平面图。若G的某个面 f 不是K3，不妨设 f 由闭途径v1v2vnv1围成，且d(f) = n 4。为简单起见，不妨设n = 4，即f 由闭途径v1v2v3v4v1围成。那么 f 只有以下三种情况：v1与v3不邻接；v1与v3

6、邻接，而v2与 v4不邻接； v1与v3邻接，而v2与 v4也邻接。4 下面我们对这三种情况分别予以讨论：极大平面图的面都是三角形证明：若v1与v3不邻接，则v1v2v3v4v1所围成内部面，v1v2v3v4 于是在该面内联 结v1和v3不破坏G的平面性，此与G的假设矛盾；若v1与v3邻接，v2与v4不邻接，则v1v2v3 v1 围成内部面，边v1v4及顶点v4必在此面的外部，v1v2v3v4 故联结v2和v4不破坏G的平面性，此与G的假设矛盾；极大平面图的面都是三角形证明：若v1与v3邻接，且 v2与v4邻接，则v1v2v3v4v1所围成的区域是内部面。因此边v1v3，v2v4都在此面之外，

7、因而必相交, 此与G的可平面性矛盾。v1v2v3v4综合以上，知结论成立。(充分性充分性)若平面图若平面图G的每个面都是三角形，的每个面都是三角形， 则是则是G是极大平面图。是极大平面图。4 证明：设平面图G的每个面都是K3，若G不是极大平面图.则G中存在u、vV(G)，使得uvE(G)，且G+uv仍为平面图。4设uv是G+uv中两个面fi和fj的公共边界.于是，G中fi和fj的面是一个面fk ，显然，d(fk)3,由此G与的每个面是K3矛盾！11.2 欧拉公式 欧拉公式4定理:对任何一个简单平面图G (p, q, r)均满足：4 p q + r = 2 .4证明：对面数r作归纳证明。4当r=

8、1时，G是树，此时q = p 1，结论成立。4假设对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。4由归纳法原理，欧拉公式成立。面等次平面图中边与点的关系4推论11.2.1：若简单平面图G (p, q, r)的每个面的次数均为m , 那么 4 q = m(p 2) / (m 2)4证明：由定理11.1.1，2q = d( fi ) = mr ，解出r，代入欧拉公式, 得4 p q + (2

9、/m)q = 24 整理上式即得证。简单平面图边数的上界4推论11.2.2 对任何简单平面图G (p, q, r) ( p 3) , q 3p 6 .4证明：由于极大简单平面图的每个面都是K3 ,故将 m = 3代入推论11.2.1中的式4q = m(p 2) / (m 2) 4 有 q= 3(p 2) = 3p 6 .4 故对一般简单平面图有q 3p 6 .K5是不可平面图4推论11.2.3 K5是不可平面图。4证明：若K5是可平面图，则由推论11.2.2知q 3p 6 ，于是4 10 = q 3p 6 =35 6 = 9 , 4 即 ：10 9 ，矛盾。故结论成立。无3次面的平面图边数的上

10、界4推论11.2.4：若简单平面图G (p, q, r)的每个面均不是K3 ，那么 q 2p 4 .4证明：由假设每个面的次数至少不小于44 2q = d( fi ) 4r4即 r q /2 ,从而由欧拉公式有4 2 = p q + r p q + q /2 = p q /24 整理后得 q 2p 4 .K3,3是不可平面图4推论11.2.5：K3,3是不可平面图。4证明：因K3,3是二分图，故它不含K3 ，假设K3,3是可平面图，则由推论11.2.4知4 9 = q 2p 4 =26 4 = 8 ,4 即 ：9 8 ，矛盾。故结论成立。简单平面图的最小度小于64推论11.2.6：任何简单平面

11、图G (p, q, r)均有4(G) 6。4证明：假设(G) 6，那么 4 q = (1/2) d( vi ) (2q = d( vi ) )4 (1/2)p (G) (6/2)p 3p 6 ,4此与推论11.2.2( 对任何简单平面图G (p, q, r) ( p 3)，都有 q 3p 6 )矛盾。故结论成立。极大平面图的五个性质 4定理11.2.2：设简单平面图G (p, q, r)是极大平面图( p 4) ，于是4 q = 3p 6 ; 4 r = 2p 4 ; 4 (G) 3 ; 4 G中至少有4个顶点的度不超过5 . 极大平面图的边数4证明：由定理11.1.2(极大简单平面图的任何一

12、个面都是三角形K3 ) ，将推论11.2.1中的式q = m(p 2) / (m 2)中的m用m=3 代入，即可得4q = 3p 6 ;极大平面图的面数证明：由性质有q = 3p 6 ，将其代入欧拉公式得： p q + r = p (3p 6) + r = 2 , 整理即得r = 2p 4 ；极大平面图连通度不小于34证明：G的面都是K3， (G) 2。4 假设(G) = 2 ，则有顶点割S =u, v。其中的u和v都应该与G S的至少两个连通分支中的顶点在G中邻接。4不妨设在G的一个平面嵌入G 中与u邻接的点按环绕u的顺序依次为u1, , ut。4而 u1, , ut中除可能有一点是v外，其

13、余的点分别属于GS的至少两个分支，必有两点ui和ui+1分属G S的两个不同分支。极大平面图连通度不小于34证明： S是顶点割，ui和ui+1分别属于G S的两个不同分支。uvui+1uif14由ui和ui+1的取法可知，在uui和uui+1之间没有其它与u邻接的边，依据定理 11.1.2，在G 中u uiui+1是一个K3面，故ui和ui+1邻接。4从而在G S中， ui也和ui+1邻接，这与S是顶点割相矛盾。所以 4(G) 3。极大平面图最小度不小于3证明：由定理7.1.1可知图的连通度不大于边连通度，而边连通度又不大于最小度，即(G) (G) (G) ；又由性质即可得极大平面图最小度不小

14、于3，即(G) (G) 3 。至少有4个顶点的度不超过5证明：设G的顶点集V = v1 , v2 , , vp。 若对i = 1, 2, , p 3，均有d(vi) 6，则由性质， 对i = p2 , p1, p，有d(vi) (G) 3。 于是，6p 21= 2q 9？因为由性质，q = 3p 6 ，于是6p 12 = 2q 2q d( vj ) (这里j = p2, p-1, p) = d(vi ) (这里i =1, 2, , p 3) 6(p 3) = 6p 18 .此为矛盾，故结论成立。习题习题11.3 可平面性判定剖分图4定义11.3.1：设G是一个图，e = uv E(G)，在G

15、uv中增加一个新点w及边wu , wv .称此过程为对图G的一次剖分运算。如果H是由G经过有限次剖分运算得到的，则称H是G的剖分图。4直观地说，剖分就是在图的某边上加个顶点。4右边就是K4的剖分。可平面图的充要条件4定理11.3.1 (Kuratowski定理) 一个图是可平面图的充分必要条件是它不包含K5或K3,3的剖分图.4该定理亦可描述为：一个图是可平面的当且仅当它没有一个可以收缩到K5或K3,3的子图。Petersen图的收缩和剖分Petersen图4例如：Petersen图不是可平面图，因为它含有K3,3的剖分。Petersen图含有K3,3的剖分Petersen图收缩为K5它也可以

16、收缩为K5。11.4 平面图的面着色给平面图着色4对简单图G(p, q)只考虑顶点和边，其着色也只有点着色和边着色。4对简单平面图G (p, q, r)则还需要考虑面，其着色还由相应的面着色。4平面图着色的一个直接的重要的应用:地图着色 。4用颜色来区分地图中的区域，需要多少种颜色呢？这就是著名的四色问题。面的邻接4定义1.4.1：设 f1 和 f2是平面图G的两个面。假设 f1 和 f2的边界至少有一条公共边，则称f1与 f2是邻接的，否则称 f1与 f2不邻接。4三种邻接：4 点邻接：两个顶点有边相关联；4 边邻接：两条边有共同的端点；4 面邻接：两个面有共同的边。有公共顶点的面不是邻接的

17、面4注意：两个面如果在边界上只有一个或有限个公共点，则它们是不邻接的。如下左图中的面A与E , A与C , A与D都不是邻接的面。下右图中的面A与C，B与D也都不是邻接的面ABCDEFABCD面着色4定义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) 。4对比：色数(G) ：最小正常k(顶点)着色；4 边色数(G) ：最小正常k边着色；4 面色数

18、*(G) ：最小正常k面着色。对偶图4如果把每个面看作一个顶点，若两个面的边界有一条公共边，则看作两个顶点之间有一条边关联。这样就可以把一个平面图G中面与面之间邻接关系描述为另一个图G*中顶点与顶点之间的邻接关系。4这样对一个平面图G进行转换，所得到的图G*称为图G的对偶图4于是可将对平面图G的面着色转换为对其对偶图G*的点着色问题。对偶图的构造4对偶图的构造：在G的每个面内放一个顶点 f*，这些顶点就构成了G*的顶点集V(G*)。 若G的两个面 f 和g有一条公共边e， 则画一条以 f*和 g*为端点的边e*， e*仅穿过e一次，对于G中仅属于一个面的割边e，则画一条以 f*为端点的环，穿过

19、e一次。4如果一个图的对偶图就是它自己，则称为自对偶图。对偶图的举例自对偶图G与G*的关系4对任何一个平面图G，G*是唯一确定的：4p(G)* = r(G) , q(G*) = q(G) ;4G*中的顶点 f* 和 g* 邻接当且仅当G中与 f* 和 g*对应的两个面 f 和 g 邻接；4G*有多重边当且仅当G的某两个面至少有两条公共边；4G*有环当且仅当G中有割边。4可将对平面图G的面着色转换为对其对偶图G*的点着色问题：(G*) = *(G)。四色问题4定理11.4.1：所有平面图都是4面可着色的当且仅当所有平面图都是4可着色的.4与四色问题等价的问题：对一个简单平面图G，是否(G) 4 ? 4 1976年 ,美国的Appel, Haken, Koch 借助计算机证明了四色问题.五色问题(一)4定理11.4.2 (Headhood ,1890)：对任何平面图G,4(G) 5 .4证明：对顶点数p作归纳证明 。4 归纳基础：当p 5时，结论显然成立。4 归纳步骤：假设对所有顶点数小于 p 的平面图，结论成立。设G为p+1个顶点的平面图，由推论11.2.6 , (G) 5 。4 考虑(p1)阶平面