MODUL 6 Materi Kuliah New_S1
KULIAH 10 Spanning tree dan minimum spanning tree -
Definisi spanning tree
T dikatakan spanning tree dari graph terhubung G bila T adalah suatu tree yang vertexvertexnya sama dengan vertexnya G dan sisi-sisi dari T adalah sisi-sisinya G, atau T adalah spanning tree dari graph terhubung G bila T adalah sebuah spanning subgraph dari g yang merupakan tree. Contoh : Graph pada contoh –41b adalah spanning tree dari graph pada contoh–41a. V3 e2 V2 V1
V3
e3
e2
e7
V2
V4
e1
e1
V4
V1
e10
e9
e8
e8
e6 e4
e3
e4
e5
e5 e11 V6
V6
V7
V7
V5
V5
(b)
(a)
Contoh –41 Catatan: a. Jika G tidak terhubung maka G terdiri dari beberapa komponen yang merupakan graph terhubung, maka dikatakan spanning tree dari komponen masing- masing, dan semua spanning tree tersebut disebut spanning forest dari graph asalnya. b. Suatu graph yang terhubung dan tak memiliki sirkuit adalah suatu spanning dari dirinya sendiri. c. Edge yang ada pada spanning tree T tersebut branch dari T dan edge di G yang tidak termasuk T disebut chord terhadap spanning tree T. Teorema :
Setiap graph terhubung memiliki paling sedikit satu spanning tree. Bukti : Jika graph G terhubung, maka hanya ada dua kemungkinan : 1. G tidak memiliki sirkuit. 2. G memiliki sirkuit.
Untuk kasus 1, G adalah suatu tree dan juga merupakan spanning tree dari G sendiri. Untuk kasus 2, misalkan S1 adalah suatu sirkuit dari G, maka dengan menghilangkan satu edge yang ada di S1, subgraph G1 yang tinggal masih terhubung. Untuk G1 adalah suatu spanning subgraph dari G yang merupakan tree, jadi G1 adalah suatu spanning tree dari G. Bila G1 memiliki sirkuit S2 maka hilangkan suatu edge di S2, subgraph G2 yang tinggal masih terhubung. Seperti tadi G2 akan merupakan suatu spanning tree dari G atau masih memiliki sirkuit. Jika hal terakhir yang terjadi, maka proses menghapus suatu edge dari sirkuit yang ada diulang terus sampai terdapat suatu spanning tree. Contoh : Spanning tree T pada contoh 41b dapat diperoleh dari graph G = ( V, E ) dengan V = {v1,v2, v3,v4, v5,v6, v7} dan E = {e1,e2, e3,e4, e5,e6, e7,e8, e9,e10, e11,e12} pada contoh – 41a dengan cara berikut : Pada graph G terdapat sirkuit S1 = (e11,e12,e13), hilangkan salah satu edge di S1, misalnya e13, maka yang tinggal adalah subgraph G1 = (V1,E1) dengan V1 = E dan E1= {e1,e2,…e11,e12}. Graph G1 masih terhubung dan terdapat sirkuit S2 = (e4,e5,e11,e12), hilangkan e12, maka yang tinggal adalah subgraph G2 = (V2,E2) dengan V2 =V dan E2 = {e1,e2, e3,… e10,e11}. Graph G2 masih terhubung dan masih ada sirkuit S3 = (e6, e10,e11), hilangkan edge e11, maka yang tinggal adalah subgraph G3 = (V3,E3) dengan V3 = V dan E3 = {e1,e2,e3,…e9,e10}. Graph G3 masih terhubung dan masih ada sirkuit S4 = (e7, e9,e10) hilangkan edge e10, maka yang tinggal adalah subgraph G4 = (V4, E4)
dengan V4 =V dan E4
={e1,e2,e3,…e7,e8,e9}. Graph G4 masih terhubung dan masih ada sirkuit S5 = (e8, e9) hilangkan edge e9, maka yang tinggal adalah subgraph G5 = (V5, E5) ={e1,e2,e3,e4,e5,e6,e7,e8,}.
dengan V5 =V dan E5
Graph G5 masih terhubung dan masih ada sirkuit S6 = (e2, e3,e7) hilangkan edge e7, maka yang tinggal adalah subgraph G6 = (V6,E6) dengan V6 =V dan E6 = {e1,e2,e3,e4,e5,e6,e8}. Graph G6 masih terhubung dan masih ada sirkuit S7 = (e1,e5,e6) hilangkan edge e6, maka yang tinggal adalah subgraph G7 = (V6,E6) dengan V7 =V dan E7 = {e1,e2,e3,e4,e5,e8}. Graph G7 masih terhubung tapi sudah tidak memiliki sirkuit lagi, G7 adalah suatu spanning tree. Teorema : Suatu graph terhubung G dengan n vertex dan e edge mempunyai (n – 1) branch dan (e – n +1) chord terhadap setiap spanning treenya. Contoh : Pada graph G di contoh –41a yang mempuyai 7 vertex dan 13 edge mempunyai Branch : e1,e2, e3,e4, e5,e2, e6,e2, e8 dan Chord
: e6,e7, e9,e10, e11,e12, e1,e13
Terhadap spanning tree T pada contoh –41b. - Operasi Graph Diberikan G1 = (V1,E1), G2 = (V2,E2), maka 1. Gabungan G1 dan G2 adalah G3 = G1 U G2 dimana G3 = (V3,E3) dengan V3 = V1 U V2 dan E3 = E1 U E2. Contoh :
V1
k
a
g
c
V2
V2
V3
V2 d
V1
V6
a
b
a
h
V1
c
V3
l
g
V6 k
b c
V3 l
d
e
h
e
V5 V4
f Graph G1
V4
V5
Graph G1
V5 f Graph G3 = G1 U G2
Gambar -42 2. Irisan G1 dan G2 adalah G4 = G1 G2 dimana g4 = (v4,e4) dengan V4 = V1 V2 dan E4 = E1 E2
Contoh : dengan G1 dan G2 pada contoh –42, maka G4 = G1 G2 adalah graph pada contoh –43. V1
V1
a
h g
V6 k
b V2
V3
V2
c
c
V3 l e
d V5
V4
Contoh –43
f
V5
Contoh –44
3. Jumlah ring (ring sum) dari G1 dan G2 adalah G5 = G1 (+) G2 di mana G5 = (V5,E5) dengan V5 = V1 U V2 dan E5 = E1 (+) e2, E5 adalah himpunan sisi-sisi yang ada di E1 atau di E2 tapi tidak di E1 dan E2. Contoh : Jumlah ring dari graph G1 dan graph dari G2 pada contoh-42 adalah graph G5 pada contoh-44. Sifat-sifat dari operasi-operasi di atas : 1. G1 U G2 = G2 U G1 (sifat komunikatif) 2. G1 G2 = G2 G1 (sifat komunikatif) 3. G1 G2 = G2 G1 (sifat komunikatif) 4. G1 U G2 = G2 G1 (sifat komunikatif) 5. G G
= graph tanpa sisi (null graph)
Sirkuit dasar (Fundamental cirkuit )
Jika T = (V1,E1) adalah suatu spanning tree dari graph terhubung G = (V, E) dan ei adalah suatu chord terhadap T di G, maka graph G = (V,E2) dimana E2 = E1 U {ei} mengandung sebuah sirkuit yang disebut sirkuit dasar terhadap spanning T untuk G. Catatan : Banyaknya sirkuit dasar dari suatu graph G yang terhubung dengan n vertex dan e edge terhadap suatu spanning tree T adalah ( e – n + 1) buah. Contoh : Beberapa sirkuit dasar dari graph G pada contoh –41a terhadap spanning tree T pada contoh –41b adalah : 1. Menambah chord e6, didapat subgraph G’ yang mengandung sirkuit dasar (e1, e5, e6). 2. Menambah chord e7, didapat subgraph G’ yang mengandung sirkuit dasar (e2, e3, e7). 3. Menambah chord e9, didapat subgraph G’ yang mengandung sirkuit dasar (e8, e9). 4. Jika dua chord e11 dan e12 ditambahkan pada T, maka terdapat subgraph G’ yang mengandung sirkuit S1 = (e1, e2, e3, e8, e11, e5) S2 = (e1, e2, e3, e8, e12, e4) S3 = (e4, e5, e3, e11, e12) Diantara ketiga sirkuit itu, sirkuit S1 dan S2 adalah sirkuit dasar, dengankan sirkuit S3 bukan sirkuit dasar. Prosedur mencari semua spanning tree dari suatu graph G yang terhubung bila diketahui sebuah spanning tree T dari G adalah sebagai berikut : Ambil graph G pada contoh –41a dengan spanning tree T pada contoh –41b sebagai spanning tree awal. Sirkuit dasar S = (e2, e3, e8, e10) akan terbentuk bila chord e10 ditambahkan ke T. Dengan menghilangkan salah satu branch di sirkuit dasar S maka akan diperoleh spanning tree yang baru : T1
= (V, E1) dengan E1 = (e1, e3, e4, e5, e8, e10) dengan menghapus branch e2
yang ada di S. T2
= (V, E2) dengan E2 = (e1, e2, e4, e5, e8, e10) dengan menghapus branch e3
yang ada di S. T3
= (V, E1) dengan E3 = (e1, e2, e3, e4, e5, e10) dengan menghapus branch e8
yang ada di S.
Jadi dengan menambah satu chord ke spanning tree awal dan menghapus satu branch yang ada di sirkuit dasar yang terbentuk diperoleh spanning tree baru. Prosedur ini disebut metode cyclic. Interchage atau elementary tree transformation. Teorema : Dengan mengambil suatu spanning tree T dari graph G yang sembarang sebagai spanning tree awal, maka dengan metode syclic interchage berurutan akan diperoleh setiap spanning tree dari G. Algoritma menentukan suatu spanning tree T dari suatu graph G. Misalnya graph G = (V, E) dengan V = {v1,v2,v3,…vn} dan E = {e1,e2,e3…,ep}. Bentuk himpunan F { f1, f2, f3,…,fp } dan H = { h1, h2, h3,…,hn }, bila e1 menghubungkan vertex f1 dan hi. Flow chart dari algoritma ini adalah :
Read F, H, e,n set K l C 0 m 0
ls vertex f k in any Ti ?
ls vertex h k in any Tj ?
No
Yes
No
C C+1 start a new tree Tc with (fk, hk)
ls vertex hk in any Tj ?
Yes
Yes
No ls i=j p
Yes
Include (f k, h k) in T 1
Include (f k, h k) in T 1
1
No Combine T1, Tj, (f k, hk) into one tree C C-1
4
1
5
2
3 m
m +1
ls m =n-1 or k = e ?
Yes
Print spanning tree/forest
No k
k +1
Fig. 11-3 Algorithm 2 : Spanning tree/forest
stop
