graf hamilton

PENGERTIANSebuah sikel yang memuat semua simpul

suatu graf disebut Sikel Hamilton.Jika graf G memuat sikel Hamilton, maka graf

G disebut Graf Hamilton.Sebuah lintasan yang memuat semua simpul

graf disebut Lintasan Hamilton. Sebuah graf tidak Hamilton yang memuat

lintasan Hamilton disebut Graf Semi Hamilton.

CONTOHGraf G berikut ini merupakan graf Hamilton,

karena memuat sikel Hamilton, yaitu: (A, B, C, E, D, A)

A

D

B C

E

G

CONTOH

Graf G1 berikut ini merupakan graf Semi Hamilton, karena memuat lintasan Hamilton, yaitu: (A, C, B, D)

A

B D

C

G1

CONTOHGraf berikut bukan graf Hamilton dan bukan

graf semi hamilton

A

B

C

D

E

Apakah graf berikut ini graf hamilton?

Sikel hamilton yang dibentuk salah satunya adalah a-b-c-d-h-m-i-o-j-p-f-k-q-r-t-u-s-l-g-e-a

a

b

cd

e

f

gk

h i

j

l

m

o

p

q r

s tu

BACK

Apakah graf berikut graf hamilton????

a

b c

de

fg h

i j

k

APAKAH GRAF DI SAMPING GRAF HAMILTON?

Jika tidak, APAKAH GRAF DISAMPING GRAF SEMI HAMILTON??

Graf di samping adalah semi hamilton dengan jalurd-a-h-k-j-g-c-f-b-e-i

BACK

Graf disamping bukan graf hamilton dan bukan graf semi hamilton

Jika G graf sederhana dengan n ≥ 3 simpul

dan

maka G graf Hamilton.

Teorema 5.1 (Teorema Dirac)(Syarat Perlu)

GVvn

vd ,2

)(

Syarat perluAnda harus sadar bahwa pernyataan dalam Teorema

5.1 itu adalah syarat perlu, bukan syarat perlu dan

cukup. Artinya, mungkin saja suatu graf G dengan n = 5

dan d(v) = 2 untuk setiap v di G adalah graf Hamilton,

umpamanya ‘segi lima’ dalam geometri adalah graf

dengan n = 5, dan d(v) = 2 < 5/2 untuk setiap v di G.

Bukti Teorema Dirac:Bukti menggunakan induksi matematika atas banyaknya simpul n di G. Jika G mempunyai n = 3 dan d(v) > 3/2 untuk setiap v di G,

maka d(v) = 2 dan G = yang merupakan graf hamilton.Jadi teorema benar untuk n = 3.

Teorema dianggap benar untuk n > 4. Misalkan J adalah jalur terpanjang di G. Misalkan J : seperti pada gambar dibawah ini :

Ini berarti bahwa J memuat simpul paling banyak yang mungkin dimuat oleh J di G.

3K

kuuu ,...,, 21

Karena tidak ada lagi jalur di G yang memuat simpul lebih

banyak daripada yang dimiliki J, maka setiap simpul yang

bertemu dengan harus berada di J. Selain itu, setiap

simpul yang bertemu (atau disebut juga “berdekatan”)

dengan harus berada di J. Karena paling sedikit

berdekatan dengan n/2 simpul yang semuanya berada di

J, maka J paling sedikit memuat sebanyak 1 + n/2 simpul.

Selanjutnya, haruslah terdapat simpul

di J, dengan , sedemikian rupa sehingga

berdekatan dengan dan berdekatan

dengan .

ki 2 iu

1iu

1u

1u

ku

iu

1u ku

Akan tetapi oleh karena paling sedikit ada n/2 simpul-simpul

berdekatan dengan simpul , maka akan ada paling sedikit

n/2 simpul-simpul tidak akan berdekatan dengan .

Akibatnya

Hal ini sesuatu yang tidak mungkin sebab . Dengan

demikian, terdapat suatu simpul di J sedemikian rupa

sehingga dan kedua-duanya merupakan rusuk G

(periksa Gambar 3.18). Akibatnya adalah terdapat sikel S:

yang memuat semua simpul di J.

Jika semua simpul di G telah berada di S, maka S adalah sikel

Hamilton dan G adalah graf Hamilton.

iu

1u

1iu ku

22

1)(nn

nud k

2)(n

ud k

iu

iuu1 ki uu 1

12111 ,...,,...,,, uuuuuu kkii

Gambar 3.18

Misalkan ada suatu simpul w di G yang tidak berada di S.

Karena S memuat paling sedikit 1 + n/2 simpul, sebanyak

kurang dari n/2 simpul di G tidak berada di S. Karena

, simpul w harus berdekatan dengan suatu simpul

di S. Akan tetapi, rusuk dan S membangun jalur

yang banyaknya simpul 1 lebih banyak daripada simpul-

simpul yang berada di J, yang tidak mungkin terjadi sebab

J memuat simpul-simpul paling banyak. Kontradiksi ini

berakibat bahwa S memuat semua simpul di G, sehingga

G adalah graf Hamilton.

2)(n

wd

ju juw

Teorema 5.2 (Teorema Ore)

Misal G graf sederhana dengan

simpul. Jika

untuk setiap pasangan

simpul v dan w yang tidak berikatan, maka G

graf Hamilton.

3n

nvdud

Bukti Teorema Ore:Akan dibuktikan G hamilton.Misal G bukan Hamilton yang memenuhi kondisi Asumsikan bahwa titik di G dengan penambahan himpunan sisi {u,v} akan membentuk graf Hamilton, untuk dua titik u,v yang tidak bertetangga. Karena G bukan Hamilton dan G + { u, v } Hamilton, maka untuk setiap siklus Hamilton di G + { u,v } memuat siklus {u, v}. Sehingga pada G terdapat lintasan Hamilton dengan dan .

u=u1 u2 uk-1 uk un-1 un=v

nvdud

nuuu ,...,, 21 nu 1 vun

Sekarang jika setiap 2 < k < n, E(G) maka E(G). Sebab kalau tidak , adalah siklus Hamilton dari G, sehingga untuk setiap titik yang bertetangga dengan titik v, akan terdapat titik lainnya tidak bertetangga dengan v.Jadi setiap bertetangga ke r titik dari maka paling sedikit r titik, jadi jika , maka sehingga . Dengan demikian hipotesis .

(Terbukti).

},{ 1 kuu },{ 1 nk uu

nkknk uuuuuu ...... 211

ku

1u },...,,{ 32 nuuu rvd 1 11 vdnud n

11 nudvd n

nudvd n 1

Perlu diketahui bahwa belum ada algoritma efisien untuk mendapatkan sebuah sikel Hamilton minimal di graf bobot G. Sebagai pendekatan sederhana, biasanya digunakan metode “tetangga terdekat” yang dikenal dengan algoritma serakah “Greedy Algirithm” sebagai berikut :

Pilih sebuah simpul v di graf G; Pilih simpul G yang lain, y misalnya, yang

“terdekat” dengan v; Pilih simpul G yang lain selain y dan v yang

terdekat dengan y; Dan seterusnya sampai semua simpul

terpilih.

Menghitung sikel Hamilton minimal di graf bobot G

Daftarlah semua sikel Hamilton pada graf berikut ini dan tentukan masing-masing bobotnya.

Manakah yang merupakan sikel Hamilton dengan bobot minimum? Selanjutnya gunakan algoritma serakah untuk menentukan sikel Hamilton minimal pada graf di samping. Apakah sama hasilnya?

5A

D

B

C

10

2

6

54

Cara menentukan ada tidaknya sikel Hamilton dalam suatu Graf: Aturan 1

Jika simpul v berderajat 2, kedua rusuk yang bertemu di v harus merupakan bagian dari sikel Hamilton.

Aturan 2Tidak ada subsikel sejati, yakni, sikel yang tidak memuat semua simpul di dalam grafnya, tidak dapat dibangun apabila membangun sikel Hamilton.

Aturan 3Segera setelah sikel Hamilton kita bangun melalui suatu simpul w, semua rusuk lain (yang tidak digunakan) yang bertemu di w dapat dibuang (karena mereka tidak dapat digunakan lagi mengingat setiap simpul harus berderajat 2).

Contoh

Buktikan bahwa gambar di samping bukan graf hamilton!

Bukti

c

a

bd

e

g

i

h

k

f

j

Bukti Menurut Aturan 1, simpul a, dan g harus masuk dalam sikel, sebab berderajat 2,

sehingga jalur : b, a, c dan jalur : e, g, i harus menjadi bagian dari sikel. Perhatikan simpul i. Kita

telah melihat bahwa rusuk gi menjadi bagian dari sikel. Karena rusuk gi simetri terhadap rusuk ij

dan ik, tidak masalah apakah kita memilih salah satu yang mana. Menggunakan Aturan 3, kita

buang rusuk ik, maka simpul k berderajat 2, sehingga menurut Aturan 1, jk dan hk harus menjadi

bagian dari sikel. Karena jk harus menjadi bagian sikel, maka menurut Aturan 3, rusuk jf harus

dibuang. Akibatnya derajat simpul f menjadi 2. Maka di f, fe dan fb harus menjadi bagian dari

sikel. Dengan penambahan fe, maka simpul e harus berderajat 2, jadi rusuk eh dan ed harus

dibuang dari bagian sikel (sebab rusuk eg telah ditetapkan ikut dalam sikel). Akibatnya simpul h

berderajat 2, sehingga rusuk kh dan hc harus menjadi bagian sikel. Sekarang terjadi kontradiksi.

Lihat bahwa sekarang simpul d telah berderajat 2. Kita harus menggunakan rusuk db dan dc

sebagai bagian sirkuit. Tetapi dengan demikian terjadilah subsikel sejati a, b, d, c, yang menurut

Aturan 2 tidak dibenarkan.