图论ppt课件第六章 平面图.ppt

《图论ppt课件第六章 平面图.ppt》由会员分享，可在线阅读，更多相关《图论ppt课件第六章 平面图.ppt（34页珍藏版）》请在三一办公上搜索。

1、1,第六章 平面图,主要内容,一、平面图概念与性质,二、特殊平面图与平面图的对偶图,三、平面图的判定与涉及平面性不变量,教学时数,安排8学时讲授本章内容,四、平面性算法,2,本次课主要内容,(一)、平面图的概念,(二)、平面图性质,平面图概念与性质,(三)、图的嵌入性问题简介,(四)、凸多面体与平面图,3,图的平面性问题是图论典型问题之一。生活中许多问题都与该问题有关。,(一)、平面图的概念,例子1：电路板设计问题,在电路板设计时，需要考虑的问题之一是连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。,显然，电路板可以模型为一个图，“要求电路元件间连接导线互不交叉”，对应于

2、“要求图中的边不能相互交叉”。,4,例子2：空调管道的设计,某娱乐中心有6个景点，位置分布如下图。,分析者认为：(1) A1与A4, (2) A2与A5, (3) A3与A6间人流较少，其它景点之间人流量大，必须投资铺设空调管道，但要求空调管道间不能交叉。如何设计？,5,如果把每个景点分别模型为一个点，景点间连线，当且仅当两景点间要铺设空调管道。那么，上面问题直接对应的图为：,于是，问题转化为：能否把上图画在平面上，使得边不会相互交叉？,6,通过尝试，可以把上图画为：,于是，铺设方案为：,7,问题：要求把3种公用设施(煤气，水和电)分别用煤气管道、水管和电线连接到3间房子里，要求任何一根线或管

3、道不与另外的线或管道相交，能否办到？,例子3：3间房子和3种设施问题,上面问题可以模型为如下偶图：,问题转化为，能否把上面偶图画在平面上，使得边与边之间不会交叉？,8,上面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得边与边之间没有交叉？,针对这一问题，我们引入如下概念,定义1 如果能把图G画在平面上，使得除顶点外，边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。可平面图G的边不交叉的一种画法，称为G的一种平面嵌入，G的平面嵌入表示的图称为平面图。,9,注: (1) 可平面图概念和平面图概念有时可以等同看待；,(2) 图的平面性问题主要涉及如下几个方面：1) 平面图的性质；2

4、) 平面图的判定；3) 平面嵌入方法(平面性算法) ;4）涉及图的平面性问题的拓扑不变量。,由 图的平面性问题研究引申出图的一般嵌入性问题的研究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘彦佩等在该方向都有重要结果。刘彦佩的专著是图的上可嵌入性理论(1994)，化学工业出版社出版。,历史上，波兰数学家库拉托斯基、美国数学家惠特尼、生于英国的加拿大数学家托特，我国数学家吴文俊等都在拓扑图论中有过精湛的研究。,10,(二)、平面图性质,定义2 (1) 一个平面图G把平面分成若干连通片，这些连通片称为G的区域，或G的一个面。G的面组成的集合用表示。,在上图G中，共有4个面。其中f4是外部面，其余

5、是内部面。=f1, f2, f3, f4。,(2) 面积有限的区域称为平面图G的内部面，否则称为G的外部面。,11,(3) 在G中，顶点和边都与某个给定区域关联的子图，称为该面的边界。某面 f 的边界中含有的边数(割边计算2次)称为该面 f 的次数, 记为deg ( f )。,在上图中，红色边在G中的导出子图为面 f3 的边界。,1、平面图的次数公式,12,定理1 设G=(n, m)是平面图，则：,证明：对G的任意一条边e, 如果e是某面割边，那么由面的次数定义，该边给G的总次数贡献2次；如果e不是割边，那么，它必然是两个面的公共边，因此，由面的次数定义，它也给总次数贡献2次。于是有：,2、平

6、面图的欧拉公式,13,定理2(欧拉公式) 设G=(n, m)是连通平面图，是G的面数，则：,证明：情形1，如果G是树，那么m=n-1, =1。在这种情况下，容易验证，定理中的恒等式是成立的。,情形2，G不是树的连通平面图。,假设在这种情形下，欧拉恒等式不成立。则存在一个含有最少边数的连通平面图G, 使得它不满足欧拉恒等式。设这个最少边数连通平面图G=(n, m), 面数为，则：,14,因为G不是树，所以存在非割边e。显然，G-e是连通平面图，边数为m-1, 顶点数为n, 面数为-1。,由最少性假设，G-e满足欧拉等式：,化简得：,这是一个矛盾。,注：该定理可以采用对面数作数学归纳证明。,3、欧

7、拉公式的几个有趣推论,15,推论1 设G是具有个面k个连通分支的平面图，则：,证明：对第i (1ik)个分支来说，设顶点数为ni，边数为mi，面数为i,由欧拉公式：,所以，,16,而：,所以得：,推论2 设G是具有n个点m条边个面的连通平面图，如果对G的每个面f ,有：deg (f) l 3,则：,17,证明：一方面，由次数公式得：,另一方面，由欧拉公式得：,所以有：,整理得：,18,注: (1)上面推论2也可以叙述为：,设G=(n, m)是连通图，如果：,则G是非可平面图。,(2) 推论2的条件是G是平面图的必要条件,不是充分条件。,例1 求证：K3,3是非可平面图。,证明：注意到，K3,3

8、是偶图，不存在奇圈，所以，每个面的次数至少是4,即 l=4,19,所以，,而m=9，这样有：,所以，由推论2，K3,3是非平面图。,推论3 设G是具有n个点m条边个面的简单平面图，则：,20,证明：情形1，G连通。,因为G是简单图，所以每个面的次数至少为3，即l=3。于是，由推论2得：,情形2，若G不连通。设G1,G2,Gk是连通分支。,一方面,由推论1：,另一方面，由次数公式得：,所以得：,21,例2，证明：K5是非可平面图。,证明：K5是简单图，m=10, n=5。3n-6=9。,得， ，所以K5是非可平面图。,推论4 设G是具有n个点m条边的连通平面图，若G的每个圈均由长度是 l 的圈围

9、成，则：,证明：由次数公式，欧拉公式容易得证。,22,推论5 设G是具有n个点m条边的简单平面图，则：,证明：若不然，设,由握手定理：,这与G是简单平面图矛盾。,注：该结论是证明“5色定理”的出发点。,23,定理3 一个连通平面图是2连通的，当且仅当它的每个面的边界是圈。,证明：“必要性”： 设G是2连通的平面图，因为环总是两个面的边界，且环面显然由圈围成。不失一般性，假设G没有环，那么G没有割边，也没有割点。所以，每个面的边界一定是一条闭迹。,设C是G的任意面的一个边界，我们证明，它一定为圈。,若不然，设C是G的某面的边界，但它不是圈。,因C是一条闭迹且不是圈，因此，C中存在子圈。设该子圈是

10、W1.因C是某面的边界，所以W1与C的关系可以表示为下图的形式：,24,容易知道：v为G的割点。矛盾！,“充分性” 设平面图G的每个面的边界均为圈。此时删去G中任意一个点不破坏G的连通性，这表明G是2连通的。,推论6 若一个平面图是2连通的，则它的每条边恰在两个面的边界上。,25,(三)、图的嵌入性问题简介,在图的平面嵌入的基础上，简单介绍：,1、曲面嵌入,1)、球面嵌入,定理4 G可球面嵌入当且仅当G可平面嵌入。,证明：我们用建立球极平面射影的方法给出证明。,将求面S放在一个平面P上，设切点为O，过O作垂直于P的直线，该直线与S相交于z。,26,2)、环面嵌入,环面的形状像一个汽车轮胎的表面

11、。,作映射 f : S -z P。定义 f (x) = y, 使得x ,y , z三点共线。该映射称为球极平面射影。,通过f, 可以把嵌入球面的图映射为嵌入平面的图。反之亦然。,27,例3 将K4, K5, K3,3嵌入到环面上。,3) 定向曲面嵌入,这是目前嵌入性问题研究热点。国内：刘彦佩，黄元秋等是从事该方向研究的代表。,28,2、图的3维空间嵌入,定理5 所有图均可嵌入R3中。,证明：在R3中作空间曲线：,把图G的顶点放在该直线的不同位置，则G的任意边不相交。,事实上，对处于曲线 l 上的任意4个相异顶点，它们对应的参数值分别为：t1,t2,t3,t4。,29,因为：,所以，上面4点不共

12、面。,(四)、凸多面体与平面图,一个多面体称为凸多面体，如果在体上任取两点，其连线均在体上。,凸多面体的一维骨架：把一个凸多面体压缩在平面上，得到一个对应的平面图，该平面图称为该凸多面体的一维骨架。,30,定理6 存在且只存在5种正多面体：它们是正四、六、八、十二、二十面体。,证明：任取一个正面体，其顶点数、棱数分别是n和m。对应的一维骨架是一个每个面次数为l ,顶点度数为r的简单平面正则图G.,31,由次数公式得：,以上两等式中：l 3, r 3,由握手定理得：,由(1)与(2) 得：,将(3)代入欧拉公式得：,在(4)中，,32,于是得不等式组：,不等式组(5)的正整数解恰有5组：,定理得证。,33,作业,P143-146 习题5 ： 2, 16，17,34,Thank You !,