第十一章 几类重要的图
11.1 欧拉图与哈密尔顿图
11.2 二部图
11.3 树
11.4 平面图退出
11.1 欧拉图与哈密尔顿图
1736年瑞士数学家欧拉发表了图论的第一篇著名论文,哥尼斯堡七桥问题,(下称七桥问题 )。 这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河,城的各部分用七桥联结,
每逢节假日,有些城市居民进行环城周游,于是便产生了能否,从某地出发,通过每桥恰好一次,在走遍了七桥后又返回到原处,的问题 。
在图 11.1.1画出了哥尼斯堡城图，城的四块陆地部分以 A,B,C，和 D标记。欧拉巧妙地把哥尼斯堡城图化为图 11.1.2所示图 G，他把陆地设为图 G中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图 G中从某一结点出发找出一条链，它通过每条边恰好一次后回到原出发结点，亦即等价于在图 G中寻找一个圈，它通过 G中每一条边恰好一次。
图 11.1.1
图 11.1.2
欧拉在这篇论文中提出了一条简单准则,
确定七桥问题是不能解的 。 下面就来讨论这个问题 。
定义 11.1.1 图 G中的一圈 (或回路 ),若它通
G中的每一条边 (或弧 )恰好一次,则称该圈 (或回路 )为欧拉圈 (或回路 ),具有这种圈 (或回路 )的图称为欧拉无向 (或有向 )图 。
定理 11.1.1 给定连通无向图 G,G有欧拉圈
G中每个结点都是偶度结点 。
由定义 11.1.1可知,具有欧拉圈的图是欧拉图,故图 G为欧拉图?G中每个结点都是偶度结点 。
由于七桥问题所对应的图中每个结点都是奇度结点,根据上述定理可知,七桥问题无解 。
定义 11.1.2 图 G中的一条链 (或路 )，若它通过 G中的每条边 (或弧 )恰好一次，则称该链 (或路 )
为欧拉链 (或路 )。
定理 11.1.2 给定连通无向图 G=<V,E>,u，
v∈ V且 u≠v,u与 v间存在欧拉链?G中仅有 u和 v
为奇度结点。
定理 11.1.3 给定弱连通有向图 G,G有欧拉回路?G中的每个结点的入度等于出度 。
定理 11.1.4 给定弱连通有向图 G=<V,E>，
u,v∈ V且 u≠v,u与 v存在欧拉路?G中唯有 u和
v的入度不等于出度,且 u的入度比其出度大于 1
和 v的出度比其入度小于 1(或者反之 )。
这两个定理的证明，可以看作是关于无向图的欧拉圈和欧拉链的推广。因为对于有向图的任意一个结点来说，如果入度与出度相等，
则该结点为偶度结点；如果入度与出度之差为 1
时，该结点必是奇度结点，所以定理 11.1.3和
14.1.4与前面两个定理的证明类似。
与欧拉圈和链 (或回路和路 )非常类似的问题是哈密尔顿圈和链 (或回路和路 )的问题。 1859
年，爱尔兰数学家哈密尔顿 (W.R.Hamilton)首先提出“环球周游”问题。他用一个正十二面体的 20个顶点代表世界上 20个大城市 (见图
11.1.4(a))，这个正十二面体同构于一个平面图
(见图 11.1.4(b)，平面图的定义稍后给出 )，要求旅游者能否找到沿着正十二面体的棱，从某个顶点 (即城市 )出发，经过每个顶点 (即每座城市 )
恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。
图 11.1.4
按图 11.1.4(c)中所给的编号进行旅游，
便是哈密尔顿问题的解。
对于任何连通图也有类似的问题。
图 11.1.4
定义 11.1.3 图 G中的一圈 (或回路 )，若它通过 G中每个结点恰好一次，则该圈 (或回路 )称为哈密尔顿圈 (或回路 )，具有哈密尔顿圈 (或回路 )
的图称为哈密尔顿无向 (或有向 )图。
由该定义可知，完全图必是哈密尔顿图。
定义 11.1.4 图 G中的一链 (或路 )，若它通过
G中的每个结点恰好一次，则该链 (或路 )称为哈密尔顿链 (或路 )。
哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一。然而，还是有不少重要成果，下面给出几个必要和充分条件的定理。
定理 11.1.5 若连通图 G=<V,E>是哈密尔顿图,S是 V的任意真子集，则 ω(G-S)≤|S|。
本定理给出是哈密尔顿图的一个必要条件,
但这个条件又不便于使用,因为它要求对 G的结点集合的所有真子集进行验证 。 尽管如此,利用它还可以证明某些图不是哈密尔顿图 。
下面给出图 G是哈密尔顿图的充分条件,
这个结果是于 1952年 G.A.Dirac研究得到的 。
定理 11.1.6 给定简单图 G=<V,E>,|V|=n，
若 n≥3和 δ≥n/2,则 G是哈密尔顿图 。
请注意,本定理给出的仅是充分条件 。 例如,十多边形显然是哈密尔顿图,但 δ=2≥
=5。
Bondy和 Chvatol于 1969年证明了更强的充分条件。他们的方法是建立下面两个引理之上的。
引理 11.1.1 给定图 G=<V,E>,|V|=n≥3。
若 u,v∈ V,u与 v不邻接且 d(u)+d(v)≥n，则 G是哈密尔顿图?G+〔 u,v〕 是哈尔密顿图。
受引理 11.1.1启示,可以定义图的闭包概念 。
定义 11.1.4 给定图 G=<V,E>,|V|=n。
图 G的闭包是由 G通过相继地用边连接两个其度之和至少为 n的不邻接结点，直到不能如此进行为止而得到的图。用 C(G)表示图 G的闭包。
引理 11.1.2 C(G)是唯一确定的。
下面定理是引理 11.1.1的直接结果：
定理 11.1.7 简单无向图 G是哈密尔顿图
C(G)是哈密尔顿图 。
容易看出,至少有三个结点的所有完全图都是哈密尔顿图 。 由此可得到下面推论：
推论 给定简单无向图 G=<V,E>,|V|≥3。
若 C(G)是完全图,则图 G是哈尔密顿图 。
对于有向图的哈密尔顿回路和路也有此类似结果,但其证明却是困难得多,因此这里只叙述由 Ghoula-Houri给出的定理如下：
定理 11.1.8 给定 n阶强连通图 G=<V,E>。
若对任意 v∈ V,有 d+(v)+d-(v) ≥n,则 G有哈密尔顿回路 。
11.2 二部图本节简要介绍二部图及二部图中匹配理论的主要概念和成果 。
定义 11.2.1 给定简单无向图 G=<V,E>，
且 V=V1∪ V2,V1∩V2=?。 若 V1和 V2的诱导子图
<V1>和 <V2>都是零图,则称 G是二部图或偶图,
并将二部图记作 G=<V1,E,V2>,并称 V1,V2
是 V的划分 。
在一个二部图 G=<V1,E,V2>中，若
|V1|=m,|V2|=n，且对任意的 u∈ V1,v∈ V2均有
u,v〕 ∈ E，则称 G为完全二部图，记为 Km,n。
定理 11.2.1 简单图 G为二部图?G中所有基本圈的长度为偶数 。
定义 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是最大匹配 。 显然,每个完全匹配是最大匹配,但反之不真 。
定义 11.2.3 令 M是图 G=<V,E>中的一个匹配 。 若存在一个链,它是由分别由 E-M和 M
中的边交替构成,则称该链是 G中的 M— 交错链；
若 M— 交错链的始结点和终结点都是 M— 不饱和的,则称该链为 M— 增广链；特别地,若
M— 交错链的始结点也是它的终结点而形成圈,
则称该圈为 M— 交错圈 。
在匹配理论中,人们特别关心的是最大匹配 。 Berge在 1957年给出了一个图中的一个匹配为最大匹配的充要条件 。 在证明这一结论时,
将要用到两个集合的对称差的概念,现叙述如下：
给定两个集合 S和 T,S与 T的对称差,记为
SΔT,其定义为：
S?T=(S∪ T)-(S∩T)
引理 11.2.1 设 M1和 M2是图 G中的两个匹配，
则在 <M1?M2>中，每个分图或是交错链，或是交错圈。
定理 11.2.2 (Berge,1957)图 G的一个匹配
M是个最大匹配 G中不含有 M— 增广链 。
在许多应用中,希望在二部图 G=<V1,E，
V2>中找出一个匹配 M,使得 V1中每个结点都是
M— 饱和的 。 1935年,Hall首先给出存在这样匹配的充分必要条件的定理 。
定理 11.2.3 给定二部图 G=<V1,E,V2>，
G中存在使 V1中每个结点饱和的匹配?对任意
S?V1有
|N(S)|≥|S| (2)
其中 N(S)表示与 S中结点邻接的所有结点集合 。
推论 若 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>
中任意一个匹配,该算法是：
(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中所有边的集合。
11.3 树定义 11.3.1 一个无圈的连通图,称为树 。
显然,由定义可知,树是个简单图,即它无环和无平行边 。
在树中,度为 1的结点称为叶或悬挂结点；
度数大于的结点称为内结点或分枝结点；而与叶或悬挂结点所关联的边,称为叶边或悬挂边 。
若图中的每个连通分图是树,则称该图为森林 。
定理 11.3.1 树 T中任两个结点间恰有一条链 。
定理 11.3.2 若图 G中每对结点间有且仅有一条链,则 G为树 。
定理 11.3.3 具有 n个结点的树中有 n-1条边,
即树 T=<V,E>中,|E|=|V|-1。
注意,具有 n个结点和恰有 n-1条边的图未必是树,但有下面两个定理：
定理 11.3.4 给定连通图 G=<V,E>,若
|E|=|V|-1,则 G是树 。
定理 11.3.5 给定图 G=<V,E>,|E|=|V|-1且
G中无圈,则 G是树 。
连通无圈完全刻划了树,这是树的一个特性；树还有另外一个重要性质是：它以最少的边使结点可达或连通 。 这便导出下面的最小连通的概念 。
定义 11.3.2 给定连通图 G=<V,E>,若对任意 e∈ E,均使 G-e不连通,则称连通图 G是最小连通的 。
显然，最小连通图不可能有圈。因为删去圈中的一条边后仍使图连通。于是，最小连通图是树。反之,如果一个连通图 G不是最小连通的，则必存在 G中一条边 ei，使 G-ei连通。所以 ei位于一圈中，这意味着 G不是树。故可得到下面定理：
定理 11.3.6 图 G是树?G是最小连通的。
上面的六个定理可以总结为下面五个不同的但却是等价的树的定义。给定图 G=<V,E>，
G是树的等价定义是：
① G是连通且无圈
② G是连通且 |E|=|V|-1
③ G是无圈且 |E|=|V|-1
④ G中每对结点间恰有一条链
⑤ G是最小连通图定理 11.3.7 给定树 T=<V,E>，若
|V|≥2，则 T中至少存在两个悬挂结点。
对于一些图,它本身未必是树,但它的子图是树 。 一个图可能有多个子图是树,
其中很重要的一类树是生成树 。
定义 11.3.3 给定图 G=<V,E>。若 G的生成子图 T是树，则称 T是 G的生成树。 T中的边称为枝，是 G中的边但不为 T中的边称为弦。
定理 11.3.8 图 G=<V,E>有生成树 T=<VT，
ET>?G是连通的 。
假设图 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。
定理 11.3.9 若 T是图 G的一棵生成树,e=[u，
v]是弦，则存在唯一的由 e和 T中某些边构成的基本圈 C。若 f是 C上与 e不同的边且由 f替换 e而得到图 T1，则 T1也是 G的一棵生成树。
定理 11.3.10 设 T1和 T2是图 G的两棵生成树 。
若 f是 T1的边但不为 T2的边 。 则存在一条是 T2但不为 T1的边 e,使得用 e代替 T1中的一条边而得到图 G的一棵生成树 T3。
下面讨论利用生成树为讨论加权图的最小连接问题 。
设 G=<V,E,W>是加权的连通图,对任意边 e?,其权 w(e)≥0。 令 T=<VT,ET,WT>是 G的一查枷权生成树,其所有枝上的权的总和
(e),称为树 T的权,记为 w(T)。 一般说来,
对于 G的不同生成树 T,w(T)也是不同的 。 可以知道,其中必有一个最小者,而这正是人们最为感兴趣的 。 因此,有如下定义 。
定义 11.3.4 给定连通加权图 G=<V,E，
W>,T0=<V,ET0,WT0>是 G的加权生成树，
w(T0)为 T0的权。若对 G的任意加权生成树 T均有
w(T0)≤w(T)，则称 T0是 G的最小生成树。
下面给出一种求最小生成树的方法 ——
Kruskal算法 (1956)，它的本质是树生成过程，
因此得名避圈法。
定理 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为止。
定义 11.3.5 给定加权连通图 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的最短链 。
)( 0 )(cEe ew
现在给出一种求从已知结点到另外一个结点的最短链的方法 — G.Dantzig算法，其本质也是一种树生长过程。
定理 11.3.12 设有 n个结点的加权连通图
G=<V,E,W>,x0∈ V。依下面算法得到 G的一棵生成树 T，使得在 T中连接 x0与 x≠x0的每一条基本链是 G中连接 x0与 x的最短链。
令 X0={x0}和 l(x0)=0，执行以下步骤：
(1) 选取 x1，连接 x0与 x1使 w([x0,x1])尽可能地小。令 l(x1)=w([x0,x1]),X1={x0,x1}和
E1={[x0,x1]}。
(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为止。
前面讨论的树,都是无向图中的树,即无向树；下面将简单地介绍有向图中的树即有向树 。
定义 11.3.6 如果一个有向图的基础图是一棵树,则该有向图称为有向树 。 其图形表示法常采用倒置树表示之,且为方便计,有时略去边之方向 。
定义 11.3.7 给定一个有向树,若只有一个结点的入度是零,其余结点的入度都是 1,则称该树为有根树 。
在有根树中,入度为零的结点称为根或根结点,出度为零的结点称为叶或叶结点；出度不为零的结点称为分枝结点或内结点 。
定义 11.3.8 在有根树中,从根到某个结点的路长即该路中的弧数,称为该结点的级 。 其中结点的级的最大者,称为有根树的树高 。
由于有向树中没有回路,因此所有的路都是基本路 。 可见,从树中任何结点到另外一个结点的路长即是两结点的距离 。 故有根树的根结点的级是零；任何结点的级,等于从根到该结点的距离 。
在有向树中,结点的出现次序是没有意义的 。 但实际应用中,有时要给出同一级中结点的相对次序,这便导出有序树的概念 。
定义 11.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是 w的“祖先”，或称 w是 u的
“子孙”，同一个分枝结点的儿子称为“兄弟”。
在前面讨论的有根树或有序树中，其结点的出度未加任何限制。现在将依据结点出度的不同情况进行讨论。
定义 11.3.10 在有根树中，若每一个结点的出度都小于或等于 m，则称该树为
m叉树。若每一个结点的出度恰好等于 m
或等于 0，则称这种树为完全 m叉树。若所有的叶结点的级相同，则称正则 m叉树。
定义 11.3.11 在 m叉树中，如果对任何结点的 m个 (或少于 m个 )儿子都分别指定好 m个不同的确定位置，则称该树为位置叉树。
当 m=2时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点 v，至多有两个子树，分别称为 v的左子树和右子树。若 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叉树的各个结点 。
如前所叙，在任何位置二叉树的 0-1串表示中，其叶结点的串集合是个前缀码，即哈夫曼编码树对应着一个哈夫曼编码。不仅如此，还可以构造性证明其逆命题：
定理 11.3.13 任何一个前缀码都对应一棵位置二叉树的 0-1串表示，即哈夫曼编码对应一棵哈夫曼编码树。
有很多实际应用,可用二叉树或 m叉树表示 。 可以指出,按下面算法,任何一棵有序树均能表成二叉树 。 其算法是：
(1) 除最左边的分枝结点外,删去所有从每一个结点长出的分枝 。 在同一级中,兄弟结点之间用从左到右的弧连接 。
(2) 选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。
上述算法能够推广到有序森林上去 。
二叉树的一个重要应用就是最优树问题。
给定一组数 w1,w2,…,wn。令一棵二叉树有 n个叶结点，并对它们分别指派
w1,w2,…,wn作为权，则该二叉树称为加权二叉树。
定义 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树。
定理 11.3.14 设 T为加权 w1,w2,…,wn且
w1≤w2≤…≤ wn的最优树，则
(1) 加权 w1和 w2的叶结点 vw1和 vw2是兄弟。
(2) 以叶结点 vw1和 vw2为儿子的分枝结点，
它是所有分枝结点的级最高者。
定理 11.3.15 设 T为加权 w1,w2,…,wn且
w1≤w2≤… ≤wn的最优树,若将以加权 w1和 w2的叶结点为儿子的分枝结点改为加权 w1+w2的叶结点而得到一棵新树 T1,则 T1是最优树 。
根据上述两个定理,求一棵有 n个权的最优树,可简化为求一棵有 n-1个权的最优树,而这又可简化为求一棵有 n-2个权的最优树,依此类推 。 具体作法是：
首先找出两个最小的权值,设 w1和 w2。 然后对 n-1个权 w1+w2,w3,…,wn求作一棵最优树,并且将这棵树中的结 w1+w2代之以 w1 w2，
依此类推 。
11.4 平面图在一些实际问题中,要涉及到图的平面性的研究,比如大家都知道的印刷线路板的布线问题 。 近些年来,大规模集成电路的发展,进一步促进了图的平面性的研究 。 本节将简要地介绍平面图的概念,欧拉公式和平面图的着色 。
定义 11.4.1 一个无向图 G=<V,E>,如果能把它画在平面上,且除 V中的结点外,任意两条边均不相交,则称该图 G为平面图 。
下面给出一种判别平面图的直观方法 。
根据平面的定义,无圈的图显然是平面图 。
故,研究图的平面性问题,只需要限制有圈的一类图即可 。 判别方法是：
(1) 对于有圈的图找出一个长度尽可能大的且边不相交的基本圈 。
(2) 将图中那些相交于非结点的边,适当放置在已选定的基本圈内侧或外侧,若能避免除结点之外边的相交,则该图是平面图；否则,
便是非平面图 。
在图论中,称 K3,3和 K5是库拉图斯基图 。 这是因为波兰数学家库拉图斯基 (K.Kuratowski)于
1930年给出了的判别平面图充要条件 (后称库拉图斯基定理 )曾用到这两个图 。 下面就来介绍这一定理,不过它要用到两个图同胚的概念 。 可以看出,在给定图 G的任何一条边上插入一个度为 2的结点,使一条边成为两条边,或者涂抹图
G中度为 2的结点,使两条边成为一条边,这些都不会影响图的平面性 。
定义 11.4.2 若图 G2可由图 G1中的一些边上适当插入或涂抹度为 2的有限个结点后而得到，则称 G1与 G2同胚。
显然，任何两个基本圈是同胚的 。
定理 11.4.1 (库拉图斯基定理 )一个图 G是平面图?G中不含同胚于 K3,3或 K5的子图 。
该定理的证明是看来不算很难但是冗长的,
略去了,有兴趣读者可参见图论专著中的证明 。
库拉图斯基定理表述还是简明的,例如,
图 11.4.4(a)所示的图称为彼得森图,它是非平面图 。 因为当删去边 [v6,v8]和 [v3,v4]时,它成为含有同胚于 K3,3的子图,如图 11.4.4(b)或 (c)所示 。
图 11.4.5
下面介绍平面图中的重要的欧拉公式 。
定义 11.4.3 设 G为一平面图,若由 G的一条或多条边所界定的区域内部不含图 G的结点和边,
这样的区域称为 G的一个面,记为 f。 包围这个区域的各条边所构成的圈,称为该面 f的边界,
其圈的长度,称为该面 f的度,记为 d(f)。 为强调平面图 G中含有面这个元素,今后把平面图表为 G=<V,E,F>,其中 F是 G中所有面的集合 。
为方便有时把平面图 G的外部的无限区域当作一个面，称为无限面或外部面，其余的面称为有限面或内部面。
由定义不难证明下面定理：
定理 11.4.2 令 G=<V,E,F>是连通平面图，
则 。
定理 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。
推论 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。
下面讨论平面图的着色问题 。
平面图的着色问题,最早起源于地图的着色 。 在一张地图中,若相邻国家着以不同的颜色,那么最少需要多少种颜色呢？ 1840年,德国数学家麦比乌斯 (A.F.Mǒbius)在他的讲稿中第一次提出了确信用四种颜色可以对地图着色的问题 (以下简称四色猜想 )。 1879年肯普 (Kempe)
给出了这个猜想的第一个证明,但到 1890年希伍德 (Hewood)发现肯普证明是有错误的,然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了,但却可以证明用五种颜色是够的,即五色定理成立 。
在这里，研究的方法并不直接去考察地图着色问题，而是把它转化成平面图。为此，先给出对偶图的概念。
定义 11.4.4 给定平面图 G=<V,E,F>，且
f1,f2,…,fn∈ F。若有图 G*=<V*,E*>满足下列条件：
(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
的对偶图。
从对偶图的定义可以看出,若 G*=<V*，
E*>是平面图 G=<V,E,F>的对偶图,则 G也
G*的对偶图 。 一个连通平面图 G的对偶图 G*，
也是平面图,而且有
|E(G*)|=|E(G)|
|V(G*)|=|F(G)|
()=dG(fi) fi?F,?v*
其中 E(G)表示图 G的所有边集合，
F(G)表示图 G的所有面的集合。于是，可得到下面定理：
定理 11.4.4 若 G=<V,E,F>是平面图，
则 。
定义 11.4.5 若图 G的对偶图 G*同构于
G,则称 G是自对偶图 。
定理 11.4.5 若平面图 G=<V,E>是自对偶图,则 |E|=2(|V|-1)。
从对偶图的定义容易知道,对于地图的着色问题,可以化为一种等价的对于平面图的结点的着色问题 。 因此,四色问题可以归结为要证明：对任意平面图一定可以用四种颜色,对其结点进行着色,使得相邻结点都有不同颜色 。
平面图 G=<V,E>的着色 α是从结点集 V到色集 C={c1,c2,…,cn}上一个映射，使对任意边 [vi,vj]∈ E均有 α(vi)≠α(vj)，即对 G的每个结点指派一种颜色，使得相邻结点都有不同的颜色。
对于平面图 G着色时，需要的最少颜色数称为 G的着色数，记为 χ(G)。
定理 11.4.6 (五色定理 )对于任何简单平面图 G=<V,E>，均有 χ(G)≤5。
由此定理及对偶图定义,可得出下面定理 。
定理 11.4.7 任何地图 M,M是五着色的,即 χ(M)≤5。
自从四色猜想提出后，一百多年来，一直成为数学上的著名难题，它吸引许许多多的人，
为之而作出大量辛劳，也得到很多重要结果，
但长久未能得到解决。直到 1976年 6月，由美国伊利诺斯大学两名数学家爱普尔 (K.I.Apple)、
黑肯 (W.Haken)在考西 (J.Koch)帮助下借助于电子计算机，用了一百多亿次逻辑判断，花了
1200多机时才证明四色猜想是成立的，从此宣告，四色猜想成为四色定理。现将它叙述如下：
定理 14.4.8 (四色定理 )对于任何平面图 G，
有 χ(G)≤4。
相应地有下面的定理。
定理 14.4.9 对于任何地图 M,M是四着色的，即 χ(M)≤4。
11.1 欧拉图与哈密尔顿图
11.2 二部图
11.3 树
11.4 平面图退出
11.1 欧拉图与哈密尔顿图
1736年瑞士数学家欧拉发表了图论的第一篇著名论文,哥尼斯堡七桥问题,(下称七桥问题 )。 这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河,城的各部分用七桥联结,
每逢节假日,有些城市居民进行环城周游,于是便产生了能否,从某地出发,通过每桥恰好一次,在走遍了七桥后又返回到原处,的问题 。
在图 11.1.1画出了哥尼斯堡城图，城的四块陆地部分以 A,B,C，和 D标记。欧拉巧妙地把哥尼斯堡城图化为图 11.1.2所示图 G，他把陆地设为图 G中的结点，把桥画成相应地联结陆地即结点的边。于是，通过哥尼斯堡城中每座桥恰好一次问题，等价于在图 G中从某一结点出发找出一条链，它通过每条边恰好一次后回到原出发结点，亦即等价于在图 G中寻找一个圈，它通过 G中每一条边恰好一次。
图 11.1.1
图 11.1.2
欧拉在这篇论文中提出了一条简单准则,
确定七桥问题是不能解的 。 下面就来讨论这个问题 。
定义 11.1.1 图 G中的一圈 (或回路 ),若它通
G中的每一条边 (或弧 )恰好一次,则称该圈 (或回路 )为欧拉圈 (或回路 ),具有这种圈 (或回路 )的图称为欧拉无向 (或有向 )图 。
定理 11.1.1 给定连通无向图 G,G有欧拉圈
G中每个结点都是偶度结点 。
由定义 11.1.1可知,具有欧拉圈的图是欧拉图,故图 G为欧拉图?G中每个结点都是偶度结点 。
由于七桥问题所对应的图中每个结点都是奇度结点,根据上述定理可知,七桥问题无解 。
定义 11.1.2 图 G中的一条链 (或路 )，若它通过 G中的每条边 (或弧 )恰好一次，则称该链 (或路 )
为欧拉链 (或路 )。
定理 11.1.2 给定连通无向图 G=<V,E>,u，
v∈ V且 u≠v,u与 v间存在欧拉链?G中仅有 u和 v
为奇度结点。
定理 11.1.3 给定弱连通有向图 G,G有欧拉回路?G中的每个结点的入度等于出度 。
定理 11.1.4 给定弱连通有向图 G=<V,E>，
u,v∈ V且 u≠v,u与 v存在欧拉路?G中唯有 u和
v的入度不等于出度,且 u的入度比其出度大于 1
和 v的出度比其入度小于 1(或者反之 )。
这两个定理的证明，可以看作是关于无向图的欧拉圈和欧拉链的推广。因为对于有向图的任意一个结点来说，如果入度与出度相等，
则该结点为偶度结点；如果入度与出度之差为 1
时，该结点必是奇度结点，所以定理 11.1.3和
14.1.4与前面两个定理的证明类似。
与欧拉圈和链 (或回路和路 )非常类似的问题是哈密尔顿圈和链 (或回路和路 )的问题。 1859
年，爱尔兰数学家哈密尔顿 (W.R.Hamilton)首先提出“环球周游”问题。他用一个正十二面体的 20个顶点代表世界上 20个大城市 (见图
11.1.4(a))，这个正十二面体同构于一个平面图
(见图 11.1.4(b)，平面图的定义稍后给出 )，要求旅游者能否找到沿着正十二面体的棱，从某个顶点 (即城市 )出发，经过每个顶点 (即每座城市 )
恰好一次，然后回到出发顶点?这便是著名的哈密尔顿问题。
图 11.1.4
按图 11.1.4(c)中所给的编号进行旅游，
便是哈密尔顿问题的解。
对于任何连通图也有类似的问题。
图 11.1.4
定义 11.1.3 图 G中的一圈 (或回路 )，若它通过 G中每个结点恰好一次，则该圈 (或回路 )称为哈密尔顿圈 (或回路 )，具有哈密尔顿圈 (或回路 )
的图称为哈密尔顿无向 (或有向 )图。
由该定义可知，完全图必是哈密尔顿图。
定义 11.1.4 图 G中的一链 (或路 )，若它通过
G中的每个结点恰好一次，则该链 (或路 )称为哈密尔顿链 (或路 )。
哈密尔顿图尽管在形式上与欧拉图极其相似，但其结论上却有很大不同，至今还没有得到关于哈密尔顿图的非平凡的充要条件，这是图论尚未解决的主要问题之一。然而，还是有不少重要成果，下面给出几个必要和充分条件的定理。
定理 11.1.5 若连通图 G=<V,E>是哈密尔顿图,S是 V的任意真子集，则 ω(G-S)≤|S|。
本定理给出是哈密尔顿图的一个必要条件,
但这个条件又不便于使用,因为它要求对 G的结点集合的所有真子集进行验证 。 尽管如此,利用它还可以证明某些图不是哈密尔顿图 。
下面给出图 G是哈密尔顿图的充分条件,
这个结果是于 1952年 G.A.Dirac研究得到的 。
定理 11.1.6 给定简单图 G=<V,E>,|V|=n，
若 n≥3和 δ≥n/2,则 G是哈密尔顿图 。
请注意,本定理给出的仅是充分条件 。 例如,十多边形显然是哈密尔顿图,但 δ=2≥
=5。
Bondy和 Chvatol于 1969年证明了更强的充分条件。他们的方法是建立下面两个引理之上的。
引理 11.1.1 给定图 G=<V,E>,|V|=n≥3。
若 u,v∈ V,u与 v不邻接且 d(u)+d(v)≥n，则 G是哈密尔顿图?G+〔 u,v〕 是哈尔密顿图。
受引理 11.1.1启示,可以定义图的闭包概念 。
定义 11.1.4 给定图 G=<V,E>,|V|=n。
图 G的闭包是由 G通过相继地用边连接两个其度之和至少为 n的不邻接结点，直到不能如此进行为止而得到的图。用 C(G)表示图 G的闭包。
引理 11.1.2 C(G)是唯一确定的。
下面定理是引理 11.1.1的直接结果：
定理 11.1.7 简单无向图 G是哈密尔顿图
C(G)是哈密尔顿图 。
容易看出,至少有三个结点的所有完全图都是哈密尔顿图 。 由此可得到下面推论：
推论 给定简单无向图 G=<V,E>,|V|≥3。
若 C(G)是完全图,则图 G是哈尔密顿图 。
对于有向图的哈密尔顿回路和路也有此类似结果,但其证明却是困难得多,因此这里只叙述由 Ghoula-Houri给出的定理如下：
定理 11.1.8 给定 n阶强连通图 G=<V,E>。
若对任意 v∈ V,有 d+(v)+d-(v) ≥n,则 G有哈密尔顿回路 。
11.2 二部图本节简要介绍二部图及二部图中匹配理论的主要概念和成果 。
定义 11.2.1 给定简单无向图 G=<V,E>，
且 V=V1∪ V2,V1∩V2=?。 若 V1和 V2的诱导子图
<V1>和 <V2>都是零图,则称 G是二部图或偶图,
并将二部图记作 G=<V1,E,V2>,并称 V1,V2
是 V的划分 。
在一个二部图 G=<V1,E,V2>中，若
|V1|=m,|V2|=n，且对任意的 u∈ V1,v∈ V2均有
u,v〕 ∈ E，则称 G为完全二部图，记为 Km,n。
定理 11.2.1 简单图 G为二部图?G中所有基本圈的长度为偶数 。
定义 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是最大匹配 。 显然,每个完全匹配是最大匹配,但反之不真 。
定义 11.2.3 令 M是图 G=<V,E>中的一个匹配 。 若存在一个链,它是由分别由 E-M和 M
中的边交替构成,则称该链是 G中的 M— 交错链；
若 M— 交错链的始结点和终结点都是 M— 不饱和的,则称该链为 M— 增广链；特别地,若
M— 交错链的始结点也是它的终结点而形成圈,
则称该圈为 M— 交错圈 。
在匹配理论中,人们特别关心的是最大匹配 。 Berge在 1957年给出了一个图中的一个匹配为最大匹配的充要条件 。 在证明这一结论时,
将要用到两个集合的对称差的概念,现叙述如下：
给定两个集合 S和 T,S与 T的对称差,记为
SΔT,其定义为：
S?T=(S∪ T)-(S∩T)
引理 11.2.1 设 M1和 M2是图 G中的两个匹配，
则在 <M1?M2>中，每个分图或是交错链，或是交错圈。
定理 11.2.2 (Berge,1957)图 G的一个匹配
M是个最大匹配 G中不含有 M— 增广链 。
在许多应用中,希望在二部图 G=<V1,E，
V2>中找出一个匹配 M,使得 V1中每个结点都是
M— 饱和的 。 1935年,Hall首先给出存在这样匹配的充分必要条件的定理 。
定理 11.2.3 给定二部图 G=<V1,E,V2>，
G中存在使 V1中每个结点饱和的匹配?对任意
S?V1有
|N(S)|≥|S| (2)
其中 N(S)表示与 S中结点邻接的所有结点集合 。
推论 若 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>
中任意一个匹配,该算法是：
(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中所有边的集合。
11.3 树定义 11.3.1 一个无圈的连通图,称为树 。
显然,由定义可知,树是个简单图,即它无环和无平行边 。
在树中,度为 1的结点称为叶或悬挂结点；
度数大于的结点称为内结点或分枝结点；而与叶或悬挂结点所关联的边,称为叶边或悬挂边 。
若图中的每个连通分图是树,则称该图为森林 。
定理 11.3.1 树 T中任两个结点间恰有一条链 。
定理 11.3.2 若图 G中每对结点间有且仅有一条链,则 G为树 。
定理 11.3.3 具有 n个结点的树中有 n-1条边,
即树 T=<V,E>中,|E|=|V|-1。
注意,具有 n个结点和恰有 n-1条边的图未必是树,但有下面两个定理：
定理 11.3.4 给定连通图 G=<V,E>,若
|E|=|V|-1,则 G是树 。
定理 11.3.5 给定图 G=<V,E>,|E|=|V|-1且
G中无圈,则 G是树 。
连通无圈完全刻划了树,这是树的一个特性；树还有另外一个重要性质是：它以最少的边使结点可达或连通 。 这便导出下面的最小连通的概念 。
定义 11.3.2 给定连通图 G=<V,E>,若对任意 e∈ E,均使 G-e不连通,则称连通图 G是最小连通的 。
显然，最小连通图不可能有圈。因为删去圈中的一条边后仍使图连通。于是，最小连通图是树。反之,如果一个连通图 G不是最小连通的，则必存在 G中一条边 ei，使 G-ei连通。所以 ei位于一圈中，这意味着 G不是树。故可得到下面定理：
定理 11.3.6 图 G是树?G是最小连通的。
上面的六个定理可以总结为下面五个不同的但却是等价的树的定义。给定图 G=<V,E>，
G是树的等价定义是：
① G是连通且无圈
② G是连通且 |E|=|V|-1
③ G是无圈且 |E|=|V|-1
④ G中每对结点间恰有一条链
⑤ G是最小连通图定理 11.3.7 给定树 T=<V,E>，若
|V|≥2，则 T中至少存在两个悬挂结点。
对于一些图,它本身未必是树,但它的子图是树 。 一个图可能有多个子图是树,
其中很重要的一类树是生成树 。
定义 11.3.3 给定图 G=<V,E>。若 G的生成子图 T是树，则称 T是 G的生成树。 T中的边称为枝，是 G中的边但不为 T中的边称为弦。
定理 11.3.8 图 G=<V,E>有生成树 T=<VT，
ET>?G是连通的 。
假设图 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。
定理 11.3.9 若 T是图 G的一棵生成树,e=[u，
v]是弦，则存在唯一的由 e和 T中某些边构成的基本圈 C。若 f是 C上与 e不同的边且由 f替换 e而得到图 T1，则 T1也是 G的一棵生成树。
定理 11.3.10 设 T1和 T2是图 G的两棵生成树 。
若 f是 T1的边但不为 T2的边 。 则存在一条是 T2但不为 T1的边 e,使得用 e代替 T1中的一条边而得到图 G的一棵生成树 T3。
下面讨论利用生成树为讨论加权图的最小连接问题 。
设 G=<V,E,W>是加权的连通图,对任意边 e?,其权 w(e)≥0。 令 T=<VT,ET,WT>是 G的一查枷权生成树,其所有枝上的权的总和
(e),称为树 T的权,记为 w(T)。 一般说来,
对于 G的不同生成树 T,w(T)也是不同的 。 可以知道,其中必有一个最小者,而这正是人们最为感兴趣的 。 因此,有如下定义 。
定义 11.3.4 给定连通加权图 G=<V,E，
W>,T0=<V,ET0,WT0>是 G的加权生成树，
w(T0)为 T0的权。若对 G的任意加权生成树 T均有
w(T0)≤w(T)，则称 T0是 G的最小生成树。
下面给出一种求最小生成树的方法 ——
Kruskal算法 (1956)，它的本质是树生成过程，
因此得名避圈法。
定理 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为止。
定义 11.3.5 给定加权连通图 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的最短链 。
)( 0 )(cEe ew
现在给出一种求从已知结点到另外一个结点的最短链的方法 — G.Dantzig算法，其本质也是一种树生长过程。
定理 11.3.12 设有 n个结点的加权连通图
G=<V,E,W>,x0∈ V。依下面算法得到 G的一棵生成树 T，使得在 T中连接 x0与 x≠x0的每一条基本链是 G中连接 x0与 x的最短链。
令 X0={x0}和 l(x0)=0，执行以下步骤：
(1) 选取 x1，连接 x0与 x1使 w([x0,x1])尽可能地小。令 l(x1)=w([x0,x1]),X1={x0,x1}和
E1={[x0,x1]}。
(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为止。
前面讨论的树,都是无向图中的树,即无向树；下面将简单地介绍有向图中的树即有向树 。
定义 11.3.6 如果一个有向图的基础图是一棵树,则该有向图称为有向树 。 其图形表示法常采用倒置树表示之,且为方便计,有时略去边之方向 。
定义 11.3.7 给定一个有向树,若只有一个结点的入度是零,其余结点的入度都是 1,则称该树为有根树 。
在有根树中,入度为零的结点称为根或根结点,出度为零的结点称为叶或叶结点；出度不为零的结点称为分枝结点或内结点 。
定义 11.3.8 在有根树中,从根到某个结点的路长即该路中的弧数,称为该结点的级 。 其中结点的级的最大者,称为有根树的树高 。
由于有向树中没有回路,因此所有的路都是基本路 。 可见,从树中任何结点到另外一个结点的路长即是两结点的距离 。 故有根树的根结点的级是零；任何结点的级,等于从根到该结点的距离 。
在有向树中,结点的出现次序是没有意义的 。 但实际应用中,有时要给出同一级中结点的相对次序,这便导出有序树的概念 。
定义 11.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是 w的“祖先”，或称 w是 u的
“子孙”，同一个分枝结点的儿子称为“兄弟”。
在前面讨论的有根树或有序树中，其结点的出度未加任何限制。现在将依据结点出度的不同情况进行讨论。
定义 11.3.10 在有根树中，若每一个结点的出度都小于或等于 m，则称该树为
m叉树。若每一个结点的出度恰好等于 m
或等于 0，则称这种树为完全 m叉树。若所有的叶结点的级相同，则称正则 m叉树。
定义 11.3.11 在 m叉树中，如果对任何结点的 m个 (或少于 m个 )儿子都分别指定好 m个不同的确定位置，则称该树为位置叉树。
当 m=2时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点 v，至多有两个子树，分别称为 v的左子树和右子树。若 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叉树的各个结点 。
如前所叙，在任何位置二叉树的 0-1串表示中，其叶结点的串集合是个前缀码，即哈夫曼编码树对应着一个哈夫曼编码。不仅如此，还可以构造性证明其逆命题：
定理 11.3.13 任何一个前缀码都对应一棵位置二叉树的 0-1串表示，即哈夫曼编码对应一棵哈夫曼编码树。
有很多实际应用,可用二叉树或 m叉树表示 。 可以指出,按下面算法,任何一棵有序树均能表成二叉树 。 其算法是：
(1) 除最左边的分枝结点外,删去所有从每一个结点长出的分枝 。 在同一级中,兄弟结点之间用从左到右的弧连接 。
(2) 选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。
上述算法能够推广到有序森林上去 。
二叉树的一个重要应用就是最优树问题。
给定一组数 w1,w2,…,wn。令一棵二叉树有 n个叶结点，并对它们分别指派
w1,w2,…,wn作为权，则该二叉树称为加权二叉树。
定义 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树。
定理 11.3.14 设 T为加权 w1,w2,…,wn且
w1≤w2≤…≤ wn的最优树，则
(1) 加权 w1和 w2的叶结点 vw1和 vw2是兄弟。
(2) 以叶结点 vw1和 vw2为儿子的分枝结点，
它是所有分枝结点的级最高者。
定理 11.3.15 设 T为加权 w1,w2,…,wn且
w1≤w2≤… ≤wn的最优树,若将以加权 w1和 w2的叶结点为儿子的分枝结点改为加权 w1+w2的叶结点而得到一棵新树 T1,则 T1是最优树 。
根据上述两个定理,求一棵有 n个权的最优树,可简化为求一棵有 n-1个权的最优树,而这又可简化为求一棵有 n-2个权的最优树,依此类推 。 具体作法是：
首先找出两个最小的权值,设 w1和 w2。 然后对 n-1个权 w1+w2,w3,…,wn求作一棵最优树,并且将这棵树中的结 w1+w2代之以 w1 w2，
依此类推 。
11.4 平面图在一些实际问题中,要涉及到图的平面性的研究,比如大家都知道的印刷线路板的布线问题 。 近些年来,大规模集成电路的发展,进一步促进了图的平面性的研究 。 本节将简要地介绍平面图的概念,欧拉公式和平面图的着色 。
定义 11.4.1 一个无向图 G=<V,E>,如果能把它画在平面上,且除 V中的结点外,任意两条边均不相交,则称该图 G为平面图 。
下面给出一种判别平面图的直观方法 。
根据平面的定义,无圈的图显然是平面图 。
故,研究图的平面性问题,只需要限制有圈的一类图即可 。 判别方法是：
(1) 对于有圈的图找出一个长度尽可能大的且边不相交的基本圈 。
(2) 将图中那些相交于非结点的边,适当放置在已选定的基本圈内侧或外侧,若能避免除结点之外边的相交,则该图是平面图；否则,
便是非平面图 。
在图论中,称 K3,3和 K5是库拉图斯基图 。 这是因为波兰数学家库拉图斯基 (K.Kuratowski)于
1930年给出了的判别平面图充要条件 (后称库拉图斯基定理 )曾用到这两个图 。 下面就来介绍这一定理,不过它要用到两个图同胚的概念 。 可以看出,在给定图 G的任何一条边上插入一个度为 2的结点,使一条边成为两条边,或者涂抹图
G中度为 2的结点,使两条边成为一条边,这些都不会影响图的平面性 。
定义 11.4.2 若图 G2可由图 G1中的一些边上适当插入或涂抹度为 2的有限个结点后而得到，则称 G1与 G2同胚。
显然，任何两个基本圈是同胚的 。
定理 11.4.1 (库拉图斯基定理 )一个图 G是平面图?G中不含同胚于 K3,3或 K5的子图 。
该定理的证明是看来不算很难但是冗长的,
略去了,有兴趣读者可参见图论专著中的证明 。
库拉图斯基定理表述还是简明的,例如,
图 11.4.4(a)所示的图称为彼得森图,它是非平面图 。 因为当删去边 [v6,v8]和 [v3,v4]时,它成为含有同胚于 K3,3的子图,如图 11.4.4(b)或 (c)所示 。
图 11.4.5
下面介绍平面图中的重要的欧拉公式 。
定义 11.4.3 设 G为一平面图,若由 G的一条或多条边所界定的区域内部不含图 G的结点和边,
这样的区域称为 G的一个面,记为 f。 包围这个区域的各条边所构成的圈,称为该面 f的边界,
其圈的长度,称为该面 f的度,记为 d(f)。 为强调平面图 G中含有面这个元素,今后把平面图表为 G=<V,E,F>,其中 F是 G中所有面的集合 。
为方便有时把平面图 G的外部的无限区域当作一个面，称为无限面或外部面，其余的面称为有限面或内部面。
由定义不难证明下面定理：
定理 11.4.2 令 G=<V,E,F>是连通平面图，
则 。
定理 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。
推论 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。
下面讨论平面图的着色问题 。
平面图的着色问题,最早起源于地图的着色 。 在一张地图中,若相邻国家着以不同的颜色,那么最少需要多少种颜色呢？ 1840年,德国数学家麦比乌斯 (A.F.Mǒbius)在他的讲稿中第一次提出了确信用四种颜色可以对地图着色的问题 (以下简称四色猜想 )。 1879年肯普 (Kempe)
给出了这个猜想的第一个证明,但到 1890年希伍德 (Hewood)发现肯普证明是有错误的,然而他指出了肯普的方法虽不能证明地图着色用四种颜色就够了,但却可以证明用五种颜色是够的,即五色定理成立 。
在这里，研究的方法并不直接去考察地图着色问题，而是把它转化成平面图。为此，先给出对偶图的概念。
定义 11.4.4 给定平面图 G=<V,E,F>，且
f1,f2,…,fn∈ F。若有图 G*=<V*,E*>满足下列条件：
(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
的对偶图。
从对偶图的定义可以看出,若 G*=<V*，
E*>是平面图 G=<V,E,F>的对偶图,则 G也
G*的对偶图 。 一个连通平面图 G的对偶图 G*，
也是平面图,而且有
|E(G*)|=|E(G)|
|V(G*)|=|F(G)|
()=dG(fi) fi?F,?v*
其中 E(G)表示图 G的所有边集合，
F(G)表示图 G的所有面的集合。于是，可得到下面定理：
定理 11.4.4 若 G=<V,E,F>是平面图，
则 。
定义 11.4.5 若图 G的对偶图 G*同构于
G,则称 G是自对偶图 。
定理 11.4.5 若平面图 G=<V,E>是自对偶图,则 |E|=2(|V|-1)。
从对偶图的定义容易知道,对于地图的着色问题,可以化为一种等价的对于平面图的结点的着色问题 。 因此,四色问题可以归结为要证明：对任意平面图一定可以用四种颜色,对其结点进行着色,使得相邻结点都有不同颜色 。
平面图 G=<V,E>的着色 α是从结点集 V到色集 C={c1,c2,…,cn}上一个映射，使对任意边 [vi,vj]∈ E均有 α(vi)≠α(vj)，即对 G的每个结点指派一种颜色，使得相邻结点都有不同的颜色。
对于平面图 G着色时，需要的最少颜色数称为 G的着色数，记为 χ(G)。
定理 11.4.6 (五色定理 )对于任何简单平面图 G=<V,E>，均有 χ(G)≤5。
由此定理及对偶图定义,可得出下面定理 。
定理 11.4.7 任何地图 M,M是五着色的,即 χ(M)≤5。
自从四色猜想提出后，一百多年来，一直成为数学上的著名难题，它吸引许许多多的人，
为之而作出大量辛劳，也得到很多重要结果，
但长久未能得到解决。直到 1976年 6月，由美国伊利诺斯大学两名数学家爱普尔 (K.I.Apple)、
黑肯 (W.Haken)在考西 (J.Koch)帮助下借助于电子计算机，用了一百多亿次逻辑判断，花了
1200多机时才证明四色猜想是成立的，从此宣告，四色猜想成为四色定理。现将它叙述如下：
定理 14.4.8 (四色定理 )对于任何平面图 G，
有 χ(G)≤4。
相应地有下面的定理。
定理 14.4.9 对于任何地图 M,M是四着色的，即 χ(M)≤4。
