Apa itu graf???

TEORI GRAF

Pada ilmu matematika dan ilmu komputer, teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) ataubusur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman.

Pengertian GRAF dalam matematika

“Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, dimana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).”

Mudahnya untuk memahami graf, Graf adalah himpunan/kumpulan  titik - titik yang memiliki bobot yang dan saling dihubungkan. Titik dalam graf diknal juga dengan simpul/vertex. Sebuah graf memiliki simpul2 yang dihubungkan oleh garis (busur). Pada kehidupan sehari-hari, secara tidak langsung kita menerapkan teori graf untuk mencari jalan pulang dengan rute terpendek. Atau contoh lainnya dapat kita temukan pada langkah-langkah di permainan catur dan halma.

Graf juga banyak dipakai untuk membantu menyelesaikan masalah-masalah yang berhubungan dengan Kecerdasan Buatan (Artificial Intelligence), seperti dalam contoh, yang merupakan suatu teka-teki yang banyak dipakai sebagai ilustrasi. Dalam hal ini, graf digunakan untuk menyatakan hubungan-hubungan yang terjadi di antara objek-objek. Dengan cara itu, deduksi ke kesimpulan akan lebih mudah dibuat.

Contoh
Ada sebuah pulau yang penghuninya hanya terdiri dari 2 macam yaitu : pemakan orang (cannibal) dan pemakan sayuran (vegetarian). Pada mulanya, ada 2 orang pemakan orang dan 2 orang pemakan sayuran di sisi barat sungai. Di sisi barat itu pula terdapat sebuah perahu kecil yang hanya dapat menampung paling banyak 2 orang. Masalahnya adalah bagaimana cara mengangkut keempat orang tersebut ke sisi timur sungai. Syaratnya adalah : jumlah pemakan manusia pada suatu sisi sungai tidak boleh lebih banyak dari jumlah pemakan sayuran di sisi yang sama, karena hal itu akan menyebabkan pemakan manusia akan memakan pemakan sayuran.

Penyelesaian:

Suatu cara penyelesaian yang sistematis adalah dengan menggambarkan semua kemungkinan keadaan, dan kemudian menghilangkan bagian-bagian yang tidak mungkin terjadi karena tidak memenuhi kendala yang diisyaratkan.

Misalkan simbol “v” menyatakan pemakan sayuran, “c” menyatakan pemakan orang, “B” menyatakan perahu dan simbol "/" menyatakan sungai. Dengan menggunakan simbol tersebut maka vvcB/c berarti suatu keadaan di mana di sisi barat sungai (di sebelah kiri simbol /) ada 2 orang pemakan sayuran dan satu orang pemakan orang, sedangkan di sisi timur sungai ada seorang pemakan orang. Perahu ada di sisi barat sungai.

Semua kemungkinan keadaan di sungai tersebut dapat digambarkan pada Gambar 6 (sumbu mendatar menyatakan jumlah pemakan sayur di timur sungai dan sumbu tegak menyatakan jumlah pemakan orang di timur sungai). Pada suatu titik tertentu, ada 2 kemungkinan posisi perahu (B), yaitu di kiri sungai atau di kanan sungai.

  

Selanjutnya, dihilangkan keadaan-keadaan yang tidak mungkin terjadi:
a. Karena jumlah pemakan orang (o) di suatu sisi sungai tidak boleh lebih banyak dari jumlah pemakan sayurnya (s), maka titik-titik : v/Bvcc, vB/vcc, vcc/Bv, vccB/v harus dihilangkan
b. Perahu harus berada pada sisi sungai yang ada orangnya. Jika tidak demikian, maka tidak ada orang yang dapat menyeberang. Oleh karena itu, harus dihilangkan titik-titik   vvcc/B dan B/vvcc

Dengan adanya beberapa titik yang dihilangkan tersebut, maka didapatkan keadaan yang dinyatakan pada Gambar berikut

Dari titik-titik yang tersisa, dibuat garis-garisnya. Suatu garis menghubungkan 2 buah titik yang dapat dicapai satu dari yang lainnya. Sebagai contoh, titik ssoP/o dapat dihubungkan dengan titik c/Bvvc karena dari titik vvcB/c, perahu dapat mengangkut 2 orang pemakan sayur (s) ke sisi kanan sungai, sehingga didapatkan titik c/Bvvc. Kondisi ini juga berlaku sebaliknya. Dari titik c/Bvvc, perahu dapat mengangkut 2 orang pemakan sayur ke kiri sungai sehingga didapatkan titik vvcB/c. Dengan penambahan semua garis yang mungkin dibuat, maka didapatkan graf yang dinyatakan pada Gambar berikut.

Untuk menyelesaikan masalah tersebut, berarti harus dicari jalur (garis) yang menghubungkan titik vvccB/ (perahu dan semua orang yang terlibat berada di barat sungai) dengan titik /Bvvcc (perahu dan semua orang yang terlibat berada di timur sungai)

Dari Gambar 3 didapatkan 2 kemungkinan jalur yaitu :
vvccB/ ® vv/Bcc ® vvcB/c ® c/Bvvc ® ccB/vv ® /Bvvcc
atau:
vvccB/ ® vc/Bvc ® vvcB/c ® c/Bvvc ® ccB/vv ® /Bvvcc

Definisi 2
Graf Sederhana (Simple Graph) adalah graf yang tidak mempunyai loop ataupun garis paralel.

PENERAPAN GRAF PADA PERMAINAN CATUR

Untuk penjelasan kali ini, saya memilih permainan catur sebagai media penerapan teori graf. Knight’s Tour dimana ini merupakan suatu aplikasi dari teori graf pada permainan catur papan. Suatu Knight’s Tour pada papan catur adalah rangkaian perjalanan kuda catur pada papan catur sehingga seluruh kotak terlewati kuda tepat satu kali.

Aturan langkah kuda pada permainan catur adalah sebagai

berikut :

•        Melangkah dua persegi ke arah horisontal kemudian satu persegi ke arah vertikal, atau

•        Melangkah dua persegi ke arah vertikal kemudian satu persegi ke arah horisontal, atau

•        Melangkah dua persegi ke arah vertikal kemudian satu persegi ke arah horisontal, atau

•        Melangkah satu persegi ke arah vertikal kemudian dua 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)

Contoh Closed Knight’s Tour

Di atas adalah contoh dari Knight’s Tour. Angka 1-64 menandakan urutan kotak yang dilewati oleh kuda catur tersebut. Langkah yang diambil oleh kuda urut dari 1

sampai dengan 64.

1. ALGORITMA RUNUT BALIK (BACKTRACK)

Algoritma runut-balik (backtracking algorithm) adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus. Runut-balik, yang merupakan perbaikan dari algoritma bruteforce, secara sistematis mencari solusi persoalan di antara  semua kemungkinan solusi yang ada. Dengan metode ini, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat. Runut-balik lebih alami dinyatakan dalam algoritma rekursif. Kadang-kadang disebutkan pula bahwa

runut-balik merupakan bentuk tipikal dari algoritma rekursif. Istilah runut-balik pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Selanjutnya, R. J. Walker, Golomb, dan Baumert menyajikan uraian umum tentang runut-balik dan penerapannya pada berbagai persoalan.

2. APLIKASI ALGORITMA RUNUT-BALIK PADA KNIGHT’S TOUR

Algoritma runut-balik (backtracking algorithm) dapat dipakai untuk menyelesaikan permasalahan dari Knight’s Tour. Ide dasar dari algoritma runut balik adalah dengan membangun solusi-solusi parsial dari masalah (dalam hal ini jalan selangkah pada papan) lalu mencoba memperluas solusi tersebut. Jika solusi yang telah dikembangkan gagal (langkah selanjutnya tidak menuju solusi) maka akan dilakukan runut-balik dan mencoba solusi parsial lainnya.

Algoritma runut-balik yang dipakai adalah:

1. Dari kotak tempat kuda tersebut berada, dibangkitkan langkah-langkah berikutnya yang memungkinkan dilalui oleh kuda tersebut.

2.    Salah satu langkah (kotak) dipilih untuk diperluas.

3.    Kuda melangkah ke kotak yang dipilih tersebut.

4.    Kembali ke langkah satu sampai langkah yang diperluas tidak dapat mencapai  solusi (kuda tidak dapat melangkah lagi).

5.  Pencarian langkah dilakukan dengan melakukan runut balik ke langkah yang telah dilalui terdekat dan kuda melangkah balik ke kotak tersebut dan kembali ke langkah satu.

6. Pencarian langkah dihentikan bila telah melakukan solusi atau tidak ada  langkah yang memungkinkan lagi bagi kuda catur tersebut.

Kesimpulan

Teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) ataubusur (arc). Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Pada intinya penggunaan graf pada kehidupan sehari-hari sudah sering kita temukan. Misalnya ketika kita memilih rute jalan pulang yang tercepat dengan mempertimbangkan segala alternatif yang ada untuk tiba di rumah dengan cepat. Contoh lain yaitu ketika hendak memutuskan suatu perkara dengan terlebih dahulu mengidentifikasikan masalah apa saja yang harus diselesaikan dan hal apa yang akan terjadi jika kita melakukan tibdakan tersebut.