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