图(graph)是一个包含顶点(vertices)及连结这些顶点的边(edges)之离散

2021年2月1日发(作者：口气大)

Hamilton circuit

劉繕榜

撰

在

1857

年，一位偉大的愛爾蘭數學家

Ha milton

專注於一個問題，就是一個

包含頂點（

< p>
vertices

）及連結這些頂點的邊（

edg es

）之圖形當中，在什麼條件之

下，從一個頂點出發，沿著邊 一筆畫通過所有在圖形中的頂點，而且這些頂點只

能通過一次（除了起始點）

< p>
，然後再回到起始的頂點，而形成一封閉的迴路

（

circuit

）？

為了紀念這位偉 大的數學家，像這種可以用一筆畫過所有的點，而且所有點

只能通過一次，最後回到起始 點的迴路，我們稱之為

Hamilton circuit

。在 我們認

識

Hamilton circuit

之前，我們先來看有關圖的知識。

< p>
圖

(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

）為

簡 單圖。

由上可知，一個簡單圖中，兩個頂點間最多只能有一個 邊，而且這個邊不具

有方向性。此外，不能有迴圈

（

< p>
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

< p>
和ν

2

之間有三個邊，所以亦不是簡單圖。

1