13
3
2
4
1
7
6
5
Gambar 2.5 Sebuah graf yang tidak berarah
2.2.3 Siklus Hamilton (Hamiltonian Cycle)
Sebuah
graf
G
=
(V,E)
yang
merupakan sebuah
graf
yang
terhubung
dengan
n
node,
dikatakan
sebagai
sebuah
Hamiltonian
Cycle
jika
dapat
membentuk
suatu
jalur
yang
melalui
n
buah
rusuk
pada
G
dan
mengunjungi
setiap
node
hanya
satu
kali
lalu
kembali
ke
node
awal.
Dengan
kata
lain
sebuah
graf
adalah
Hamiltonian Cycle
jika
dimulai
dari
suatu
node
vi
?
G
dan
semua
node
dalam
G
dikunjungi dengan
urutan
v1,
v2, ..., v
n+1
dengan rusuk-rusuk
yang menghubungkan verteks-verteks tersebut
merupakan anggota E
dalam G,
pada
i
=
i
=
n
dan semua v
i
berbeda kecuali v1 dan v
n+1
yang merupakan node yang sama.
Sir
William
Rowan
Hamilton
memasarkan
sebuah
teka-teki
pada
pertengahan
1800-an
dalam
bentuk
sebuah
dodecahedron
(lihat
Gambar
2.8).
Masing-masing sudut
yang
berjumlah
20
tersebut
diberi
nama
sebuah
kota
dan
masalahnya berawal
dari
sembarang
kota,
kemudian
menjalani
rusuk-rusuk,
mengunjungi
setiap
kota
tepat
satu
kali,
dan
kembali
ke
kota
semula.
Kita
sebut
siklus
dalam
graf
G
yang
mengandung
 |