Graf Euler dan Graf Hamilton

1. Graf Euler

A. Lintasan, sirkuit, dan graf Euler

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. Bila lintasan tersebut kembali ke titik asal, membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Euler. Jadi, sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali.

Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).

B. Kriteria derajat titik untuk graf Euler tak berarah

"Graf terhubung tak-berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap titik di dalam graf tersebut berderajat genap."

Bukti untuk teorema ini sangat mudah ditunjukkan. Ketika mulai berangkat dari titik awal, a, ke titik selanjutnya, b, sisi (a, b) menyumbangkan 1 untuk derajat titik a. Jika sirkuit Euler dilalui, maka pada setiap titik terdapat dua buah sisi yang bersisian, yang berarti setiap titik berderajat 2 (genap). Ketika kembali ke titik awal, a, sisi dari titik terakhir ke titik a menyumbangkan 1 lagi untuk derajat titik a, sehingga derajat titik asal adalah 2 (genap). Kita menyimpulkan bahwa graf terhubung tak-berarah memiliki sirkuit Euler jika setiap titik di dalam graf berderajat genap.

Dengan menggunakan teorema yang terakhir ini jelaslah masalah jembatan Königsberg tidak memiliki sirkuit Euler karena semua titik berderajat ganjil.

Jika kita ingin membuat graf yang mempunyai sirkuit Euler, maka harus dipenuhi kondisi berikut: 

(1) graf tersebut harus terhubung, dan 

(2) semua titik pada graf berderajat genap.

C. Kriteria derajat titik untuk graf semi-Euler tak berarah

Jika lintasan yang dilalui tidak membentuk sirkuit, maka lintasan yang terbentuk adalah lintasan terbuka yang disebut lintasan Euler. Di sini titik awal tidak sama dengan titik terakhir. Baik titik awal maupun titik akhir di dalam lintasan Euler berderajat 1 (ganjil). Karena itu, agar sebuah graf mempunyai lintasan Euler (tapi bukan sirkuit Euler), maka graf tersebut harus memiliki tepat dua buah titik berderajat ganjil. Persyaratan ini dinyatakan dalam  berikut.

"Graf terhubung tak-berarah G adalah graf semi-Euler (memiliki lintasant Euler) jika dan hanya jika di dalam graf tersebut terdapat tepat dua titik berderajat ganjil."

Catatlah bahwa graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya. Jika kita ingin membuat graf yang mempunyai lintasan Euler (tanpa membentuk sirkuit), maka harus dipenuhi kondisi berikut: 

(1) graf tersebut harus terhubung, dan 

(2) graf memiliki tepat dua buah titik berderajat ganjil.

D. Kriteria derajat titik untuk graf Euler berarah

Graf terhubung berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap titik memiliki derajat-masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua titik, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

E. Permainan menggambar graf

Ada satu permainan sederhana yang sering dimainkan dikala senggang. Permainan itu adalah menggambarkan sesuatu dengan gerakan pensil secara menerus tanpa mengangkat pensil dan tidak menggambar ulang garis-garisnya.

Secara umum, proses penggambarannya seolah-olah mencari lintasan Euler pada suatu graf. Untuk menentukan mungkin atau tidaknya, dengan mengecek derajat masing-masing titik.

1. Untuk kasus semua titik berderajat genap, penggambarannya memungkinkan untuk dilakukan dan bisa dimulai dari titik mana saja.

2. Untuk kasus terdapat dua titik berderajat ganjil, penggambarannya memungkinkan untuk dilakukan, dimulai dari salahsatu titik berderajat ganjil, dan akan berakhir di titik ganjil yang lain.

3. Untuk kasus terdapat lebih dari dua titik berderajat ganjil, penggambarannya mustahil untuk dilakukan, karena grafnya tidak memiliki lintasan Euler.

Sebagai contoh, mungkinkah gambar berikut ini digambarkan secara terus menerus tanpa mengangkat pensil dan tidak menggambar ulang garis-garisnya.

Jawabannya adalah mungkin, karena gambar ini merupakan graf yang semua titiknya berderajat genap.
Contoh lainnya

Gambar ini juga mungkin, karena merupakan graf dengan 2 titik berderajat ganjil, yaitu B dan C. Caranya adalah dengan memulai dari B sehingga berakhir di C, atau memulai dari C sehingga berakhir di B.
Adapun gambar berikut:

Gambar ini tidak memungkinkan, karena ada lebih dari 2 titik berderajat ganjil, yaitu A, B, C, dan D.

2. Graf Hamilton

A. Lintasan, sirkuit, dan graf Hamilton

Lintasan Hamilton ialah lintasan yang melalui tiap titik di dalam graf tepat satu kali. Bila lintasan itu kembali ke titik asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton ialah sirkuit yang melalui tiap titik di dalam graf tepat satu kali, kecuali titik asal (sekaligus titik akhir) yang dilalui dua kali.

Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

Nama sirkuit Hamilton muncul ketika Sir William Hamilton membuat permainan dodecahedron. Pada tahun 1859 Sir William Hamilton menawarkan mainan teka-teki ke pabrik alat mainan Dublin. Mainan itu terdiri dari dodecahedron (yaitu benda yang disusun oleh 12 buah pentagonal dan di sini ada 20 buah titik sudut) dan tiap titik sudut diberi nama ibukota negara. Permainan yang dapat dilakukan adalah membentuk perjalanan keliling dunia, yang mengunjungi setiap ibukota tepat satu kali dan kembali lagi ke kota asal. Persoalan ini dinamakan mencari sirkuit Hamilton.

B. Teorema Dirac

Jika G adalah graf sederhana dengan n buah titik (n ≥ 3) sedemikian sehingga derajat tiap titik paling sedikit n/2 (yaitu, d(v) ≥ n/2 untuk setiap titik v di G), maka G adalah graf Hamilton.

C. Teorema Ore

Jika G adalah graf sederhana dengan n buah titik (n ≥ 3) sedemikian sehingga d(v) + d(u) ≥ n untuk setiap pasang titik tidak-bertetangga u dan v, maka G adalah graf Hamilton.

D. Hubungan graf lengkap dengan graf Hamilton

1. Setiap graf lengkap adalah graf Hamilton.

2. Di dalam graf lengkap G dengan n buah titik (n ≥ 3) terdapat sebanyak (n − 1)!/2 buah sirkuit Hamilton.

3. Di dalam graf lengkap G dengan n buah titik (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.

3. Persoalan Pedagang Keliling (Travelling Salesperson Problem)

Persoalan Pedagang Keliling (TSP) merupakan salah satu masalah terkenal dalam teori graf. Inti persoalannya adalah mencari sirkuit terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal. Dalam graf, kota direpresentasikan sebagai titik, sedangkan jalan antar kota sebagai sisi berbobot, di mana bobot menyatakan jarak antar kota. Masalah ini pada dasarnya adalah pencarian sirkuit Hamilton dengan bobot minimum pada graf terhubung.

Walaupun dinamakan “pedagang keliling”, TSP memiliki banyak penerapan lain. Contohnya, penentuan rute optimal bagi mobil pos yang mengambil surat dari berbagai kotak pos dan kembali ke kantor pos, atau lintasan minimum bagi lengan robot yang harus mengencangkan mur dalam jalur perakitan, sehingga total waktu perpindahan antarmur dapat diminimalkan. Dalam dunia industri, TSP juga digunakan untuk menjadwalkan urutan produksi beberapa komoditas oleh mesin, dengan tujuan meminimalkan biaya perubahan antar produksi.

Jika grafnya lengkap dengan n titik, maka terdapat sebanyak (n – 1)!/2 sirkuit Hamilton yang berbeda. Namun, jumlah ini sangat besar jika n besar — misalnya untuk n = 20 terdapat sekitar 6 × 10¹⁶ sirkuit yang harus diperiksa. Oleh karena itu, TSP termasuk dalam kategori masalah komputasi yang sulit (hard problem). Secara teoritis, masalah ini dapat diselesaikan dengan enumerasi semua sirkuit Hamilton dan memilih yang paling pendek, tetapi pendekatan ini tidak praktis untuk n besar.

Walau umumnya TSP dikaitkan dengan graf lengkap, persoalan ini juga bisa diterapkan pada graf tidak lengkap selama terdapat sirkuit Hamilton di dalamnya. Hingga kini belum ada algoritma yang efisien untuk menyelesaikan TSP secara umum, namun berbagai metode heuristik seperti branch and bound telah dikembangkan untuk mendekati solusi optimal.

4. Persoalan Tukang Pos China (Chinese Postman Problem)

Mengenai Masalah Tukang Pos Cina (Chinese Postman Problem):

Masalah ini pertama kali diajukan oleh Mei Gan dari Cina pada tahun 1962. Awalnya, masalah ini bertujuan untuk menemukan rute bagi seorang tukang pos agar bisa melewati setiap jalan tepat satu kali dan kembali ke titik awal.

Dalam istilah graf, masalah ini adalah mencari sirkuit Euler. Jika grafnya adalah graf Euler (semua titik memiliki derajat genap), maka sirkuitnya mudah ditemukan.

Namun, jika grafnya bukan graf Euler, maka beberapa jalan harus dilalui lebih dari satu kali. Oleh karena itu, masalah ini dirumuskan kembali menjadi mencari rute terpendek yang dapat dilalui oleh tukang pos untuk melewati setiap jalan minimal satu kali dan kembali ke titik awal.

Sebagaimana persoalan pedagang keliling, hingga kini belum ada algoritma yang efisien untuk menyelesaikan CPP secara umum.