Pengantar Teori Graf

 

Hai hai semua . Ketemu lagi sama aye, Admin K yang kritis lagi manis . Tentu saja, masih di blog kesayangan kita yang gak bisa dianggap sepele ini, KnK Land. Nah, kali ini aye bakal membahas salah satu bidang yang lumayan unik dalam matematika terutama kombinatorika. Aye bakal ngebahas teori graf atau dalam bahasa kafir Inggris disebut Graph Theory. Eits, disini kita gak ngebahas tentang grafik koordinat x-y atau sejenisnya. Nah, daripada kalian penasaran, mending kita langsung aja cekidoot .

Sebelum masuk ke pembahasan utama. Alangkah baiknya aye bercerita terlebih dahulu.

Pada zaman dahulu terdapat sebuah kota. Kota tersebut bernama kota Königsberg.

Kota tersebut dibangun di antara kedua sisi sungai Pregel dan meliputi dua pulau yakni Kneiphof dan Lomse yang semuanya tersambung satu sama lain oleh 7 jembatan. Jadi, terdapat 4 area yang terhubung satu sama lain oleh jembatan.

Suatu ketika, para warga yang tinggal di kota tersebut bertanya-tanya, apakah bisa melewati semua jembatan dengan syarat masing-masing jembatan dilewati satu kali? Seorang pria, sebut saja namanya Oddy pun mencoba membuat coret-coretan pada kertas untuk mencari rute mana yang harus dilewati sehingga semua jembatan bisa terlewati tepat satu kali. Dia pun mencoba sampai belasan kali, tidak menemukan hasilnya. Kemudian, seorang wanita, sebut saja namanya Mia menyarankan untuk melakukan coba-coba untuk setiap kemungkinan yang mungkin. Selain itu, para warga yang lain pun ikut berpartisipasi untuk memecahkan teka-teki ini.

Berita mengenai teka-teki jembatan Königsberg ini pun menyebar dengan cepat bagaikan terbawa angin sampai suatu ketika tersiul di telinga seorang matematikawan yang bernama Leonhard Euler. Euler tidak menyukai ide untuk mencoba semua rute yang mungkin. Untuk menyelesaikan masalah ini, Euler lebih menyukai pendekatan dengan menggunakan daya analisa serta pemahaman yang lebih mendalam. Melakukan brute force untuk mencoba semua kemungkinan tidak dapat memberikan pemahaman dan pengertian.

Lalu, ide seperti apa yang dimiliki oleh Euler sehingga bisa memecahkan teka-teki ini. Setelah beberapa lama, Euler pun menemukan solusinya dan menyimpulkan bahwa tidak ada cara yang bisa dilakukan untuk melewati semua jembatan masing-masing tepat satu kali. Euler menggunakan suatu alat, alat itu bernama graf.

Mari kita lihat proses kotretannya Euler.

Mari kita perhatikan terlebih dahulu dengan seksama peta kota Königsberg.

Perhatikan bahwa kota Königsberg adalah kota yang terdiri dari 4 "pulau" atau bagian yang terhubung oleh 7 buah jembatan (yang ditandai warna merah). Kalau kita misalkan pulau dengan titik, lalu kita hubungkan titik-titik tersebut dengan garis sesuai dengan jembatan yang ada, maka jadilah gambar sebagai berikut.

Nah, masalah yang awalnya masalah "bagaimana cara melewati semua jembatan masing-masing sekali lewat" berubah menjadi masalah "bagaimana menggambar garis-garis tersebut dengan hanya sekali garis tanpa mengangkat pulpen atau pensil". Jadi, kalau kita bisa menggambar garis tersebut dengan sekali garis tanpa mengangkat pensil maka kita juga bisa melewati semua jembatan di kota Königsberg dengan sekali jalan. Sebaliknya juga berlaku kalau tidak. Apakah masalah kota Königsberg selesai? Yap, selesai, diselesaikan oleh Euler. Ternyata terbukti bahwa mustahil kita bisa melewati semua jembatan di kota Königsberg masing-masing satu kali hanya dalam sekali jalan. Nah, sekumpulan titik dan garis-garis penghubung (yang disebut sisi) inilah yang disebut dengan graf.

Secara rigor atau biar lebih matematika, graf didefinisikan sebagai pasangan himpunan. Kedua himpunan tersebut adalah himpuan titik dan sisi. Himpunan titik sendiri bisa sebarang himpunan apa saja asalkan berhingga. Sedangkan himpunan sisi adalah himpunan yang berisi beberapa atau semua pasangan tak berurutan dari elemen-elemen di himpunan titik.

Definisi Graf

Suatu pasangan himpunan   disebut graf apabila yang disebut himpunan titik (atau biasa juga disebut himpunan simpul) merupakan himpunan berhingga (setiap elemennya disebut titik/simpul) dan adalah subhimpunan dari yakni disebut himpunan sisi serta setiap elemennya disebut sisi (secara intuisi, setiap elemen di mengartikan dua titik berbeda di terhubung di graf ).

Bagi kalian yang pusing-pusing dikit, nih aye berikan contoh. Misal himpunan titiknya adalah dan himpunan sisinya adalah . Dengan demikian, anggur, apel, stroberi, dan mangga adalah titik. Selanjutnya, anggur dan stroberi saling terhubung, begitupun apel dengan stroberi dan mangga. Graf ini bisa digambarkan sebagai berikut.

Dua titik yang saling terhubung oleh sisi disebut saling bertetangga. Contohnya titik "stroberi" bertetangga dengan titik "apel" karena ada sisi {stroberi, apel}. Sedangkan sisi yang menghubungkan keduanya disebut "mengaitkan". Jadi, sisi {stroberi, apel} mengaitkan titik "stroberi" dan titik "apel".

Definisi graf di atas memang definisi yang sangat ketat sehingga tidak memungkinkan adanya titik yang bertetangga dengan dirinya sendiri atau dua titik dihubungkan oleh lebih dari dua sisi. Memang ada orang yang mendefinisikan graf dengan pendefinisian yang lain sehingga memungkinkan adanya loop (titik bertetangga dengan dirinya sendiri) serta sisi paralel (2 sisi atau lebih yang sama-sama menghubungkan 2 titik tertentu). Definisi di atas biasanya disebut definisi "graf sederhana" atau "simple graph" bagi kalian yang lebih prefer definisi graf secara umum yang memungkinkan adanya loop dan sisi paralel. Ini hanya masalah definisi aja, silakan gunakan definisi yang mana saja tergantung selera dan kebutuhan.

Berikut adalah contoh graf yang mempunyai loop dan sisi paralel. Ini tentu saja tidak menggunakan definisi graf yang di atas.

 

Contoh di atas merupakan contoh graf yang bukan graf sederhana sebab terdapat loop. Bisa dilihat bahwa titik a bertetangga dengan dirinya sendiri yang dihubungkan oleh sisi f. Hal yang sama juga berlaku pada titik c. Selain itu, titik a dan b terhubung oleh dua sisi paralel yakni sisi g dan sisi h. Hal yang sama juga berlaku pada titik e dan d yang dihubungkan oleh 3 sisi paralel.

Nah, itulah sedikit pengantar teori graf. Disini aye hanya membahas sedikit mengenai definisi serta notasi yang digunakan. Untuk lebih memperdalam lagi mungkin masalah notasi, pengaplikasian, atau teori lebih lanjut bakal aye posting lain kali. Yang terpenting intuisinya dapat dulu kalo graf itu seperti apa, bagaimana representasinya sebagai pasangan dua buah himpunan serta representasinya dalam bentuk gambar. Kalau ada pertanyaan, protes, atau tambahan silakan sampaikan di kolom komentar. Sampai jumpa di postingan selanjutnya. Bye~