文档介绍：第四章 Euler 图和 Hamilton 图
§1. Euler 图
一、基本概念
七桥问题:如下图。从任一陆地点出发,经过每座桥一次且仅一次回到出发点,是否可能?

⇒

哥尼斯堡七桥 G

转化为图论问题:图 G 中从任一顶点出发,经过每条边恰好一次回到出发点,是否可能?
Euler 环游(tour,circuit,closed trail):经过图 G 的每条边恰好一次的闭迹。
Euler 迹(trail):经过每条边恰好一次的迹。
Euler 图:有 Euler 环游的图。
七桥问题:图 G 是否 Euler 图?
二、Euler 图的判定
定理一个非空连通图是 Euler 图当且仅当它没有奇度顶点。
证明必要性:设图 G 是 Euler 图,C 是 G 中一个 Euler 环游。对∀v ∈V (G) ,v 必在 C 上
出现。因 C 每经过 v 一次,就有两条与 v 关联的边被使用。设 C 经过 v 共 k 次,则 d(v) = 2k 。
充分性:无妨设ν(G) > 1 。因 G 连通,故至少有一条边。下面用反证法证明充分性结论。
假设图 G 无奇度顶点,但它不是 Euler 图。令
S={G|G 至少有一条边,无奇度顶点,且不是 Euler 图}
则 S ≠φ。取 S 中边数最少的一个,记为 G′。因δ(G′) ≥ 2 ,故 G′含有圈,因而含有闭迹。
设 C 是 G′中一条最长的闭迹。由假设,C 不是 G′的 Euler 环游。因此 G′\ E(C) 必有一个
连通分支至少含有一条边。记这个连通分支为 G0 。由于 C 是闭迹,故 G0 中没有奇度顶点,
且ε(G0 ) < ε(G′) 。由 G′的选择可知,G0 必有 Euler 环游C0 。由于 G′连通,故 C 必经过 G0
中至少一个顶点,从而。因此是的一条闭迹,且
V (C) IV (C0 ) ≠φ C + C0 G′
ε(C + C0 ) > ε(C) ,这与 C 的选取矛盾。证毕。
1
充分性的另一种证法(数学归纳法):
无妨设ν(G) > 1 。因 G 连通且无奇度顶点,故δ(G) ≥ 2 ,因而必含有圈。
当ν(G) = 2 时,设仅有的两点为 u,v,则 u,v 间必有偶数条边,它们显然构成 Euler 回路。
假设ν(G) = k 时,结论成立。
当时,任取。令的所有关联边。记中的边为,
ν(G) = k + 1 v ∈V (G) S = {v } S e1, e2 ,Lem
其中 m = d(v) 为偶数。记 G′= G \ v 。对 G′作如下操作:
(1) 任取 ei , e j ∈ S ,设 ei = vi v , e j = v j v ;
(2) G′:= G′+ vi v j , S := S \ {ei , e j } ;
(3) 若 S = φ,则令 G′:= G′− v ,停止;否则转(1)继续。
这个过程最终得到的 G′有 k 个顶点,且每个顶点在 G′中的度与在 G 中完全一样。由归纳假
设,G′中有 Euler 环游,设为 P。将 P 中上述添加边 vi v j 都用对应的两条边 ei , e j