Bab 1
PENDAHULUAN
1.1 Latar Belakang Masalah
Teori graf merupakan pokok bahasan yang memiliki banyak terapan sampai saat ini. Graf di gunakan untuk merepresentasikan objek – objek diskrit dan hubungan antara objek – objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, verteks, bulatan, atau verteks, sedangkan hubungan antara objek dinyatakan dengan garis.
Konsep graf Eulerian yang diawali oleh karya Euler pada problem Jembatan Konigsberg pada tahun 1735 merupakan awal dari lahirnya teori graf. Meskipun umurnya relatif muda, teori graf sebagai cabang dari matematik diskrit telah berkembang sangat pesat akhir akhir ini, baik dalam bidang pengembangan teori maupun aplikasi di berbagai bidang. Di sadari atau tidak, banyak aplikasi teori graf dalam kehidupan kita. Banyak sekali struktur yang bisa di representasikan dengan graf banyak masalah yang bisa diselesaikan dengan bantuan graf, bahkan dalam permainan catur pun ternyata ada aplikasi teori graf.
Suatu graf adalah himpunan benda – benda yang disebut verteks (atau node) yang terhubung oleh sisi (atau edge atau arc). Biasanya graf digambarkan
Universitas Sumatera Utara
sebagai kumpulan verteks (melambangkan verteks) yang dihubungkan oleh garis – garis (melambangkan sisi atau edge).
Dalam bahasa matematika di sebutkan: Graf G = (V,E), yang dalam hal ini : V = Himpunan tidak kosong dan berhingga dari verteks – verteks (vertices atau node) ={v1, v2, v3, ... , vn} E = Himpunan sisi (edges atau arcs) yang menghubungkan sepasang verteks ={e1, e2, e3, ... , en}
Order dari graf G, ditulis dengan notasi
, menyatakan banyaknya
verteks (verteks) pada graf G.Pada graf G, jalan J dari verteks v0 ke verteks vn adalah suatu barisan selang seling dari verteks dan sisi v0, e0, v1, ... , vn-1, en-1, vn yang dimulai dan diakhiri dengan verteks, dengan sisi e1 = vivi+1 untuk i = 0, 1, 2, 3, ..., n sedemikian sehingga vivi+1 1,
E(G). Panjang dari jalan v0, e0, v1, ... , vn-1, en-
vn adalah banyaknya sisi pada barisan tersebut. Verteks vo dan vn disebut ujung
dari jalan jalan tersebut. Jika pada jalan J berlaku vo = vn maka J disebut jalan tertutup dan dikatakan jalan terbuka jika vo ≠ vn. Jalan J disebut lintasan (path) bila semua verteksnya berbeda. Sedangkan jika setiap sisinya yang berbeda maka jalan tersebut dinamakan jejak (trail). Jejak tertutup disebut sirkuit. Sirkuit yang semua verteksnya berlainan disebut siklus (cycle).
Dalam graf penulis dapat membagi menjadi dua jenis lintasan, yaitu lintasan Euler dan Hamilton. Lintasan Euler ialah lintasan yang melalui masing – masing edge didalam graf tepat satu kali. Bila lintasan tersebut kembali ke verteks asal, membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Euler. Jadi sirkuit Euler ialah sirkuit yang melewati masing – masing edge tepat satu kali.
Universitas Sumatera Utara
Dan lintasan Hamilton ialah lintasan yang melalui tiap verteks di dalam graf tepat satu kali. Bila lintasan itu kembali ke verteks asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton adalah sirkuit yang melalui tiap verteks didalam graf tepat satu kali, kecuali verteks asal (sekaligus verteks akhir) yang dilalui dua kali.
Di tahun 1859, Matematikawan dari Irish, Sir William Rowan Hamilton mengembangkan permainan yang di beli dari perusahaan mainan di Dublin. Permainan itu dinamakan Prominent Cities. Tujuan dari permainan iu adalah mencari sirkuit sepanjang jalan yang terbentuk sehingga di dalam itu terdapat 20 kota dan dapat dilewati tepat satu kali.
Penulis dapat menggambarkan alat itu dengan sebuah graf : Verteks dari graf melambangakan verteks dari alat tersebut dan panjangnya edges disamakan dengan alat tersebut :
Untuk menentukan sebuah graf itu adalah Siklus Hamilton atau tidak, pastinya lebih sulit daripada menentukan itu Eulerian. Dan tidak ada cara pasti yang diketahui untuk menentukan itu.
Siklus dalam graf akan terbagi menjadi dua yaitu Euler dan Hamilton. Eulerian adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua edges yang ada dalam graf tersebut. Dan tidak menjadi suatu masalah jika sebuah verteks dilewati sebanyak apapun. Tetapi pada Hamilton
Universitas Sumatera Utara
adalah sebuah siklus dalam graf yang memastikan bahwa dirinya telah melewati semua verteks dalam graf tersebut dan hanya tepat satu kali, kecuali verteks awal didatangi dua kali. Jika sebuah verteks itu telah dilewati dua atau lebih dalam suatu siklus maka siklus tesebut tidak dapat dikatakan sebagai siklus Hamiltonian.
Diberikan contoh dalam suatu graf ada terdapat lima buah verteks. Di misalkan A, B, C, D, dan E. Dari siklus yang terjadi penulis dapat menentukan A
siklus itu Hamilton atau tidak. Siklus 1 : A – B – C – D – E Siklus 2 : A – B – C – B – D – E
B
E
Siklus 3 : A – C – B – E – D Siklus 4 : A – B – E – C – B – D D
C
Dari empat siklus penulis dapat lihat siklus 1 dan 3 adalah Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan hanya tepat satu kali. Tetapi pada siklus 2 dan 4 adalah bukan Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan ada yang melebihi satu kali. Pada siklus 2 dan 4 muncul verteks B sebanyak dua kali. Dan itu melanggar
sifat dari sebuah siklus Hamilton. Siklus Hamilton dapat
ditemukan di banyak hal.
Pembahasan dalam makalah ini difokuskan pada aplikasi teori graf pada permaianan catur. Permasalahan yang diangkatpun dikhususkan pada siklus Hamiltondan langkah kuda (Knight’s Tour) pada permainan catur.
Permasalahan menarik yang terkait dengan Siklus Hamilton adalah langkah kuda (Knight’s Tour). Suatu Knight’s Tour pada papan catur adalah rangkaian perjalanan kuda catur pada papan catur sehingga seluruh kotak (kotak terkecil) terlewati kuda tepat satu kali.
Aturan langkah kuda pada permainan catur adalah sebagai berikut :
Universitas Sumatera Utara
• Melangkah dua kotak ke arah horisontal kemudian satu persegi ke arah vertikal, atau • Melangkah dua kotak ke arah vertikal kemudian satu persegi ke arah horisontal.
Jika dalam Knight’s Tour setiap persegi dari papan catur dapat dilewati tepat satu kali dan kuda kembali pada persegi semula maka disebut langkah kuda tertutup (Closed Knight’s Tour). Namun, jika semua persegi telah dilewati dan kuda tidak dapat kembali ke posisi semula maka disebut langkah kuda yang terbuka (Open Knight’s Tour).
1.2 Perumusan Masalah
Masalah yang akan diangkat penulis adalah bagaimana penerapan teori graf khususnya siklus Hamilton pada saat menyelesaikan persoalan Knight’s Tour.
1.3 Pembatasan Masalah Dalam Skripsi ini masalah yang dibahas penulis adalah penyelesaian knight’s tour dalam papan catur berukuran 8x8. Setelah itu, Knight’s Tour ini hanya dilakukan oleh sebuah kuda dalam catur dengan langkahnya yang berbentuk “L”.
1.4 Tinjauan Pustaka
Sam ganzfried[3], sebuah bentuk dari Knight’s Tour dalam papan catur adalah semua pasangan berurutan yang berhubungan dan tidak ada kotak di dalam barisan itu lebih dari sekali. Penulis dapat memisalkan langkah kuda tersebut dengan menamai setiap kotak dan dipakai dalam barisan. Dan tidak akan muncul kembali di dalam barisan itu. Di semua verteks yang telah muncul dalam barisan itu ditetapkan dan tidak di kunjungi lagi. Maka didapat jumlah langkah yang terjadi adalah lebih kecil atau sama dengan jumlah kotak yang ada pada papan catur yaitu 64 langkah.
Universitas Sumatera Utara
Brandon D. McKay[5] Langkah kuda harus mencari alternatif dari kotak genap dan ganjil dari semua kotak di papan catur tersebut. Di papan dengan jumlah kotaknya ganjil maka perjalanan langkah kuda harus dimulai dari kotak yang genap dan akan berakhir di kotak yang genap juga. Di papan dengan jumlah kotaknya genap maka perjalanan akan dimulai dari satu kotak dan berakhir di kotak yang berbeda warnanya. Dan di dapati bahwa tidak adanya sirkuit yang terjadi jika papan n x m dan hasil kali m dan n adalah ganjil.
Joe De Maio[4] Tidak akan ada closed Knight’s Tour jika bagian dari sisinya adalah n dimana n adalah ganjil. Dan menjadi penjelasan yang jelas tidak ada hasil jika n x m dimana n dan m adalah bilangan ganjil. Itu tidak dapat dihasilkan untuk sebuah persegi. Khususnya untuk kebebasan lebih memilih persegi dengan 8 sampai 24 langkah. Untuk papan catur dengan jumlah ganjil dan dimulai dari sudut kiri atas dengan warna hitam.
1.5 Tujuan Penelitian
Tujuan yang ingin dicapai penulis adalah mengetahui analisis teori graf siklus Hamilton untuk Knight’s Tour sehingga permasalahan Knight’s Tour dapat diselesaikan.
1.6 Manfaat Penelitian
Penelitian ini dapat dimanfaatkan untuk menjadi bahan permasalahan dalam aplikasi teori graf khususnya dalam sirkuit Hamilton dan dapat diterapkan didalam pemasangan ubin sebagai perwujudan dalam pengaplikasian teori graf.
1.7 Metodologi Penelitian
Metodologi penelitian ini bersifat literatur atau kepustakaan dengan langkah :
Universitas Sumatera Utara
1. Memaparkan bagaimana sebuah siklus hamilton akan berada dalam sebuah permainan catur dengan langkah dari sebuah Knight’s Tour. 2. Mencari beberapa langkah yang mungkin dan merupakan hasil dari sebuah Knight’s Tour a.
Menentukan apakah sebuah knight tour’s itu adalah sebuah open Knight’s Tour.
b.
Menentukan apakah sebuah knight tour’s itu adalah sebuah open Knight’s Tour.
Universitas Sumatera Utara
