第7章图论II.ppt

《第7章图论II.ppt》由会员分享，可在线阅读，更多相关《第7章图论II.ppt（108页珍藏版）》请在三一文库上搜索。

1、第八章 几类重要的图,退出,8.1 欧拉图与哈密尔顿图 8.2 二部图 8.3 树 8.4 平面图,8.1 欧拉图与哈密尔顿图,1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”(下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。,在图11.1.1画出了哥尼斯堡城图，城的四块陆地部分以A，B，C，和D标记。欧拉巧妙地把哥尼斯堡城图化为图11.1.2所示图G，他把陆地设为图G中的结点，把桥画成相应地联结陆地即结点

2、的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图G中从某一结点出发找出一条链，它通过每条边恰好一次后回到原出发结点，亦即等价于在图G中寻找一个圈，它通过G中每一条边恰好一次。,图 11.1.1,A,B,D,C,图 11.1.2,欧拉在这篇论文中提出了一条简单准则，确定七桥问题是不能解的。下面就来讨论这个问题。 定义8.1.1 图G中的存在一个回路，若它通过G中的每一条边(或弧)恰好一次，则称该回路为欧拉回路(欧拉环游，Euler tour)，具有这种回路的图称为欧拉图。欧拉回路是一个闭迹。 定理8.1.1 给定连通无向图G，G有欧拉回路G中每个结点都是偶度结点。,Proof . Th

3、e degree condition is clearly necessary: a vertex appearing k times in an Euler tour (or k +1 times, if it is the starting and finishing vertex and as such counted twice) must have degree 2k. Conversely, let G be a connected graph with all degrees even, and let W = v0e0 . . . el-1vl be a longest wal

4、k in G using no edge more than once. Since W cannot be extended, it already contains all the edges at vl. By assumption, the number of such edges is even. Hence vl= v0, so W is a closed walk.,Suppose W is not an Euler tour. Then G has an edge e outside W but incident with a vertex of W, say e = uvi.

5、 Here we use the connectedness of G,then the walk ueviei . . . el-1vl e0 . . . ei-1vi is longer than W, a contradiction. 由定义11.1.1可知，具有欧拉回路的图是欧拉图，故图G为欧拉图G中每个结点都是偶度结点。 由于七桥问题所对应的图中每个结点都是奇度结点，根据上述定理可知，七桥问题无解。,定义8.1.2 图G中的一条通道，若它通过G中的每条边恰好一次，则称该通道为欧拉迹。 定理8.1.2 给定连通无向图G=，u，vV且uv，u与v间存在欧拉迹G中仅有u和v为奇度点。 (补

6、证)。,定理8.1.3 给定弱连通有向图G，G有欧拉回路G中的每个结点的入度等于出度。 定理8.1.4 给定弱连通有向图G=，u，vV且uv，u与v之间存在欧拉迹G中唯有u和v的入度不等于出度，且u的入度比其出度大于1和v的出度比其入度小于1(或者反之)。,这两个定理的证明，可以看作是关于无向图的欧拉回路和欧拉迹的推广。因为对于有向图的任意一个结点来说，如果入度与出度相等，则该结点为偶度结点；如果入度与出度之差为1时，该结点必是奇度结点，所以定理11.1.3和14.1.4与前面两个定理的证明类似。,与欧拉回路和迹非常类似的问题是哈密尔顿圈和哈密尔顿圈路的问题。 1859年，爱尔兰数学家哈密尔顿

7、(W.R.Hamilton)首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市(见图11.1.4(a)，这个正十二面体同构于一个平面图(见图11.1.4(b)，平面图的定义稍后给出)，要求旅游者能否找到沿着正十二面体的棱，从某个顶点(即城市)出发，经过每个顶点(即每座城市)恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。,图 11.1.4,按图11.1.4(c)中所给的编号进行旅游，便是哈密尔顿问题的解。 对于任何连通图也有类似的问题。,图 11.1.4,定义8.1.3 图G中的一个圈，若它通过G中每个结点恰好一次，则该圈称为哈密尔顿圈，具有哈密尔顿圈的图称为

8、哈密尔顿图。 由该定义可知，完全图必是哈密尔顿图。,定义8.1.4 图G中的一条路，若它通过G中的每个结点恰好一次，则该路称为哈密尔顿 路。 哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一。然而，还是有不少重要成果，下面给出几个必要和充分条件的定理。,定理8.1.5 若连通图G=是哈密尔顿图，S是V 的任意真子集，则(G-S)|S|。 (课上补证) 本定理给出是哈密尔顿图的一个必要条件，但这个条件又不便于使用，因为它要求对G的结点集合的所有真子集进行验证。尽管如此，利用它还可以证明某些图不是哈密尔顿

9、图。,不过，利用这个必要条件不总是有效的。例如: 彼得森图：满足必要条件，但是非汉密尔顿的。,下面给出图G是哈密尔顿图的充分条件，这个结果是于1952年Dirac研究得到的。 定理8.1.6 给定简单图G=，|V|=n，若n3和(G)n/2，则G是哈密尔顿图。 请注意，本定理给出的仅是充分条件。例如，十多边形显然是哈密尔顿图，但=2 =5。,Proof . Let G = (V,E) be a graph with |G| = n3 and (G)n/2. Then G is connected: otherwise, the degree of any vertex in the small

10、est component C of G would be less than |C|n/2. Let P = x0 . . . xk be a longest path in G. By the maximality of P, all the neighbours of x0 and all the neighbours of xk lie on P. Hence at least n/2 of the vertices x0, . . . , xk-1are adjacent to xk, and at least n/2 of these same k n vertices xi ar

11、e such that x0xi+1E. By the pigeon hole principle, there is a vertex xi that has both properties, so we have x0xi+1E and xixkE for some i k.,We claim that the cycle C := x0xi+1PxkxiPx0 is a Hamilton cycle of G. Indeed, since G is connected, C would otherwise have a neighbour in G C, which could be c

12、ombined with a spanning path of C into a path longer than P.,x0,xk,xi+1,xi,Bondy和Chvatol于1974年证明了更强的充分条件。他们的方法是建立下面两个引理之上的。 引理8.1.1 给定图G=，|V|=n3。若u，vV，u与v不邻接且d(u)+d(v)n，则G是哈密尔顿图G +uv是哈尔密顿图。,受引理8.1.1启示，可以定义图的闭包概念。 定义8.1.4 给定图G=，|V|=n。图G的闭包是由G通过相继地用边连接两个其度之和至少为n的不邻接结点，直到不能如此进行为止而得到的图。用C(G)表示图G的闭包。 引理8

13、.1.2 C(G)是唯一确定的。,下面定理是引理11.1.1的直接结果： 定理8.1.7 简单无向图G是哈密尔顿图C(G)是哈密尔顿图。 容易看出，至少有三个点的所有完全图都是哈密尔顿图。由此可得到下面推论： 推论 给定简单无向图G=，|V|3。若C(G)是完全图，则图G是哈尔密顿图。,对于有向图的哈密尔顿回路和路也有此类似结果，但其证明却是困难得多，因此这里只叙述由Ghoula-Houri给出的定理如下： 定理8.1.8 给定n阶强连通图G=。若对任意vV，有d+(v)+d-(v)n，则G有哈密尔顿回路。,8.2 二部图,本节简要介绍二部图及二部图中匹配理论的主要概念和成果。 定义8.2.1

14、 给定简单无向图G=，且V=V1V2，V1V2=。若V1和V2的导出子图和都是零图，则称G是二部图或偶图，并将二部图记作G=，并称V1，V2是V的划分。,在一个二部图G=中，若|V1|=m，|V2|=n，且对任意的uV1，vV2均有(u,v)E，则称G为完全二部图，记为Km,n。 定理8.2.1 简单图G为二部图G中不含奇圈。 定理： 若G为n阶二部图，则|E(G)|n2/4。 注：课上补证。,定义8.2.2 给定简单无向图G=，若ME且M中任意两条边都是不邻接的，则子集M称为G的一个匹配或对集(matching)，并把M中的边所关联的两个结点称为在M下是匹配的。 令M是G的一个匹配，若结点v

15、与M中的边关联，则称v是M饱和的；否则，称v是M不饱和的；若G中的每个结点都是M饱和的，则称M是完全匹配(perfect matching)。如果G中没有匹配M1，使|M1|M|，则称M是最大匹配。显然，每个完全匹配是最大匹配，但反之不真。,定义8.2.3 令M是图G=中的一个匹配。若存在一条路，它是由分别由E-M和M中的边交替构成，则称该路是G中的M-交错路(M-alternating path)； 若M-交错路的始结点和终结点都是M-不饱和的，则称该链为M-增广路(M-augmenting path)；特别地，若M-交错路的始结点也是它的终结点而形成圈，则称该圈为M-交错圈。,在匹配理论中

16、，人们特别关心的是最大匹配。Alternating paths play an important role in the practical search for large matchings. Berge在1957年给出了一个图中的一个匹配为最大匹配的充要条件。在证明这一结论时，将要用到两个集合的对称差的概念，现叙述如下：给定两个集合S和T，S与T的对称差，记为ST，其定义为：ST=(ST)-(ST).,引理8.2.1 设M1和M2是图G中的两个匹配，则在中，每个(连通)分支或是交错路，或是交错圈。 定理8.2.2 (Berge，1957)图G的一个匹配M是个最大匹配当且仅当G中不含有M

17、-增广路。 证：Let M be a maximum matching in G. Suppose that G contains an M-augmenting path P. Then M := ME(P) is a matching in G, and |M| = |M| + 1. Thus M is not a maximum matching.,Conversely, suppose that M is not a maximum matching, and let M be a maximum matching in G, so that |M| |M|. Set H := GMM

18、, as illustrated in Figure. Each vertex of H has degree one or two in H, for it can be incident with at most one edge of M and one edge of M . Consequently, each component of H is either an even cycle with edges alternately in M and M , or else a path with edges alternately in M and M . Because | M|

19、 |M|, the subgraph H contains more edges of M than of M, and therefore some path-component P of H must start and end with edges of M. The origin and terminus of P, being covered by M, are not covered by M. The path P is thus an M-augmenting path in G.,在许多应用中，希望在二部图G=中找出一个匹配M，使得V1中每个结点都是M饱和的。1935年，Ha

20、ll首先给出存在这样匹配的充分必要条件的定理。 定理8.2.3 (Hall 1935) 给定二部图G=，G中存在使V1中每个结点饱和的匹配对任意SV1有 |N(S)|S| (2) 其中N(S)表示与S中结点邻接的所有结点集合。 证：We apply induction on |A|. For |A| = 1 the assertion is true. Now let |A|2, and assume that the marriage condition is sufficient for the existence of a matching of A when |A| is smalle

21、r.,If |N(S)|S|+1 for every non-empty set S A, we pick an edge ab G and consider the graph G* := Ga, b . Then every non-empty set S Aa satisfies|NG* (S)|NG(S)|1 |S| , so by the induction hypothesis G* contains a matching of Aa. Together with the edge ab, this yields a matching of A in G. Suppose now

22、that A has a non-empty proper subset A* with |B*| = |A*| for B* := N(A*). By the induction hypothesis, G* := GA*B* contains a matching of A*. But GG* satisfies the marriage condition too: for any set S AA* with |NGG* (S)| |S| we would have |NG(SA*)| |SA*|, contrary to our assumption. Again by induct

23、ion, GG* contains a matching of AA*. Putting the two matchings together, we obtain a matching of A in G.,推论 若G=是二部图，且对于任意vV1或V2有d(v)=k0，则G有一个完全匹配。 证: If G is k-regular, then clearly |A| = |B|; it thus suffices to show by Theorem 11.2.3 that G contains a matching of A. Now every set S A is joined to

24、N(S) by a total of k |S| edges, and these are among the k |N(S)| edges of G incident with N(S). Therefore k |S|k|N(S)|, so G does indeed satisfy the marriage condition.,在定理8.2.3的证明中，它提供了在二部图G=中寻找一个匹配M，使V1中每个结点是M一饱和的。下面给出的称为Hungarian方法的算法。令M是G=中任意一个匹配，该算法是：,(1) 若V1中每个结点是M饱和的，停止。否则，令v是V1中M不饱和结点，作 S=v和

25、T= (2) 若N(S)=T，因为|T|=|S|-1，则|N(S)|S|，由Hall定理知，不存在使V1中每个结点都是饱和的匹配，停止，否则，令yN(S)-T。 (3) 若y是M饱和的，令y，zM，作 SSz和TTy 并转到(2)；否则，令CM是以v为始结点和y为终结点的M增广路，作MME(CM)并转到(1)。其中E(CM)表示CM中所有边的集合。,8.3 树,定义8.3.1 一个无圈的连通图，称为树(tree)。 显然，由定义可知，树是个简单图，即它无环和无平行边。 在树中，度为1的点称为叶子(leave)或悬挂点；度数大于的点称为内点或分枝点；而与叶或悬挂点所关联的边，称为叶边或悬挂边。

26、若图中的每个连通分支是树，则称该图为森林(forest)。,定理8.3.1 树T中任两个点间恰有一条路。 定理8.3.2 若图G中每对点间有且仅有一条路，则G为树。 定理8.3.3 具有n个点的树中有n-1条边，即树T=中，|E|=|V|-1。(Induction) (课上补证)。,注意，具有n个点和恰有n-1条边的图未必是树，但有下面两个定理： 定理8.3.4 给定连通图G=，若|E|=|V|-1，则G是树。(induced tree) 定理8.3.5 给定图G=，|E|=|V|-1且G中无圈，则G是树。(By contradiction),连通、无圈完全刻划了树，这是树的一个特性；树还有另

27、外一个重要性质是：它以最少的边使得顶点可达或连通。这便导出下面的最小连通的概念。 定义8.3.2 给定连通图G=，若对任意eE，均使G-e不连通，则称连通图G是最小连通的。,显然，最小连通图不可能有圈。因为删去圈中的一条边后仍使图连通。于是，最小连通图是树。反之， 如果一个连通图G不是最小连通的，则必存在G中一条边ei，使G-ei连通。所以ei位于一圈中，这意味着G不是树。故可得到下面定理：,定理8.3.6 图G是树G是最小连通的。 上面的六个定理可以总结为下面五个不同的但却是等价的树的定义。给定图G=，G是树的等价定义是： G是连通且无圈 G是连通且|E|=|V|-1 G是无圈且|E|=|V

28、|-1 G中每对顶点间恰有一条路 G是最小连通图,定理8.3.7 给定树T=，若|V|2，则T中至少存在两个悬挂点。(the longest path) 对于一些图，它本身未必是树，但它的子图是树。一个图可能有多个子图是树，其中很重要的一类树是生成树。,定义8.3.3 给定图G=。若G的生成子图T是树，则称T是G的生成树。T中的边称为枝，是G中的边但不为T中的边称为弦。 定理8.3.8 图G=有生成树T=G是连通的。,假设图G=是连通图，G的一个生成树是T=，则|ET|=|V|-1。因此，要确立G的一棵生成树必须从G中删去|E|-(|V|-1)条边。称数(|E|-|V|+1)为图G的圈秩，它表

29、现打破全部圈所必须从G中删去的最小边数，即由G产生的生成树应删去弦的数目。例如，对于图11.3.3所示的图，其圈秩是3。,定理8.3.9 若T是图G的一棵生成树，e=uv是弦，则存在唯一的由e和T中某些边构成的圈C。若f是C上与e不同的边且由f替换e而得到图T1，则T1也是G的一棵生成树。 定理8.3.10 设T1和T2是图G的两棵生成树。若f是T1的边但不为T2的边。则存在一条是T2但不为T1的边e，使得用e代替T1中的一条边而得到图G的一棵生成树T3。,下面讨论利用生成树为讨论加权图的最小连接问题。 设G=是加权的连通图，对任意边e，其权w(e)0。令T=是G的一加权生成树，其所有枝上的权

30、的总和 ，称为树T的权，记为w(T)。一般说来，对于G的不同生成树T，w(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，有如下定义。,定义8.3.4 给定连通加权图G=，T0=是G的加权生成树，w(T0)为T0的权。若对G的任意加权生成树T均有w(T0)w(T)，则称T0是G的最小生成树。 下面给出一种求最小生成树的方法Kruskal算法(1956)，它的本质是树生成过程，因此得名避圈法。,定理8.3.11 设G是有n个结点的连通图，下面算法产生的是最小生成树。 (1) 选取具有尽可能小的权的边e1；假定in-1和已选取边为e1，e2，ei。 (2) 在G中选取

31、不同于e1，e2，ei的边ei+1，使e1，e2，ei，ei+1的导出子图无圈且ei+1是满足此条件的权尽可能小的边。重复作下去直至选出边e1，e2，en-1为止。,定义8.3.5 给定加权连通图G=，对任意eE均有w(e)0，及u，vV。连接u和v的路C0：u=x1，x2，xk=v，其路长记为l(v)或l(C0)，等于 ，如果对G中连接u与v的任何路C均有l(C0)l(C)，则称C0是G中连接u和v的最短路。,现在给出一种求从已知结点到另外一个结点的最短路的方法G.Dantzig算法，其本质也是一种树生长过程。 定理8.3.12 设有n个结点的加权连通图G=，x0V。依下面算法得到G的一棵生

32、成树T，使得在T中连接x0与xx0的每一条路是G中连接x0与x的最短路。,令 X0=x0和l(x0)=0，执行以下步骤： 选取x1，连接x0与x1使w(x0x1)尽可能地小。令l(x1)=w(x0x1)，X1=x0，x1和E1=x0x1。,(2) 假设已确定点集Xk=x0，x1，xk和边集Ek。对于xiXk，选取yiXk，使得xiyiE且w(xiyi)尽可能地小(若选不取yi，则略过xi)。选取xpXk，使得对于i=0，1，k有l(xp)+w(xpyp)l(xi)+w(xiyi)，令xk+1=yp和l(xk+1)=l(xp)+w(xpyp)，再令Xk+1=x0，x1，xk，xk+1和Ek+1=

33、Ekxpxk+1。 (3) 重复(2)，直到Xn-1=x0，x1，xn-1和En-1为止。,前面讨论的树，都是无向图中的树，即无向树；下面将简单地介绍有向图中的树即有向树。 定义8.3.6 如果一个有向图的基础图是一棵树，则该有向图称为有向树。其图形表示法常采用倒置树表示之，且为方便计，有时略去边之方向。,定义8.3.7 给定一个有向树，若只有一个结点的入度是零，其余结点的入度都是1，则称该树为根树。 在根树中，入度为零的点称为根或根点，出度为零的点称为叶子；出度不为零的点称为分枝点或内点。,定义8.3.8 在有根树中，从根到某个点的路长即该路中的弧数，称为该点的级。其中点的级的最大者，称为根

34、树的树高。 由于有向树中没有回路，因此从树中任何点到另外一个点的路长即是两点的距离。故根树的根的级是零；任何点的级，等于从根到该点的距离。 在有向树中，点的出现次序是没有意义的。但实际应用中，有时要给出同一级中点的相对次序，这便导出有序树的概念。,定义8.3.9 在一棵根树中，在每一级的结点都指定某种次序，称树为有序树。例如，图11.3.11与图11.3.10表示两棵不同的有序树。,图 11.3.10,图 11.3.11,为表示点间的关系，有时借用家族中的术语。令u是根树中的分枝点，若从u到v有一条弧或说u与v是邻接的，则点v称为点u的“儿子”，或称u是v的“父亲”；若从u到w有一条路，称u是

35、w的“祖先”，或称w是u的“子孙”，同一个分枝点的儿子称为“兄弟”。 在前面讨论的根树或有序树中，其点的出度未加任何限制。现在将依据结点出度的不同情况进行讨论。,定义8.3.10 在根树中，若每一个结点的出度都小于或等于m，则称该树为m叉树。若每一个结点的出度恰好等于m或等于0，则称这种树为完全m叉树。若所有的叶子的级相同，则称正则m叉树。,定义8.3.11 在m叉树中，如果对任何结点的m个(或少于m个)儿子都分别指定好m个不同的确定位置，则称该树为位置叉树。 当m=2时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点v，至多有两个子树，分别称为v的左子树和右子树。

36、若v只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，v的左子树画在v的左下方，v的右子树画在v的右下方。,在位置二叉树中，每个结点可用字符表0，1上的字符串唯一地表示。串中的字符个数称为串的长度。结点v的任何一个儿子所对应的串的前缀是v所对应的串；任何一个叶结点的串不能放置在其它结点的串的前面，这树是位置二叉树的0-1串表示或称哈夫曼编码。对应于叶子的串的集合形成一个前缀码或哈夫曼编码。例如，000，001，01，10，110，111是前缀码，因为它正是图11.3.12(b)中树的叶结点0-1串表示的集合。不难看出，利用字符表0，1，2，m-1上的字符串，可表示位置m叉树的各个

37、结点。,如前所叙，在任何位置二叉树的0-1串表示中，其叶子的串集合是个前缀码，即哈夫曼编码树对应着一个哈夫曼编码。不仅如此，还可以构造性证明其逆命题： 定理8.3.13 任何一个前缀码都对应一棵位置二叉树的0-1串表示，即哈夫曼编码对应一棵哈夫曼编码树。,有很多实际应用，可用二叉树或m叉树表示。可以指出，按下面算法，任何一棵有序树均能表成二叉树。其算法是： (1) 除最左边的分枝点外，删去所有从每一个结点长出的分枝。在同一级中，兄弟结点之间用从左到右的弧连接。,(2) 选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。 上述算法能够推广

38、到有序森林上去。 二叉树的一个重要应用就是最优树问题。 给定一组数w1，w2，wn。令一棵二叉树有n个叶子，并对它们分别指派w1，w2，wn作为权，则该二叉树称为加权二叉树。,定义8.3.12 在权分别为w1，w2，wn的加权二叉树T中，若权是wi的叶结点，其级为L(wi)，则 称为加权二叉树T的权，并记为w(T)。 已知w1，w2，wn为权，T0为加权二叉树，其权为w(T0)，如果对任意加权二叉树T，它的权是w(T)，均有w(T0)w(T)，则称T0是最优树或Huffman树。,定理8.3.14 设T为加权w1，w2，wn且w1w2wn的最优树，则 (1) 加权w1和w2的叶子vw1和vw2

39、是兄弟。 (2) 以叶子vw1和vw2为儿子的分枝点，它是所有分枝点的级最高者。,定理8.3.15 设T为加权w1，w2，wn且w1w2wn的最优树，若将以加权w1和w2的叶子为儿子的分枝点改为加权w1+w2的叶子而得到一棵新树T1，则T1是最优树。,根据上述两个定理，求一棵有n个权的最优树，可简化为求一棵有n-1个权的最优树，而这又可简化为求一棵有n-2个权的最优树，依此类推。具体作法是： 首先找出两个最小的权值，设w1和w2。然后对n-1个权w1+w2，w3，wn求作一棵最优树，并且将这棵树中的结w1+w2代之以w1 w2，依此类推。,8.4 平面图,在一些实际问题中，要涉及到图的平面性的

40、研究，比如大家都知道的印刷线路板的布线问题。近些年来，大规模集成电路的发展，进一步促进了图的平面性的研究。本节将简要地介绍平面图的概念，欧拉公式和平面图的着色。 定义8.4.1 一个无向图G=，如果能把它画在平面上，且除V中的结点外，任意两条边均不相交，则称该图G为平面图。,下面给出一种判别平面图的直观方法。 根据平面的定义，无圈的图显然是平面图。故，研究图的平面性问题，只需要限制有圈的一类图即可。判别方法是： (1) 对于有圈的图找出一个长度尽可能大的且边不相交的圈。 (2) 将图中那些相交于非结点的边，适当放置在已选定的圈内侧或外侧，若能避免除结点之外边的相交，则该图是平面图；否则，便是非

41、平面图。,在图论中，称K3,3和K5是库拉图斯基图。这是因为波兰数学家库拉图斯基(K.Kuratowski)于1930年给出了的判别平面图充要条件(后称库拉图斯基定理)曾用到这两个图。下面就来介绍这一定理，不过它要用到两个图同胚的概念。可以看出，在给定图G的任何一条边上插入一个度为2的结点，使一条边成为两条边，或者收缩G中与度为2的结点关联的两条边，使两条边成为一条边，这些都不会影响图的平面性。,定义8.4.2 若图G2可由图G1中的一些边上适当插入一些度为2的点或收缩与度为2的点关联的边为一条边，则称G1与G2同胚。 显然，任何两个圈是同胚的。,定理8.4.1 (库拉图斯基定理)一个图G是平

42、面图G中不含同胚于K3,3或K5的子图。 该定理的证明是看来不算很难但是冗长的，略去了，有兴趣读者可参见图论专著中的证明。 库拉图斯基定理表述还是简明的，例如，图11.4.4(a)所示的图称为彼得森图，它是非平面图。因为当删去边v6,v8和v3,v4时，它成为含有同胚于K3,3的子图，如图11.4.4(b)或(c)所示。,图 11.4.5,下面介绍平面图中的重要的欧拉公式。 定义8.4.3 设G为一平面图，若由G的一条或多条边所界定的区域内部不含图G的结点和边，这样的区域称为G的一个面，记为f。包围这个区域的各条边所构成的圈，称为该面f的边界，其圈的长度，称为该面f的度，记为d(f)。为强调平

43、面图G中含有面这个元素，今后把平面图表为G=，其中F是G中所有面的集合。,为方便有时把平面图G的外部的无限区域当作一个面，称为无限面或外部面，其余的面称为有限面或内部面。 由定义不难证明下面定理： 定理8.4.2 令G=是连通平面图，则 。,定理8.4.3 设G=是连通平面图，则|V|-|E|+|F|=2。(by induction, 从|F|=1 begin) 这便是著名的欧拉公式。 推论1 给定连通简单平面图G=。若|V|3，则|E|3|V|-6。(补证，除|E|=2外，每个面度至少是3)。 推论2 设G=是一个连通简单平面图，若|V|3，则存在vV，使得d(v)5。,推论3 给定连通简单

44、平面图G=。若对于每个面fF，有d(f)4，则 |E|2|V|-4 推论4 完全图K5是非平面图。(用推论1) 推论5 完全二部图K3,3是非平面图。(用推论3),下面讨论平面图的着色问题。 平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1840年，德国数学家麦比乌斯(A.F.Mbius)在他的讲稿中第一次提出了确信用四种颜色可以对地图着色的问题(以下简称四色猜想)。1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够

45、了，但却可以证明用五种颜色是够的，即五色定理成立。,在这里，研究的方法并不直接去考察地图着色问题，而是把它转化成平面图。为此，先给出对偶图的概念。 定义8.4.4 给定平面图G=，且f1，f2，fnF。若有图G*=满足下列条件：,(1) 对于任意fiF内部有且仅有一个结点v*iV*； (2) 对于G中面fi和面fj的公共边ek有且仅有一条边e*kE*，使得ek*= v*i v*j且e*k与ek相交； (3) 当且仅当ek只是一个面fi的边界时，v*i存在一个环ek*且e*k与ek相交，则称图G*是图G的对偶图。,从对偶图的定义可以看出，若G*=是平面图G=的对偶图，则G也G*的对偶图。一个连通

46、平面图G的对偶图G*，也是平面图，而且有 |E(G*)|=|E(G)| |V(G*)|=|F(G)| dG*(v*)=dG(fi) fiF，v* V *,其中E(G)表示图G的所有边集合，F(G)表示图G的所有面的集合。于是，可得到下面定理： 定理8.4.4 若G=是平面图，则 。,定义8.4.5 若图G的对偶图G*同构于G，则称G是自对偶图。 定理8.4.5 若平面图G=是自对偶图，则|E|=2(|V|-1)。 证：因|F|=|V*|=|V|，|V|-|E|+|F|=2，所以|V|-|E|+|V|=2.,从对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的结点的着色问题

47、。 因此，四色问题可以归结为要证明：对任意平面图一定可以用四种颜色，对其结点进行着色，使得相邻结点都有不同颜色。,平面图G=的着色是从结点集V到色集C=c1，c2，cn上一个映射，使对任意边vivjE均有(vi)(vj)，即对G的每个结点指派一种颜色，使得相邻结点都有不同的颜色。 对于平面图G着色时，需要的最少颜色数称为G的着色数，记为(G)。 定理8.4.6 (五色定理)对于任何简单平面图G=，均有(G)5。,Proof . Let G be a plane graph with n6 vertices and m edges. We assume inductively that ever

48、y plane graph with fewer than n vertices can be 5-coloured. By Corollary 4.2.10, d(G) = 2m/n2 (3n6)/n 6 ; let vG be a vertex of degree at most 5. By the induction hypothesis, the graph H := Gv has a vertex colouring c: V (H) 1, . . . , 5 . If c uses at most 4 colours for the neighbours of v, we can extend it to a 5-colouring of G. Let us assume, therefore, that v has exactly 5 neighbours, and that these have distinct colours.,Let D be an open disc