Matematika Diskrit : Lintasan dan Sirkuit Hamilton

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.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up