Graph

Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Sebagai contoh, peta jaringan jalan kereta api yang menghubungkan sejumlah kota di pulau Jawa. Sesungguhnya peta tersebut adalah sebuah graph, yang dalam ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, maka dapat diketahui apakah ada lintasan jalan antara dua buah kota. Selain itu, bila panjang jalan kereta api antara dua buah kota bertetangga diketahui, maka juga dapat ditentukan rute perjalanan tersingkat dari kota A ke kota B.

Dalam pemrograman komputer, graph dapat direpresentasikan dengan menggunakan beberapa macam representasi graph, antara lain adjacency matrix, incidency matrix dan adjacency list. Namun, saya merekomendasikan untuk menggunakan adjacency list karena lebih efisien dan efektif dalam pengkodean dan lebih menghemat memori.

Pewarnaan Graph

Ada tiga macam persoalan pewarnaan graph (graph colouring), yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah (region). Pembahasan kali ini hanya dibatasi pada pewarnaan simpul saja.

Pewarnaan simpul adalah memberi warna pada simpul-simpul di dalam graph sedemikian sehingga setiap dua simpul bertetanga mempunyai warna yang berbeda. Salah satu terapan penting pewarnaan graph adalah mewarnai peta (colouring of map). Di dalam persoalan pewarnaan graph, tidak hanya sekedar mewarnai simpul-simpul dengan warna berbeda dari warna simpul tetangganya saja, namun juga menginginkan jumlah macam warna yang digunakan sesedikit mungkin.

Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik graph G.

Algoritma Welch Powell

Algoritma Welch-Powell dapat digunakan untuk mewarnai sebuah graf G secara efisien. Algoritma ini tidak selalu memberikan jumlah warna minimum yang diperlukan untuk mewarnai G, namun algoritma ini cukup praktis untuk digunakan dalam pewarnaan simpul graph. Algoritma Welch-Powell dapat dinyatakan sebagai berikut:

1. Urutkan simpul-simpul dari G dalam derajat yang menurun.

2. Gunakan satu warna untuk mewarnai simpul pertama (yang mempunyai derajat tertinggi) dan simpul-simpul lain (dalam urutan yang berurut) yang tidak tertetangga dengan simpul pertama ini.

3. Mulai lagi dengan simpul derajat tertinggi berikutnya di dalam daftar terurut yang belum diwarnai dan ulangi proses pewarnaan simpul dengan menggunakan warna kedua.

4. Ulangi penambahan warna-warna sampai semua simpul telah diwarnai.

Algoritma Recursive Largest First

Langkah kerja dari algoritma Recursive Largest First secara singkat :
1. Buat daftar semua simpul yang belum diwarnai dengan derajat tetangga (jumlah node tetangga yang belum diwarnai) terurut secara descending.
2. Ambil simpul yang memiliki derajat tetangga tertinggi dan warnai dengan sebuah warna.
3. Buang simpul yang telah diwarnai pada langkah (2) dan semua simpul yang bertetangga dengan simpul tersebut dari daftar simpul.
4. Warnai semua simpul yang tersisa pada daftar simpul dengan warna yang sama dengan warna simpul tadi.
5. Ulangi langkah-langkah diatas hingga semua node pada graph terwarnai.

Tree

Pohon (tree) adalah graph yang khusus. Pohon dapat didefinisikan sebagai graph-tak-berarah terhubung yang tidak mengandung sirkuit. Menurut definisi ini, ada dua sifat penting pada pohon, yaitu terhubung dan tidak mengandung sirkuit.

Dalam kehidupan sehari-hari, orang telah lama menggunakan pohon untuk menggambarkan hirarkhi. Misalnya, pohon silsilah keluarga, struktur organisasi, organisasi pertandingan, dan lain-lain. Para ahli bahasa menggunakan pohon untuk menguraikan kalimat, yang disebut pohon parsing (parse tree).

Spanning Tree

Misalkan G = (V, E) adalah graph-tak-berarah terhubung yang bukan pohon, yang berarti di G terdapat beberapa sirkuit. G dapat diubah menjadi pohon T = (V₁, E₁) dengan cara memutuskan sirkuit-sirkuit yang ada. Caranya, mula-mula dipilih sebuah sirkuit, lalu hapus satu buah sisi dari sirkuit ini. G akan tetap terhubung dan jumlah sirkuitnya berkurang satu. Bila proses ini dilakukan berulang-ulang sampai semua sirkuit di G hilang, maka G menjadi sebuah pohon T, yang dinamakan pohon merentang (spanning tree).

Contoh aplikasi pohon merentang misalnya pada pemeliharaan jalan raya.

Minimum Spanning Tree

Jika G adalah graph berbobot, maka bobot pohon merentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T. Pohon merentang yang berbeda mempunyai bobot yang berbeda pula. Di antara semua pohon merentang di G, pohon merentang yang berbobot minimum dinamakan pohon merentang minimum (minimum spanning tree). Pohon merentang minimum merupakan pohon merentang yang paling penting. Pohon merentang minimum mempunyai terapan yang luas dalam praktek.

Misalkan pemerintah akan membangun jalur rel kereta api yang menghubungkan sejumlah kota. Membangun jalur rel kereta api biayanya mahal, karena itu pembangunan jalur ini tidak perlu menghubungkan langsung dua buah kota, tetapi cukup membangun jalur kereta seperti pohon merentang. Karena di dalam sebuah graph mungkin saja terdapat lebih dari satu pohon merentang, harus dicari pohon merentang yang mempunyai jumlah jarak terpendek, dengan kata lain harus dicari pohon merentang minimum.

Algoritma yang dapat digunakan untuk membangun pohon merentang minimum ada dua buah, yaitu algoritma Prim dan algoritma Kruskal.

Algoritma Prim

Langkah kerja dari algoritma Prim dapat dinyatakan sebagai berikut: (G = graph input, T = graph hasil)

a. Ambil sisi dari graph G yang berbobot minimum, masukkan ke dalam T.

b. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e tidak membentuk sirkuit di T. Masukkan e ke dalam T.

c. Ulangi langkah (b) sebanyak n – 2 kali.

Algoritma Kruskal

Pada algoritma Kruskal, sisi-sisi di dalam graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Setelah itu, baru dilakukan langkah kerja berikut ini:

a. T masih kosong.

b. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T.

c. Ulangi langkah (b) sebanyak n – 1 kali.

N.B. : Suatu graph dapat memiliki lebih dari satu buah minimum spanning tree.