《图论平面图》PPT课件.ppt
4-6 4-6 平面图平面图重点：掌握欧拉定理及其证明。重点：掌握欧拉定理及其证明。一、平面图一、平面图1、定义定义定义定义4-6.1 4-6.1 如果无向图如果无向图G=的所有结点和边的所有结点和边可以在一个平面上图示出来，而使各边仅在顶点处可以在一个平面上图示出来，而使各边仅在顶点处相交。无向图相交。无向图G称为称为平面图，平面图，平面图，平面图，否则称否则称G为为非平面图非平面图非平面图非平面图。有些图形从表面看有几条边是相交的，但是不有些图形从表面看有几条边是相交的，但是不能就此肯定它不是平面图，例如，下面左图表面看能就此肯定它不是平面图，例如，下面左图表面看有几条边相交，但如把它画成右图，则可看出它是有几条边相交，但如把它画成右图，则可看出它是一个平面图。一个平面图。有些图形不论怎样改画，除去结点外，有些图形不论怎样改画，除去结点外，总有边相交。故是非平面图。总有边相交。故是非平面图。2、面、边界、面、边界 定义定义4-6.2：设：设G是一连通平面图，由图中的边所是一连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为图的边，这样的区域称为G的一个面，包围该面的诸的一个面，包围该面的诸边所构成的回路称为这个面的边界。边所构成的回路称为这个面的边界。面面r的边界的长度的边界的长度称为该面的次数，记为称为该面的次数，记为deg(r)。定义定义定义定义4-6.3 4-6.3 设图设图G=是一连通平面图是一连通平面图,由图中由图中各边所界定的区域称为平面图的各边所界定的区域称为平面图的面面面面(regions)。有界。有界的区域称为的区域称为有界面有界面有界面有界面，无界的区域称为，无界的区域称为无界面无界面。界定各。界定各面的面的闭的路径闭的路径称为面的称为面的边界边界边界边界（boundary），面），面r的边界的边界长度称为长度称为面面r的度的度（degree）记为记为deg(r)，又称为面，又称为面r的的次数次数。例如图例如图deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3 deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18 如边是两个面的分界线，该边在两个面的度数中如边是两个面的分界线，该边在两个面的度数中各记各记1次。如边不是两个面的分界线次。如边不是两个面的分界线(称为割边称为割边)则该则该边在该面的度数中重复记了两次，故定理结论成立。边在该面的度数中重复记了两次，故定理结论成立。3.3.定理定理定理定理4-6.14-6.1 设设G为一有限平面图，面的次数之为一有限平面图，面的次数之和等于其边数的两倍。和等于其边数的两倍。证明思路：任一条边或者是两个面的共同边界证明思路：任一条边或者是两个面的共同边界（贡献（贡献2 2次），或者是一个面的重复边（贡献次），或者是一个面的重复边（贡献2 2次）次）4、欧拉定理、欧拉定理 定理定理定理定理4-6.24-6.2（欧拉定理）（欧拉定理）（欧拉定理）（欧拉定理）设设G为一平面连通图，为一平面连通图，v为其顶点数，为其顶点数，e为其边数，为其边数，r 为其面数，那么欧拉公为其面数，那么欧拉公式成立式成立 v e+r=2证明证明 （1 1）若）若G G为一个孤立结点，则为一个孤立结点，则v=1v=1，e=0e=0，r=1r=1，故故 v-e+r=2 v-e+r=2成立。成立。（2 2）若）若G G为一个边，即为一个边，即v=2v=2，e=1e=1，r=1r=1，则则 v-e+r=2 v-e+r=2成立。成立。（3 3）设）设G G为为k k条边时，欧拉公式成立，即条边时，欧拉公式成立，即 v vk k-e-ek k+r+rk k=2=2。考察的情况。考察的情况。因为在因为在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-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。例：已知一个平面图中结点数例：已知一个平面图中结点数v=10，每个面均由，每个面均由4条边围成，求该平面图的边数和面数。条边围成，求该平面图的边数和面数。解：因每个面的次数均为解：因每个面的次数均为4，则，则2e=4r，即，即e=2r，又又v=10，代入欧拉公式，代入欧拉公式v-e+r=2有有10-2r+r=2解得解得r=8，则，则e=2r=16。说明：这是简单图是平面图的必要条件。5.5.定理定理定理定理4-6.34-6.3 设设G为一简单连通平面图，其顶点数为一简单连通平面图，其顶点数v3，其边数为，其边数为e，那么，那么 e3v 6 证明思路：设证明思路：设G G的面数为的面数为r r,当当v=3,e=2v=3,e=2时上式成立时上式成立,若若e=3e=3,则每一面的次数不小于则每一面的次数不小于3 3,各面次数之和不小于各面次数之和不小于2e2e,因此因此 2e2e3r3r,r r2e/3 代入欧拉公式代入欧拉公式:2=v-e+r2=v-e+rv-e+2e/3 整理后得整理后得:e3v 6 本定理的用途本定理的用途:判定某图是非平面图。判定某图是非平面图。例如：例如：K5中中e=10，v=5，3v-6=9，从而，从而e3v-6，所以，所以K5不是平面图。不是平面图。定理定理4.6.3的条件不是充分的。如的条件不是充分的。如K3,3图满图满足定理足定理4-6.3的条件（的条件（v=6，e=9，3v-6=12，e3v-6成立），但成立），但K3,3不是平面图。不是平面图。证明证明K3,3图图不是平面图。不是平面图。在在K3,3中有中有6个结点个结点9条边，条边，2v-4=26-4=89,与与 2v-4e 矛盾，矛盾，故故 K3,3不是平面图。不是平面图。证明证明 假设假设K3,3图是平面图。图是平面图。在在K3,3中任取三个结点，其中必有两个结点不中任取三个结点，其中必有两个结点不邻接，故每个面的次数都不小于邻接，故每个面的次数都不小于4，由由4r2e，re/2，即，即 v-e+e/2v-e+r=2，v-e/22，2v-e 4，2v-4e。
