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.

MU VS CHELSEA

Manchester United akan berhadapan dengan Chelsea, sementara di tempat lain Arsenal akan menghadapi Wolverhampton Wanderers. Akankah terjadi suksesi pemuncak klasemen akhir pekan ini?

MU yang baru saja ditaklukkan Bayern Munich di Allianz Arena akan menjamu Chelsea di Old Trafford hari Sabtu ini. The Blues beruntung karena mereka punya waktu lebih banyak untuk mempersiapkan diri menghadapi laga ini.

Sejak tersingkir dari Liga Champions, pasukan arahan Carlo Ancelotti ini tinggal fokus ke Premier League, dan Piala FA sebagai tambahannya. Terhitung sejak membantai Aston Villa 7-1 pada akhir pekan lalu, Chelsea punya waktu tujuh hari untuk memulihkan tenaga.

Bahkan penyerang andalan mereka, Didier Drogba, sudah beristirahat sejak melawan Villa. Drogba yang sama sekali tak diturunkan kala melawan Villa bisa jadi akan sangat segar pada akhir pekan ini.

Bandingkan dengan MU yang harus repot-repot membagi konsentrasi dengan laga melawan Bayern hari Rabu lalu dan menjaga kebugaran pemain-pemainnya dengan melakukan rotasi. Sial bagi 'Setan Merah', sudah berusaha demikian pun tetap saja ada ganjalan buat mereka.

MU harus kehilangan Wayne Rooney yang merupakan mesin gol utama mereka musim ini mengalami cedera  saat bertandang kandang Bayern Munich. Kemungkinan Besar mesin gol tersebut, tak bisa diturunkan  kala menghadapi Chelsea. Sir Alex Ferguson pun tinggal mengandalkan Dimitar Berbatov, yang akhir pekan lalu mencetak dua gol, dan penyerang muda, Federico Macheda, di lini depan.

Dengan status sebagai pemuncak klasemen, kememang adalag harga mati bagi  MU jika tak ingin posisinya diambil-alih Chelsea. Dengan poin 72 yang sudah dikoleksi, MU kini hanya tinggal unggul satu poin atas Chelsea.

Di sisi lain, Arsenal akan melihat pertandingan tersebut dari jarak jauh. The Gunners yang akan menjamu Wolverhampton di Emirates Stadium di atas kertas tak akan sulit meraih tiga poin atas lawannya itu.

Hanya saja, pasukan asal London Utara ini terhalang masalah cedera. Cesc Fabregas dan William Gallas adalah dua nama terakhir yang masuk ruang perawatan setelah Arsenal ditahan imbang 2-2 oleh Barcelona di Liga Champions kamis kemarin.

Tetapi pasukan arahan Arsene Wenger ini tentunya tak akan menahan godaan meraih tiga poin atas Wolves, sembari berharap MU dan Chelsea imbang saja. Ya, dengan sisa enam pekan menuju akhir musim, mendoakan lawan bernasib buruk agar diri sendiri bisa meraih titel juara memang terlihat sah-sah saja.