Lintasan Graf Euler dan Hamilton

Definisi Graf Eulerian

Lintasan Euler atau Eulerian path melalui graf adalah lintasan yang daftar sisinya memuat setiap sisi graf tepat satu kali.  

Lintasan Euler yang berawal dan berakhir pada simpul yang sama disebut sirkuit Euler. Graf Euler adalah graf yang memiliki sirkuit Euler.

Teorema Graf Euler 

Kasus Umum: Graf tak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki nol atau dua simpul yang berderajat ganjil. Jika tidak ada simpul yang berderajat ganjil, maka grafnya adalah Euler.

Berdasarkan teorema diatas akan didapatkan teorema dibawah:

Jika suatu graf terhubung dan setiap simpul berderajat genap, maka ia memiliki setidaknya satu sirkuit Euler.

Jika suatu graf terhubung dan memiliki tepat dua simpul berderajat ganjil, maka graf tersebut memiliki paling sedikit satu lintasan Euler (biasanya lebih). Setiap jalur tersebut harus dimulai pada salah satu simpul derajat ganjil dan berakhir di simpul lainnya.

Jumlah derajat semua simpul dari suatu graf sama dengan dua kali jumlah sisi (dan karenanya harus bilangan genap).

Cara Mencari Lintasan Sirkuit Euler / Eulerian 

1. Pastikan bahwa setiap simpul dalam jaringan memiliki derajat genap.
2. Mulailah rangkaian Euler di sembarang simpul dalam jaringan.
3. Saat Anda memilih tepi, jangan pernah menggunakan tepi yang merupakan satu-satunya koneksi ke bagian jaringan yang belum Anda kunjungi.
4. Beri label tepi dalam urutan yang Anda tempuh dan lanjutkan ini sampai Anda telah melakukan perjalanan di sepanjang setiap tepi tepat satu kali dan Anda berakhir di simpul awal.

Definisi Graf Hamiltonian

Lintasan Hamilton atau Hamiltonian melalui suatu graf adalah lintasan yang daftar simpulnya berisi setiap simpul dari graf tepat satu kali, kecuali jika lintasannya adalah sirkuit, dalam hal ini simpul awal muncul untuk kedua kalinya sebagai simpul terminal/akhir. Jika lintasannya berupa sirkuit, maka disebut sirkuit Hamilton. Graf Hamilton adalah graf yang memiliki sirkuit Hamilton.

Teorema Hamilton

Grafik lengkap pasti memiliki sirkuit Hamilton.

Graf lengkap dengan N simpul adalah (N-1)! sirkuit Hamilton. Karena setengah dari sirkuit adalah bayangan cermin dari setengah lainnya, sebenarnya hanya ada setengah dari banyak sirkuit unik ini.

Cara mengatasi Travelling Salesman Problem (TSP)

Masalah penjual keliling adalah masalah di mana Anda membayangkan bahwa penjual keliling melakukan perjalanan bisnis. Dia mulai di kota asalnya (A) dan kemudian perlu melakukan perjalanan ke beberapa kota yang berbeda untuk menjual barang dagangannya (kota lainnya adalah B, C, D, dll.). Untuk menyelesaikan TSP, Anda perlu menemukan cara termurah bagi penjual keliling untuk memulai di rumah, A, bepergian ke kota lain, dan kemudian pulang ke A di akhir perjalanan. Ini hanya menemukan sirkuit Hamilton dalam grafik lengkap yang memiliki bobot keseluruhan terkecil. Ada beberapa algoritma yang berbeda yang dapat digunakan untuk memecahkan masalah jenis ini.

Algoritma Brute Force

1. Daftar semua kemungkinan sirkuit Hamilton dari grafik.
2. Untuk setiap sirkuit, temukan bobot totalnya.
3. Sirkuit dengan bobot total paling kecil adalah sirkuit Hamilton yang optimal.

Algoritma Tetangga Terdekat (Nearest-Neighbor Algorithm)

1. Pilih simpul sebagai titik awal.
2. Dari titik awal pergi ke simpul dengan tepi dengan bobot terkecil. Jika ada lebih dari satu pilihan, pilih secara acak.
3. Lanjutkan membangun sirkuit, satu per satu simpul dari antara simpul yang belum dikunjungi.
4. Dari simpul terakhir, kembali ke titik awal.

Algoritma Tetangga Terdekat Berulang (Repetitive Nearest-Neighbor Algorithm)

1. Biarkan X menjadi sembarang simpul. Terapkan Algoritma Tetangga Terdekat dengan menggunakan X sebagai titik awal dan hitung total biaya rangkaian yang diperoleh.
2. Ulangi proses tersebut dengan menggunakan setiap simpul lain dari graf sebagai simpul awal.
3. Dari sirkuit Hamilton yang didapat, pertahankan yang terbaik. Jika ada titik awal yang ditunjuk, tulis ulang rangkaian ini dengan titik tersebut sebagai titik referensi.

Algoritma Tautan Termurah (Cheapest-Link Algorithm)

1. Pilih link dengan bobot terkecil terlebih dahulu (jika ada seri, pilih salah satu secara acak). Tandai tepi yang sesuai dengan warna merah.
2. Pilih tautan termurah berikutnya dan tandai tepi yang sesuai dengan warna merah.
3. Lanjutkan memilih tautan termurah yang tersedia. Tandai tepi yang sesuai dengan warna merah kecuali jika a) menutup sirkuit atau b) menghasilkan tiga tepi yang keluar dari satu simpul.
4. Ketika tidak ada lagi simpul untuk dihubungkan, tutup sirkuit merah.