欧拉图和哈密顿图

欧拉图：欧拉图是一笔画出的边不重复的回路.

1. 定义

2. 无向欧拉图的判别法

定理15.1

无向图G是欧拉图当且仅当G连通且无奇度数顶点

.

定理15.2

无向图G是半欧拉图当且仅当G连通且恰有两个奇度

数顶点.

3．有向欧拉图的判别法

定理15.3 有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.

定理15.4 有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.

定理15.5 G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并.

4. Fleury算法

哈密顿图

1. 定义：哈密顿图是周游世界问题.

2. 无向哈密顿图的一个必要条件

定理15.6 设无向图G=<V, E>是哈密顿图，对于任意V1ÌV且V1¹Æ，均有

p(G-V1) £ |V1|

推论 设无向图G=<V, E>是半哈密顿图，对于任意的V1ÌV且V1 ¹ Æ，均有

p(G-V1) £ |V1|+1

3．无向哈密顿图的一个充分条件

定理15.7 设G是n阶无向简单图，若对于任意不相邻的顶点vi, vj，均有

d(vi)+d(vj) ³ n-1 (*)

则G中存在哈密顿通路.

推论 设G为n（n³3）阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有

d(vi)+d(vj) ³ n （**）

则G中存在哈密顿回路，从而G为哈密顿图.

定理15.8 设u,v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)³n，则G为哈密顿图当且仅当GÈ(u,v)为哈密顿图.

4．n（n³2）阶竞赛图中存在哈密顿通路

定理15.9 若D为n（n³2）阶竞赛图，则D中具有哈密顿通路

几点说明：

Ø规定平凡图为欧拉图也是哈密顿图；

Ø欧拉通路是生成的简单通路，欧拉回路是生成的简单回路. 而哈密顿通路是初级通路，哈密顿回路是初级回路；

Ø环不影响图的欧拉性也不影响哈密顿性，平行边不影响哈密顿性；

Ø哈密顿图的实质是能将图中的所有顶点排在同一个圈上。