图论第6章节课件

《图论第6章节课件》由会员分享，可在线阅读，更多相关《图论第6章节课件（73页珍藏版）》请在金锄头文库上搜索。

1、第六章 平面图,电子科技大学数学科学学院 王也洲,,定义1 若图 G 可画在一个平面上使除顶点外边不交叉，则称 G 可嵌入平面，或称 G 为可平面图。可平面图 G 的边不交叉的一种画法称为 G 的一个平面嵌入，G 的平面嵌入表示的图称为平面图。,例1,=,平面图, 6.1平面图,可平面图,不可平面图,=,不可平面图,=,可平面图,=,=,可平面图,定义： 设G 是一个平面图，G 将所嵌入的平面划分为若干个区域，每个区域的内部连同边界称为 G 的面，无界的区域称为外部面或无限面。每个平面图有且仅有一个外部面。设 f 是 G 的一个面，构成 f 的边界的边数（割边计算两次）称为 f 的次数，记为

2、deg(f )。,6,例2,有5个面：f1，f2，f3，f4，f5 （ f5 为外部面）,图不连通，其外部面的次数为5,deg(f1) =1,deg(f2) =2,deg(f3) = 3,deg(f4) = 6,deg(f5)= 10,定理1 设具有m 条边的平面图G 的所有面的集合为, 则,证明 任取G 的一条边 e 。若 e 是两个面的公共边，则在计算面的次数时，e 被计算两次。若 e 不是公共边，则 e 是 G 的割边，由面的次数的定义，e 也被计算两次。所以所有面的次数之和是边数的2倍，即（1.1）式成立。,证明,对 用归纳法。,设 = k 时，（1.2）式成立。,定理2（Euler公

3、式） 设G 是具有 n 个点m 条边个面的连通平面图，则有 n m + =2 （1.2）,当 =1时 ，G 无圈又连通，从而是树，有 n =m+1,于是 n -m+ =（m+1）- m + 1= 2,同时 n = n ， m = m - 1， = - 1,代入（1.3）式得 n -（m-1）+（ -1）= 2,即 n m + =2,当 = k+1 时，此时 G 至少两个面，从而有圈 C。删去 C 中一条边，记所得之图为 G 。并设 G 的点数、边数和面数依次为 n , m 和 , 易知 G 仍连通，但只有 k 个面，由归纳假设有,n - m + = 2 （1.3）,证明 设G的k个连通分支分别

4、为G1, G2, ,Gk ,对每个G i用欧拉公式可得： ni mi +i = 2 ， i=1，2，k 其中 ni， mi ，i 分别为G i的点数、边数和面数，将k个等式两边相加得,定理3 设G是具有个面k个连通分支的平面图，则 n - m += k + 1,将它们代入（1.4）式得 n m + k-1 = 2k,定理4 设 G 是具有n 个点m 条边的连通平面图, 是G 中所有面的集合，若对 任意的 f 均有 deg( f )l 3，则,证明 设G 有 个面 ，因每个面均有 deg(f)l ，故,将上式代入 Euler 公式 n m + = 2 得,推论1 设简单可平面图 G 有 n个点m

5、 条边，且n3，则,m3n-6 （1.6）,证明 先假定G 连通。因G 至少有三个点又连通且为简单图，故对G 相应的平面图中每个面的次数至少是3。由定理3，取 l = 3 得,设G 不连通。若G 存在至少有三个点的连通分支，因对G 的这些分支均满足（1.6）式，将各不等式相加也得类似不等式，设为m1 3n 1 - 6。,设G 没有多于两个点的连通分支。此时m n 。因 n 3 时， n 3n - 6，所以有 m3n - 6。,再设G 的所有少于3个点的连通分支的总边数为m2，总点数为n 2。此时有 m2 n 2 3n 2 ， 于是 m1+m2 3(n 1 + n 2 ) - 6， 从而有 m

6、3n - 6。,推论2 设G是具有n个点m条边的连通平面图，若G中所有面均由长度为 l 的圈围成，则 m (l-2) = l (n-2) (1.7）,证明 只需在定理4的证明中将所有不等号改为等号即可得(1.7)式。,例3 在右图所示的图中， m=12，n = 8，l = 4 有 12(4-2) = 4(8-2)， 满足（1.7）式。,例4 证明 K5 和 K 3,3 是不可平面图。,证明 若 K5 是可平面图，则因 K5 是至少三个点的简单图，由推论1，K5 应满足 m3n -6。而 K5 中 m=10， n = 5，代入不等式 (1.6) 得 1035 6 = 9 矛盾，所以 K5 是不可

7、平面图。,对 K 3,3，因 K 3,3 没有长小于4的圈，所以若 K 3,3 是可平面图，则对其相应的平面图中每个面的次数至少为4。由定理4，K 3,3 应满足 l = 4 的不等式（1.5）即,而K 3,3中m = 9， n = 6，代入上式得: 926-4 = 8 矛盾，所以 K 3,3 是不可平面图。,定理5 若 G 是简单平面图，则5.,证明,对点数 n =1，2，直接验证可知结论成立。 设n 3，若 6，则,这与定理4的推论1矛盾。 所以5。,1. 若图G能画在曲面S上使它的边仅在端点相交，则称图G可嵌入曲面S；图G的这样一种画法（若存在的话）称为G的一个S嵌入。,K5不可嵌入平面

8、，但能嵌入环面，也存在不可嵌入环面的图。,平面嵌入概念的推广,例 下图表示了K5 的环面嵌入，其中矩形的两对对边相等同。,2. 可以证明对每个曲面S总存在不可嵌入S的图。另一方面每个图又存在可以嵌入的某个可定向的曲面。,3. 一个图可嵌入平面当且仅当它可嵌入球面 。,简证 将球面S放在一个平面P上，设切点为O，过O点作垂直于P的直线，此直线与S的交点设为z。作映射,定义 f（x）= y 当且仅当点 z，x，y共线。这样的映射f （如图6-9所示）便称为球极平面射影。,通过球极平面射影可将嵌入球面S的图映射为嵌入平面的图，反之亦然。,4. 如果将一个有n个顶点，m条棱和个面的凸多面体的顶点作为顶

9、点，棱作为边，则这个多面体可视为一个图G，很明显G可嵌入球面，从而可嵌入平面而得到一个连通的平面图。因而由定理2，凸多面体的顶点数，棱数与面数也满足 n-m +=2。这个公式也称为欧拉公式。,定理6（Platonic） 存在且只存在5种正多面体：正四面体、正方体、正八面体、正十二面体和正二十面体。,证明 任取一个正面体A ，设A 有n个顶点，m条棱。将A 嵌入平面记所得的平面图为G。易知G是一个每个面的次数均相同（设为l）的r 度简单正则图。从而有,l = 2m，nr = 2m，l3，r3,将上两式代入Euler 公式n-m+=2 得,因n 和l 均为正，由（1.9）式得,这样我们得到不等式组

10、,此不等式组的整数解恰为5组。将这5组解分别代入（1.9）和 (1.8)式可求得相应的值，其结果见下表。,n = 4l(2l lr+2r)-1 (1.9),正八面体 正二十面体,正八面体和正二十面体的平面表示为,定理7 一个连通平面图是2连通的，当且仅当它的每个面的边界是圈。,证明,不失一般性，假设G没有环，那么G没有割边，也没有割点。所以，每个面的边界一定是一条闭迹。,“必要性”,设C是G的任意面的一个边界，我们证明，它一定为圈。,若不然，设C是G的某面的边界，但它不是圈。,因C是一条闭迹且不是圈，因此，C中存在子圈。,设该子圈是W1。因C是某面的边界，所以W1与C的关系可以表示为如图的形式

11、：,容易知道：v为G的割点。矛盾！,“充分性”,设平面图G的每个面的边界均为圈。,此时删去G中任意一个点不破坏G的连通性，这表明G是2连通的。,推论 若一个平面图是2连通的，则它的每条边恰在两个面的边界上。,6.2 一些特殊平面图及平面图的对偶图,一、一些特殊平面图,定义1设G是简单可平面图，如果G是Ki (1i4),或者在G的任意两个不相邻的顶点间添加一条边后，得到的图均是不可平面图，则称G是极大可平面图。极大可平面图的平面嵌入称为极大平面图。,极大可平面图,极大可平面图,非极大可平面图,引理 设G是极大平面图，则G必连通； 若G的点数n3，则G无割边。,证明 若G不连通，则G至少存在两个连

12、通分支G1与G2。,显然G1与G2也是平面图。,将G2画在G1的外部面内，并分别在G1与G2的外部面上各取一个点u和v。,很明显， u与v不相邻。,易知G*也是平面图，这与G是极大平面图矛盾，所以G连通。,连接u和v，记所得的图为G* 。,因n3，所以G1与G2中必有一个至少含两个点，不妨设G2至少含两个点。,设n3。若G 存在割边 uv，则 G-uv 不连通，恰有两个连通分支G1与G2。,设 f 是 G1中含点u的面，将G2画在 f 内。,因G2是简单图，故在G2的外部面上存在不等于v的点t。,在G中连接不相邻点u和t，记所得的图为G*，易知G* 也是平面图，这与G是极大平面图矛盾。所以G不

13、含割边。,定理8 设G是至少有3 个顶点的平面图。则G是极大平面图的充分必要条件为G中各面的次数均为3且为简单图。,证明 充分性显然，下证必要性。,设G是极大平面图。由定义知，G是简单图。,又因G至少有3 个顶点，所以G中各面次数至少为3。,这样，若结论不成立，则G中必存在一个面 f，满足deg(f )4。,由引理知 ，G无割边，所以围成 f 的边界所成的回路是一个圈，不妨设为v1v2vtv1，其中t4。,若 v1与v3不相邻，则在 f 内连接v1与v3不破坏G的平面性，这与G为极大平面图矛盾。所以v1与v3必相邻。,因面 f 内无边，故边v1v3必在 f 外。,同理，v2与v4必相邻并且边v

14、2v4也在 f 外。,这样边 v1v3 与边 v2v4 必相交(如图所示)，这就与G是平面图矛盾。,所以G中各面次数只能为3。,推论 设G是一个有n个点m条边个面的极大平面图， 且n3，则 （1）m = 3n-6； （2）= 2n-4。 证明留作习题。,推论表明对一个极大平面图G，当其点数n给定时，G的边数和面数也就确定了，从而G的结构框架也大体确定了。,例如，当n=4时，G为K4；当n=6时，G为正八面体；,当 n=9时，G 有21 条边14个面，其中一个的结构如图所示：,当n=12时，G有30条边20个面，此时，其中的两个G一个为正二十面体，另一个如图右所示。,定义2 如果在不可平面图G中

15、任意删去一条边所得的图为可平面图，则称G为极小不可平面图。例如K5和K3,3。,定义3 若一个可平面图存在一个所有顶点均在同一个面的平面嵌入，则称该图为外可平面图。外可平面图的任一外平面嵌入（即所有顶点均在同一个面的嵌入）称为外平面图。,例 下图给出了一个外可平面图(a)及两种外平面嵌入(b)和(c)。,注：对外可平面图G来说，一定存在一种外平面嵌入，使得G的顶点均在外部面的边界上。这由球极投影法可以说明。,定义4 设G是一个简单外可平面图，若在G中任意不邻接顶点间添上一条边后，G成为非外可平面图，则称G是极大外可平面图。极大外可平面图的外平面嵌入，称为极大外平面图。,极大外平面图的外部面的周界是由多边形组成，内部面均有三角形围成。,例如,定理9 设G是一个有n (n3)个点，且所有点均在外部面上的极大外平面图，则G有n-2个内部面。,证明 对G的阶数作数学归纳。,当n=3时，G是三角形，显然只有一个内部面；,设当n=k时，结论成立。,当n=k+1时，首先，注意到G必有一个2度顶点u在G的外部面上。,考虑G1=G-v。,由归纳假设，G1有k-2个内部面。这样G有k-1个内部面。于是定理得证。,定理10