Dalam cabang ilmu matematika diskrit dan teori graf, terdapat satu topik klasik yang selalu menarik untuk dibahas karena aplikasinya yang sangat luas di dunia nyata, mulai dari optimasi rute logistik hingga desain sirkuit komputer. Topik tersebut adalah Graf Hamilton. Berbeda dengan Graf Euler yang fokus pada melintasi setiap sisi tepat satu kali, Graf Hamilton berfokus pada perjalanan yang melewati setiap simpul (vertex) tepat satu kali.
Baca juga:Memahami Obligasi At Par Secara Lengkap: Pengertian, Konsep, dan Contoh Soal Pembahasan
Artikel ini akan mengupas tuntas mengenai definisi, perbedaan dengan Euler, hingga penyajian contoh soal graf hamilton yang dirancang untuk menguji pemahaman logis Anda secara sistematis.
Apa Itu Graf Hamilton?
Nama Hamilton diambil dari matematikawan asal Irlandia, Sir William Rowan Hamilton, yang menemukan permainan “Icosian Game” pada tahun 1857. Permainan ini menantang pemain untuk menemukan rute di sepanjang rusuk-rusuk dodekahedron yang mengunjungi setiap sudut tepat satu kali dan kembali ke titik awal.
1. Lintasan Hamilton
Lintasan Hamilton adalah lintasan yang melalui setiap simpul di dalam graf tepat satu kali.
2. Sirkuit Hamilton
Sirkuit Hamilton adalah sirkuit yang melalui setiap simpul di dalam graf tepat satu kali, kecuali simpul awal dan simpul akhir yang merupakan simpul yang sama.
3. Graf Hamilton
Sebuah graf disebut Graf Hamilton jika graf tersebut memiliki sirkuit Hamilton. Jika sebuah graf hanya memiliki lintasan Hamilton namun tidak memiliki sirkuit Hamilton, maka graf tersebut disebut Graf Semi-Hamilton.
Perbedaan Utama: Graf Hamilton vs Graf Euler
Banyak pemula terjebak dalam membedakan kedua konsep ini. Berikut adalah poin kunci untuk membedakannya tanpa kebingungan:
- Graf Euler: Fokus pada sisi (edge). Setiap sisi wajib dilewati tepat satu kali. Syaratnya sangat pasti (semua simpul berderajat genap).
- Graf Hamilton: Fokus pada titik/simpul (vertex). Setiap simpul wajib dikunjungi tepat satu kali. Syarat pastinya (syarat perlu dan cukup) hingga saat ini masih menjadi salah satu masalah tersulit dalam teori graf (masalah NP-Complete).
Syarat Cukup Keberadaan Sirkuit Hamilton
Meskipun tidak ada syarat sederhana yang berlaku untuk semua graf, terdapat beberapa teorema yang membantu kita menentukan apakah sebuah graf pasti memiliki sirkuit Hamilton:
Teorema Dirac (1952)
Jika $G$ adalah graf sederhana dengan jumlah simpul $n \geq 3$ sedemikian sehingga derajat setiap simpul $v$ berlaku $deg(v) \geq n/2$, maka $G$ adalah graf Hamilton.
Teorema Ore (1960)
Jika $G$ adalah graf sederhana dengan simpul $n \geq 3$ sedemikian sehingga untuk setiap pasangan simpul yang tidak bertetangga $u$ dan $v$ berlaku $deg(u) + deg(v) \geq n$, maka $G$ adalah graf Hamilton.
Kumpulan Contoh Soal Graf Hamilton dan Pembahasannya
Berikut adalah simulasi latihan soal untuk mempertajam analisis Anda dalam menentukan karakteristik sebuah graf.
Contoh Soal 1: Analisis Graf Lengkap (Kn)
Pertanyaan:
Apakah graf lengkap dengan 4 simpul ($K4$) merupakan graf Hamilton? Jika ya, sebutkan sirkuit Hamilton yang mungkin!
Jawaban:
Ya, graf lengkap $Kn$ untuk $n \geq 3$ selalu merupakan graf Hamilton. Pada $K4$ dengan simpul $\{A, B, C, D\}$, setiap simpul terhubung dengan semua simpul lainnya. Salah satu sirkuit Hamilton yang dapat dibentuk adalah $A – B – C – D – A$. Lintasan ini mengunjungi setiap simpul tepat satu kali dan kembali ke asal.
Contoh Soal 2: Menentukan Graf Semi-Hamilton
Pertanyaan:
Diberikan sebuah graf berbentuk garis lurus dengan 5 simpul yang terhubung berurutan ($A-B-C-D-E$). Analisislah apakah graf ini termasuk graf Hamilton, semi-Hamilton, atau bukan keduanya!
Jawaban:
Graf ini memiliki lintasan Hamilton, yaitu $A – B – C – D – E$ (semua simpul dikunjungi tepat satu kali). Namun, karena dari simpul $E$ kita tidak bisa kembali ke simpul $A$ tanpa melewati simpul lain untuk kedua kalinya, maka graf ini tidak memiliki sirkuit Hamilton. Kesimpulannya, graf ini adalah Graf Semi-Hamilton.
Contoh Soal 3: Penerapan Teorema Dirac
Pertanyaan:
Sebuah graf memiliki 6 simpul. Diketahui setiap simpul pada graf tersebut memiliki derajat minimal 3. Tanpa menggambar grafnya, apakah kita bisa memastikan graf tersebut memiliki sirkuit Hamilton?
Jawaban:
Berdasarkan Teorema Dirac, jika $n = 6$, maka syarat cukup agar graf menjadi Hamilton adalah derajat setiap simpul $v \geq n/2$, yaitu $6/2 = 3$. Karena soal menyatakan setiap simpul memiliki derajat minimal 3, maka syarat Teorema Dirac terpenuhi. Jadi, dapat dipastikan graf tersebut adalah Graf Hamilton.
Contoh Soal 4: Graf Bipartit Sederhana
Pertanyaan:
Apakah graf bintang (Star Graph) dengan 1 simpul pusat dan 3 simpul daun memiliki sirkuit Hamilton?
Jawaban:
Tidak. Dalam graf bintang, untuk mengunjungi semua simpul daun, kita harus berkali-kali melewati simpul pusat. Misalnya, dari daun 1 ke pusat, lalu ke daun 2, kita harus kembali lagi ke pusat untuk menuju daun 3. Karena simpul pusat dikunjungi lebih dari satu kali sebelum kembali ke awal, maka graf bintang tidak memiliki lintasan maupun sirkuit Hamilton.
Contoh Soal 5: Kompleksitas Graf Siklus (Cn)
Pertanyaan:
Sebutkan sirkuit Hamilton pada graf siklus $C5$ dengan simpul yang disusun melingkar $1, 2, 3, 4, 5$!
Jawaban:
Pada graf siklus $Cn$, sirkuit Hamilton adalah urutan simpul itu sendiri karena setiap simpul terhubung membentuk cincin. Sirkuitnya adalah $1 – 2 – 3 – 4 – 5 – 1$. Semua graf siklus dengan $n \geq 3$ adalah graf Hamilton.
Aplikasi Graf Hamilton dalam Kehidupan Nyata
Mempelajari contoh soal graf hamilton bukan sekadar latihan logika, melainkan persiapan untuk memecahkan masalah nyata seperti:
- Traveling Salesman Problem (TSP): Mencari rute terpendek bagi seorang pedagang untuk mengunjungi sejumlah kota dan kembali ke kota asal.
- Logistik dan Distribusi: Pengaturan rute kurir agar melewati semua alamat pengiriman secara efisien tanpa berputar-putar di titik yang sama.
- Genetika: Digunakan dalam penyusunan fragmen DNA untuk menentukan urutan genom yang tepat.
- Robotika: Pemrograman gerakan lengan robot dalam industri manufaktur agar menyentuh setiap titik pengelasan tepat satu kali.
Kesimpulan
Graf Hamilton adalah konsep esensial dalam matematika diskrit yang menitikberatkan pada efisiensi kunjungan simpul. Meskipun menentukan keberadaan sirkuit Hamilton pada graf besar sangat menantang (NP-Complete), pemahaman dasar melalui graf sederhana dan teorema pendukung seperti Dirac dan Ore akan sangat membantu.
Dengan memperbanyak latihan pada berbagai contoh soal graf hamilton, Anda akan lebih peka dalam melihat pola konektivitas antar objek, yang merupakan kemampuan krusial di era big data dan optimasi sistem saat ini.
Penulis: marfel nurhidayat
Post Comment