第十一章 几类重要的图 11.1 欧拉图与哈密尔顿图 11.2 二部图 11.3 树 11.4 平面图 退出.

Presentation on theme: "第十一章 几类重要的图 11.1 欧拉图与哈密尔顿图 11.2 二部图 11.3 树 11.4 平面图 退出."— Presentation transcript:

1 第十一章 几类重要的图 11.1 欧拉图与哈密尔顿图 11.2 二部图 11.3 树 11.4 平面图 退出

2 11.1 欧拉图与哈密尔顿图 1736年瑞士数学家欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”(下称七桥问题)。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。

3 在图11. 1. 1画出了哥尼斯堡城图，城的四块陆地部分以A，B，C，和D标记。欧拉巧妙地把哥尼斯堡城图化为图11. 1
在图11.1.1画出了哥尼斯堡城图，城的四块陆地部分以A，B，C，和D标记。欧拉巧妙地把哥尼斯堡城图化为图11.1.2所示图G，他把陆地设为图G中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图G中从某一结点出发找出一条链，它通过每条边恰好一次后回到原出发结点，亦即等价于在图G中寻找一个圈，它通过G中每一条边恰好一次。

4 图

5 图

6 欧拉在这篇论文中提出了一条简单准则，确定七桥问题是不能解的。下面就来讨论这个问题。
定义 图G中的一圈(或回路)，若它通G中的每一条边(或弧)恰好一次，则称该圈(或回路)为欧拉圈(或回路)，具有这种圈(或回路)的图称为欧拉无向(或有向)图。 定理 给定连通无向图G，G有欧拉圈G中每个结点都是偶度结点。

7 由定义11.1.1可知，具有欧拉圈的图是欧拉图，故图G为欧拉图G中每个结点都是偶度结点。
由于七桥问题所对应的图中每个结点都是奇度结点，根据上述定理可知，七桥问题无解。

8 定义11.1.2 图G中的一条链(或路)，若它通过G中的每条边(或弧)恰好一次，则称该链(或路)为欧拉链(或路)。
定理 给定连通无向图G=<V，E>，u，v∈V且u≠v，u与v间存在欧拉链G中仅有u和v为奇度结点。

9 定理11.1.3 给定弱连通有向图G，G有欧拉回路G中的每个结点的入度等于出度。
定理 给定弱连通有向图G=<V，E>，u，v∈V且u≠v，u与v存在欧拉路G中唯有u和v的入度不等于出度，且u的入度比其出度大于1和v的出度比其入度小于1(或者反之)。

10 这两个定理的证明，可以看作是关于无向图的欧拉圈和欧拉链的推广。因为对于有向图的任意一个结点来说，如果入度与出度相等，则该结点为偶度结点；如果入度与出度之差为1时，该结点必是奇度结点，所以定理11.1.3和14.1.4与前面两个定理的证明类似。

11 与欧拉圈和链(或回路和路)非常类似的问题是哈密尔顿圈和链(或回路和路)的问题。1859年，爱尔兰数学家哈密尔顿(W. R
与欧拉圈和链(或回路和路)非常类似的问题是哈密尔顿圈和链(或回路和路)的问题。1859年，爱尔兰数学家哈密尔顿(W.R.Hamilton)首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市(见图11.1.4(a))，这个正十二面体同构于一个平面图(见图11.1.4(b)，平面图的定义稍后给出)，要求旅游者能否找到沿着正十二面体的棱，从某个顶点(即城市)出发，经过每个顶点(即每座城市)恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。

12 图

13 按图11.1.4(c)中所给的编号进行旅游，便是哈密尔顿问题的解。
对于任何连通图也有类似的问题。

14 图

15 定义11.1.3 图G中的一圈(或回路)，若它通过G中每个结点恰好一次，则该圈(或回路)称为哈密尔顿圈(或回路)，具有哈密尔顿圈(或回路)的图称为哈密尔顿无向(或有向)图。
由该定义可知，完全图必是哈密尔顿图。

16 定义11.1.4 图G中的一链(或路)，若它通过G中的每个结点恰好一次，则该链(或路)称为哈密尔顿链(或路)。
哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一。然而，还是有不少重要成果，下面给出几个必要和充分条件的定理。

17 定理11.1.5 若连通图G=<V，E>是哈密尔顿图，S是V的任意真子集，则ω(G-S)≤|S|。

18 下面给出图G是哈密尔顿图的充分条件，这个结果是于1952年G.A.Dirac研究得到的。
定理 给定简单图G=<V，E>，|V|=n，若n≥3和δ≥n/2，则G是哈密尔顿图。 请注意，本定理给出的仅是充分条件。例如，十多边形显然是哈密尔顿图，但δ=2≥ =5。

19 Bondy和Chvatol于1969年证明了更强的充分条件。他们的方法是建立下面两个引理之上的。
引理 给定图G=<V，E>，|V|=n≥3。若u，v∈V，u与v不邻接且d(u)+d(v)≥n，则G是哈密尔顿图G+〔u，v〕是哈尔密顿图。 受引理11.1.1启示，可以定义图的闭包概念。

20 定义11.1.4 给定图G=<V，E>，|V|=n。图G的闭包是由G通过相继地用边连接两个其度之和至少为n的不邻接结点，直到不能如此进行为止而得到的图。用C(G)表示图G的闭包。

21 下面定理是引理11.1.1的直接结果： 定理 简单无向图G是哈密尔顿图C(G)是哈密尔顿图。 容易看出，至少有三个结点的所有完全图都是哈密尔顿图。由此可得到下面推论： 推论 给定简单无向图G=<V，E>，|V|≥3。若C(G)是完全图，则图G是哈尔密顿图。

22 对于有向图的哈密尔顿回路和路也有此类似结果，但其证明却是困难得多，因此这里只叙述由Ghoula-Houri给出的定理如下：
定理 给定n阶强连通图G=<V，E>。若对任意v∈V，有d+(v)+d-(v) ≥n，则G有哈密尔顿回路。

23 11.2 二部图 本节简要介绍二部图及二部图中匹配理论的主要概念和成果。
11.2 二部图 本节简要介绍二部图及二部图中匹配理论的主要概念和成果。 定义 给定简单无向图G=<V，E>，且V=V1∪V2，V1∩V2=。若V1和V2的诱导子图<V1>和<V2>都是零图，则称G是二部图或偶图，并将二部图记作G=<V1，E，V2>，并称V1，V2是V的划分。

24 在一个二部图G=<V1，E，V2>中，若|V1|=m，|V2|=n，且对任意的u∈V1，v∈V2均有u，v〕∈E，则称G为完全二部图，记为Km，n。
定理 简单图G为二部图G中所有基本圈的长度为偶数。

25 定义11.2.2 给定简单无向图G=<V，E>，若ME且M中任意两条边都是不邻接的，则子集M称为G的一个匹配或对集，并把M中的边所关联的两个结点称为在M下是匹配的。
令M是G的一个匹配，若结点v与M中的边关联，则称v是M—饱和的；否则，称v是M—不饱和的；若G中的每个结点都是M—饱和的，则称M是完全匹配。如果G中没有匹配M1，使|M1|＞|M|，则称M是最大匹配。显然，每个完全匹配是最大匹配，但反之不真。

26 定义 令M是图G=<V，E>中的一个匹配。若存在一个链，它是由分别由E-M和M中的边交替构成，则称该链是G中的M—交错链；若M—交错链的始结点和终结点都是M—不饱和的，则称该链为M—增广链；特别地，若M—交错链的始结点也是它的终结点而形成圈，则称该圈为M—交错圈。

27 在匹配理论中，人们特别关心的是最大匹配。Berge在1957年给出了一个图中的一个匹配为最大匹配的充要条件。在证明这一结论时，将要用到两个集合的对称差的概念，现叙述如下：
给定两个集合S和T，S与T的对称差，记为SΔT，其定义为： ST=(S∪T)-(S∩T)

28 引理11.2.1 设M1和M2是图G中的两个匹配，则在<M1M2>中，每个分图或是交错链，或是交错圈。
定理 (Berge，1957)图G的一个匹配M是个最大匹配G中不含有M—增广链。

29 在许多应用中，希望在二部图G=<V1，E，V2>中找出一个匹配M，使得V1中每个结点都是M—饱和的。1935年，Hall首先给出存在这样匹配的充分必要条件的定理。
定理 给定二部图G=<V1，E，V2>，G中存在使V1中每个结点饱和的匹配对任意SV1有 |N(S)|≥|S| (2) 其中N(S)表示与S中结点邻接的所有结点集合。

30 推论 若G=<V1，E，V2>是二部图，且对于任意v∈V1或V2有d(v)=k＞0，则G有一个完全匹配。
在定理11.2.3的证明中，它提供了在二部图G=<V1，E，V2>中寻找一个匹配M，使V1中每个结点是M一饱和的。下面给出的称为Hungarian方法的算法。令M是G=<V1，E，V2>中任意一个匹配，该算法是：

31 (1) 若V1中每个结点是M—饱和的，停止。否则，令v是V1中M—不饱和结点，作
S={v}和T= (2) 若N(S)=T，因为|T|=|S|-1，则|N(S)|＜|S|，由Hall定理知，不存在使V1中每个结点都是饱和的匹配，停止，否则，令y∈N(S)-T。 (3) 若y是M—饱和的，令〔y，z〕∈M，作 S←S∪{z}和T←T∪{y} 并转到(2)；否则，令CM是以v为始结点和y为终结点的M—增广链，作M←MΔE(CM)并转到(1)。其中E(CM)表示CM中所有边的集合。

32 11.3 树 定义11.3.1 一个无圈的连通图，称为树。 显然，由定义可知，树是个简单图，即它无环和无平行边。
11.3 树 定义 一个无圈的连通图，称为树。 显然，由定义可知，树是个简单图，即它无环和无平行边。 在树中，度为1的结点称为叶或悬挂结点；度数大于的结点称为内结点或分枝结点；而与叶或悬挂结点所关联的边，称为叶边或悬挂边。 若图中的每个连通分图是树，则称该图为森林。

33 定理 树T中任两个结点间恰有一条链。 定理 若图G中每对结点间有且仅有一条链，则G为树。 定理 具有n个结点的树中有n-1条边，即树T=<V，E>中，|E|=|V|-1。

34 注意，具有n个结点和恰有n-1条边的图未必是树，但有下面两个定理：
定理 给定连通图G=<V，E>，若|E|=|V|-1，则G是树。 定理 给定图G=<V，E>，|E|=|V|-1且G中无圈，则G是树。

35 连通无圈完全刻划了树，这是树的一个特性；树还有另外一个重要性质是：它以最少的边使结点可达或连通。这便导出下面的最小连通的概念。
定义 给定连通图G=<V，E>，若对任意e∈E，均使G-e不连通，则称连通图G是最小连通的。

36 显然，最小连通图不可能有圈。因为删去圈中的一条边后仍使图连通。于是，最小连通图是树。反之， 如果一个连通图G不是最小连通的，则必存在G中一条边ei，使G-ei连通。所以ei位于一圈中，这意味着G不是树。故可得到下面定理：

37 定理 图G是树G是最小连通的。 上面的六个定理可以总结为下面五个不同的但却是等价的树的定义。给定图G=<V，E>，G是树的等价定义是： ① G是连通且无圈 ② G是连通且|E|=|V|-1 ③ G是无圈且|E|=|V|-1 ④ G中每对结点间恰有一条链 ⑤ G是最小连通图

38 定理11.3.7 给定树T=<V，E>，若|V|≥2，则T中至少存在两个悬挂结点。
对于一些图，它本身未必是树，但它的子图是树。一个图可能有多个子图是树，其中很重要的一类树是生成树。

39 定义11.3.3 给定图G=<V，E>。若G的生成子图T是树，则称T是G的生成树。T中的边称为枝，是G中的边但不为T中的边称为弦。
定理 图G=<V，E>有生成树T=<VT，ET>G是连通的。

40 假设图G=<V，E>是连通图，G的一个生成树是T=<V，ET>，则|ET|=|V|-1。因此，要确立G的一棵生成树必须从G中删去|E|-(|V|-1)条边。称数(|E|-|V|+1)为图G的基本圈的秩，它表现打破全部基本圈所必须从G中删去的最小边数，即由G产生的生成树应删去弦的数目。例如，对于图11.3.3所示的图，其圈秩是3。

41 定理11.3.9 若T是图G的一棵生成树，e=[u，v]是弦，则存在唯一的由e和T中某些边构成的基本圈C。若f是C上与e不同的边且由f替换e而得到图T1，则T1也是G的一棵生成树。
定理 设T1和T2是图G的两棵生成树。若f是T1的边但不为T2的边。则存在一条是T2但不为T1的边e，使得用e代替T1中的一条边而得到图G的一棵生成树T3。

42 下面讨论利用生成树为讨论加权图的最小连接问题。
设G=<V，E，W>是加权的连通图，对任意边e，其权w(e)≥0。令T=<VT,ET,WT>是G的一查枷权生成树，其所有枝上的权的总和 (e)，称为树T的权，记为w(T)。一般说来，对于G的不同生成树T，w(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，有如下定义。

43 定义 给定连通加权图G=<V，E，W>，T0=<V，ET0，WT0>是G的加权生成树，w(T0)为T0的权。若对G的任意加权生成树T均有w(T0)≤w(T)，则称T0是G的最小生成树。 下面给出一种求最小生成树的方法——Kruskal算法(1956)，它的本质是树生成过程，因此得名避圈法。

44 定理11.3.11 设G是有n个结点的连通图，下面算法产生的是最小生成树。
(1) 选取具有尽可能小的权的边e1；假定i＜n-1和已选取边为e1，e2，…，ei。 (2) 在G中选取不同于e1，e2，…，ei的边ei+1，使{e1，e2，…，ei，ei+1}的诱导子图无圈且ei+1是满足此条件的权尽可能小的边。重复作下去直至选出边e1，e2，…，en-1为止。

45 定义 给定加权连通图G=<V，E，W>，对任意e∈E均有w(e)≥0，及u，v∈V。连接u和v的链C0：u=x1，x2，…，xk=v，其链长记为l(v)或l(C0)，等于 ，如果对G中连接u与v的任何链C均有l(C0)≤l(C)，则称C0是G中连接u和v的最短链。

46 现在给出一种求从已知结点到另外一个结点的最短链的方法—G.Dantzig算法，其本质也是一种树生长过程。
定理 设有n个结点的加权连通图G=<V，E，W>，x0∈V。依下面算法得到G的一棵生成树T，使得在T中连接x0与x≠x0的每一条基本链是G中连接x0与x的最短链。

47 令 X0={x0}和l(x0)=0，执行以下步骤：
(1) 选取x1，连接x0与x1使w([x0，x1])尽可能地小。令l(x1)=w([x0，x1])，X1={x0，x1}和E1={[x0，x1]}。

48 (2) 假设已确定结点集Xk={x0，x1，…，xk}和边集Ek，k1。对于xi∈Xk选取yiXk，使得[xi，yi]∈E且w([xi，yi])尽可能地小(若选不取yi，则略过xi)。选取xp∈Xk，使得对于i=0，1，…，k有l(xp)+w([xp，yp])≤l(xi)+w([xi，yi])，令xk+1=yp和l(xk+1)=l(xp)+w([xp，yp])，再令Xk+1={x0，x1，…，xk，xk+1}和Ek+1=Ek∪{[xp，xk+1]}。 (3) 重复(2)，直到Xn-1={x0，x1，…，xn-1}和En-1为止。

49 前面讨论的树，都是无向图中的树，即无向树；下面将简单地介绍有向图中的树即有向树。
定义 如果一个有向图的基础图是一棵树，则该有向图称为有向树。其图形表示法常采用倒置树表示之，且为方便计，有时略去边之方向。

50 定义11.3.7 给定一个有向树，若只有一个结点的入度是零，其余结点的入度都是1，则称该树为有根树。
在有根树中，入度为零的结点称为根或根结点，出度为零的结点称为叶或叶结点；出度不为零的结点称为分枝结点或内结点。

51 定义11.3.8 在有根树中，从根到某个结点的路长即该路中的弧数，称为该结点的级。其中结点的级的最大者，称为有根树的树高。
由于有向树中没有回路，因此所有的路都是基本路。可见，从树中任何结点到另外一个结点的路长即是两结点的距离。故有根树的根结点的级是零；任何结点的级，等于从根到该结点的距离。 在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。

52 定义11.3.9 在一棵有根树中，在每一级的结点都指定某种次序，称树为有序树。例如，图11.3.11与图11.3.10表示两棵不同的有序树。

53 图

54 图

55 为表示结点间的关系，有时借用家族中的术语。令u是有根树中的分枝结点，若从u到v有一条弧或说u与v是邻接的，则结点v称为结点u的“儿子”，或称u是v的“父亲”；若从u到w有一条路，称u是w的“祖先”，或称w是u的“子孙”，同一个分枝结点的儿子称为“兄弟”。 在前面讨论的有根树或有序树中，其结点的出度未加任何限制。现在将依据结点出度的不同情况进行讨论。

56 定义11.3.10 在有根树中，若每一个结点的出度都小于或等于m，则称该树为m叉树。若每一个结点的出度恰好等于m或等于0，则称这种树为完全m叉树。若所有的叶结点的级相同，则称正则m叉树。

57 定义11.3.11 在m叉树中，如果对任何结点的m个(或少于m个)儿子都分别指定好m个不同的确定位置，则称该树为位置叉树。
当m=2时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点v，至多有两个子树，分别称为v的左子树和右子树。若v只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，v的左子树画在v的左下方，v的右子树画在v的右下方。

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

59 如前所叙，在任何位置二叉树的0-1串表示中，其叶结点的串集合是个前缀码，即哈夫曼编码树对应着一个哈夫曼编码。不仅如此，还可以构造性证明其逆命题：
定理 任何一个前缀码都对应一棵位置二叉树的0-1串表示，即哈夫曼编码对应一棵哈夫曼编码树。

60 有很多实际应用，可用二叉树或m叉树表示。可以指出，按下面算法，任何一棵有序树均能表成二叉树。其算法是：
(1) 除最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一级中，兄弟结点之间用从左到右的弧连接。

61 (2) 选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。
上述算法能够推广到有序森林上去。

62 二叉树的一个重要应用就是最优树问题。 给定一组数w1，w2，…，wn。令一棵二叉树有n个叶结点，并对它们分别指派w1，w2，…，wn作为权，则该二叉树称为加权二叉树。

63 定义11.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树。

64 定理11.3.14 设T为加权w1，w2，…，wn且w1≤w2≤…≤wn的最优树，则
(1) 加权w1和w2的叶结点vw1和vw2是兄弟。 (2) 以叶结点vw1和vw2为儿子的分枝结点，它是所有分枝结点的级最高者。

65 定理11.3.15 设T为加权w1，w2，…，wn且w1≤w2≤…≤wn的最优树，若将以加权w1和w2的叶结点为儿子的分枝结点改为加权w1+w2的叶结点而得到一棵新树T1，则T1是最优树。

66 根据上述两个定理，求一棵有n个权的最优树，可简化为求一棵有n-1个权的最优树，而这又可简化为求一棵有n-2个权的最优树，依此类推。具体作法是：
首先找出两个最小的权值，设w1和w2。然后对n-1个权w1+w2，w3，…，wn求作一棵最优树，并且将这棵树中的结w1+w2代之以w1 w2，依此类推。

67 11.4 平面图 在一些实际问题中，要涉及到图的平面性的研究，比如大家都知道的印刷线路板的布线问题。近些年来，大规模集成电路的发展，进一步促进了图的平面性的研究。本节将简要地介绍平面图的概念，欧拉公式和平面图的着色。 定义 一个无向图G=<V，E>，如果能把它画在平面上，且除V中的结点外，任意两条边均不相交，则称该图G为平面图。

68 下面给出一种判别平面图的直观方法。 根据平面的定义，无圈的图显然是平面图。故，研究图的平面性问题，只需要限制有圈的一类图即可。判别方法是： (1) 对于有圈的图找出一个长度尽可能大的且边不相交的基本圈。 (2) 将图中那些相交于非结点的边，适当放置在已选定的基本圈内侧或外侧，若能避免除结点之外边的相交，则该图是平面图；否则，便是非平面图。

69 在图论中，称K3,3和K5是库拉图斯基图。这是因为波兰数学家库拉图斯基(K
在图论中，称K3,3和K5是库拉图斯基图。这是因为波兰数学家库拉图斯基(K.Kuratowski)于1930年给出了的判别平面图充要条件(后称库拉图斯基定理)曾用到这两个图。下面就来介绍这一定理，不过它要用到两个图同胚的概念。可以看出，在给定图G的任何一条边上插入一个度为2的结点，使一条边成为两条边，或者涂抹图G中度为2的结点，使两条边成为一条边，这些都不会影响图的平面性。

70 定义11.4.2 若图G2可由图G1中的一些边上适当插入或涂抹度为2的有限个结点后而得到，则称G1与G2同胚。
显然，任何两个基本圈是同胚的。

71 定理11.4.1 (库拉图斯基定理)一个图G是平面图G中不含同胚于K3,3或K5的子图。
该定理的证明是看来不算很难但是冗长的，略去了，有兴趣读者可参见图论专著中的证明。 库拉图斯基定理表述还是简明的，例如，图11.4.4(a)所示的图称为彼得森图，它是非平面图。因为当删去边[v6,v8]和[v3,v4]时，它成为含有同胚于K3,3的子图，如图11.4.4(b)或(c)所示。

72 图

73 下面介绍平面图中的重要的欧拉公式。 定义 设G为一平面图，若由G的一条或多条边所界定的区域内部不含图G的结点和边，这样的区域称为G的一个面，记为f。包围这个区域的各条边所构成的圈，称为该面f的边界，其圈的长度，称为该面f的度，记为d(f)。为强调平面图G中含有面这个元素，今后把平面图表为G=<V，E，F>，其中F是G中所有面的集合。

74 为方便有时把平面图G的外部的无限区域当作一个面，称为无限面或外部面，其余的面称为有限面或内部面。
由定义不难证明下面定理： 定理 令G=<V，E，F>是连通平面图，则 。

75 定理11.4.3 设G=<V，E，F>是连通平面图，则|V|-|E|+|F|=2。
这便是著名的欧拉公式。 推论1 给定连通简单平面图G=<V，E，F>。若|V|≥3，则|E|≤3|V|-6。 推论2 设G=<V，E，F>是一个连通简单平面图，若|V|≥3，则存在v∈V，使得d(v)≤5。

76 推论3 给定连通简单平面图G=<V，E，F>。若对于每个面f∈F，有d(f)≥4，则
|E|≤2|V|-4 推论4 完全图Kn是平面图n≤4。 推论5 完全二部图Km,n是平面图m≤2或n≤2。

77 下面讨论平面图的着色问题。 平面图的着色问题，最早起源于地图的着色。在一张地图中，若相邻国家着以不同的颜色，那么最少需要多少种颜色呢？1840年，德国数学家麦比乌斯(A.F.Mǒbius)在他的讲稿中第一次提出了确信用四种颜色可以对地图着色的问题(以下简称四色猜想)。1879年肯普(Kempe)给出了这个猜想的第一个证明，但到1890年希伍德(Hewood)发现肯普证明是有错误的，然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了，但却可以证明用五种颜色是够的，即五色定理成立。

78 在这里，研究的方法并不直接去考察地图着色问题，而是把它转化成平面图。为此，先给出对偶图的概念。
定义 给定平面图G=<V，E，F>，且f1，f2，…，fn∈F。若有图G*=<V*，E*>满足下列条件：

79 (1) 对于任意fi∈F内部有且仅有一个结点v*i∈V*；
(2) 对于G中面fi和面fj的公共边ek有且仅有一条边e*k∈E*，使得ek*=〔v*i，v*j〕且e*k与ek相交； (3) 当且仅当ek只是一个面fi的边界时，v*i存在一个环ek*且e*k与ek相交，则称图G*是图G的对偶图。

80 从对偶图的定义可以看出，若G. =<V. ，E. >是平面图G=<V，E，F>的对偶图，则G也G
从对偶图的定义可以看出，若G*=<V*，E*>是平面图G=<V，E，F>的对偶图，则G也G*的对偶图。一个连通平面图G的对偶图G*，也是平面图，而且有 |E(G*)|=|E(G)| |V(G*)|=|F(G)| ()=dG(fi) fiF，v*

81 其中E(G)表示图G的所有边集合，F(G)表示图G的所有面的集合。于是，可得到下面定理：
定理 若G=<V，E，F>是平面图，则 。

82 定义11.4.5 若图G的对偶图G*同构于G，则称G是自对偶图。

83 定理11.4.5 若平面图G=<V，E>是自对偶图，则|E|=2(|V|-1)。
从对偶图的定义容易知道，对于地图的着色问题，可以化为一种等价的对于平面图的结点的着色问题。因此，四色问题可以归结为要证明：对任意平面图一定可以用四种颜色，对其结点进行着色，使得相邻结点都有不同颜色。

84 平面图G=<V，E>的着色α是从结点集V到色集C={c1，c2，…，cn}上一个映射，使对任意边[vi，vj]∈E均有α(vi)≠α(vj)，即对G的每个结点指派一种颜色，使得相邻结点都有不同的颜色。 对于平面图G着色时，需要的最少颜色数称为G的着色数，记为χ(G)。 定理 (五色定理)对于任何简单平面图G=<V，E>，均有χ(G)≤5。

85 由此定理及对偶图定义，可得出下面定理。 定理 任何地图M，M是五着色的，即χ(M)≤5。

86 自从四色猜想提出后，一百多年来，一直成为数学上的著名难题，它吸引许许多多的人，为之而作出大量辛劳，也得到很多重要结果，但长久未能得到解决。直到1976年6月，由美国伊利诺斯大学两名数学家爱普尔(K.I.Apple)、黑肯(W.Haken)在考西(J.Koch)帮助下借助于电子计算机，用了一百多亿次逻辑判断，花了1200多机时才证明四色猜想是成立的，从此宣告，四色猜想成为四色定理。现将它叙述如下：

87 定理14.4.8 (四色定理)对于任何平面图G，有χ(G)≤4。
相应地有下面的定理。 定理 对于任何地图M，M是四着色的，即χ(M)≤4。