-
Hamilton circuit
劉繕榜
撰
在
1857
年，一位偉大的愛爾蘭數學家
Ha
milton
專注於一個問題，就是一個
包含頂點（
vertices
）及連結這些頂點的邊（
edg
es
）之圖形當中，在什麼條件之
下，從一個頂點出發，沿著邊
一筆畫通過所有在圖形中的頂點，而且這些頂點只
能通過一次（除了起始點）
，然後再回到起始的頂點，而形成一封閉的迴路
（
circuit
）？
為了紀念這位偉
大的數學家，像這種可以用一筆畫過所有的點，而且所有點
只能通過一次，最後回到起始
點的迴路，我們稱之為
Hamilton circuit
。在
我們認
識
Hamilton
circuit
之前，我們先來看有關圖的知識。
圖
(graph)
是一個包含頂點（
vertices
）及連結這些頂點的邊（
edge
s
）之離散
結構（
discrete
structures
）
。以
G=
（
V
,E
）表示，
其中
V
表在
G
中所有頂點的集
合，而
E
則為在在
G
中所有邊的集合。我們首先定義一個集合，如下：
R
?
{(
< br>u
,
v
)
u
,
v
?
V
,
u
?
v
}
然後我們再定義一個從
E
到
R
的函數
F
。即若
F(
ε
i
)=(u,v)
，則表ε
i
連接在
V
中
u
和
v
頂點的邊。
< br>在數學中，圖可分為許多種，其中最基本的是「簡單圖」
（
simple graph
）
。
<
/p>
定義Ⅰ：令
V={
ν
1,
ν
2,…,
ν
n
}
，
E={
ε
1,
ε
< br>2,…,
ε
k
}
。其中ε
i
為
V
中兩個不同
頂點間不具有方向性的邊，且
F(
ε
i
)=
F(
ε
j
)
，
1
≦
i
≠
j
≦<
/p>
k
，則稱
G=
（
V
,E
）為
簡
單圖。
由上可知，一個簡單圖中，兩個頂點間最多只能有一個
邊，而且這個邊不具
有方向性。此外，不能有迴圈
（
loop
）
的情況，即一個邊的兩個頂點是不一樣
的。
ν
1
ν
4
ν
1
ν
3
ν
2
ν
3
ν
2
（
G
1
）
（
G 2
）
上圖的（
G1
）和（
< br>G2
）為簡單圖。
ν
1
ν
4
ν
1
ν
4
ν
3
ν
2
ν
2
ν
3
ν
2
ν
3
ν
1
（
G 3
）
（
G
4
）
（
G 5
）
上圖的（
G 3
）
，其邊有方向性，所以不是簡單圖；而（
G 4
）中ν
1,
ν
2
有迴
圈，所以不是簡單圖；在
（
G 5
）
中ν
1
和ν
2
之間有三個邊，所以亦不是簡單圖。
1
-
-
-
-
-
-
-
-
-
上一篇：教师用英语单词拼读规则
下一篇：当代研究生英语读写教程上下册课文译文