Lintasan Hamilton

Sebuah lintasan Hamilton dalam dodekahedron.

Graf Herschel adalah graf polihedral terkecil yang mungkin yang tidak memiliki lintasan Hamilton.

Lintasan Hamilton adalah lintasan yang melalui tiap verteks di dalam graf tepat satu kali. Bila lintasan itu kembali ke verteks asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton adalah sirkuit yang melalui tiap verteks di dalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali. Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

Pada tahun 1859, Matematikawan dari Irish, Sir William Rowan Hamilton mengembangkan permainan yang di beli dari perusahaan mainan di Dublin. Permainan itu dinamakan Prominent Cities. Tujuan dari permainan iu adalah mencari sirkuit sepanjang jalan yang terbentuk sehingga di dalam itu terdapat 20 kota dan dapat dilewati tepat satu kali.

Penulis dapat menggambarkan alat itu dengan sebuah graf: Verteks dari graf melambangakan verteks dari alat tersebut dan panjangnya edges disamakan dengan alat tersebut.

Untuk menentukan sebuah graf itu adalah Siklus Hamilton atau tidak, pastinya lebih sulit dari pada menentukan itu Eulerian. Selain itu, tidak ada cara pasti yang diketahui untuk menentukannya.

Siklus dalam graf akan terbagi menjadi dua yaitu Euler dan Hamilton. Eulerian adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua edges yang ada dalam graf tersebut. Dan tidak menjadi suatu masalah jika sebuah verteks dilewati sebanyak apapun. Tetapi pada Hamilton adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua verteks dalam graf tersebut dan hanya tepat satu kali, kecuali verteks awal didatangi dua kali. Jika sebuah verteks itu telah dilewati dua atau lebih dalam suatu siklus maka siklus tesebut tidak dapat dikatakan sebagai siklus Hamiltonian.

Diberikan contoh dalam suatu graf ada terdapat lima buah verteks. Di misalkan A, B, C, D, dan E. Dari siklus yang terjadi penulis dapat menentukan siklus itu Hamilton atau tidak.

• Siklus 1: A – B – C – D – E
• Siklus 2: A – B – C – B – D – E
• Siklus 3: A – C – B – E – D
• Siklus 4: A – B – E – C – B – D

Dari empat siklus diatas dapat dilihat siklus 1 dan 3 adalah Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan hanya tepat satu kali. Tetapi pada siklus 2 dan 4 bukan Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan ada yang melebihi satu kali. Pada siklus 2 dan 4 muncul verteks B sebanyak dua kali. Dan itu melanggar sifat dari sebuah siklus Hamilton. Siklus Hamilton dapat ditemukan di banyak hal.

Ilustrasi

• Graf yang memiliki lintasan Hamilton, contohnya 3, 2, 1 4 (a)
• Graf yang memiliki lintasan Hamilton & hamilton cycle, contohnya 1, 2, 3, 4, 1 (b)
• Graf yang tidak memiliki lintasan maupun sirkuit Hamilton (c)

Teorema

• Syarat cukup (jadi bukan syarat perlu) supaya graf sederhana G dengan n (³ 3) buah simpul adalah graf Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) ³ n/2 untuk setiap simpul v di G).
• Setiap graf lengkap adalah graf Hamilton.
• Di dalam graf lengkap G dengan n buah simpul (n ³ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.
• Di dalam graf lengkap G dengan n buah simpul (n ³ 3 dan n ganjil), terdapat (n - 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n ³ 4, maka di dalam G terdapat (n - 2)/2 buah sirkuit Hamilton yang saling lepas.

Contoh

(Persoalan pengaturan tempat duduk) Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?

• Jumlah pengaturan tempat duduk yang berbeda adalah (9 - 1)/2 = 4

Dengan graf

• Graf Hamilton sekaligus Euler (a)
• Graf Hamilton sekaligus graf semi-Euler (b)