11.1
11.1
欧拉图与哈密尔顿图
欧拉图与哈密尔顿图
1736
1736
年瑞士数学家欧拉发表了图论的第一
年瑞士数学家欧拉发表了图论的第一
篇著名论文“哥尼斯堡七桥问题”
篇著名论文“哥尼斯堡七桥问题”
(
(
下称七桥问
下称七桥问
题
题
)
)
。这个问题是这样的：哥尼斯堡城有一条横
。这个问题是这样的：哥尼斯堡城有一条横
贯全城的普雷格尔河，城的各部分用七桥联结，
贯全城的普雷格尔河，城的各部分用七桥联结，
每逢节假日，有些城市居民进行环城周游，于
每逢节假日，有些城市居民进行环城周游，于
是便产生了能否“从某地出发，通过每桥恰好一
是便产生了能否“从某地出发，通过每桥恰好一
次，在走遍了七桥后又返回到原处”的问题。
次，在走遍了七桥后又返回到原处”的问题。
在图
在图
11.1.1
11.1.1
画出了哥尼斯堡城图，城的四块
画出了哥尼斯堡城图，城的四块
陆地部分以
陆地部分以
A
A
，
，
B
B
，
，
C
C
，和
，和
D
D
标记。欧拉巧妙地
标记。欧拉巧妙地
把哥尼斯堡城图化为图
把哥尼斯堡城图化为图
11.1.2
11.1.2
所示图
所示图
G
G
，他把陆
，他把陆
地设为图
地设为图
G
G
中的结点，把桥画成相应地联结陆地
中的结点，把桥画成相应地联结陆地
即结点的边。于是，通过哥尼斯堡城中每座桥恰好
即结点的边。于是，通过哥尼斯堡城中每座桥恰好
一次问题，等价于在图
一次问题，等价于在图
G
G
中从某一结点出发找出
中从某一结点出发找出
一条链，它通过每条边恰好一次后回到原出发结点，
一条链，它通过每条边恰好一次后回到原出发结点，
亦即等价于在图
亦即等价于在图
G
G
中寻找一个圈，它通过
中寻找一个圈，它通过
G
G
中每
中每
一条边恰好一次。
一条边恰好一次。
