7-5-平面图.ppt

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

1、离散数学Discrete Mathematics 课程回顾课程回顾欧拉图欧拉图：哥尼斯堡七桥问题、无向欧拉图定：哥尼斯堡七桥问题、无向欧拉图定义与判定定理、一笔画问题、有向欧拉图定义与判定定理、一笔画问题、有向欧拉图定义与判定定理、计算机鼓轮设计及其它应用义与判定定理、计算机鼓轮设计及其它应用汉密尔顿图汉密尔顿图：周游世界问题、汉密尔顿图定：周游世界问题、汉密尔顿图定义与判定定理、图的闭包、判别汉密尔顿路义与判定定理、图的闭包、判别汉密尔顿路不存在的标号法不存在的标号法第七章第七章 图论第图论第5讲讲 7-5 平面图平面图7-6 对偶图与着色对偶图与着色问题引入问题引入例例 考虑把三座房和三种

2、考虑把三座房和三种设施每种都连接起来的问题，设施每种都连接起来的问题，如图如图7-64所示，是否有可能使所示，是否有可能使得这样的连接里不发生交叉？得这样的连接里不发生交叉？这个问题可以用这个问题可以用K3,3来建模。来建模。原来的问题可以重新叙述为：原来的问题可以重新叙述为：能否在平面里画出能否在平面里画出K3,3 ，使得，使得没有两条边发生交叉？没有两条边发生交叉？ 例如印刷线路板上的布线。例如印刷线路板上的布线。 在现实生活中，常常要画一些图形，希望在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，边与边之间尽量减少相交的情况，7-5 平面图平面图学习本节要熟悉如下术语（

3、学习本节要熟悉如下术语（8个）：个）：平面图、平面图、边界、边界、面、面、要求：要求：掌握掌握4个定理，重点掌握欧拉定理。个定理，重点掌握欧拉定理。在在2度结点内同构度结点内同构非平面图、非平面图、有界面、有界面、无界面、无界面、 面的次数、面的次数、一、平面图一、平面图 本节重点考虑无向图。本节重点考虑无向图。1、定义定义7-5.17-5.1 如果无向图如果无向图G=的所有的所有结点和边可以在一个平面上图示出来，而使结点和边可以在一个平面上图示出来，而使各边仅在顶点处相交。无向图各边仅在顶点处相交。无向图G称为称为平面图平面图（planar graph），否则称），否则称G为为非平面图非平面

4、图。 有些图形从表面看有几条边是相交的，有些图形从表面看有几条边是相交的，但是不能就此肯定它不是平面图。但是不能就此肯定它不是平面图。v例例1 判断下面的两个图是否为平面图。判断下面的两个图是否为平面图。解：解：K4是平面图，因为可以不带交叉地画出是平面图，因为可以不带交叉地画出它（图它（图7-66所示）；所示）；Q3是平面图（图是平面图（图7-68所示）；所示）； 有些图形不论怎样改画，除去结点外，有些图形不论怎样改画，除去结点外，总有边相交。如总有边相交。如K3,3图，故它是非平面图。图，故它是非平面图。K3,32、面、边界、面、边界 定义定义7-5.2 7-5.2 设设G=是一连通平面图

5、，是一连通平面图，由图中的边所包围的区域，在区域内既不包含由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为图的结点，也不包含图的边，这样的区域称为G的一个的一个面面 (regions) ，包围该面的诸边所构成的，包围该面的诸边所构成的回路称为这个面的回路称为这个面的边界边界（boundary）。有界的区有界的区域称为域称为有界面有界面，无界的区域称为，无界的区域称为无界面无界面。面。面r的的边界长度称为边界长度称为面面r r的度的度（degree）记为记为deg (r) ，又称为面又称为面r的的次数次数 。2、面、边界、面、边界 定义定义7-5.2 7-5.2

6、设设G=是一连通平面图，是一连通平面图，G的边将的边将G所在的平面分成若干个区域，每个所在的平面分成若干个区域，每个区域称为区域称为G的一个的一个面面 (regions) ，包围该面的所有，包围该面的所有边所构成的边所构成的回路回路称为这个面的称为这个面的边界边界（boundary）。面积面积有限的区域称为有限的区域称为有界面（内部面）有界面（内部面），面积，面积无限的区域称为无限的区域称为无界面（外部面）无界面（外部面）。面。面r的边界的边界长度称为长度称为面面r r的度的度（degree）记为记为deg (r) ，又，又称为面称为面r的的次数次数 。例如图例如图7-5.3deg(r1)=3

7、deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3 deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18 如边是两个面的分界线，该边在两个面的度数中如边是两个面的分界线，该边在两个面的度数中各记各记1次。如边不是两个面的分界线次。如边不是两个面的分界线(称为割边称为割边)则该边则该边在该面的度数中重复记了两次，故定理结论成立。在该面的度数中重复记了两次，故定理结论成立。见前面的图见前面的图7-5.3定理定理7-5.17-5.1 设设G为一有限平面图，面的次为一有限平面图，面的次数之和等于其边数的两倍。数之和等于其边数的两倍。 证明思路：任一

8、条边或者是两个面的共同边界证明思路：任一条边或者是两个面的共同边界（贡献（贡献2 2次），或者是一个面的重复边（贡献次），或者是一个面的重复边（贡献2 2次）次） 4、欧拉定理、欧拉定理 定理定理7-5.27-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-

9、e+r=2成立。成立。 （3 3）设）设G G为为k条边时，欧拉公式成立，即条边时，欧拉公式成立，即 v vk k-e-ek k+r+rk k=2=2。考察考察G G为为k+1条边时条边时的情况。的情况。 因为在因为在k条边的连通图上增加一条边，使它仍为连条边的连通图上增加一条边，使它仍为连通图，只有下述两种情况：通图，只有下述两种情况：加上一个新结点加上一个新结点b，b与图上的一点与图上的一点a相连，相连，此时此时v vk k和和e ek k两者都增加两者都增加1，而面数，而面数r rk k没变，故没变，故（ v vk k +1）-（ e ek k +1）+ r rk k = v vk k-

10、e-ek k+r+rk k=2=2。用一条边连接图上的已知两点，此时用一条边连接图上的已知两点，此时e ek k和和r rk k都增加都增加1，结点数，结点数v vk k没变，故没变，故 v vk k -（e ek k +1）+（r rk k +1）=v vk k-e-ek k+r+rk k=2=2。 练习 317页（1）练习317页（6）证明证明 彼得森图中每个面由彼得森图中每个面由5条边围成，条边围成，k=5，e=15，v=10，k(v-2)/(k-2)=40/3=3e=3, ,则每一面的次数不小于则每一面的次数不小于3 3, ,各面次数之和为各面次数之和为2e2e, ,因此因此 2e2e

11、3r3r, , r r2e/3 代入欧拉公式代入欧拉公式: : 2=2=v-e+rv-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图图不是平面图。不是平面图。

12、在在K3,3中任取三个结点，其中必有两个结点不中任取三个结点，其中必有两个结点不邻接，故每个面的次数都不小于邻接，故每个面的次数都不小于4，由由4r2e，re/2，即，即 v-e+e/2v-e+r=2， v-e/22， 2v- e 4， 2v-4e。证明证明 假设假设K3,3图是平面图。图是平面图。 在在K3,3中有中有6个结点个结点9条边，条边，2v-4=26-4=89,与与 2v-4e 矛盾，矛盾，故故 K3,3不是平面图。不是平面图。 在给定图在给定图G的边上，插入一个新的度数的边上，插入一个新的度数为为2的结点，使一条边分成两条边，或者对的结点，使一条边分成两条边，或者对于关于度数为于

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