文档介绍：第第四四部部分分第廿九讲2信息科学与工程学院信息科学与工程学院第七章第七章图论图论7-5 平面图定义7-=<V,E>是一个无向图,如果能够把G的所有结点和边画在平面上,且使得任何两条边除了端点外没有其他的交点,则称G是一个平面图。。。。。。。。。。。。。。。。。。3信息科学与工程学院信息科学与工程学院第七章第七章图论图论定义7-,由图中的边所包围的区域,在区域中既不包含图的结点,也不包含图的边,这样的区域称为G的一个面,包围该面的诸边所构成的回路称为这个面的边界。v3。。。。。。v1v2v4v5v6v7r1r2r3r4无限面无限面面的面的边界的回路长度,称边界的回路长度,称作该面的作该面的次数次数,记为,记为deg(r)deg(r)4信息科学与工程学院信息科学与工程学院第七章第七章图论图论定理7-,面的次数之和等于其边数的两倍。证:因为任何一条边,或者是两个面的公共边,或者在一个面中作为边界被重复计算两次,故面的次数之和等于其边数的两倍。v3。。。。。。v1v2v4v5v6v7r1r2r3r45信息科学与工程学院信息科学与工程学院第七章第七章图论图论定理7-(欧拉定理)设有一个连通的平面图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条边的连通图上增加一条边,使其仍为连通图,只有两种情况:。。。。。。。。。。。。QQ11QQ22aa。。。。。。。。。。QQ11QQ22bb6信息科学与工程学院信息科学与工程学院第七章第七章图论图论例1:证明若G是每个面至少由k(k≥3)条边围成的连通平面图,则e ≤ k(v-2)/(k-2)。证明:由定理7- ≥kr再结合定理7-。例2 证明在6个结点12条边的连通简单平面图中,每个面是用3条边围成的。证明:由定理7-=8再由定理7- 及每个面的次数至少为3故结论成立。7信息科学与工程学院信息科学与工程学院第七章第七章图论图论定理7-,若v≥3,则e≤3v-6。证:当v=3,e=2时,显然成立。(对于无限面而言)除此之外,设连通简单平面图G的面数为r,若e≥3,则每一面的次数不小于3,由前面定理知各面数之和为2e,因此2e ≥ 3r 代入欧拉定理:v-e+r=2二式结合得:e≤3v-6提示:此定理可作为判定某图G是平面图的必要条件,而非充分条件。8信息科学与工程学院信息科学与工程学院第七章第七章图论图论例3 判断下图是否为平面图。K5。。。。。。。。。。。。。。。。。证明:K3,3不是平面图。(反证法)若是,则任取3个结点,其中必有两个结点不邻接,故每个面的次数都不小于4,于是有4r≤2e,代入欧拉公式v-e+r=2 可得2v-4≥e由此可判定K3,3不是平面图。K3,39信息科学与工程学院信息科学与工程学院第七章第七章图论图论例4 证明小于30条边的简单平面图至少有一个结点度数小于等于4。证明:(反证法)握手定理定理7--,如果它们是同构的,或者通过反复插入或删除度为2的结点后,使G1和G2同构,则称该两图是在2度结点内同构的。定义7-(Kruatowski定理)一个图是平面图当且仅当它不包含与K5或K3,3在2度结点内同构的子图。。。。。。。。。。。。