Grafik terhubung adalah suatu struktur data yang terdiri atas simpul-simpul yang dihubungkan oleh sisi-sisi. Sederhananya, grafik terhubung adalah sebuah jaringan yang terbentuk dari beberapa titik yang dihubungkan oleh garis-garis. Grafik terhubung memiliki beberapa subtipe, seperti pohon (tree), grafik berarah, dan lain-lain.
Pada artikel ini, kita tidak akan membahas jenis-jenis grafik secara rinci, namun kita akan fokus pada salah satu subtipe yang sangat penting dalam memahami grafik terhubung, yaitu grafik berarah. Grafik berarah adalah suatu grafik terhubung yang memiliki sisi-sisi yang diarahkan ke arah tertentu.
Grafik berarah memiliki beberapa ciri khas, seperti derajat simpul (degree of a node). Derajat simpul adalah jumlah sisi yang menghubungi simpul tersebut. Grafik berarah juga dapat memiliki bobot (weight) pada setiap sisi, yang menunjukkan "harga" perjalanannya.
Grafik terhubung digunakan dalam berbagai aplikasi, seperti algoritma dan struktur data penting. Contohnya, grafik terhubung dapat digunakan untuk menyelesaikan masalah penggunaan jaringan internet.
Menyusun Rangkaian Kata
Menggunakan grafik terhubung untuk menyelesaikan suatu masalah sangat menarik. Misalnya, kita memiliki daftar kata-kata seperti {Amsterdam Melbourne New York Kyiv Vienna}. Kita dapat menghubungkan huruf-huruf "nodal" pada kata-kata tersebut menjadi sebuah grafik berarah.
Grafik ini memiliki sisi-sisi yang diarahkan ke arah tertentu, yang menunjukkan "harga" perjalanannya. Jika kita menemukan cara untuk melintasi semua sisi dari titik ke titik sehingga kita mengunjungi setiap sisi hanya satu kali, masalah kita akan terpecahkan.
Mendistribusikan Node pada Diagram
Sekarang kita dapat melihat dengan lebih baik bahwa grafik kita adalah loop tertutup. Kita bisa memulai urutannya dengan kata apa saja, dan itu akan menjadi keputusan yang tepat. Namun, kondisi masalahnya memberi tahu kita bahwa satu solusi saja sudah cukup.
Grafik yang Memuat Jalur Euler
Kita dapat melihat dua konsekuensi: pertama, kita harus menambahkan simpul baru, huruf P, dan kedua, kita melihat bahwa grafik kita tidak dapat lagi dilingkarkan. Kita dapat rangkum semua hal di atas dan perkenalkan dua istilah baru: 1) Graf terhubung yang sisi-sisinya dapat dilintasi hanya dengan mengunjungi masing-masing graf satu kali saja disebut graf yang memuat "jalur Euler" (Eulerian Path). Ciri graf seperti itu (kecuali tidak adanya simpul tanpa tepi) adalah derajat genap semua simpul kecuali dua (dan hanya dua).
- Jika ternyata dapat kembali ke simpul semula, kita katakan bahwa terdapat "siklus Euler" pada grafik tersebut (Eulerian Cycle). Ciri graf seperti itu (kecuali tidak adanya simpul tanpa tepi) adalah derajat genap semua simpul.
Bayangkan Daftar Kota
Pada artikel ini, kita akan bayangkan daftar kota seperti {Moscow Anapa Adler Rostov-on-Don Wuhan}. Kita dapat membuat grafik:
Grafik ini memiliki jalur Euler. Hanya ada dua simpul yang berderajat ganjil yaitu M dan L, selebihnya genap: A berderajat 4, karena loop dihitung dua kali, dan P dan Y memiliki derajat 2.
Solusi untuk Masalah Kata Domino
Jika kita menemukan algoritma yang dapat membangun rute Euler berdasarkan skema ini, katakanlah, dalam bentuk daftar {M, A, A, P, Y , L}, maka kita selesaikan masalahnya, karena mengeluarkan kata-kata dalam urutan tertentu hanya masalah teknik. Jadi, solusi untuk masalah kata domino kita adalah dengan menerapkan algoritma untuk menemukan jalur Euler (siklusnya "bebas") dalam grafik berarah.
Dalam kesempatan berikutnya, kita akan membahas lebih lanjut tentang grafik terhubung dan aplikasinya dalam kehidupan sehari-hari.