第四章 Euler图和 Hamilton图 S4.1 Euler图 基本概念 通常认为,图论见诸于文献的起始研究之一是瑞士数学家欧拉关于七桥问题的研究。在 世纪普鲁士的哥尼斯堡城( Konigsberg),普雷格尔( Pregel)河穿城流过,河中有两个河 心岛,有七座桥将小岛与河岸连接起来(如下图)。有市民尝试从河岸或岛屿的任一陆地点 出发,经过每座桥一次且仅一次回到出发点,但一直未能获得成功。人们怀疑,这样的走法 是否存在?这便是七桥问题。 哥尼斯堡七桥 1741年,欧拉经过对七桥问题的研究,发表了第一篇有关图论的论文,从而使七桥问 题闻名于世。欧拉将四块陆地用平面上四个点来表示,两块陆地间有一座桥相连,就在两个 相应的点间连一条边,最终获得如图1所示的一个图G。于是七桥问题转化为一个图论问题: 图G中从任一顶点出发,经过每条边恰好一次回到出发点,是否可能? 为了进一步的讨论,我们需要定义如下术语 Euler闭迹( closed trail,tour, circuit):经过图G的每条边恰好一次的闭迹 Euler迹(trai):经过每条边恰好一次的迹 Euler图:有 Euler闭迹的图 利用这些术语,七桥问题可叙述为:图1中的图G是否为 Euler图?欧拉对此做出了否 定的回答。事实上,欧拉研究了更一般的情况,获得了任意一个图是否为欧拉图的判定条件 、Euer图的判定 定理411一个非空连通图是Euer图当且仅当它没有奇度顶点。 证明必要性:设图G是 Euler图,C是G中一个 Euler闭迹。对vv∈V(G),v必在C上 出现。因C每经过v一次,就有两条与v关联的边被使用。设C经过v共k次,则d(v)=2k。 充分性:无妨设v(G)>1。因G连通,故至少有一条边。下面用反证法证明充分性结论。 假设图G无奇度顶点,但它不是 Euler图。令 G|G至少有一条边,无奇度顶点,且不是 Euler图}1 第四章 Euler 图和 Hamilton 图 §4.1 Euler 图 一、基本概念 通常认为，图论见诸于文献的起始研究之一是瑞士数学家欧拉关于七桥问题的研究。在 18 世纪普鲁士的哥尼斯堡城（Königsberg），普雷格尔（Pregel）河穿城流过，河中有两个河 心岛，有七座桥将小岛与河岸连接起来（如下图）。有市民尝试从河岸或岛屿的任一陆地点 出发，经过每座桥一次且仅一次回到出发点，但一直未能获得成功。人们怀疑，这样的走法 是否存在？这便是七桥问题。 ⇒ 哥尼斯堡七桥 图 1 1741 年，欧拉经过对七桥问题的研究，发表了第一篇有关图论的论文，从而使七桥问 题闻名于世。欧拉将四块陆地用平面上四个点来表示，两块陆地间有一座桥相连，就在两个 相应的点间连一条边，最终获得如图 1 所示的一个图 G。于是七桥问题转化为一个图论问题： 图 G 中从任一顶点出发，经过每条边恰好一次回到出发点，是否可能？ 为了进一步的讨论，我们需要定义如下术语。 Euler 闭迹(closed trail, tour, circuit)：经过图 G 的每条边恰好一次的闭迹。 Euler 迹（trail）：经过每条边恰好一次的迹。 Euler 图：有 Euler 闭迹的图。 利用这些术语，七桥问题可叙述为：图 1 中的图 G 是否为 Euler 图？欧拉对此做出了否 定的回答。事实上，欧拉研究了更一般的情况，获得了任意一个图是否为欧拉图的判定条件。 二、Euler 图的判定 定理 4.1.1 一个非空连通图是 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 图}