Logo UNTAN Universitas
Tanjungpura
Pontianak

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.

[img] PDF (Cover-Bab1)
Cover-Bab1_H1011201041.pdf - Published Version

Download (745kB)
[img] 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:
CreatorsNomor Induk Mahasiswa (NIM)Email
Fadilatul, AmaliaNIMH1011201041UNSPECIFIED
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 View Item