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

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1第六章第六章 平面图平面图主要内容主要内容一、平面图概念与性质一、平面图概念与性质二、特殊平面图与平面图的对偶图二、特殊平面图与平面图的对偶图三、平面图的判定与涉及平面性不变量三、平面图的判定与涉及平面性不变量教学时数教学时数安排安排8学时讲授本章内容学时讲授本章内容四、平面性算法四、平面性算法 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2本次课主要内容本次课主要内容(一一)、平面图的概念、平面图的概念(二二)、平面图性质、平面图性质平面图概念与性质平面图概念与性质(三三)、图的嵌入性问题简介、图的嵌入性问题简介(四四)、凸多面体与平面图、凸多面体与平面图 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 图的平面性问题是图论典型问题之一。生活中许多问题图的平面性问题是图论典型问题之一。生活中许多问题都与该问题有关。都与该问题有关。(一一)、平面图的概念、平面图的概念 例子例子1：电路板设计问题：电路板设计问题 在电路板设计时，需要考虑的问题之一是连接电路元件在电路板设计时，需要考虑的问题之一是连接电路元件间的导线间不能交叉。否则，当绝缘层破损时，会出现短间的导线间不能交叉。否则，当绝缘层破损时，会出现短路故障。路故障。 显然，电路板可以模型为一个图，显然，电路板可以模型为一个图，“要求电路元件间连要求电路元件间连接导线互不交叉接导线互不交叉”，对应于，对应于“要求图中的边不能相互交叉要求图中的边不能相互交叉”。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 例子例子2：空调管道的设计：空调管道的设计 某娱乐中心有某娱乐中心有6个景点，位置分布如下图。个景点，位置分布如下图。A1A4A5A3A2A6 分析者认为：分析者认为：(1) A1与与A4, (2) A2与与A5, (3) A3与与A6间人流较间人流较少，其它景点之间人流量大，必须投资铺设空调管道，但少，其它景点之间人流量大，必须投资铺设空调管道，但要求空调管道间不能交叉。如何设计？要求空调管道间不能交叉。如何设计？ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 如果把每个景点分别模型为一个点，景点间连线，当且如果把每个景点分别模型为一个点，景点间连线，当且仅当两景点间要铺设空调管道。那么，上面问题直接对应仅当两景点间要铺设空调管道。那么，上面问题直接对应的图为：的图为：A6A5A4A3A2A1 于是，问题转化为：能否把上图画在平面上，使得边不于是，问题转化为：能否把上图画在平面上，使得边不会相互交叉？会相互交叉？ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 通过尝试，可以把上图画为：通过尝试，可以把上图画为： 于是，铺设方案为：于是，铺设方案为：A6A5A4A3A2A1A1A4A5A3A2A6 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 问题：要求把问题：要求把3种公用设施种公用设施(煤气，水和电煤气，水和电)分别用煤气管分别用煤气管道、水管和电线连接到道、水管和电线连接到3间房子里，要求任何一根线或管道间房子里，要求任何一根线或管道不与另外的线或管道相交，能否办到？不与另外的线或管道相交，能否办到？ 例子例子3：3间房子和间房子和3种设施问题种设施问题 上面问题可以模型为如下偶图：上面问题可以模型为如下偶图：H3H2H1EWG 问题转化为，能否把上面偶图画在平面上，使得边与边问题转化为，能否把上面偶图画在平面上，使得边与边之间不会交叉？之间不会交叉？ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 上面的例子都涉及同一个图论问题：能否把一个图画在上面的例子都涉及同一个图论问题：能否把一个图画在平面上，使得边与边之间没有交叉？平面上，使得边与边之间没有交叉？ 针对这一问题，我们引入如下概念针对这一问题，我们引入如下概念 定义定义1 如果能把图如果能把图G画在平面上，使得除顶点外，边与边画在平面上，使得除顶点外，边与边之间没有交叉，称之间没有交叉，称G可以嵌入平面，或称可以嵌入平面，或称G是可平面图。可是可平面图。可平面图平面图G的边不交叉的一种画法，称为的边不交叉的一种画法，称为G的一种平面嵌入，的一种平面嵌入，G的平面嵌入表示的图称为平面图。的平面嵌入表示的图称为平面图。H3H2H1EWG图图GH3H2H1EWG图图G的平面嵌入的平面嵌入 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 注注: (1) 可平面图概念和平面图概念有时可以等同看待；可平面图概念和平面图概念有时可以等同看待； (2) 图的平面性问题主要涉及如下几个方面：图的平面性问题主要涉及如下几个方面：1) 平面图的平面图的性质；性质；2) 平面图的判定；平面图的判定；3) 平面嵌入方法平面嵌入方法(平面性算法平面性算法) ;4）涉及图的平面性问题的拓扑不变量。涉及图的平面性问题的拓扑不变量。 由由 图的平面性问题研究引申出图的一般嵌入性问题的研图的平面性问题研究引申出图的一般嵌入性问题的研究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘究，形成了拓扑图论的主要内容。我国数学家吴文俊、刘彦佩等在该方向都有重要结果。刘彦佩的专著是彦佩等在该方向都有重要结果。刘彦佩的专著是图的上图的上可嵌入性理论可嵌入性理论(1994)，化学工业出版社出版。，化学工业出版社出版。 历史上，波兰数学家库拉托斯基、美国数学家惠特尼、历史上，波兰数学家库拉托斯基、美国数学家惠特尼、生于英国的加拿大数学家托特，我国数学家吴文俊等都在生于英国的加拿大数学家托特，我国数学家吴文俊等都在拓扑图论中有过精湛的研究。拓扑图论中有过精湛的研究。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10(二二)、平面图性质、平面图性质 定义定义2 (1) 一个平面图一个平面图G把平面分成若干连通片，这些连把平面分成若干连通片，这些连通片称为通片称为G的区域，或的区域，或G的一个面。的一个面。G的面组成的集合用的面组成的集合用表示。表示。 在上图在上图G中，共有中，共有4个面。其中个面。其中f4是外部面，其余是内部是外部面，其余是内部面。面。= =f1, f2, f3, f4。平面图平面图Gf1f3f2f4 (2) 面积有限的区域称为平面图面积有限的区域称为平面图G的内部面，否则称为的内部面，否则称为G的外部面。的外部面。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 (3) 在在G中，顶点和边都与某个给定区域关联的子图，称中，顶点和边都与某个给定区域关联的子图，称为该面的边界。某面为该面的边界。某面 f 的边界中含有的边数的边界中含有的边数(割边计算割边计算2次次)称为该面称为该面 f 的次数的次数, 记为记为deg ( f )。平面图平面图Gf1f3f2f4 在上图中，红色边在在上图中，红色边在G中的导出子图为面中的导出子图为面 f3 的边界。的边界。1deg()1f2deg()3f3deg()6f4deg()6f 1、平面图的次数公式、平面图的次数公式 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 定理定理1 设设G=(n, m)是平面图，则：是平面图，则：deg()2ffm 证明：对证明：对G的任意一条边的任意一条边e, 如果如果e是某面割边，那么由面是某面割边，那么由面的次数定义，该边给的次数定义，该边给G的总次数贡献的总次数贡献2次；如果次；如果e不是割边，不是割边，那么，它必然是两个面的公共边，因此，由面的次数定义，那么，它必然是两个面的公共边，因此，由面的次数定义，它也给总次数贡献它也给总次数贡献2次。于是有：次。于是有：deg()2ffm 2、平面图的欧拉公式、平面图的欧拉公式 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 定理定理2(欧拉公式欧拉公式) 设设G=(n, m)是连通平面图，是连通平面图，是是G G的面的面数，则：数，则：2nm 证明：情形证明：情形1，如果，如果G是树，那么是树，那么m=n-1, =1。在这种情。在这种情况下，容易验证，定理中的恒等式是成立的。况下，容易验证，定理中的恒等式是成立的。 情形情形2，G不是树的连通平面图。不是树的连通平面图。 假设在这种情形下，欧拉恒等式不成立。则存在一个含假设在这种情形下，欧拉恒等式不成立。则存在一个含有最少边数的连通平面图有最少边数的连通平面图G, 使得它不满足欧拉恒等式。设使得它不满足欧拉恒等式。设这个最少边数连通平面图这个最少边数连通平面图G=(n, m), 面数为面数为，则：，则：2nm 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 因为因为G不是树，所以存在非割边不是树，所以存在非割边e。显然，。显然，G-e是连通平面是连通平面图，边数为图，边数为m-1, 顶点数为顶点数为n, 面数为面数为-1。 由最少性假设，由最少性假设，G-e满足欧拉等式：满足欧拉等式： 化简得：化简得：(1)(1)2nm2nm 这是一个矛盾。这是一个矛盾。 注：该定理可以采用对面数注：该定理可以采用对面数作数学归纳证明。作数学归纳证明。 3、欧拉公式的几个有趣推论、欧拉公式的几个有趣推论 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 推论推论1 设设G是具有是具有个面个面k k个连通分支的平面图，则：个连通分支的平面图，则：1nmk 证明：对第证明：对第i (1ik)ik)个分支来说，设顶点数为个分支来说，设顶点数为n ni i，边数，边数为为m mi i，面数为，面数为i i, ,由欧拉公式：由欧拉公式：2iiinm 所以，所以，12kiiiinmk 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 而：而：1112kkkiiiiiinmk1kiinn1kiimm11kiik 所以得：所以得：1nmk 推论推论2 设设G是具有是具有n n个点个点m m条边条边个面的连通平面图，如个面的连通平面图，如果对果对G G的每个面的每个面f f , ,有：有：deg (deg (f f) ) l 3,3,则：则：(2)2lmnl 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 证明：一方面，由次数公式得：证明：一方面，由次数公式得：22deg()fmmfll 另一方面，由欧拉公式得：另一方面，由欧拉公式得：2nm 所以有：所以有：22mnml 整理得：整理得：(2)2lmnl 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 注注: (1)上面推论上面推论2也可以叙述为：也可以叙述为： 设设G=(n, m)是连通图，如果：是连通图，如果：(2)2lmnl 则则G是非可平面图。是非可平面图。 (2) 推论推论2的条件是的条件是G是平面图的必要条件是平面图的必要条件,不是充分条件。不是充分条件。 例例1 求证：求证：K3,3是非可平面图。是非可平面图。 证明：注意到，证明：注意到，K3,3是偶图，不存在奇圈，所以，每是偶图，不存在奇圈，所以，每个面的次数至少是个面的次数至少是4,即即 l=4 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 所以，所以， 而而m=9，这样有：，这样有： 所以，由推论所以，由推论2，K3,3是非平面图。是非平面图。4(2)(62)822lnl(2)2lmnl 推论推论3 设设G是具有是具有n n个点个点m m条边条边个面的简单平面图，个面的简单平面图，则：则：36mn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 证明：情形证明：情形1，G连通。连通。 因为因为G是简单图，所以每个面的次数至少为是简单图，所以每个面的次数至少为3，即，即l=3。于是，由推论于是，由推论2得：得： 情形情形2，若，若G不连通。设不连通。设G1,G2,Gk是连通分支。是连通分支。36mn 一方面一方面,由推论由推论1：1nmk 另一方面，由次数公式得：另一方面，由次数公式得：23m 所以得：所以得：33(1)36mnkn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 例例2，证明：，证明：K5是非可平面图。是非可平面图。 证明：证明：K5是简单图，是简单图，m=10, n=5。3n-6=9。 得，得， ，所以，所以K5是非可平面图。是非可平面图。36mn 推论推论4 设设G是具有是具有n n个点个点m m条边的连通平面图，若条边的连通平面图，若G G的的每个圈均由长度是每个圈均由长度是 l 的圈围成，则：的圈围成，则：(2)(2)m ll n 证明：由次数公式，欧拉公式容易得证。证明：由次数公式，欧拉公式容易得证。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 推论推论5 设设G是具有是具有n n个点个点m m条边的简单平面图，则：条边的简单平面图，则：5 证明：若不然，设证明：若不然，设6 由握手定理：由握手定理：()6( )236v V Gnd vmmn 这与这与G是简单平面图矛盾。是简单平面图矛盾。 注：该结论是证明注：该结论是证明“5色定理色定理”的出发点。的出发点。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 定理定理3 一个连通平面图是一个连通平面图是2连通的，当且仅当它的每连通的，当且仅当它的每个面的边界是圈。个面的边界是圈。 证明：证明：“必要性必要性”： 设设G是是2连通的平面图，因为环连通的平面图，因为环总是两个面的边界，且环面显然由圈围成。不失一般性，总是两个面的边界，且环面显然由圈围成。不失一般性，假设假设G没有环，那么没有环，那么G没有割边，也没有割点。所以，没有割边，也没有割点。所以，每个面的边界一定是一条闭迹。每个面的边界一定是一条闭迹。 设设C是是G的任意面的一个边界，我们证明，它一定为圈。的任意面的一个边界，我们证明，它一定为圈。 若不然，设若不然，设C是是G的某面的边界，但它不是圈。的某面的边界，但它不是圈。 因因C是一条闭迹且不是圈，因此，是一条闭迹且不是圈，因此，C中存在子圈。设该中存在子圈。设该子圈是子圈是W1.因因C是某面的边界，所以是某面的边界，所以W1与与C的关系可以表的关系可以表示为下图的形式：示为下图的形式： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24vvj-1v1v2vi-1vi+1vnW1 容易知道：容易知道：v为为G的割点。矛盾！的割点。矛盾！ “充分性充分性” 设平面图设平面图G的每个面的边界均为圈。此时的每个面的边界均为圈。此时删去删去G中任意一个点不破坏中任意一个点不破坏G的连通性，这表明的连通性，这表明G是是2连连通的。通的。 推论推论6 若一个平面图是若一个平面图是2连通的，则它的每条边恰在两连通的，则它的每条边恰在两个面的边界上。个面的边界上。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25(三三)、图的嵌入性问题简介、图的嵌入性问题简介 在图的平面嵌入的基础上，简单介绍：在图的平面嵌入的基础上，简单介绍： 1、曲面嵌入、曲面嵌入 1)、球面嵌入、球面嵌入 定理定理4 G可球面嵌入当且仅当可球面嵌入当且仅当G可平面嵌入。可平面嵌入。 证明：我们用建立球极平面射影的方法给出证明。证明：我们用建立球极平面射影的方法给出证明。 将求面将求面S放在一个平面放在一个平面P上，设切点为上，设切点为O，过，过O作垂直作垂直于于P的直线，该直线与的直线，该直线与S相交于相交于z。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 2)、环面嵌入、环面嵌入 环面的形状像一个汽车轮胎的表面。环面的形状像一个汽车轮胎的表面。PzyOx球极投影示意图球极投影示意图 作映射作映射 f : S -z P。定义。定义 f (x) = y, 使得使得x ,y , z三点三点共线。该映射称为球极平面射影。共线。该映射称为球极平面射影。 通过通过f, 可以把嵌入球面的图映射为嵌入平面的图。反可以把嵌入球面的图映射为嵌入平面的图。反之亦然。之亦然。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 例例3 将将K4, K5, K3,3嵌入到环面上。嵌入到环面上。 3) 定向曲面嵌入定向曲面嵌入K4的环面嵌入的环面嵌入K5的环面嵌入的环面嵌入K3,3的环面嵌入的环面嵌入 这是目前嵌入性问题研究热点。国内：刘彦佩，黄元这是目前嵌入性问题研究热点。国内：刘彦佩，黄元秋等是从事该方向研究的代表。秋等是从事该方向研究的代表。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 2、图的、图的3维空间嵌入维空间嵌入 定理定理5 所有图均可嵌入所有图均可嵌入R3中。中。 证明：在证明：在R3中作空间曲线：中作空间曲线：23:xtlytzt 把图把图G的顶点放在该直线的不同位置，则的顶点放在该直线的不同位置，则G的任意边不的任意边不相交。相交。 事实上，对处于曲线事实上，对处于曲线 l 上的任意上的任意4个相异顶点，它们对个相异顶点，它们对应的参数值分别为：应的参数值分别为：t1,t2,t3,t4。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 因为：因为：2311123222233332344411011tttttttttttt 所以，上面所以，上面4点不共面。点不共面。(四四)、凸多面体与平面图、凸多面体与平面图 一个多面体称为凸多面体，如果在体上任取两点，其一个多面体称为凸多面体，如果在体上任取两点，其连线均在体上。连线均在体上。 凸多面体的一维骨架：把一个凸多面体压缩在平面上，凸多面体的一维骨架：把一个凸多面体压缩在平面上，得到一个对应的平面图，该平面图称为该凸多面体的一得到一个对应的平面图，该平面图称为该凸多面体的一维骨架。维骨架。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 定理定理6 存在且只存在存在且只存在5种正多面体：它们是正四、六、种正多面体：它们是正四、六、八、十二、二十面体。八、十二、二十面体。 证明：任取一个正证明：任取一个正面体，其顶点数、棱数分别是面体，其顶点数、棱数分别是n n和和m m。对应的一维骨架是一个每个面次数为。对应的一维骨架是一个每个面次数为l , ,顶点度数为顶点度数为r r的简单平面正则图的简单平面正则图G.G.正八面体一正八面体一维骨架维骨架正二十面体正二十面体一维骨架一维骨架 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 由次数公式得：由次数公式得： 以上两等式中：以上两等式中：l 3, r 32(1)ml 由握手定理得：由握手定理得：2(2)mnr 由由(1)与与(2) 得：得：2,(3)2nrmnrmll 将将(3)代入欧拉公式得：代入欧拉公式得：14 (22 )(4)nlllrr 在在(4)中，中，2202()llrrlrlr 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 32 于是得不等式组：于是得不等式组： 不等式组不等式组(5)的正整数解恰有的正整数解恰有5组：组：2()3(5)3lrlrlr正二十面体正二十面体203012355正八面体正八面体8126344正十二面体正十二面体123020533正方体正方体6128432正四面体正四面体464331相应的正多面体相应的正多面体mnrl序号序号 定理得证。定理得证。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 33 作业作业 P143-146 习题习题5 ： 2, 16，17 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 34Thank You !