Pohon Merentang dan MST

1. Pohon Merentang dan Hutan Merentang

A. Pohon Merentang (Spanning Tree)

Misalkan G = (V, E) adalah graf 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 banyak 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). Disebut pohon merentang karena semua titik pada pohon T sama dengan semua titik pada graf G, dan sisi-sisi pada pohon T merupakan sisi-sisi pada graf G, yang berarti V₁ = V dan E₁ ⊆ E.

Dengan kata lain, jika subgraf dari graf terhubung berbentuk pohon, maka subgraf merentang tersebut dinamakan pohon merentang.

B. Hutan Merentang (Spanning Forest)

Harus diingat bahwa pohon merentang didefinisikan hanya untuk graf terhubung, karena pohon selalu terhubung. Pada graf tak-terhubung dengan n buah titik kita tidak dapat menemukan subgraf terhubung dengan n buah titik. Tiap komponen dari graf tak-terhubung mempunyai satu buah pohon merentang. Dengan demikian, graf tak-terhubung dengan k komponen mempunyai hutan merentang (spanning forest) yang terdiri dari k buah pohon merentang.

2. Fitur-Fitur Terkait Pohon Merentang

A. Keberadaan Pohon Merentang

"Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang."

Graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Pada graf yang mengandung sirkuit, pohon merentangnya diperoleh dengan cara memutuskan sirkuit yang ada.

B. Fitur-Fitur Pohon dan Hutan Merentang

Sisi pada pohon merentang – disebut cabang (branch) – adalah sisi dari graf semula, sedangkan tali-hubung (chord atau link) dari pohon adalah sisi dari graf yang tidak terdapat di dalam pohon merentang. Pada graf terhubung dengan m buah sisi dan n buah titik terdapat n − 1 buah cabang dan m − n + 1 buah tali. Himpunan tali-hubung beserta titik yang bersisian dengannya disebut komplemen pohon. Untuk graf terhubung G dengan n buah titik dan m buah sisi, kita dapat menghitung banyak cabang dan tali-hubung dengan rumus

banyak cabang = n − 1

banyak tali-hubung = m − n + 1

dan pada graf tidak terhubung dengan k komponen, m buah sisi dan n buah titik,

banyak cabang = n − k

banyak tali-hubung = m − n + k

Banyak cabang pada pohon merentang dari sebuah graf G disebut rank graf G, dan banyak tali-hubung pada graf G disebut nullity graf G. Dapat dilihat bahwa

rank + nullity = banyak sisi graf G

Nullity graf sering diacu sebagai bilangan siklomatik, atau bilangan Betti pertama.

C. Sirkuit Fundamental

Ingatlah kembali bahwa jika kita menambahkan sebuah sisi antara dua buah titik pada pohon maka akan terbentuk sirkuit. Tinjau kembali pohon merentang T pada graf terhubung G. Dengan menambahkan sebuah tali-hubung pada T akan terbentuk sirkuit. Sirkuit yang terbentuk dengan penambahan sebuah tali-hubung pada pohon merentang disebut sirkuit fundamental (fundamental circuit). Berapa banyak sirkuit fundamental pada sebuah graf? Tentu saja sebanyak jumlah tali-hubung.

3. Definisi Pohon Merentang Minimum (Minimum Spanning Tree), disingkat MST

Jika G adalah graf berbobot, maka 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) - 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 seperti yang digambarkan oleh graf pada gambar diatas. 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 graf 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.

4. Algoritma Prim untuk Minimum Spanning Tree

Misalkan T pohon merentang dari graf G. Dengan menggunakan algoritma Prim, kita dapat menentukan T dengan bobot minimum. Berikut ini algoritmanya:

a. Pilih satu titik di graf G, boleh memilih secara bebas

b. Pilih sisi yang incident dengan titik pada poin (a), pilih bobot terkecil, dan pastikan tidak membentuk sirkuit, lalu masukkan juga titik ujung yang lain.

c. Pilih sisi yang incident dengan titik-titik yang sudah masuk, pilih bobot terkecil, dan pastikan tidak membentuk sirkuit, lalu masukkan juga titik ujung yang lain.

d. Ulangi langkah c sampai semua titik masuk

Sebagai contoh, perhatikan graf berikut:

akan ditentukan minimum spanning tree menggunakan algoritma Prim.
Mula-mula kita pilih satu titik, misal Minfor memilih titik A. Perhatikan:

Terdapat 2 sisi yang incident dengan A, yaitu AB berbobot 2 dan AC berbobot 3. Pilih sisi berbobot terkecil, yaitu AB, dengan ini masukkan titik B.

Dari titik-titik yang sudah masuk, yaitu A, dan B; terdapat 3 sisi incident, yaitu AC, BD, BE. Pilih sisi berbobot terkecil, yaitu AC berbobot 3, dengan ini masukkan titik C.

Dari titik-titik yang sudah masuk, yaitu A, B, C; terdapat 4 sisi incident, yaitu BD, BE, CD, CG. Pilih sisi berbobot terkecil, yaitu CD berbobot 1, dengan ini masukkan titik D.

Dari titik-titik yang sudah masuk, yaitu A, B, C, D; terdapat 6 sisi incident, yaitu BD, BE, CG, DE, DF, DG. Pilih sisi berbobot terkecil, yaitu CG berbobot 3, dengan ini masukkan titik G.

Dari titik-titik yang sudah masuk, yaitu A, B, C, D, G; terdapat 6 sisi incident, yaitu BD, BE, DE, DF, DG, GI. Sisi BD dan GI sama-sama berbobot terkecil, yaitu 4. Akan tetapi memasukkan sisi BD akan membentuk sirkuit, sehingga dipilih GI, dengan ini masukkan titik I.

Dari titik-titik yang sudah masuk, yaitu A, B, C, D, G, I; terdapat 6 sisi incident, yaitu BE, DE, DF, DG, FI, IJ. Pilih sisi berbobot terkecil, yaitu FI berbobot 3, dengan ini masukkan titik F.

Dari titik-titik yang sudah masuk, yaitu A, B, C, D, F, G, I; terdapat 6 sisi incident, yaitu BE, DE, DF, DG, FH, IJ. Pilih sisi berbobot terkecil, yaitu FH berbobot 1, dengan ini masukkan titik H.

Dari titik-titik yang sudah masuk, yaitu A, B, C, D, F, G, H, I; terdapat 7 sisi incident, yaitu BE, DE, DF, DG, EH, HJ, IJ. Pilih sisi berbobot terkecil, yaitu EH berbobot 2, dengan ini masukkan titik E.

Tersisa titik J yang belum masuk, ada 2 sisi menuju J, yaitu IJ dan HJ. Pilih sisi berbobot terkecil, yaitu IJ berbobot 5, dan akhirnya semua titik masuk.

Hasil terakhir ini merupakan minimum spanning tree, dengan bobot total 24.

5. Algoritma Kruskal untuk Minimum Spanning Tree

Misalkan T pohon merentang dari graf G. Dengan menggunakan algoritma Kruskal, kita dapat menentukan T dengan bobot minimum. Berikut ini algoritmanya:

a. Pilih sisi berbobot terkecil, masukkan.

b. Dari sisi-sisi yang belum masuk, pilih sisi berbobot terkecil, selama tidak membentuk sirkuit masukkan, sedangkan sisi yang membentuk sirkuit dieliminasi.

c. Ulangi langkah (b) sampai semua titik masuk

Sebagai contoh, perhatikan graf berikut:

akan ditentukan minimum spanning tree menggunakan algoritma Kruskal.

Mula-mula cari sisi berbobot terkecil, ternyata CD dan FH merupakan sisi berbobot terkecil dengan masing-masing berbobot 1. Perhatikan:

Kita boleh memilih CD maupun FH, misalnya Minfor memilih CD.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah FH berbobot 1. Masukkan FH.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah AB dan EH yang masing-masing berbobot 2. Kita boleh memilih AB maupun EH, misalnya Minfor memilih AB.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah EH berbobot 2. Masukkan EH.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah AC, CG, dan FI yang masing-masing berbobot 3. Kita boleh memilih AC, CG, maupun FI; misalnya Minfor memilih AC.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah CG dan FI yang masing-masing berbobot 3. Kita boleh memilih CG maupun FI; misalnya Minfor memilih CG.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah FI berbobot 3. Masukkan FI.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah BD dan GI yang masing-masing berbobot 4. Perhatikan bahwa memasukkan BD akan membentuk sirkuit, sehingga BD dieliminasi, dan dipilih GI.

Dari sisi-sisi yang belum masuk, sisi berbobot terkecil adalah BE dan IJ yang masing-masing berbobot 5. Perhatikan bahwa memasukkan BE akan membentuk sirkuit, sehingga BE dieliminasi, dan dipilih IJ.

Akhirnya semua titik masuk, hasil terakhir ini merupakan minimum spanning tree, dengan bobot total 24.

6. Algoritma Boruvka untuk Minimum Spanning Tree

Misalkan T pohon merentang dari graf G. Dengan menggunakan algoritma Boruvka, kita dapat menentukan T dengan bobot minimum. Berikut ini algoritmanya:

a. Mula-mula semua titik merupakan komponen tersendiri

b. Cari sisi berbobot terkecil dari masing-masing yang menghubungkan ke komponen lain, pastikan tidak membentuk sirkuit, akan membentuk komponen

c. Cari sisi berbobot terkecil dari masing-masing yang menghubungkan ke komponen lain, pastikan tidak membentuk sirkuit, akan membentuk komponen, ulangi langkah ini sampai seluruh komponen menyatu

Sebagai contoh, perhatikan graf berikut:

akan ditentukan minimum spanning tree menggunakan algoritma Boruvka.

Mula-mula, semua titik merupakan komponen tersendiri

Tentukan sisi berbobot terkecil dari masing-masing komponen yang menghubungkan ke komponen lain.

Komponen	Sisi terkecil	Bobot
A	A-B	2
B	A-B	2
C	C-D	1
D	C-D	1
E	E-H	2
F	F-H	1
G	C-G	3
H	F-H	1
I	F-I	3
J	I-J	5

Hubungkan menjadi

Terbentuk 3 komponen, yaitu {A, B}, {C, D, G}, dan {E, F, H, I, J}. Selanjutnya tentukan sisi berbobot terkecil dari masing-masing komponen yang menghubungkan ke komponen lain.

Komponen	Sisi terkecil	Bobot
{A, B}	A-C	3
{C, D, G}	A-C	3
{E, F, H, I, J}	G-I	4

Hubungkan menjadi

Akhirnya semua komponen menyatu, hasil terakhir ini merupakan minimum spanning tree, dengan bobot total 24.