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

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

定理：(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是非平面图，而 是平面图

此定理告诉我们： (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的剖分。

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

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

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

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

设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。

对于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)成立。

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

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

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

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

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

证明：(1)设G是没有自环的平面图, 则它的对偶G*没有桥，所以是一个地图。 如果G是k-可着色的, 则由于G*的每个面恰含G中一个顶点,把G*每个面着上它所包含的顶点的颜色。 因为G是k-可着色的,G中任何两个相邻的顶点有不同的颜色, 所以G*中任何两个相邻面着上不同的颜色, 因此G*是 k-面可着色的。 (2) G*是k-面可着色的

定理 6.10(五色定理)：任何平面图G是5-可着色的。 证明：不妨设G是平面简单图。下面对G的顶点数采用归纳法证明。 当n5时结论显然成立 假设对n-1个顶点的所有平面简单图G是5-可着色的。 考虑n个顶点的平面简单图G, 由定理 6.2知, G中存在顶点v0,使d(v0)5。 删去v0及其关联边得到G'=G-v0 由归纳假设, G- v0是5-可着色的, 在给定G- v0的一种着色后, 将v0及其关联边加回到原图中, 得到G.

(1)d(v0)<5, (2)d(v0)=5 定理 6.11(二色定理)：地图G是2-面可着色的当且仅当它是一个欧拉图。 证明：(1) G是2-面可着色的，则它是一个欧拉图 (2) G是欧拉图，则G是2-面可着色的

第七章 树 7.1树及其性质 定义 7.1：一个连通无回路的图称为树,记为T。树中度数为1的顶点称为树叶(或称悬挂点)。度数大于1的顶点称为分枝点或内点。不相交的树的全体称为森林。平凡图也可称为平凡树。(平凡图即只有一个点)

图 (a)是一棵树；(b)是森林,也就是无回路的图,它的每个分支是一棵树。

除了定义 7.1 给出树的定义外还有几个树的等价定义, 即下面的定理。 定理7.1：设图T有n个顶点,有下列6条T是树的等价定义: (1)T是无回路的连通图; (2)T是无回路图,且e=n-1,其中e是边数; (3)T是连通图,且e=n-1; (4)T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路(称T为最大无回路图); (5)T是连通图,但删去任一边后,便不连通(称T为最小连通图); (6)T的每一对不同的顶点之间有唯一的一条路。

证明：(1)→(2): T是无回路的连通图要证明T是无回路图,且e=n-1，即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图，显然只能是下图所示： 故结论成立。 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}。

(2)→(3): T是无回路图,且e=n-1,要证明T是连通图,且e=n-1。即证明T是连通图,用反证法,

(3)→(4):在T是连通图,且e=n-1的条件下,证明T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路。 n=2时e=1,且连通, 只能是下图 显然T是无回路的。

假设n=k-1时结论成立,考察n=k时,由于T是连通的,所以,每个顶点度数1(e=k-1)。可以证明,至少存在一个顶点u,使 d(u)=1。Why?

2)再证明如果在连通图T的任两个不相邻顶点之间添加一边,记为{vi,vj},则该边与T中从vi到vj的一条路 (vi,vi1,…, vis,vj) 构成一条回路(vi,vi1,…, vis,vj,vi)。 若这条回路不唯一，由于T无回路，而T∪{vi,vj}得到了回路，因此另一条回路C'也含有边{vi,vj}，

(4)→(5): 在T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路的条件下证明T是连通图,但删去任一边后,便不连通。 若T不连通, 则存在顶点vi和vj,在vi与vj之间没有路。显然,若加一边{vi,vj},不会产生回路,与假设矛盾。 又由于T无回路,则删去任一边,便不连通

(5)→(6): 在T是连通图,但删去任一边后,便不连通的条件下证明T的每一对不同的顶点之间有唯一的一条路。 由于T是连通的,任两点之间有一条路。如果某两个顶点之间多于一条路,则T中必含有回路,(Why?) 删去该回路上任一边,图仍连通,与假设矛盾。 (6)→(1): 在T的每一对不同的顶点之间有唯一的一条路的条件下，证明T是无回路的连通图。显然图是连通的。若有回路, 则回路上任两点之间有两条路, 从而导致矛盾。

推论：若G是n个顶点个分支的森林, 则G有n-条边。 定理7.2:在任一棵非平凡树T中, 至少有两片树叶。 证明:由于T是连通的,对T的任一顶点vi,d(vi)1,并且e=n-1,即所有顶点度数之和=2(n-1). 下面证明T中至少有两个顶点的度数为 1 。

作业: P131 8,9,11,12,14,15,16 P152 1,2,3,4,5,6,7