(57)--6.5 欧拉公式离散数学离散数学.ppt

《(57)--6.5 欧拉公式离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(57)--6.5 欧拉公式离散数学离散数学.ppt（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、欧拉公式设设G是任意的连通平面图，则有是任意的连通平面图，则有n m+f=2成立。成立。其中：其中：n为结点数，为结点数，m为边数，为边数，f f为面数。为面数。欧拉公式欧拉公式证明：证明：(1)若G为一个孤立结点，则n=1，m0，fl，故n m+f=2成立。(2)若G为一条边，即n2，m1，f1，则n m+f=2成立。设设G是任意的连通平面图，则有是任意的连通平面图，则有n m+f=2成立。成立。其中：其中：n为结点数，为结点数，m为边数，为边数，f f为面数。为面数。欧拉公式欧拉公式证明：证明：(3)设G有k条边时，欧拉公式成立，即nk mk+fk=2。考虑G有k+1条边：加上一个新结点v

2、，v与图G的一点u相连，如图(a)所示，此时点数和边数都增加1，而面数不变，因此，(nk+1)(mk+1)+fk=nk mk+fk=2。用一条边连接图上的两已知的点u和v，如图(b)所示，此时边数和面数都增加l，而点数不变，因此，nk(mk+1)+(fk+1)=nk mk+fk=2。综上所述，命题得证。例：设连通平面图G有7个结点，11条边，问G有多少个面？解：根据欧拉公式n-m+f=2，有7-11+f=2，则面数 f=6。设设G是连通分支为是连通分支为p p(p 2)的的(n，m)平面图平面图，有，有 f 个个面面，则有则有 n m+f=p+1。推论推论例：设非连通平面图G有9个结点，2个连

3、通分支，且所有的有限面的次数均为3，而无限面的次数为7，问G有多少边和面？解：设边数m，面数f。则：9-m+f=2+1；7+3(f-1)=2m；得出：m=14，f=8，所以G有14条边8个面。设设G G是是（n，m）连通平面图，且每个面的次数至少为连通平面图，且每个面的次数至少为l l(l l 3 3)，则则 。推论2设G是一个（n，m）连通简单平面图，若n3，则m3n-6。推论1设G有f个面，因为G的阶数大于2，所以每个面的次数不小于3。由平面图的所有面的次数之和是边数的2倍，有 代入欧拉公式得：整理可得：。证明：K5K3,3nK5的结点数n=5，边数m=10，3n-6=3*5-6=9，所以

4、不满足m3n-6，所以K5不是平面图。nK3,3的结点数n=6，边数m=9，3n-6=3*6-6=12，满足m3n-6，但是K3,3不是平面图。n假设K3,3是平面图，其中最短的回路长度为4，则每个面的次数至少为4，由定理得：9=2(6-2)=8，产生矛盾。所以K3,3不是平面图。收收 缩：缩：图图G中相邻结点中相邻结点u,v间的收缩，即删除边间的收缩，即删除边(u,v)，以新的结点，以新的结点w 取代取代u,v，使，使w关联关联u,v的的除除(u,v)外外的的一切边。一切边。同同 胚：胚：如果两个图如果两个图G1和和G2同构，或经过反复同构，或经过反复插入或消去插入或消去2度结点度结点后后 同构，则称同构，则称G1与与G2同胚。同胚。abcdefbcdefgabcdawd图G1 图G2 图G3 图G4平面图的判定一个图是平面图当且仅当不含与一个图是平面图当且仅当不含与K5或或K3,3同胚子图。同胚子图。或或没有可以收缩到没有可以收缩到K5或或K3,3的子图。的子图。Kuratowski定理定理平面图的判定abcdefbcdefgabcdawd图G1 图G2 图G3 图G4THANK YOU