Aplikasi Graf pada Permainan Catur

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).
Setiap garis berhubungan (adjacent) dengan satu titik atau dua titik, titik-titik 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 adalah titik-titik ujung garis untuk i = 0, 1, 2, …, n.
Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua garisnya berbeda dan dituliskan sebagai dengan dengan . Path sederhana dengan panjang n dari v ke w adalah path dari v ke w yang semua titiknya berbeda, berbentuk dengan dengan dan untuk k ≠ m.
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 dengan dan untuk k ≠ m kecuali .
Dalam perkembangannya aplikasi graf yang sering digunakan untuk menentukan jarak terpendek, atau yang sering digunakan oleh para penjaja, traveling, knight’s 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.
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.