TEORI GRAF

Pohon Merentang (spanning tree)

Definisi Misalkan G adalah sebuah graph. Sebuah pohon di G yang memuat semua titik G disebut pohon rentang (spanning tree) dari G.

Contoh

Misalkan kita mempunyai graph G seperti pada gambar 4.6 di bawah ini. Terdapat 3 pohon rentang dari graph G, yaitu graph A, B, dan C. Tampak jelas bahwa graph A, B, dan C masing-masing memuat semua simpul dari graph G serta mengandung sisi-sisi dari G demikian sehingga tidak terbentuk sikel.

Teorema 6

Graph G terhubung jika dan hanya jika G memuat pohon rentang.

Bukti

Jika graph G memuat pohon rentang, jelas G terhubung. Kita buktikan konvers pernyataan ini dengan induksi pada |E(G)|. Jika G terhubung dan |E(G)| = 0, maka G = K1, sehingga jelas G memuat pohon rentang.

Asumsikan: setiap graph terhubung dengan k + 1 sisi, maka G memuat pohon rentang. 

Pandang sebuah graph terhubung G dengan k + 1 sisi. Jika G tidak memuat sikel, maka G sebuah pohon rentang. Jika G memuat sikel, dan misalkan e adalah sebuah sisi dari sikel di G, maka graph G1 = G - e terhubung dengan k sisi. Sehingga berdasarkan asumsi, G1 memuat pohon rentang. Sebut T, pohon rentang di G1. Jelas, T adalah juga pohon rentang dari G. Teorema terbukti.

Sebuah graph terhubung mungkin memuat lebih dari satu pohon rentang, seperti terlihat pada Gambar. Graph G memuat pohon rentang T1, T2, dan T3. 

Jadi, pohon merentang:

·         Pohon merentang dari graf terhubung adalah subgraf merentang yang berupa pohon.

·        Pohon merentang diperoleh dengan memutus  sirkuit di dalam graf.

• Setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang.
• Graf tak-terhubung dengan k komponen mempunyai k buah hutan merentang yang disebut hutan merentang (spanning forest).

Pohon Rentang Minimum

·         Graf terhubung-berbobot mungkin mempunyai lebih dari 1 pohon merentang

·         Pohon rentang yang berbobot minimum – dinamakan pohon merentang minimum (minimum spanning tree)

Dalam kehidupan nyata, salah satu contoh aplikasi spanning tree adalah menentukan rangkaian jalan dengan jarak total seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain.

Dalam menentukan suatu minimum spanning tree dari suatu graf terhubung, kita dapat menentukannya dengan mengunakan dua cara yaitu algoritma Prim dan algoritma Kruskal.

Algoritma Prim

Langkah 1: ambil sisi dari graf G yang berbobot minimum,  masukkan ke dalam T

Langkah 2:  pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T

Langkah 3:  ulangi langkah 2

Contoh: 

            Langkah      Sisi       Bobot        Pohon rentang 

Pohon merentang minimum yang dihasilkan:  

Pohon merentang minimum yang dihasilkan: 

Bobot = 10 + 25 + 15 + 20 + 35 = 105

Algoritma Kruskal

 ( Langkah 0: sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya – dari bobot kecil ke bobot besar)

Langkah 1:  T masih kosong

Langkah 2: pilih sisi (u, v) dengan bobot minimum yang tidak membentuk  sirkuit di T. Tambahkan (u, v) ke dalam T.

Langkah 3:   ulangi langkah 2

Contoh: 

Sisi-sisi diurut menaik:

Pohon merentang minimum yang dihasilkan:

Bobot = 10 + 25 + 15 + 20 + 35 = 105