📋 Daftar Isi
Lintasan dan Sirkuit Hamilton
Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.
Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.
Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.
(a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4)
(b) graf yang memiliki sirkuit Hamilton (1, 2, 3, 4, 1)
(c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton
Teorema
Syarat cukup 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).
Teorema
Setiap graf lengkap adalah graf Hamilton.
Teorema
Di dalam graf lengkap G dengan n buah simpul (n ≥ 3), terdapat (n – 1)!/2 buah sirkuit Hamilton.
Teorema
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
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?
Penyelesaian:
Jumlah pengaturan tempat duduk yang berbeda adalah (9 – 1)/2 = 4.
sumber: Buku Matematika Diskrit (Rinaldi Munir)
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.
