对于简单图来讲，它的每个内部面至少要由三条边围成，每条边最多为两个面的边界。

Presentation on theme: "对于简单图来讲，它的每个内部面至少要由三条边围成，每条边最多为两个面的边界。"— Presentation transcript:

1 对于简单图来讲，它的每个内部面至少要由三条边围成，每条边最多为两个面的边界。
定理6.1：若连通平面图G有n个顶点,e条边和f个面,则n-e+f=2---称为欧拉公式 证明：对边数进行归纳证明: 对于一条边的连通平面图, 第一个n=2,f=1,e=1,n-e+f=2,成立 第二个n=1,f=2,e=1,n-e+f=2,成立

2 假设对于一切m-1条边的连通平面图, 欧拉公式均成立。现考察m条边的连通平面图。
(1)若G有一个度数为1的顶点, 则删去该顶点及其关联边, 便得到一个连通平面图G'。 删去度数为1的顶点不影响连通性。而且度数为1的顶点不在回路上，因此不会增加和减少回路数。因此面数不变。

3 (2)若G中没有度数为1的顶点,则删去一个有界面边界上的任一条边,因为删去回路上的一条边不影响连通性，因此得到一个连通平面图G'。

4 对于平面图，嵌如平面的画法可以有多种，但不管怎样，面数总是相等的。必须强调的是：欧拉公式只适用于连通平面图，
即任何一个连通平面图一定满足欧拉公式， 不满足欧拉公式的连通图一定不是平面图。 但是面数确定是比较困难的。

5 推论 6.1：若G是n3的平面简单图, 则e3n-6。 证明:显然只要对连通平面简单图证明即可。
设G 是n3的连通平面简单图,G的每个面由三条或更多条边围成,因此边的总数s大于或等于3f(这里边的总数包括重复计算在内)。 即s3f s= =16 另一方面, 因为每条边至多是两个面的公共边, 也就是说每条边至多被计算两次,即s2e,

6 由此定理我们可以证明K5是非平面图, 因为K5是连通的， n=5,e=10， 若K5是平面图，则由推论应该有e3n-6 即103*5-6=9, 矛盾，所以K5不是平面图。 在这里要注意：对于n3的平面简单图, 一定成立e3n-6。 若e>3n-6,则一定不是平面图。 但对于简单图，即使满足e3n-6，也不一定是平面图。 例如，K3,3，n=6,e=9, 3n-6=3*6-6=12>9=e，成立，但K3,3不是平面图。

7 推论 6.2：若平面图的每个面由四条或更多条边围成, 则e2n-4
证明：因为每个面由四条或更多条边围成，因此边的总数s大于或等于4f，即s4f 证明K3,3不是平面图

8

9 例：小于30条边的连通平面简单图中存在顶点度数不超过4的顶点。
证明：若所有顶点度数都大于4，即G中所有顶点度数都5。

10 二、平面图的特征 找出一个图是平面图的充分必要条件的研究曾经持续了几十年, 直到 1930 年库拉托斯基 (Kuratowski) 给出了平面图的一个非常简洁的特征。

11 首先介绍剖分的概念： 给定图G的一个剖分是对G实行有限次下述过程而得到的图: 删去它的一条边{u,v}后添加一个新的点w以及新的边{w,u}和{w,v}。 也就是说在G的边上插入有限个点便得到 G的一个剖分。 下图中给出了K5的一个剖分。

12

13 定理：(1)若图G的一个子图是Kn的剖分，则G中至少有n个顶点度数大于等于n-1；
(2)若图G的一个子图是Kn,n的剖分，则G中至少有2n个顶点度数大于等于n。 例：G=(V,E)，|V|=7，若G中含有K5的剖分，则 不含有K5或K3,3的剖分. 定理 6.3 (库拉托斯基定理):图G是平面图当且仅当它的任何子图都不是K5或 K3,3的剖分。 上例中G是非平面图，而 是平面图

14 此定理告诉我们： (1)一个图是平面图，则不含有K5的剖分，也不含有K3,3的剖分。 (2)若图G不含有K5的剖分，也不含有K3,3的剖分。则G一定是平面图。 (3)若图G含有K5的剖分，则G一定不是平面图；若图G含有K3,3的剖分，则G一定不是平面图。 (4)若图G不是平面图，则或者G含有K5的剖分，或者G含有K3,3的剖分。

15 库拉托斯基定理虽然很漂亮, 但是在具体判定一个图是不是平面图时,这个定理并不能起作用。因此以后仍有许多这方面的研究工作。

16

17

18 在这里几何对偶常简称为对偶。 由定义可知,若G是连通平面图, 则G*也是连通平面图,而且G和G*的顶点数, 面数和边数有下列简单的关系。 定理 6.4：设G是有n个顶点,e条边,f个面的连通平面图;又设G的几何对偶G*有n*个顶点,e*条边,f*个面,则 n*=f,e*=e,f*=n。

19 由于平面图G的对偶G*也是平面图, 同样可对G*作几何对偶,记为G**。若G是连通的, 则G**与G之间有一个特别简单的关系, 如下所述。

20 6.2顶点着色 定义 6.4:设G是一个没有自环的图, 对G的每个顶点着色, 使得没有两个相邻的顶点着上相同的颜色,这种着色称为图的正常着色。图G的顶点可用k种颜色正常着色, 称G为k-可着色的。使G是k-可着色的数k的最小值称为G的色数, 记为(G)。如果(G)=k,则称G是k色的。 如下图(a)中的图的色数是4, (b)中的图的色数是3。

21

22

23 设G是连通、没有自环的图,如果有多重边,则可删去多重边,用一条边代替, 因此下面考虑连通简单图G。
有几类图的色数是很容易决定的, 即: 定理6.6：(1)G是零图当且仅当(G)=1; (2)对于完全图Kn,有(Kn)=n,而; (3)对于n个顶点构成的回路Cn,当n是偶数时, (Cn)=2;当n 是奇数时, (Cn)=3; (4)G是二分图当且仅当(G)=2。

24 对于n3的n色图的特征至今尚未弄清楚, 但色数的上界则是有结论的。
定理6.7：如果图G的顶点的最大度数为(G),则(G)1+ (G)。 证明：只要证明图G用1+(G)种颜色就可正常着色。 对G的顶点数采用归纳法, 当n=2时,若(G)=0，则G是零图，用一种颜色即可，所以(G)1+(G)成立；若(G)=1，G有一条边(在讨论点着色时，假设图是简单图)，用两种颜色即可，所以(G)1+(G)成立。

25 假设对于n -1个顶点的图, 结论成立。 现设G有n个顶点, 顶点的最大度数是,如果删去任一点v及其关联的边, 得到n-1个顶点的图G',它的最大顶点度数(G') (G)。

26 定理 6.7 的上界是很弱的, 例如G是二分图时, (G)=2，而(G)可以取得相当大。
布鲁克斯(Brooks)在1941年证明了这样的结果, 使 (G)=1+(G)的图只有两类: 或是奇回路, 或是完全图。布鲁克斯定理如下, 证明从略。 定理 6.8：如果连通图G的顶点的最大度数是(G)，G不是奇回路，又不是完全图, 则(G)(G)。

27 6.3平面图的着色 1852 年英国有位青年名叫格思里(Guthrie),他在画地图时发现: 如果相邻两国着上不同的颜色, 那么画任何一张地图只需要四种颜色就够了。 这就是地图的四色问题 一百多年来, 许多数学家的证明都失败了。 1976 年 6 月美国伊利诺斯大学两位教授阿培尔和哈根使用高速电子计算机,花了 1200 多个小时证明了四色问题,终于解决了这个大难题。 仍有许多数学家试图用通常证明方法来论证四色问题, 尚未得到解决。

28 定义 6.5：一个没有桥的连通平面图称为地图 地图可以有自环和多重边。地图中每一边是两个面的公共边,两个面相邻是指这两个面至少有一条公共边(而不是公共点)。 定义 6.6：设G是一个地图, 对G的每个面着色,使得没有两个相邻的面着上相同的颜色, 这种着色称为地图的正常面着色。地图G可用k种颜色正常面着色,称G是k-面可着色的。使G的k-面可着色的数k的最小值称为G的面色数, 记为*(G)。若*(G)=k,则称G是k面色的。

29

30

31 现在地图的四色问题可以叙述为: 任何地图是4-面可着色的。
对于一个没有自环的平面图, 它的对偶是一个没有桥的连通平面图, 即地图。 可以证明一个没有自环的平面图G的顶点着色问题等价于它的对偶图G*的面着色问题。 定理 6.9:：设G是没有自环的平面图, G*是G的对偶,则G是k-可着色当且仅当G*是k-面可着色。

32 作业: P ,2,3,6,7,9,11,12， 求14中的(G) ，*(G)