Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas tentang lintasan dan sirkuit Hamilton dalam Teori Graf. Lintasan terpendek dari simpul A ke B, konsep lintasan Euler, serta lintasan dan sirkuit Hamilton dijelaskan. Teorema Dirac dan Ore memberikan syarat eksistensi sirkuit Hamilton dalam graf. Graf lengkap pasti memiliki sirkuit Hamilton, sementara graf dengan simpul berderajat satu atau derajat tidak memenuhi syarat sirkuit Hamilton. Penjelasan juga diberikan mengenai cara menentukan graf yang memiliki sirkuit Hamilton.

Masalah yang terkait dengan lintasan yang juga menarik adalah mencari lintasan terpendek dari simpul A ke simpul B.

Kalau kita suka pakai Google Map itu sebetulnya menggunakan teori ini, jadi dari satu tempat ke tempat lain itu mana jalan yang terpendek, mana jalan yang tercepat.

Jadi kalau Google Map itu menyatukan dengan juga ada data-data yang real time tentang kemacepan di jalan tersebut, bisa lewat tol atau tidak.

Cuma lintasan terpendek di sini atau shortest path kita tidak bahas di kuliah matematik diskret.

Nah konsep lain itu ada yang kita sebut sebagai kembali ke awal itu tentang lintasan Euler.

Jadi pertama kali ditemukan graf itu sebetulnya kita mau mencari lintasan Euler, itu lintasan yang melalui semua busur yang ada di dalam graf tersebut.

Nah kalau lingkaran Euler berarti lingkaran yang memuat semua busur.

Nah selain lintasan dan sirkuit Euler, ada yang lebih seru lagi yang kita sebut sebagai lintasan dan sirkuit Hamilton.

Idenya berasal dari suatu permainan, a voyage around the world.

Jadi ceritanya kita mengunjungi kota-kota di seluruh dunia, tapi gambarnya itu adalah seperti ini.

Jadi kita pilih satu kota kemudian pilih kota yang lain dalam game-nya itu ada lubang-lubang gitu yang ada jalan di antara itu.

Nah kalau kita mau keliling dunia artinya kita mengunjungi semua simpul-simpul yang ada di dalam permainan tersebut

yang ternyata bisa dikembangkan atau digeneralisasi menjadi suatu graf secara umum.

Jadi misalnya kalau kita punya lintasan sederhana di graf G dan dia melalui semua simpul tepat satu kali itu kita sebut sebagai lintasan Hamilton.

Karena ini yang membuat game-nya itu Pak Hamilton.

Kalau sirkuit sederhana melalui semua simpul tepat satu kali itu disebut sirkuit Hamilton.

Jadi kalau kita pakai notasi lintasan sederhana X0, X1 sampai Xn dalam graf itu adalah lintasan Hamilton jika

Jadi maksudnya semua simpul itu ada di dalam lintasan tersebut dan Xe itu akan sama dengan Xj itu kalau Xe dan Xj-nya awal dan akhir.

Jadi untuk sirkuit kalau enggak berarti dia tidak sama.

Jadi kita akan punya lintasan Hamilton X0 sampai Xn, sirkuit Hamilton X0, X1 sampai Xn kembali ke X0 lagi.

Jadi kita lihat contohnya mana graf yang mempunyai lintasan Hamilton.

Graf yang pertama itu gampang karena kita bisa mulai dari mana saja.

Misalnya kita mau mulai dari A kemudian jalan ke B kemudian ke C ke D ke E kemudian kembali ke A.

Jadi kita bisa muter nanti kita akan dapat sirkuit Hamilton.

Untuk G2 kita enggak akan punya sirkuit Hamilton karena disini ada simpul yang derajatnya cuma satu.

Jadi kalau kita mulai dari A enggak mungkin kita kembali ke A.

Sekarang kita mau lihat apakah dia punya lintasan Hamilton.

Mulainya pasti dari A dulu karena dia yang lebih mudah kalau kita ambil yang derajatnya satu.

Jadi kita bisa dari A kemudian ke B, dari B ini terserah mau ke C atau ke D.

Kalau misalnya kita mulai dari C terus berakhir ke D.

Jadi kita punya lintasan yang melalui semua simpul lintasannya kita sebut lintasan Hamilton.

Sekarang kalau kita lihat yang G3 ini bagaimanapun kita mencoba tidak akan mungkin punya lintasan Hamilton apalagi sirkuit Hamilton.

Kita tahu bahwa dia enggak punya sirkuit Hamilton karena di sini malah ada tiga simpul yang derajatnya satu.

Tapi yang lintasan Hamilton pun itu juga tidak bisa kita lakukan.

Karena kalau misalnya kita mulai dari A kemudian ke B terus nanti ada lintasan mengunjungi D.

Maka untuk ke F itu kita harus mengulang kembali lewat C lagi.

Padahal kan lintasan Hamilton itu syaratnya setiap simpul hanya dikunjungi satu kali.

Jadi di sini enggak mungkin yang di G3 itu enggak mungkin ada lintasan Hamilton apalagi sirkuit Hamilton.

Sampai saat ini belum ada teorema atau sifat yang bisa menentukan syarat perlu dan cukup tentang eksistensi sirkuit Hamilton.

Jadi ada beberapa teorema yang memberikan syarat eksistensi tapi tidak dikarakterisasi.

Jadi misalnya contoh graf yang mempunyai simpul berajat satu itu enggak mungkin punya sirkuit Hamilton.

Ada dua teorema yang sangat terkenal di graf terkait sama sirkuit Hamilton atau lintasan Hamilton.

Yang disebut sebagai teorema Dirac dan teorema Ore.

Teorema Dirac itu mengatakan kalau suatu grafnya itu graf sederhana dan punya n simpul.

Nnya dalam hal ini lebih besar sama dengan tiga.

Sehingga setiap simpulnya derajatnya itu paling sedikit n per dua.

Jadi ini banyak sekali busurnya maka G pasti mempunyai sirkuit atau lingkaran Hamilton.

Ore mengatakan dengan syarat yang sama tapi derajat dari U dan V untuk sembarang UV itu pasti lebih besar n.

Maka setiap simpul yang tidak bertetangga itu UV-nya tadi maka si G-nya itu pasti mempunyai lingkaran Hamilton.

Jadi Ore ini sebetulnya kalau degree U ditambah degree V atau derajat U ditambah derajat V lebih besar n.

Jadi masing-masing itu kira-kira n per dua.

Jadi mirip sama yang Dirac tapi Dirac itu bahwa setiap simpulnya itu harus berderajat lebih besar dari n per dua.

Tapi kalau yang Ore bilang jumlahnya itu lebih besar dari n.

Jadi bisa saja ada simpul yang derajatnya kurang dari n per dua.

Kalau yang Dirac kan harus lebih besar atau sama dengan n per dua.

Kita lihat contohnya, di G itu tidak ada sirkuit Hamilton.

Gara-garanya atau penyebabnya adalah simpul E itu berderajat satu.

Kalau yang H ini juga tidak punya sirkuit Hamilton karena derajatnya ini A, B, C, D semuanya dua dan C ini derajatnya empat.

Si C ini yang bikin gara-gara dia tidak punya sirkuit Hamilton karena dia pasti akan dilalui dua kali untuk mencapai si AB dan untuk mencapai DE.

Sehingga kita bisa mengambil kesimpulan sirkuit Hamilton itu tidak ada di H.

Karena harus memuat si empat busur ini si AC, BC, CD dan CE.

Jadi dengan cara itu akan didapat suatu kontradiksi.

Graf lengkap itu pasti mempunyai sirkuit Hamilton.

Kalau kita gambar menjadi bentuk yang setiap simpulnya ada di lingkaran luar kemudian baru kita buat busur-busur di antaranya.

Misalnya di sini adalah kalima yang lebih sederhana.

Maka untuk membuat sirkuit Hamilton itu kita bisa mulai dari mana saja.

Kita akan pilih yang paling gampang adalah tetangga dalam lingkaran luarnya.

Jadi ini kita kunjungi simpul 2, kemudian simpul ke 3, kemudian ke 4, kemudian ke 5, kemudian balik lagi ke simpul 1.

Karena kalau kita mulai dari simpul 1 kita boleh pilih langsung ke simpul 4, kemudian ke simpul 2, kemudian ke simpul 5, kemudian ke simpul 3.

Kalau mau membuat sirkuit balik lagi ke simpul 1.

Karena setiap pasang simpulnya di sini bertetangga, jadi kita boleh lewat mana saja.

Nanti bisa dicoba untuk yang lebih heboh lagi, ini penamanya graph lengkapnya.

Mulai dari mana saja itu pasti kita bisa mendapatkan suatu sirkuit Hamilton.

Kalau misalnya kita punya graph yang lain yang sembarang,

kalau kita bisa mendapatkan suatu bentuk atau menggambarnya dengan lingkaran di luar,

untuk semua simpul-simpulnya terletak di lingkaran seperti ini,

kemudian busur-busurnya itu bisa kita pasang di sini, terserah bagaimana bentuknya.

Ini sudah bisa dipastikan bahwa dia adalah graph yang mempunyai lingkaran Hamilton.

Tapi kalau bentuk penggambarannya itu tidak seperti ini,

kita harus melihat dulu satu persatu apakah dia bisa atau tidak.

Dengan ini kita sudah selesai membahas tentang lintasan dan sirkuit Hamilton dan connectivity.