1、7.4 欧拉图与汉密尔顿图 7.4.1 欧拉图 7.4.2汉密尔顿图 7.4.1 欧拉图 历史上的哥尼斯堡七桥问题是著名的图论问题。 问题是这样的： 18世纪的东普鲁士有个哥尼斯堡城， 在横贯全城的普雷格尔河两岸和两个岛之间架设了 7座桥， 它们把河的两岸和两个岛连接起来（如图7.4.1）。 每逢假日， 城中居民进行环城游玩， 人们对此提出了一个 “遍游 ”问题， 即能否有这样一种走法， 使得从某地出发通过且只通过每座桥一次后又回到原地呢？ 我们将图 7.4.1中的哥尼斯堡城的 4块陆地部分分别标以 A， B， ， D， 将陆地设想为图的结点， 而把桥画成相应的连接边， 这样图 7.4.1可简
2、化成图7.4.2。 于是七桥 “遍游 ”问题等价于在图 7.4.2中， 从某一结点出发找到一条回路， 通过它的每条边一次且仅一次， 并回到原来的结点。 图 7.4.1哥尼斯堡七桥问题示图 图 7.4.2哥尼斯保七桥问题简化图 定义 7.5.1 给定无孤立结点的图 G， 若 存在一条 经过 G中 每边一次且仅一次 的回路， 则该回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 例如， 给出如图 7.4.3所示的两个图， 容易看出， (a)是欧拉图， 而 (b)不是欧拉图。 图 7.4.3 定理 7.5.1 连通图 G是欧拉图的 充要条件 是 G的所有结点的度数都是偶数。 证明 : 必要性： 设 G
3、是一欧拉图， 是 G中的一条欧拉回路。 当 通过 G的任一结点时， 必通过关联于该点的两条边。 又因为 G中的每条边仅出现一次， 所以 所通过的每个结点的度数必定是偶数。 图 7.4.4 图 G 充分性： 我们可以这样来作一个闭迹 ， 假设它从某结点 A开始， 沿着一条边到另一结点， 接着再从这个结点， 沿没有走过的边前进， 如此继续下去。 因为我们总是沿着先前没有走过的新边走， 又由于图 G的边数有限， 所以这个过程一定会停止。 但是， 因为每一个结点都与偶数条边关联， 而当沿 前进到达结点 v 时， 若vA， 走过了与 v关联的奇数条边， 这样在 v上总还有一条没有走过的边。 因此， 必定返回停止在 A（见图 7.4.4）。
