图论第六章平面图幻灯片.ppt

《图论第六章平面图幻灯片.ppt》由会员分享，可在线阅读，更多相关《图论第六章平面图幻灯片.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论课件第六章平面图1第1页，共35页，编辑于2022年，星期五第六章第六章 平面图平面图主要内容主要内容一、平面图概念与性质一、平面图概念与性质二、特殊平面图与平面图的对偶图二、特殊平面图与平面图的对偶图三、平面图的判定与涉及平面性不变量三、平面图的判定与涉及平面性不变量教学时数教学时数安排安排8学时讲授本章内容学时讲授本章内容四、平面性算法四、平面性算法2第2页，共35页，编辑于2022年，星期五本次课主要内容本次课主要内容(一一)、平面图的概念、平面图的概念(二二)、平面图性质、平面图性质平面图概念与性质平面图概念与性质(三三)、图的嵌入性问题简介、图的嵌入性问题简介(四四)、凸多面体与

2、平面图、凸多面体与平面图3第3页，共35页，编辑于2022年，星期五 图的平面性问题是图论典型问题之一。生活中许多问题都与该问题有图的平面性问题是图论典型问题之一。生活中许多问题都与该问题有关。关。(一一)、平面图的概念、平面图的概念 例子例子1：电路板设计问题：电路板设计问题 在电路板设计时，需要考虑的问题之一是连接电路元件间的导在电路板设计时，需要考虑的问题之一是连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。线间不能交叉。否则，当绝缘层破损时，会出现短路故障。显然，电路板可以模型为一个图，显然，电路板可以模型为一个图，“要求电路元件间连接导线要求电路元件间连接导线互

3、不交叉互不交叉”，对应于，对应于“要求图中的边不能相互交叉要求图中的边不能相互交叉”。4第4页，共35页，编辑于2022年，星期五 例子例子2：空调管道的设计：空调管道的设计 某娱乐中心有某娱乐中心有6个景点，位置分布如下图。个景点，位置分布如下图。A1A4A5A3A2A6 分析者认为：分析者认为：(1)A1与与A4,(2)A2与与A5,(3)A3与与A6间人流较少，间人流较少，其它景点之间人流量大，必须投资铺设空调管道，但要求空调管道间不其它景点之间人流量大，必须投资铺设空调管道，但要求空调管道间不能交叉。如何设计？能交叉。如何设计？5第5页，共35页，编辑于2022年，星期五 如果把每个景

4、点分别模型为一个点，景点间连线，当且仅当两如果把每个景点分别模型为一个点，景点间连线，当且仅当两景点间要铺设空调管道。那么，上面问题直接对应的图为：景点间要铺设空调管道。那么，上面问题直接对应的图为：A6A5A4A3A2A1 于是，问题转化为：能否把上图画在平面上，使得边不会相互交叉于是，问题转化为：能否把上图画在平面上，使得边不会相互交叉？6第6页，共35页，编辑于2022年，星期五 通过尝试，可以把上图画为：通过尝试，可以把上图画为：于是，铺设方案为：于是，铺设方案为：A6A5A4A3A2A1A1A4A5A3A2A67第7页，共35页，编辑于2022年，星期五 问题：要求把问题：要求把3种

5、公用设施种公用设施(煤气，水和电煤气，水和电)分别用煤气管道、分别用煤气管道、水管和电线连接到水管和电线连接到3间房子里，要求任何一根线或管道不与另外的线间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？或管道相交，能否办到？例子例子3：3间房子和间房子和3种设施问题种设施问题 上面问题可以模型为如下偶图：上面问题可以模型为如下偶图：H3H2H1EWG 问题转化为，能否把上面偶图画在平面上，使得边与边之间不会交叉问题转化为，能否把上面偶图画在平面上，使得边与边之间不会交叉？8第8页，共35页，编辑于2022年，星期五 上面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得上

6、面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得边与边之间没有交叉？边与边之间没有交叉？针对这一问题，我们引入如下概念针对这一问题，我们引入如下概念 定义定义1 如果能把图如果能把图G画在平面上，使得除顶点外，边与边之间没画在平面上，使得除顶点外，边与边之间没有交叉，称有交叉，称G可以嵌入平面，或称可以嵌入平面，或称G是可平面图。可平面图是可平面图。可平面图G的的边不交叉的一种画法，称为边不交叉的一种画法，称为G的一种平面嵌入，的一种平面嵌入，G的平面嵌入表的平面嵌入表示的图称为平面图。示的图称为平面图。H3H2H1EWG图图GH3H2H1EWG图图G的平面嵌入的平面嵌入9第9页，共

7、35页，编辑于2022年，星期五 注注:(1)可平面图概念和平面图概念有时可以等同看待；可平面图概念和平面图概念有时可以等同看待；(2)图的平面性问题主要涉及如下几个方面：图的平面性问题主要涉及如下几个方面：1)平面图的性质；平面图的性质；2)平面图的判定；平面图的判定；3)平面嵌入方法平面嵌入方法(平面性算法平面性算法);4）涉及图的平）涉及图的平面性问题的拓扑不变量。面性问题的拓扑不变量。由由 图的平面性问题研究引申出图的一般嵌入性问题的研究，形成了图的平面性问题研究引申出图的一般嵌入性问题的研究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘彦佩等在该方向都有重要拓扑图论的主要内容。我国

8、数学家吴文俊、刘彦佩等在该方向都有重要结果。刘彦佩的专著是结果。刘彦佩的专著是图的上可嵌入性理论图的上可嵌入性理论(1994)，化学工业出，化学工业出版社出版。版社出版。历史上，波兰数学家库拉托斯基、美国数学家惠特尼、生于英国的历史上，波兰数学家库拉托斯基、美国数学家惠特尼、生于英国的加拿大数学家托特，我国数学家吴文俊等都在拓扑图论中有过精湛的研加拿大数学家托特，我国数学家吴文俊等都在拓扑图论中有过精湛的研究。究。10第10页，共35页，编辑于2022年，星期五(二二)、平面图性质、平面图性质 定义定义2 (1)一个平面图一个平面图G把平面分成若干连通片，这些连通片称把平面分成若干连通片，这些

9、连通片称为为G的区域，或的区域，或G的一个面。的一个面。G的面组成的集合用的面组成的集合用表示。表示。在上图在上图G中，共有中，共有4个面。其中个面。其中f4是外部面，其余是内部面。是外部面，其余是内部面。=f1,f2,f3,f4。平面图平面图Gf1f3f2f4 (2)面积有限的区域称为平面图面积有限的区域称为平面图G的内部面，否则称为的内部面，否则称为G的外部面。的外部面。11第11页，共35页，编辑于2022年，星期五 (3)在在G中，顶点和边都与某个给定区域关联的子图，称为该面的中，顶点和边都与某个给定区域关联的子图，称为该面的边界。某面边界。某面 f 的边界中含有的边数的边界中含有的边

10、数(割边计算割边计算2次次)称为该面称为该面 f 的次的次数数,记为记为deg(f)。平面图平面图Gf1f3f2f4 在上图中，红色边在在上图中，红色边在G中的导出子图为面中的导出子图为面 f3 的边界。的边界。1、平面图的次数公式、平面图的次数公式12第12页，共35页，编辑于2022年，星期五 定理定理1 设设G=(n,m)是平面图，则：是平面图，则：证明：对证明：对G的任意一条边的任意一条边e,如果如果e是某面割边，那么由面的次数是某面割边，那么由面的次数定义，该边给定义，该边给G的总次数贡献的总次数贡献2次；如果次；如果e不是割边，那么，它必不是割边，那么，它必然是两个面的公共边，因此

11、，由面的次数定义，它也给总次数然是两个面的公共边，因此，由面的次数定义，它也给总次数贡献贡献2次。于是有：次。于是有：2、平面图的欧拉公式、平面图的欧拉公式13第13页，共35页，编辑于2022年，星期五 定理定理2(欧拉公式欧拉公式)设设G=(n,m)是连通平面图，是连通平面图，是是G G的面数，则：的面数，则：证明：情形证明：情形1，如果，如果G是树，那么是树，那么m=n-1,=1。在这种情况下，。在这种情况下，容易验证，定理中的恒等式是成立的。容易验证，定理中的恒等式是成立的。情形情形2，G不是树的连通平面图。不是树的连通平面图。假设在这种情形下，欧拉恒等式不成立。则存在一个含有最少边数

12、的假设在这种情形下，欧拉恒等式不成立。则存在一个含有最少边数的连通平面图连通平面图G,使得它不满足欧拉恒等式。设这个最少边数连通平面图使得它不满足欧拉恒等式。设这个最少边数连通平面图G=(n,m),面数为面数为，则：，则：14第14页，共35页，编辑于2022年，星期五 因为因为G不是树，所以存在非割边不是树，所以存在非割边e。显然，。显然，G-e是连通平面图，是连通平面图，边数为边数为m-1,顶点数为顶点数为n,面数为面数为-1。由最少性假设，由最少性假设，G-e满足欧拉等式：满足欧拉等式：化简得：化简得：这是一个矛盾。这是一个矛盾。注：该定理可以采用对面数注：该定理可以采用对面数作数学归纳

13、证明。作数学归纳证明。3、欧拉公式的几个有趣推论、欧拉公式的几个有趣推论15第15页，共35页，编辑于2022年，星期五 推论推论1 设设G是具有是具有个面个面k k个连通分支的平面图，则：个连通分支的平面图，则：证明：对第证明：对第i(1ik)ik)个分支来说，设顶点数为个分支来说，设顶点数为n ni i，边数为，边数为m mi i，面，面数为数为i i,由欧拉公式：由欧拉公式：所以，所以，16第16页，共35页，编辑于2022年，星期五 而：而：所以得：所以得：推论推论2 设设G是具有是具有n n个点个点m m条边条边个面的连通平面图，如果对个面的连通平面图，如果对G G的每个面的每个面f

14、 f,有：有：deg(deg(f f)l 3,3,则：则：17第17页，共35页，编辑于2022年，星期五 证明：一方面，由次数公式得：证明：一方面，由次数公式得：另一方面，由欧拉公式得：另一方面，由欧拉公式得：所以有：所以有：整理得：整理得：18第18页，共35页，编辑于2022年，星期五 注注:(1)上面推论上面推论2也可以叙述为：也可以叙述为：设设G=(n,m)是连通图，如果：是连通图，如果：则则G是非可平面图。是非可平面图。(2)推论推论2的条件是的条件是G是平面图的必要条件是平面图的必要条件,不是充分条件。不是充分条件。例例1 求证：求证：K3,3是非可平面图。是非可平面图。证明：注

15、意到，证明：注意到，K3,3是偶图，不存在奇圈，所以，每个面的次数是偶图，不存在奇圈，所以，每个面的次数至少是至少是4,即即 l=419第19页，共35页，编辑于2022年，星期五 所以，所以，而而m=9，这样有：，这样有：所以，由推论所以，由推论2，K3,3是非平面图。是非平面图。推论推论3 设设G是具有是具有n n个点个点m m条边条边个面的简单平面图，则：个面的简单平面图，则：20第20页，共35页，编辑于2022年，星期五 证明：情形证明：情形1，G连通。连通。因为因为G是简单图，所以每个面的次数至少为是简单图，所以每个面的次数至少为3，即，即l=3。于是，。于是，由推论由推论2得：得

16、：情形情形2，若，若G不连通。设不连通。设G1,G2,Gk是连通分支。是连通分支。一方面一方面,由推论由推论1：另一方面，由次数公式得：另一方面，由次数公式得：所以得：所以得：21第21页，共35页，编辑于2022年，星期五 例例2，证明：，证明：K5是非可平面图。是非可平面图。证明：证明：K5是简单图，是简单图，m=10,n=5。3n-6=9。得，得，所以，所以K5是非可平面图。是非可平面图。推论推论4 设设G是具有是具有n n个点个点m m条边的连通平面图，若条边的连通平面图，若G G的每个圈均的每个圈均由长度是由长度是 l 的圈围成，则：的圈围成，则：证明：由次数公式，欧拉公式容易得证。

17、证明：由次数公式，欧拉公式容易得证。22第22页，共35页，编辑于2022年，星期五 推论推论5 设设G是具有是具有n n个点个点m m条边的简单平面图，则：条边的简单平面图，则：证明：若不然，设证明：若不然，设 由握手定理：由握手定理：这与这与G是简单平面图矛盾。是简单平面图矛盾。注：该结论是证明注：该结论是证明“5色定理色定理”的出发点。的出发点。23第23页，共35页，编辑于2022年，星期五 定理定理3 一个连通平面图是一个连通平面图是2连通的，当且仅当它的每个面的连通的，当且仅当它的每个面的边界是圈。边界是圈。证明：证明：“必要性必要性”：设设G是是2连通的平面图，因为环总是两个连通

18、的平面图，因为环总是两个面的边界，且环面显然由圈围成。不失一般性，假设面的边界，且环面显然由圈围成。不失一般性，假设G没有环，没有环，那么那么G没有割边，也没有割点。所以，每个面的边界一定是没有割边，也没有割点。所以，每个面的边界一定是一条闭迹。一条闭迹。设设C是是G的任意面的一个边界，我们证明，它一定为圈。的任意面的一个边界，我们证明，它一定为圈。若不然，设若不然，设C是是G的某面的边界，但它不是圈。的某面的边界，但它不是圈。因因C是一条闭迹且不是圈，因此，是一条闭迹且不是圈，因此，C中存在子圈。设该子中存在子圈。设该子圈是圈是W1.因因C是某面的边界，所以是某面的边界，所以W1与与C的关系

19、可以表示为下图的关系可以表示为下图的形式：的形式：24第24页，共35页，编辑于2022年，星期五vvj-1v1v2vi-1vi+1vnW1 容易知道：容易知道：v为为G的割点。矛盾！的割点。矛盾！“充分性充分性”设平面图设平面图G的每个面的边界均为圈。此时删去的每个面的边界均为圈。此时删去G中任中任意一个点不破坏意一个点不破坏G的连通性，这表明的连通性，这表明G是是2连通的。连通的。推论推论6 若一个平面图是若一个平面图是2连通的，则它的每条边恰在两个面的连通的，则它的每条边恰在两个面的边界上。边界上。25第25页，共35页，编辑于2022年，星期五(三三)、图的嵌入性问题简介、图的嵌入性问

20、题简介 在图的平面嵌入的基础上，简单介绍：在图的平面嵌入的基础上，简单介绍：1、曲面嵌入、曲面嵌入 1)、球面嵌入、球面嵌入 定理定理4 G可球面嵌入当且仅当可球面嵌入当且仅当G可平面嵌入。可平面嵌入。证明：我们用建立球极平面射影的方法给出证明。证明：我们用建立球极平面射影的方法给出证明。将求面将求面S放在一个平面放在一个平面P上，设切点为上，设切点为O，过，过O作垂直于作垂直于P的的直线，该直线与直线，该直线与S相交于相交于z。26第26页，共35页，编辑于2022年，星期五 2)、环面嵌入、环面嵌入 环面的形状像一个汽车轮胎的表面。环面的形状像一个汽车轮胎的表面。PzyOx球极投影示意图球

21、极投影示意图 作映射作映射 f:S-z P。定。定义义 f(x)=y,使得使得x,y,z三点共三点共线线。该该映射称映射称为为球极平面射影。球极平面射影。通过通过f,可以把嵌入球面的图映射为嵌入平面的图。反之亦可以把嵌入球面的图映射为嵌入平面的图。反之亦然。然。27第27页，共35页，编辑于2022年，星期五 例例3 将将K4,K5,K3,3嵌入到环面上。嵌入到环面上。3)定向曲面嵌入定向曲面嵌入K4的环面嵌入的环面嵌入K5的环面嵌入的环面嵌入K3,3的环面嵌入的环面嵌入 这是目前嵌入性问题研究热点。国内：刘彦佩，黄元秋等这是目前嵌入性问题研究热点。国内：刘彦佩，黄元秋等是从事该方向研究的代表

22、。是从事该方向研究的代表。28第28页，共35页，编辑于2022年，星期五 2、图的、图的3维空间嵌入维空间嵌入 定理定理5 所有图均可嵌入所有图均可嵌入R3中。中。证明：在证明：在R3中作空间曲线：中作空间曲线：把图把图G的顶点放在该直线的不同位置，则的顶点放在该直线的不同位置，则G的任意边不相交。的任意边不相交。事实上，对处于曲线事实上，对处于曲线 l 上的任意上的任意4个相异顶点，它们对应的个相异顶点，它们对应的参数值分别为：参数值分别为：t1,t2,t3,t4。29第29页，共35页，编辑于2022年，星期五 因为：因为：所以，上面所以，上面4点不共面。点不共面。(四四)、凸多面体与平

23、面图、凸多面体与平面图 一个多面体称为凸多面体，如果在体上任取两点，其连线均在一个多面体称为凸多面体，如果在体上任取两点，其连线均在体上。体上。凸多面体的一维骨架：把一个凸多面体压缩在平面上，凸多面体的一维骨架：把一个凸多面体压缩在平面上，得到一个对应的平面图，该平面图称为该凸多面体的一维得到一个对应的平面图，该平面图称为该凸多面体的一维骨架。骨架。30第30页，共35页，编辑于2022年，星期五 定理定理6 存在且只存在存在且只存在5种正多面体：它们是正四、六、八、十种正多面体：它们是正四、六、八、十二、二十面体。二、二十面体。证明：任取一个正证明：任取一个正面体，其顶点数、棱数分别是面体，

24、其顶点数、棱数分别是n n和和m m。对。对应的一维骨架是一个每个面次数为应的一维骨架是一个每个面次数为l,顶点度数为顶点度数为r r的简单平面的简单平面正则图正则图G.G.正八面体一正八面体一维骨架维骨架正二十面体正二十面体一维骨架一维骨架31第31页，共35页，编辑于2022年，星期五 由次数公式得：由次数公式得：以上两等式中：以上两等式中：l 3,r 3 由握手定理得：由握手定理得：由由(1)与与(2)得：得：将将(3)代入欧拉公式得：代入欧拉公式得：在在(4)中，中，32第32页，共35页，编辑于2022年，星期五 于是得不等式组：于是得不等式组：不等式组不等式组(5)的正整数解恰有的正整数解恰有5组：组：正二十面体正二十面体203012355正八面体正八面体8126344正十二面体正十二面体123020533正方体正方体6128432正四面体正四面体464331相应的正多面体相应的正多面体mnrl序号序号 定理得证。定理得证。33第33页，共35页，编辑于2022年，星期五 作业作业 P143-146 习题习题5：2,16，1734第34页，共35页，编辑于2022年，星期五Thank You!35第35页，共35页，编辑于2022年，星期五