计算机数学基础离散数学辅导(6) .pdfVIP

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=V,E中V3,任意不同结点u,vG,deg(u)deg(v)V,则G是哈

密顿图.(充分条件，定理4)

(2)有向完全图D＝V,E,若V3，则图D是哈密顿图.(充分条件，定理5推论)

(3)设无向图G=V,E,VV，则P(G－V)V(必要条件，定理3)

111

VVPGVVG

若此条件不满足，即，使得(－),则一定不是哈密顿图(非哈密顿图

1!1

的充分条件).

3.平面图

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

面、边界和面的次数由连通平面图G的边围成的其内部不含G的结点和边的区域是

面，常用r表示.围成面的各边组成的回路是边界.边界回路的长度是面的次数，记作deg(r).

重要结论

r



(1)平面图GV,E,Vv,Ee,则deg(r)2e(所有面的次数之和＝边的2

i

i1

倍)(定理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不含与K或K在2度结点内同构的

335

，

子图.

4.树