TI POLITALA MATDIS 1C

LINTSAN 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. 

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?

Jawaban: Jumlah pengaturan tempat duduk yang berbeda adalah (9 – 1)/2 = 4.

Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, dan sebagainya.

PEWARNAAN GRAF

-Ada dua macam: pewarnaan simpul, dan pewarnaan sisi Hanya dibahas perwarnaan simpul

-Pewarnaan simpul: memberi warna pada simpul-simpul graf sedemikian sehingga dua simpul bertetangga mempunyai warna berbeda

-Aplikasi pewarnaan graf: mewarnai peta.

-Peta terdiri atas sejumlah wilayah.

-Wilayah dapat menyatakan kecamatan, kabupaten, provinsi, atau negara.

-Peta diwarnai sedemikian sehingga dua wilayah bertetangga mempunyai warna berbeda.

Graf kosong

            Karena semua simpul tidak terhubung, jadi untuk mewarnai semua simpul cukup dibutuhkan satu warna saja.

                                               

Graf lengkap

Semua simpul saling terhubung sehingga diperlukan n buah warna.

Graf bipartit

Kmn mempunyai x( G ) = 2, satu untuk simpul-simpul di himpunan V 1 dan satu lagi untuk simpul-simpul di V 2.

Untuk graf-graf yang lain tidak dapat dinyatakan secara umum bilangan kromatiknya.

Materi lainnya:

• Graf Planar dan Graf Bidang

https://cucusulaiman.blogspot.com/2018/12/graf-planar-planar-graph-dan-grafbidang.html

• Reprentasi Graf dan Graf Isomorfik

https://anggrainidians.blogspot.com/2018/12/representasi-graf-matriksketetanggaan.html

• Definisi Graf dan  Graf Bipartite

https://maysarahhmay.blogspot.com/2018/12/matdis-graf.html