1
《计算机数学基础》离散数学辅导(6)
??第6章 几种特殊的图(2001级用) 中央电大 冯 泰
本章重点：欧拉图和哈密顿图、平面图和树的基本概念.
一、重点内容
1. 欧拉图 ? 欧拉通路(回路)与欧拉图 通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路). 存在欧拉回路的图就是欧拉图.
欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，且走过所有结点，就是所谓的一笔画.
?欧拉图或通路的判定 (1) 无向连通图G是欧拉图?G不含奇数度结点(G的所有结点度数为偶数):(定理1) (2) 非平凡连通图G含有欧拉通路?G最多有两个奇数度的结点；(定理1的推论) (3) 连通有向图D含有有向欧拉回路(即欧拉图)?D中每个结点的入度＝出度
连通有向图D含有有向欧拉通路?D中除两个结点外，其余每个结点的入度＝出度，
－＋
且此两点满足deg(u)－deg(v)＝?1. (定理2) 2. 哈密顿图
?哈密顿通路(回路)与哈密顿图 通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图.
判断哈密顿图是较为困难的.
?哈密顿图的充分条件和必要条件 (1) 在无向简单图G=
(2) 有向完全图D＝
若此条件不满足，即?V1?V，使得P(G－V!)>?V1?,则G一定不是哈密顿图(非哈密顿图的充分条件).
3.平面图
? 平面图 一个图能画在平面上，除结点之外，再没有边与边相交.
面、边界和面的次数 由连通平面图G的边围成的其内部不含G的结点和边的区域是面，常用r表示. 围成面的各边组成的回路是边界. 边界回路的长度是面的次数，记作deg(r).
?重要结论
(1)平面图G??V,E?,V?v,E?e,则倍)(定理6).
(2)欧拉公式：平面图G??V,E?,V?v,E?e, 面数为r，则v?e?r?2(结点数与面数之和＝边数＋2)(定理7)
(3)平面图G??V,E?,V?v,E?e,若v?3，则e?3v?6(定理8)
?判定条件：图G是平面图的充分必要条件是G不含与K3，3或K5在2度结点内同构的子图. 4. 树
?树 连通无回路的无向图.
?树的判别 图T??V,E?,V?n,E?m,T是树的充分必要条件是(六个等价定义)
?deg(r)?2e(所有面的次数之和＝边的
ii?1r2
2
(定理14):
(1) T是无回路的连通图； (2) 图T无回路且m＝n－1； (3) 图T连通且m＝n－1
(4) 图T无回路，若增加一条边，就得到一条且仅一条回路； (5) 图T连通，若删去任一边，G则不连通；
(6) 图T的每一对结点之间有一条且仅有一条通路. ?生成树 图G的生成子图是树，该树就是生成树.
?权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T的所有边的权之和是生成树T的权，记作W(T).
?最小生成树 带权最小的生成树.
?有向树 有向图删去边的方向为树，该有向图就是有向树.
?根树与树根 非平凡有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树. ?每个结点的出度小于或等于2的根树为二元树(二叉树)；每个结点的出度等于0或2的根树为二元完全树(二叉完全树)；每个结点的出度等于2的根树称为正则二元树(正则二叉树).
?哈夫曼树 用哈夫曼算法得到的最优二叉树. 4. 有关树的求法
v4? ?v5 E? ? F ?生成树的破圈法和避圈法求法；
?最小生成树的克鲁斯克尔求法；
? ?哈夫曼树的哈夫曼求法.
A 二、实例
v2? ? v3 B? ? C 例6.1 判别图6－1的两幅图
?v1 ? D 是否可以一笔画出？
（a） (b) 解 在图6－1(a) 中， 图6－1 deg(v1)=deg(v2)=deg(v3)＝3
有两个以上的结点的度为3. 故在(a)中不存在欧拉通路，不能一笔画出. 在图6－1(b) 中，deg(A)=2, deg(B) =deg(C)= deg(D)=4，deg(E) =deg(F)=3
只有两个奇数度的结点，所以存在欧拉通路，可以一笔画出. 一条欧拉通路，如EDBEFCABCDF. 例6.2 判定图6－2中，两个图是否有欧拉回路？若有请把欧拉回路写出来.
v1? 解 在图D1中，v1点的出度为2，
v1? d ? v4
入度为0； v5的出度为0，入度为2，
v2? ? v5 f h 且这两点出度与入度之差不等于?1，
a g e c
所以，图D1不存在欧拉通路，图D1
v3 ? ? v4 v2 ? b ? v3
不是欧拉图.
D1 D2
图D2中，各个结点的出度、入度
图6－2
都相等2，所以存存欧拉回路，图D2
是欧拉图. 一个欧拉回路为v1 a v2 b v3 f v1 e v3 c v4 h v2 g v4 dv1 例6.3 指出图6－3各图是否哈密顿图，有无哈密顿通路， 回路？ 解 (1) 容易判断，存在哈密顿回路，故是哈密顿图.
(2) 只有哈密顿通路，无哈密顿回路，故不是哈密顿图. (3) 无哈密顿通路，显然不是哈密顿图. 例6.4 画出具有下列条件的有5个结
? ? ? ? ? ? ? ? ? ? ? ? ? ?
3
点的无向图.
(1) 不是哈密顿图，也不是欧拉图； (2) 有哈密顿回路，没有欧拉回路； (3) 没有哈密顿回路，有欧拉回路； (4) 是哈密顿图，也是欧拉图. 解 作图如图6－4(不唯一).
? ? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ? ? ? (1) (2) (3) (4) 图6－4
例6.5给定三个图如图6－5所示，试判断它们是否为欧拉图、哈密顿图、或平面图？并说明理由，
a b c d
e f g 图G1 图G2 图G3 图6－5
解 图G1是欧拉图，因为每个结点度数均为偶数． 图G2是哈密顿图，存在哈密顿回路，如cdgfebac． (不惟一) 图G3是平面图．可以改画成可平面图，如图6－7．
例6.6 在具有n个结点的完全图Kn中，需要删去
多少条边才能.得到树？ 图6－7
解 n个结点的完全图共有????条边，而n个结点的树共有n－1条边. 因此需要删去
?n??2??n?(n?1)(n?2)? ? ?(n?1)??2?2??条边后方可得到树.
例6.7 设G是图，无回路，但若外加任意一条边于G后，就形成一回路. 试证明G必为树. 证明 由树的定义可知，只需证G连通即可. 任取不相邻两点u,v, 由题设，加上边
b ?
G是连通的，故G必是树.
23 1 15 例6.8 如图6－8是有6个结点a,b,c,d,e,f
c? 25 ? a 4 ? f
的带权无向图，各边的权如图所示. 试求
28 9 16 3 其最小生成树.
d ? 15 ? e
解 构造连通无圈的图，即最小生成树，
图6－8
.用克鲁斯克尔算法：
b ? 23 1
c? ? a 4 ? f 9 3 d ? ? e
4
第一步： 取ab＝1；第二步： 取af=4；第三步： 取fe=3；第四步： 取ad=9；第五步： 取bc=23. 如图6－9. 权为1+4+3+9+23=30 例6.9 单项选择题
1.无向图G是欧拉图，当且仅当( ) (A)G的所有结点的度数为偶数 (B) G的所有结点的度数为奇数
(C) G连通且所有结点的度数为偶数 (D) G连通且所有结点的度数为奇数 答案：(C) 解答：见本章定理1.
2. 设G??V,E?,V?n,E?m为连通平面图且有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)
?n?(n?1)(n?2)?解答：删去边的公式为?. 故选择(C)正确. ?(n?1)??2?2??4. 在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。
(A) 2 (B) 3 (C) 5 (D) 4
答案：(B) 解答：二元完全树，即每个结点只有0个或2树枝的树，树根必有2个树枝，于是2个树枝只能其一又有2个树枝，而另一个就无树枝. 满足5个结点4条边. 可见有3片树叶. 选择(B)正确. 一般地，在二元完全树中，有m条边，t片树叶，则有m=2(t－1) 5. 图6－10是( ) (A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图 答案：(D)
? ? ?
解答：因为n=6, 每对结点度数之和 大于或大于6，满足存在哈密顿回路的条 件，故为哈密顿图. 选择(D)正确. 例6.10 填空题
? ? ?
1.设G是完全二叉树，G有15个结点， 图6－10
其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数是 . 答案： 14； 28； 7； 6. 解答：可画图如图6－11. 有8个树叶，15个结点的完全二叉树，
? 2. 连通有向图D含有欧拉回路
? ? 的充分必要条件是
? ? ? ? 答案：D中每个结点的入度＝出度.
????????
解答：见欧拉回路的判断方法，定理2.
图6－11
3. 设G是n个结点的简单图，若G中每对结点的度数之和 ，则G一
定是哈密顿图.
5
边.
答案：大于或等于n 解答：见定理4. 4.设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的 条答案：m－n+1 解答：见生成树的破圈或避圈求法.
5. 一个有向树T称为根树，若 ，其中 ，称为树根， 称为树叶. 答案：若有向图T恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；入度为1的结点. 解答：见根树、树根、树叶的定义. 三、练习题
1. 在图6－12中，哪些是欧拉图？哪些是哈密顿图？哪些是平面图？
?u ? ? ? ?
? ? ? ? ?
?v ? ? ? ? ? (1) ? ? ? ? ? ? (3)
(2)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (4) ? (5)
(6) 图6－12
2. 设G是平面图，并且G的所有面的次数均为3，证明
e??v??
其中e是G的边数. v是G的结点数. 3. 设G是无向图，如图 a 3 d 6－13，说明G不 1 2 是欧拉图； 4. 求带权图，如图 e 6－14的最小生成树. 5 3 4 6 5.将平面图G1，G2(如图6－ b 1 c －15) 改写成不相交的形式. 图6－13 图6－14 6. 已知有向图D的邻接矩阵为
? ? ? ? ?00000??10110? ? ? ?? ?10000? ? ? ?
?? ? ? ? ? 00100?? G1 G2 ??00000?? 图6－15
计算机数学基础离散数学辅导(6)
