Penerapan Algoritma Warnsdorff dalam Identifikasi Lintasan dan Sirkuit Hamilton pada Graf Sederhana
Fadilatul, Amalia (2024) Penerapan Algoritma Warnsdorff dalam Identifikasi Lintasan dan Sirkuit Hamilton pada Graf Sederhana. Skripsi thesis, Universitas Tanjungpura.
|
PDF (Cover-Bab1)
Cover-Bab1_H1011201041.pdf - Published Version Download (745kB) |
|
|
PDF (H1011201041_FADILATUL_AMALIA)
H1011201041_FADILATUL_AMALIA.pdf - Accepted Version Restricted to Repository staff only Download (4MB) |
Abstract
Graf Hamilton adalah salah satu konsep dalam teori graf yang berkaitan dengan lintasan yang mengunjungi setiap simpul tepat satu kali sebelum kembali ke simpul awal dalam kasus sirkuit Hamilton. Penelitian ini berfokus untuk menentukan apakah suatu graf memiliki lintasan atau sirkuit Hamilton dengan menggunakan algoritma Warnsdorff. Algoritma Warnsdorff awalnya dikembangkan untuk menyelesaikan permainan Knight’s Tour pada papan catur dengan memilih simpul yang memiliki derajat terkecil untuk mengurangi kemungkinan terjebak dalam kondisi tanpa langkah lanjutan. Namun, algoritma ini memiliki kelemahan karena tidak selalu berhasil menemukan lintasan Hamilton pada berbagai jenis graf. Oleh karena itu, penelitian ini memodifikasi algoritma Warnsdorff dengan strategi pemilihan simpul awal berdasarkan derajat terkecil dan menerapkan mekanisme pencarian ulang jika lintasan Hamilton tidak ditemukan. Jika tetap tidak ditemukan, maka simpul awal akan diganti dengan simpul berderajat terkecil berikutnya hingga lintasan ditemukan atau seluruh kemungkinan telah diuji. Modifikasi ini diharapkan dapat meningkatkan peluang algoritma dalam menemukan lintasan Hamilton dibandingkan dengan algoritma Warnsdorff yang belum dimodifikasi. Metodologi penelitian mencakup penerapan algoritma Warnsdorff yang telah dimodifikasi pada berbagai graf sederhana serta analisis kinerjanya dalam menemukan lintasan Hamilton. Hasil penelitian menunjukkan bahwa modifikasi algoritma Warnsdorff dapat mengidentifikasi lintasan Hamilton dalam beberapa struktur graf. Kesimpulan penelitian ini menegaskan bahwa meskipun modifikasi algoritma Warnsdorff meningkatkan keberhasilannya dalam menemukan lintasan Hamilton, pengembangan lebih lanjut masih diperlukan agar lebih andal dalam menangani graf dengan struktur yang lebih kompleks.
| Item Type: | Thesis (Skripsi) | ||||||
|---|---|---|---|---|---|---|---|
| Creators: |
|
||||||
| Subjects: | 500 – Ilmu Pengetahuan > 510 Matematika > 511 Prinsip-prinsip umum matematika | ||||||
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika S1 | ||||||
| SWORD Depositor: | Robiatul Adawiyah | ||||||
| Depositing User: | Robiatul Adawiyah | ||||||
| Date Deposited: | 23 Jul 2026 04:11 | ||||||
| Last Modified: | 23 Jul 2026 04:11 | ||||||
| URI: | https://repository.untan.ac.id/id/eprint/6557 |
Actions (login required)
![]() |
View Item |
