第8章 几种特殊的图

本章讨论几种常见的特殊图，有欧拉图、哈密顿图、平面图、树和二分图。

一、基本要求

1. 了解欧拉通路(回路)、欧拉图的概念，掌握欧拉的判别方法(定理或一笔画)。

2. 了解哈密顿通路(回路)、哈密顿图的概念，知道哈密顿图的某些判别条件(一个必要条件和两个充分条件)。

3. 了解平面图的概念：平面图、面、边界、面的次数和非平面图。

掌握欧拉公式：v(点)+r(面)－e(边)=2

4. 知道四色可染问题。

5. 了解无向树、树叶、分支点、森林、平凡树、生成树以及生成树的补和最小生成树等概念；知道树的六个等价定义。

6. 了解有向树、根树、树根、子树、有序树、最优二元树等概念。

7. 知道带权二叉树、最优二叉树(哈夫曼树)的概念，知道最优二叉树的哈夫曼算法。

8. 知道二分图、完全二分图和匹配等概念和无向图是二分图的充分必要条件以及霍尔定理。

本章重点：欧拉图和哈密顿图、平面图和树的基本概念。

二、学习辅导

1. 欧拉图

h 欧拉回路与欧拉图 包含了图G的每一条边，且每条边仅出现一次的通路，就是欧拉通路。包含了图G的每一条边，且每条边仅出现一次的回路，就是欧拉回路。存在欧拉回路的图，就是欧拉图。

欧拉回路要求边不能重复，结点可以重复。笔不离开纸，不重复地走完所有的边，回到原处。就是所谓的一笔画。

h欧拉图的判定：

(1) 无向连通图G是欧拉图ÛG不含奇数度的结点(即G的所有结点的度均为偶数(0视为偶数))；(定理1)

(2) 非0平凡图G是欧拉图ÛG最多有两个奇数度的结点；(定理1的推论)

(3) 有向图D是欧拉图ÛD是连通的，且D的所有结点的入度等于出度。或除两个结点外，均出度等于入度，且这两点deg^－(v)－deg^＋(v)＝±1。 (定理2)

例6.1 判别图6－1的两幅图是否可以一笔画出？

解 (1) 在图6－1(a) 中，

deg(v₁)= deg(v₂) =deg(v₃)＝3

有两个以上的结点的度为3。故

在(a)中不存在欧拉回路，所以

不是欧拉图。不能一笔画出。

(b) 在图6－1(b) 中，

deg(A)=2,

deg(B) =deg(C)= deg(D)=4

deg(E) =deg(F)=3

只有两个奇数度的结点，具有

欧拉通路，是欧拉图。可以一笔画出。

例6.2 判定图6－2中，两个图是否有欧拉回路？若有请把欧拉回路写出来。

解 在图D中，v₁点的出度为2，入度为0，出度不等于入度，v₅的出度为0，入度为2，出度不等于入度，且这两点

出度与入度之差不等于±1，所

以，图D不具有欧拉回路，图

D不是欧拉图。

图M中，各个结点的出

度、入度都相等2，所以存

在欧拉回路，图M是欧拉图。

有一个欧拉回路为

v₁ a v₂ b v₃ f v₁ e v₃ c v₄ h v₂ g v₄ dv₁

2. 哈密顿图

h哈密顿通路与哈密顿回路 通过图G的每个结点一次，且仅一次的通路，就是哈密顿通路，通过图G的每个结点一次，且仅一次的回路，就是哈密顿回路。

h哈密顿图 存在哈密顿回路的图就是哈密顿图。

h哈密顿图的判别

(1) 在无向简单图G=<V,E>.中，，则G是哈密顿图；

(2) 有向完全图D＝<V,E>,若，则图D是哈密顿图。

例6.3 指出图6－3各图是

否哈密顿图，有无哈密顿通路，

回路？

解 (1) 有哈密顿回路，故

是哈密顿图。

(2) 只有哈密顿通路，无

哈密顿回路，故不是哈密顿图。

(3) 既无哈密顿通路，又无

哈密顿回路，当然不是哈密顿图。

例6.4 画出具有下列条件的有

5个结点的图。

(1) 没有哈密顿回路，也不能适当指定各边的方向，使其具有欧拉路；

(2) 有哈密顿回路，但是不能适当指定各边的方向，使其具有欧拉路；

(3) 没有哈密顿回路，但是能适当指定各边的方向，使其具有欧拉路；

(4) 有哈密顿回路，也能适当指定各边的方向，使其具有欧拉路。

解 作图如图6－4。

h h h h h h h

h h h h h

h h h h h h h h

(1) (2) (3) (4)

图6－4

在图(1)中，可以走遍5个点，但不是回路，无哈密顿回路，故不是哈密顿图。无论指定怎样的方向，可以走遍所有边，但不是回路，不能构成欧拉路。

在图(2)中，容易找出走遍5个点的回路，即有哈密顿回路，故是哈密顿图。但是构成回路，要么出现重复边，要么漏掉边，即不存在欧拉回路，因此不是欧拉图。

在图(3)中，不重复地走遍5个点是不可能的，故不是哈密顿图。如指定右边垂直边方向向上，就可以画出一个走遍所有的边，又不重复的回路，所以有欧拉回路，故是哈欧拉图。

在图(4)中 ，满足要求的条件是显然的。

3.平面图

h 平面图 一个图能画在平面上，除结点之外，再没有边与边相交。

面、边界和面的次数：由连通的平面图G的边围成的其内部不含G的结点和边的区域，是面。围成面的各边组成的回路，是边界。边界回路的长度是面的次数deg(r)。

h重要结论：

(1) (1) 平面图(所有面的次数之和＝边数的2倍)。

(2) (2) 欧拉公式：平面图面数为r，则(结点数与面数之和＝边数＋2)。

(3) (3) 平面图。

h判定条件：一个图是平面图G的充分必要条件是G不含与K_3，3或K₅在2度结点内同构的子图。

例6.5 判断图6－5中两个图是否为平面图？

解 G与K₅不同构，

结点度数不同。K₅所有

结点都是4次的。G有 v₁h h v¢₁

度数是3次的结点。且

没有子图与K₅在2度结 v₂h h v₃ v¢₂h v¢₆ h h v¢₃

内同构。G与K _3，3也不 v¢₇h hv¢₈

同构。K_3，3 结点度数都

是3。G有的结点度数 v₄h h v₅ v¢₄h h v¢₅

是4。只有一个结点度 G M

数是3，且没有子图在 图6－5

2度内与K_3，3同构。所以G是平面图。

图M与K_3，3在2度结点内同构，实质上是去掉2度结点v¢₄ ，v¢₅，而M¢恰与K_3，3同构。

同构映射是g：g(v¢₁)= v₆，g(v¢₁)= v₆,g(v¢₇) =v₄,g(v¢₆)=v₃, g(v¢₈)=v₂, g(v¢₃)= v₁。故M不是平面图。

4. 树

h树 连通无回路的无向图。

h树的判别 图，是树的充分必要条件是：

① G是无回路的连通图；

② 无回路，且m＝n－1；

③ 连通且m＝n－1

④ 无回路，若增加一条边，就得到一条仅一条回路；

⑤ 连通，若删去任一边，G则不连通；

⑥ 每一对结点之间有一条且仅有一条通路。

h生成树 图G的生成子图是树，该树就是生成树。

生成树的破圈求法和避圈求法。

h权 n个结点的连通图G，每边指定一正数，称为权，G的生成树T的每边权之和是生成树T的权。

h最小生成树 带权最小的生成树。

h有向树 有向图删去边的方向为树，那么原有向图就是有向树。

h根树与树根 非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树。

h二叉树(二元树) 每个结点的出度均小于或等于2的根树。

h哈夫曼树 用哈夫曼算法得到的最优二叉树。

h 方法：

生成树的破圈法和避圈法求法；

最小生成树的克鲁斯克尔求法；

哈夫曼树的哈夫曼求法。

例6.6 在具有n个结点的完全图K_n中，需要删去多少条边才能得到树。

解 n个结点的完全图共有条边，而n个结点的树共有n－1条边。因此需要删去

条边后方可得到树。

例6.7 设G是图，无回路，但若外加任意一条边于G后，就形成一回路。试证明G必为树。

证明 由树的定义可知，只需证G连通即可。任取不相邻两点u,v,由题设，加上边<u,v>就形成一回路，于是去掉边<u,v>,从u到v仍有路u,…,v，即u,v连通，由u,v的任意性可知，G是连通的，故G必是树。

例6.8 将图6－6给出的三元树转化为二

元树。

解 (1)对每个结点只保留它的最左分支，

删去其它分支；如图6－7(1)；

(2) 在同一级上的结点，从左到右用边

连结起来；如图6－7(2);

(3) 对任一结点选定在该结点下的结点为它的左儿子，在该结点右边的为它的右儿子；

(4) 将结点的左儿子画在结点的左下方，右儿子画在结点的右下方。

如图6－7为所求。

5. 二分图

h定义 无向图G＝<V,E>,存在，任意

则(偶图)。

h判定方法： 图G是的充分必要条件是图G的所有回路的长度均为偶数。

h完全二分图 若，V₁的每一个结点与V₂的每一个结点仅有一条边相关联。记作K_n,m，。

h匹配 图G＝<V,E>，，使得E^*的任意两条边都不相邻，E^*是G的一个匹配。

例 6.9 完全二分图K_n,m=<V₁,V₂,E>中共有多少条边？有多少个结点？

解 由于V₁的每一个结点与V₂的每一个结点仅有一条边相关联，所以V₁的每一个结点与关联条边。而V₁中有n个结点，因此K_n,m共有nm条边。有n+m个结点。

例10 图6－8所示，是否二分图？若是，试写出

它的互补结点集。

解 是二分图。其中

与是它的互补结点集。

三、实例

例1 无向图G是欧拉图，当且仅当( )

(A) (A) G的所有结点的度数全为偶数 (B) G的所有结点的度数全为奇数

(C) G连通且所有结点的度数全为偶数 (D) G连通且所有结点的度数全为奇数

答案：(C)

解答：见本章定理1。

例2 设为连通平面图且有r个面，则r＝( )

(A) m－n+2 (B) n－m－2 (C) n+m-2 (D) m+n+2

答案：(A)

解答：见定理7，欧拉公式。

例3 设G是由5个结点组成的完全图，则从G中删去( )条边可以得到树。

(A) 4 (B)5 (C)6 (D)10

答案：(C)

解答：删去边的公式为。故选择(C)正确。

例4 由5个结点可构成的根树中，其叉数m最多为( )

(A) 2 (B) 3 (C) 5 (D) 4

答案：(D)

解答：在非平凡有向树中，一个结点出度为0，那么就有4个结点的入度为1，使得5个结点，每点的出度小于或等于4,故m最大为4。选择(D)正确。

例5 图6－9是( )

(A) 完全图 (B) 哈密顿图

(C) 欧拉图 (D) 平面图

答案：(B)

解答：因为n=6,每对结点度数之和

大于或大于6，满足存在哈密顿回路的

条件，故为哈密顿图。选择(B)正确。

例6 设G是完全二叉树，G有15个

结点，其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数是 。

答案： 14； 28； 7； 6。

解答：有8个树叶，15个解答的完全二叉树，

如图6－10。

例7 无孤立点的有向图G含有欧拉回路

的充分必要条件是

答案：G中每个结点的入度＝出度。

解答：见欧拉回路的判断方法，定理2。

例8 设G是有n个结点的简单图，若G中每对结点的度数之和 ，则G一定是哈密顿图。

答案：大于或等于n

解答：见定理4。

例9 无向图G具有生成树，当且仅当 ，若G是有n个结点，m条边的连通图，要确定G的一颗生成树，必须删去G的 条边。

答案：G连通；m+1－n

解答：见生成树的破圈或避圈求法。

例10 一个有向树T称为根树，若 ，其中 ，称为树根，

称为树叶。

答案：若有向图T恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；入度为1的结点。

解答：见根树、树根、树叶的定义。

例11 在图6－11中，哪些是二分图？哪些是欧拉图？哪些是哈密顿图？哪些是平面图？

(6)

图6－11

解 (1) 中存在长度为奇数的回路，所以它不是二分图。删去结点u,v，得到V的三个连通分支，所以它不是哈密顿图。由于它是连通的，且无奇数度结点，所以它是欧拉图，显然是平面图。

(2) 中无长度为奇数的回路，所以它是二分图。也是平面图。由于它非连通，所以它不是欧拉图，也不可能是哈密顿图。

(3) 中无长度为奇数的回路，所以它是二分图。也是平面图。因为无回路，所以它不是欧拉图，也不是哈密顿图。

(4) 中无长度为奇数的回路，所以它是二分图。也是平面图。因为奇数度的结点超过二个，所以不是欧拉图，而是哈密顿图。

(5) 中存在长度为奇数的回路，所以它不是二分图。但是平面图。因为无奇数度的结点，所以是欧拉图，又因为可以找到一条哈密顿回路，所以是哈密顿图。

(6) 中无长度为奇数的回路，所以它是二分图。但不是平面图。它又奇数度的结点，所以它不是欧拉图，也不是哈密顿图。