APLIKASI GRAF PADA PERMAINAN CATURSKRIPSI Diajukan Kepada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Yogyakarta Untuk Memenuhi Sebagian Persyaratan Guna Memperoleh Gelar Sarjana Sains

Disusun Oleh Epri Kurniawan NIM. 06305144031

PROGRAM STUDI MATEMATIKA JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI YOGYAKARTA 2010

1

PENDAHULUAN

A. Latar Belakang Matematika mempunyai andil cukup besar dalam kemajauan diberbagai bidang. Teori graf merupakan salah satu cabang matematika yang turut memberikan andil. Konsep graf Eulerian yang diawali oleh karya Euler pada permasalahan jembatan Konighsberg pada tahun 1736, Euler merupakan matematikawan yang terkenal dari Swiss. Konigsberg merupakan suatu kota di Prusia bagian timur Jerman. Di kota itu mengalir sebuah sungai pregel yang membelah kota dan memisahkan daratannya menjadi empat bagian. Untuk menghubungkan keempat daratan tersebut dibutuhkan tujuh jembatan. Dari hal tersebut dibuat sebuah teka-teki yaitu mungkinkah seseorang berjalan mengelilingi kota yang dimulai dan diakhiri pada tempat yang sama, dengan melintasi ketujuh jembatan masing-masing tepat satu kali. Graf merupakan suatu diagram yang memuat informasi tertentu jika diinterpresentasikan secara tepat. Dalam kehidupan sehari-hari graf digunakan untuk menggambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengerti. Secara informal, suatu graf adalah himpunan benda-benda yang disebut vertex (atau node) yang terhubung oleh sisi (atau edge atau arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan vertex) yang

dihubungkan oleh garis-garis (melambangkan sisi). Secara formal atau dalam bahasa matematika, suatu graf disimbolkan dengan G terdiri dari dua himpunan yang berhingga, yaitu himpunan titik-titik tidak kosong disimbolkan dengan V(G) dan himpunan garis-garis disimbolkan E(G).

2

Setiap garis berhubungan (adjacent) dengan satu titik atau dua titik, titiktitik tersebut disebut Titik Ujung (Isolating Poin). Garis yang hanya berhubungan dengan satu titik ujung dinamakan Loop. Dua garis berbeda yang

menghubungkan titik yang sama disebut Garis Paralel. Dua titik dikatakan berhubungan jika ada garis yang menghubungkan kedua titik tersebut. Titik yang tidak mempuyai garis hubung dengan titik lain dinamakan Titik Terasing. Graf yang tidak mempunyai titik, sehingga tidak mempunyai garis dinamakan Graf Kosong. Berdasarkan jenis garis-garisnya, graf dibedakan dalam dua kategori yaitu Graf Berarah (Directed Graph atau yang sering disebut dengan Digraph) dimana semua garis berarah dan Graf Tidak Berarah (Undirected Graph) dimana semua garisnya tidak berarah. Lintasan (Path) bila semua titiknya berbeda. Sedangkan jika setiap sisinya yang berbeda maka jalan tersebut dinamakan Jekak (Trail). Jekan tertutup disebut sirkel sirkuit yangs emua titiknya berlainan disebut sirkuit (Cycle). Order dari graf, ditulis dengan notasi |V(G)|, yang menyatakan banyaknya titik pada graf G. Pada graf G, jalan (Walk) v ke w adalah barisan titik-titik berhubungan dan garis secara selang-seling, diawali dari titik v dan diakhiri pada titik w. Jalan dengan panjang n dari v ke w ditulis sebagai berikut : dengan titik ujung garis untuk i = 0, 1, 2, , n. adalah titik-

Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua garisnya berbeda dan dituliskan sebagai dengan adalah path dengan dari v ke . Path sederhana dengan panjang n dari v ke w w yang semua dengan untuk k m. titiknya dengan berbeda, dan berbentuk

3

Sirkuit dengan panjang n adalah path yan dimulai dan diakhiri pada titik yang sama. Sirkuit adalah path yang berbentuk dengan

. Sirkuit sederhana dengan panjang n adalah sirkuit yang semua titiknya berbeda. Sirkuit sederhana berbentuk dengan dan untuk k m kecuali . dengan

Dalam perkembangannya aplikasi graf yang sering digunakan untuk menentukan jarak terpendek, atau yang sering digunakan oleh para penjaja, traveling, knights tour adalah sirkuit Euler dan sirkuit Hamilton. Menurut Definisi 8.9 Sirkuit Euler G adalah sirkuit dimana setiap titik dalam G muncul paling sedikit sekali dan setiap garis dalam G muncul tepat satu kali (Drs. Jong Jek Siang, 2002 : hal 213). Sedangkan sirkuit Hamilton adalah suatu gaf terhubung G bila ada sirkuit yang mengunjungi setiap titiknya tepat satu kali (kecuali titik awal yang sama dengan titik akhirnya) (Drs. Jong Jek Siang, 2002 : hal 220). Perbedaan sirkuir Euler dan sirkuit Hamilton adalah pada sirkuit Euler, semua garis harus dilalui tepat satu kali, sedangkan semua titiknya boleh dikunjungi lebih dari satu kali. Sebaliknya, dalam sirkuit Hamilton semua titiknya tidak harus dikunjungi tepat satu kali dan tidak harus melaluli semua garisnya. Dalam sirkuit Euler, yang diperhatikan adalah garisnya, sebaliknya dalam sirkuit Hamilton, yang diperhatikan adalah kunjungan pada titiknya. Terlepas dari perbedaan antara sirkuit Euler dan sirkuit Hamilton, terdapat perbedaan yang nyata tentang cara menentukan apakah suatu graf merupakan sirkuit Euler dan apakan suatu graf merupakan sirkut Hamilton. Teorema 8.4 misalkan G adalah graf terhubung. G adalah sirkuit Euler bila dan hanya bila semua titik dalam G mempunyai derajat genap (Drs. Jong Jek Siang, 2002: hal 216). Sebaliknya, tidak ada syarat-syarat yang pasti untuk menentukan apakah suatu graf merupakan sirkuit Hamilton. Hanya saja ada petunjuk untuk menentukan bahwa suatu graf bukan suatu sirkuit Hamilton.

4

Jika G merupakan sirkuit

Hamilton, maka G mempunyai subgraf H

dengan sifat (1) H terhubung, (2) H memuat semua titik G, (3) H mempunyai jumlah garis yang sama dengan jumlah titiknya, dan (4) setiap titik dalam H mempunyai derajad 2. Syarat (1) dan (2) jelas menurut definisi sirkuit Hamilton, yang mengharuskan mengunjungi semua titik dalam G. Syarat (4) adalah sebagai akibat kunjungan semua titik yang hanya boleh dilakukan sekali. Selama kunjungan, di setiap titik pasti ada suatu garis masuk dan satu garis keluar sehingga derajad setiap titik sama dengan 2. Karena dalam sirkuit Hamilton, setiap dua titik dihubungkan dengan tepat satu garis, maka jumlah garis sama dengan jumlah titiknya. Hal ini dinyatakan dalam syarat (3). Jika salah satu dari ke-4 syarat tersebut tidak dipenuhi maka graf-nya bukanlah graf Hamilton. Pada kesempatan kali ini penulis akan membahas lebih detail tentang sirkuit Hamilton, sehingga pembahasan dalam tulisan ini difokuskan pada aplikasi teori graf pada permainan catur.

B. Rumusan Masalah Berdasarkan latar belakang permasalahan tersebut, maka permasalahan yang diangkatpun dikhususkan pada sirkuit Hamilton dan langkah kuda (Knights Tour) pada permainan catur. Permasalahan yang dapat diambil yaitu sebagai berikut: 1. Bagaimana cara menentukan sirkuit Hamilton pada permainan catur? 2. Dipermainan catur, apakah terdapat sirkuit Hamilton pada langkah kuda? 3. Jika diberikan papan catur dengan ukuran standar, yaitu ukuran 8 x 8, apakah terdapat sirkuit Hamilton?

5

C. Tujuan Dari rumusan masalah tersebut, maka tujuan dari penulisan tugas akhir ini adalah sebagai berikut: 1. Dapat mengetahui cara menetukan sirkuit Hamilton secara tepat, sehingga diharapkan nantinya dapat diaplikasikan pada kehidupan sehari-hari; 2. Dapat mengetahui ternyata aplikasi graf juga dapat diaplikasikan pada permainan catur; 3. Dapat menyelesaikan permasalahan yang ada dengan menggunakan sirkuit Hamilton; 4. Dapat mengetahui keunggulan/ kelebihan dalam menggunakan sirkuit Hamilton.

D. Manfaat Manfaat dari penulisan tugas akhir ini adalah: 1. Mengetahui cara menentukan sirkuit Hamilton secara tepat; 2. Mengetahui macam-macam sirkuit Hamilton; 3. Mengetahui kelebihan dalam menentukan rute terpendek dengan menggunakan sirkuit Hamilton; 4. Dapat mengaplikasikan sirkuit Hamilton pada kehidupan sehari-hari secara langsung.

6

7