7-5-平面图.ppt

《7-5-平面图.ppt》由会员分享，可在线阅读，更多相关《7-5-平面图.ppt（32页珍藏版）》请在课桌文档上搜索。

1、离散数学Discrete Mathematics,课程回顾,欧拉图：哥尼斯堡七桥问题、无向欧拉图定义与判定定理、一笔画问题、有向欧拉图定义与判定定理、计算机鼓轮设计及其它应用,汉密尔顿图：周游世界问题、汉密尔顿图定义与判定定理、图的闭包、判别汉密尔顿路不存在的标号法,第七章 图论第5讲 7-5 平面图7-6 对偶图与着色,问题引入,例 考虑把三座房和三种设施每种都连接起来的问题，如图7-64所示，是否有可能使得这样的连接里不发生交叉？这个问题可以用K3,3来建模。原来的问题可以重新叙述为：能否在平面里画出K3,3，使得没有两条边发生交叉？,例如印刷线路板上的布线。在现实生活中，常常要画一些图形

2、，希望边与边之间尽量减少相交的情况，,7-5 平面图,学习本节要熟悉如下术语（8个）：,平面图、,边界、,面、,要求：掌握4个定理，重点掌握欧拉定理。,在2度结点内同构,非平面图、,有界面、,无界面、,面的次数、,一、平面图 本节重点考虑无向图。1、定义7-5.1 如果无向图G=的所有结点和边可以在一个平面上图示出来，而使各边仅在顶点处相交。无向图G称为平面图（planar graph），否则称G为非平面图。,有些图形从表面看有几条边是相交的，但是不能就此肯定它不是平面图。,例1 判断下面的两个图是否为平面图。,解：K4是平面图，因为可以不带交叉地画出它（图7-66所示）；Q3是平面图（图7-

3、68所示）；,有些图形不论怎样改画，除去结点外，总有边相交。如K3,3图，故它是非平面图。,K3,3,2、面、边界 定义7-5.2 设G=是一连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为G的一个面(regions)，包围该面的诸边所构成的回路称为这个面的边界（boundary）。有界的区域称为有界面，无界的区域称为无界面。面r的边界长度称为面r的度（degree）记为deg(r)，又称为面r的次数。,2、面、边界 定义7-5.2 设G=是一连通平面图，G的边将G所在的平面分成若干个区域，每个区域称为G的一个面(regions)，包围该面的所有边所

4、构成的回路称为这个面的边界（boundary）。面积有限的区域称为有界面（内部面），面积无限的区域称为无界面（外部面）。面r的边界长度称为面r的度（degree）记为deg(r)，又称为面r的次数。,例如图7-5.3,deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3,deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18,如边是两个面的分界线，该边在两个面的度数中各记1次。如边不是两个面的分界线(称为割边)则该边在该面的度数中重复记了两次，故定理结论成立。,见前面的图7-5.3,3、定理7-5.1 设G为一有限平面图，面的

5、次数之和等于其边数的两倍。,证明思路：任一条边或者是两个面的共同边界（贡献2次），或者是一个面的重复边（贡献2次）,4、欧拉定理 定理7-5.2（欧拉定理）设G为一平面连通图，v为其顶点数，e为其边数，r 为其面数，那么欧拉公式成立 v e+r=2,证明（1）若G为一个孤立结点，则v=1，e=0，r=1，故 v-e+r=2成立。,（2）若G为一个边，即v=2，e=1，r=1，则 v-e+r=2成立。,（3）设G为k条边时，欧拉公式成立，即 vk-ek+rk=2。考察G为k+1条边时的情况。,因为在k条边的连通图上增加一条边，使它仍为连通图，只有下述两种情况：,加上一个新结点b，b与图上的一点a

6、相连，此时vk和ek两者都增加1，而面数rk没变，故（vk+1）-（ek+1）+rk=vk-ek+rk=2。,用一条边连接图上的已知两点，此时ek和rk都增加1，结点数vk没变，故 vk-（ek+1）+（rk+1）=vk-ek+rk=2。,练习 317页（1）,练习317页（6）,证明彼得森图是非平面图。,例：已知一个平面图中结点数v=10，每个面均由4条边围成，求该平面图的边数和面数。,解：因每个面的次数均为4，则2e=4r，即e=2r，又v=10，代入欧拉公式v-e+r=2有10-2r+r=2解得r=8，则e=2r=16。,说明：这是简单连通平面图的必要条件。,5、定理7-5.3 设G为一

7、简单连通平面图，其顶点数v3，其边数为e，那么 e3v 6,证明思路：设G的面数为r,当v=3,e=2时上式成立,若e=3,则每一面的次数不小于3,各面次数之和为2e,因此 2e3r,r2e/3 代入欧拉公式:2=v-e+rv-e+2e/3 整理后得:e3v 6 本定理的用途:判定某图是非平面图。,例如：K5中e=10，v=5，3v-6=9，从而e3v-6，所以K5不是平面图。,定理7-5.3的条件不是充分的。如K3,3图满足定理7-5.3的条件（v=6，e=9，3v-6=12，e3v-6成立），但K3,3不是平面图。,315页例2 证明K3,3图不是平面图。,在K3,3中任取三个结点，其中必

8、有两个结点不邻接，故每个面的次数都不小于4，由4r2e，re/2，即 v-e+e/2v-e+r=2，v-e/22，2v-e 4，2v-4e。,在给定图G的边上，插入一个新的度数为2的结点，使一条边分成两条边，或者对于关于度数为2的结点的两条边，去掉这个结点，使两条边化成一条边，这些都不会影响图的平面性。,6、定义7-5.3 给定两图G1和G2，或者它们是同构的，或者反复地插入或去掉二度结点后，使G1和G2同构，则称G1和G2是在2度结点内同构的，也称G1和G2是同胚的。,7、库拉托夫斯基定理(Kuratowski定理)定理7-5.4 一个图是平面图的充要条件是它不含与K5或K3，3在二度结点内同构的子图。,欧拉公式有时可以用来判定某个图是非平面图。下面的库拉托夫斯基定理给出了判定一个图是平面图的充要条件,K3，3,K5,K5和K3，3常称作库拉托夫斯基图。,例2 确定下图所示的图是否为平面图？,解：G有与K5二度结点内同构的子图,作业317页（2）（3）（5）,本节内容到此结束,谢谢大家！,