BAB 2 DEGREE CONSTRAINED MINIMUM SPANNING TREE
Pada bab ini diberikan beberapa konsep dasar seperti beberapa definisi dan teorema sebagai landasan berfikir dalam melakukan penelitian ini dan akan mempermudah dalam hal pembahasan hasil utama pada bab berikutnya. Konsep dasar tersebut berkaitan dengan masalah yang dibahas dalam penelitian ini, yakni: konsep dasar graph, tree, dan degree constrained tree minimum spanning tree.
2.1 Konsep Dasar Graph Istilah baku graph diadopsi dari Vasudev, 2006. Suatu graph G = (V, E) merupakan himpunan objek V = {v1, v2, v3, ...} disebut verteks (disebut juga point atau node) dan himpunan E = {e1, e2, ...} yang elemennya disebut edge (disebut juga line atau arc), sehingga untuk setiap edge em dikenal sebagai penghubung pasangan verteks (vi , vj ). Verteks vi , vj yang dihubungkan oleh edge em disebut verteks ujung dari em . Suatu graph dapat direpresentasikan secara grafis dengan cara setiap verteks direpresentasikan sebagai titik dan setiap edge vi vj sebagai garis dari titik vi ke titik vj . Contoh 2.1a: Berikut diberikan representasi dari graph. s
v2
v1 s
sv4
s v3
Gambar 2.1 : Graph
Sumatera Utara Dari gambar 2.1a dapat diketahui bahwa V (G) = {vUniversitas 1 , v2 , v3 , v4 } dan E(G)
5 = {v1v1 , v1v2, v1v3, v1 v4, v2v3, v2v4 , v3v3, v3v4 }. Berdasarkan definisi, edge merupakan penghubung pasangan verteks vj , vk . Untuk suatu edge yang memiliki kedua verteks ujung yang sama disebut loop. Dari gambar 2.1a dapat dilihat bahwa edge v1 dan v3 merupakan loop. Jika untuk setiap edge pada graph G diberi suatu nilai atau bobot W = {w1 , w2, ..., wm}, maka graph tersebut dikatakan graph berbobot. Contoh 2.1b: Berikut diberikan representasi dari graph berbobot. s
s
v2
e4 = w4 v5 e5 = w5
e1 = w1 v1 s
e3 = w3
e2 = w2
s v3
Gambar 2.2 : Graph Berbobot
Graph yang tidak memiliki loop ataupun edge ganda disebut graph sederhana. Graph sederhana, dimana setiap verteks dihubungkan tepat satu edge ke verteks lainnya disebut graph lengkap. Contoh 2.1c: Berikut diberikan representasi dari gaph sederhana dan graph lengkap.
v1 s
s v2
v4 s
s v3
v1 s
vs 2
v5 s
sv3 s
v4
a
b
Gambar 2.3 : (a)Graph Lengkap dan (b) Graph Sederhana Universitas Sumatera Utara
6 2.1.1 Incident dan Degree Ketika verteks vi merupakan verteks ujung dari beberapa edge ej , vi dan ej dikatakan incident satu sama lain. Dua edge nonparalel dikatakan adjacent jika mereka incident pada verteks yang sama. Dengan cara yang sama, dua verteks dikatakan adjacent jika mereka merupakan verteks ujung dari edge yang sama. Sebagai contoh pada gambar 2.1a dapat dilihat bahwa v1v2 , v1v3, v1v4 merupakan incident pada v1. Adjacent untuk v1 adalah v2, v3, v4 . Sedangkan, v1 dan v3 adjacent untuk diri mereka sendiri. Jumlah edge incident dari suatu verteks vi, dengan edge yang merupakan loop dihitung 2 disebut degree dari verteks tersebut. Degree dari suatu verteks dinotasikan dengan degG (vi ) atau deg vi atau d(vi ) atau d(v). Verteks yang tidak memiliki edge incident disebut verteks terisolasi. Sedangkan verteks yang berdegree satu disebut verteks pendent atau verteks ujung. Contoh 2.1.1: Berikut diberikan representasi dari verteks ujung dan verteks terisolasi v1 s
s v2
v4 s
s v3
s v5
Gambar 2.4 : verteks ujung dan verteks terisolasi
Adapun degree dari setiap verteks pada gambar 2.3, d(v1 ) = 1, disebut pendant verteks, dan d(v2 ) = 3, d(v3 ) = 2, d(v4 ) = 3, dan d(v5 ) = 0 karena tidak memiliki edge incident (v5 disebut verteks terisolasi).
Teorema 2.1 Untuk sebarang graph jumlah degree dari seluruh verteks G sama dengan dua kali jumlah edge di G.
Universitas Sumatera Utara
7 Bukti: Diberikan graph G dengan n verteks v1 , v2, ..., vn dan e edge. Karena setiap edge memiliki tepat dua verteks vi dan vj (untuk loop, i = j), maka edge memberikan kontribusi 2 degree, yakni 1 degree untuk verteks vi dan 1 degree untuk verteks vj . Hal ini mengakibatkan penjumlahan degree dari seluruh verteks di G adalah dua kali dari edge di G, yaitu n X
d(vi ) = 2e
i=1
Teorema 2.2 Banyak verteks berdegree ganjil pada suatu graph selalu genap.
Bukti: Dari teorema 2.1, diketahui bahwa n X
d(vi ) = 2e
i=1
Jika verteks yang berdegree ganjil dan berdegree genap dipisahkan, maka persamaan diatas dapat dibentuk menjadi n X
d(vi ) =
i=1
Karena
Pn
i=1 d(vi )
X
d(vj ) +
even
adalah genap, dan
X
d(vk )
odd
P
even
d(vj ) juga genap, maka
P
odd d(vk )
juga suatu bilangan genap. Karena d(vk ) adalah ganjil, maka syarat agar jumlah seluruh d(vk ) genap, banyaknya vk haruslah genap. Hal ini membuktikan bahwa banyak verteks berdegree ganjil pada suatu graph selalu genap. 2.1.2 Walk, Path, dan Cycle Diberikan graph G dengan verteks v dan w. Sebuah walk dengan panjang m dari v ke w didefinisikan sebagai barisan edge dan dituliskan sebagai berikut: (v0, v1), (v1v2 ), ..., (vm−1vm ) untuk m > 0, v0 = v dan vm = w. Sebuah walk biasa dinotasikan dengan v →w w dan panjangnya dinotasikan dengan l(w).
Universitas Sumatera Utara
8 Sebuah trail dari v ke w adalah walk dari v ke w tanpa perulangan edge. Sebuah path didefinisikan sebagai sebuah trail tanpa perulangan verteks. Path tertutup adalah path yang dimulai dan diakhiri dengan verteks yang sama. Sebuah cycle merupakan sebuah path tertutup, dan sebuah loop merupakan sebuah cycle dengan panjang 1. Contoh 2.1.2: Sebagai contoh masing-masing untuk walk, trail, path, cycle, dan loop dapat dilihat pada gambar berikut: s
v1 v2 s
v4 s
s v3
s v5
Gambar 2.5 : (5,8) Graph
a. v1 → v3 → v5 → v3 → v2 → v4 disebut walk. b. v1 → v2 → v3 → v5 → v2 → v4 disebut trail, walk tanpa perulangan edge. c. v1 → v2 → v4 → v5 disebut path, walk tanpa perulangan edge dan verteks. d. v1 → v2 → v4 → v5 → v3 → v1 disebut cycle, Karena adanya perulangan pada verteks awal dan akhir disebut juga p ath tertutup. e. v1 → v1 dan v3 → v3 disebut loop, cycle dengan panjang 1. .
2.1.3 Subgraph Suatu subgraph dari G adalah graph yang memiliki verteks dan edge yang ada di G. Jika G dan T merupakan dua graph dengan himpunan verteks V (T ), Universitas Sumatera Utara
9 V (G) dan himpunan edge E(T ) dan E(G) sehingga V (T ) ⊆ V (G) dan E(T ) ⊆ E(G), maka T disebut subgraph G atau G disebut supergraph T . Contoh 2.1.3: Berikut diberikan representasi dari subgraph G.
G:
v1 s
vs 2
s
v3
v4 s
s
s
v6
v5
T :
v1 s
s
s
v3
s
s
v6
v2
v5
Gambar 2.6 : (G) Graph dan (T ) Subgraph
Berdasarkan definisi, dapat dikatakan bahwa:
1. Setiap graph merupakan subgraph itu sendiri. 2. Sebuah subgraph dari subgraph G merupakan subgraph G. 3. Sebuah verteks tunggal di G merupakan subgraph G. 4. Sebuah edge tunggal di G, bersama dengan verteks ujungnya, juga merupakan subgraph G.
2.1.4
Graph Terhubung, Graph Tidak Terhubung, dan Komponen Diberikan graph G dengan v dan w merupakan dua verteks di G. Graph G
dikatakan terhubung jika dan hanya jika diberikan sebarang dua verteks v dan w di G sedemikian hingga terdapat paling sedikit satu path dari v ke w. Selebihnya, G dikatakan tidak terhubung. Pada gambar 2.6 menunjukkan bahwa (a) adalah graph terhubung karena terdapat path dari satu verteks ke verteks yang lainnya, dan (b) adalah graph tak berhubung karena tidak terdapat path dari v1 ke v3 . Dari gambar 2.3 dapat Universitas Sumatera Utara kita lihat bahwa graph tersebut terdiri dari dua bagian. Bagian pertama adalah
10 verteks v1, v2 dengan edge v1v2 , sedangkan bagian kedua adalah verteks v3, v4, dan v5, dengan edge v3v4 , v3v5 , dan v4v5. Masing-masing bagian ini disebut komponen. Contoh 2.1.4: Berikut diberikan representasi dari 2 buah graph terhubung dan tidak terhubung. v5
s
v1 s
v8 v9
v4 s
v6
s s
s s
v7 a
v5
s
v2
v1 s
s
v3
v4 s
s
s
v2
s
v3
b
Gambar 2.7 : (a) Graph terhubung dan (b) Graph tak berhubung
Teorema 2.3 Suatu graph G dikatakan tidak terhubung jika dan hanya jika verteks himpunan V dapat dibagi ke dalam dua komponen tak kosong, himpunan bagian V1 dan V2 terpisah, sehingga tidak ada edge di G yang memiliki satu verteks ujung di dalam himpunan bagian V1 begitu juga di himpunan bagian V2 .
Bukti: Andaikan komponen ada. Anggap dua sembarang verteks a dan b di G, sehingga a ∈ V1 dan b ∈ V2 . Tidak ada path yang bisa diantara verteks a dan b; sebaliknya terdapat paling sedikit satu edge dimiliki verteks ujung V1 dan lainnya di V2 . Akibatnya jika komponen ada, G tidak terhubung. Dan sebaliknya, andaikan G menjadi graph tidak terhubung. Anggap sebuah verteks a di G. Andaikan V1 menjadi himpunan seluruh verteks yang dihubungkan oleh path ke a. Karena G tidak terhubung, maka V1 tidak memasukkan semua verteks G. Selebihnya verteks akan berbentuk(tak kosong) himpunan V2 . Tidak ada verteks di V1 yang dihubungkan ke sebarang V2 dengan sebuah edge. Hal ini berakibat adanya komponen.
Universitas Sumatera Utara
11 Teorema 2.4 Jika suatu graph memiliki tepat dua verteks berdegree ganjil, pasti terdapat path yang menyertai dua verteks tersebut.
Bukti: Andaikan G sebuah graph dengan seluruh verteksnya berdegree genap kecuali verteks v1 dan v2, yang berdegree ganjil. Berdasarkan teorema 2.2, hal ini berlaku untuk seluruh graph, oleh karenanya untuk setiap komponen graph tak terhubung, tak ada graph yang bisa memiliki jumlah ganjil dari verteks ganjil. Karenanya, di graph G v1 dan v2 harus berada pada komponen yang sama, akibatnya pasti ada path diantara mereka.
2.1.5 Bridge Suatu edge vi vj pada graph G terhubung dikatakan bridge jika penghapusan edge vivj mengakibatkan G menjadi tidak terhubung. Contoh 1.1.5: Berikut diberikan representasi dari bridge. s
v1
v4 s
s
v2
s
vs 7
v6
v5
v3
s
sv8 s
v9
Gambar 2.8 : Bridge
v3v5 merupakan bridge karena penghapusan edge v3v5 akan menyebabkan graph menjadi tak terhubung.
2.2 Tree Suatu tree merupakan graph terhubung tanpa adanya cycle. Untuk graph tak terhubung dan tanpa cycle disebut forest. Suatu verteks tunggal juga termasuk tree yang disebut trivial tree.
Universitas Sumatera Utara
12 Contoh 2.2a: Berikut diberikan representasi dari tree.
s
s s
s
s s s
s
s s
a
s
s
s
b
s
s s
s
c
Gambar 2.9 : Tree
Teorema 2.5 Hanya ada satu path antara setiap pasangan verteks di tree T .
Bukti: Karena T terhubung, maka terdapat paling sedikit satu path diantara semua pasangan verteks di T . Sekarang anggap bahwa diantara dua verteks a dan b di T terdapat path yang berbeda. Penggabungan dari dua path yang berbeda akan menghasilkan cycle, karenanya T bukanlah tree. Sebaliknya,
Teorema 2.6 Jika pada graph G hanya ada satu path diantara setiap pasangan verteks, maka G merupakan tree.
Bukti: Adanya path diantara setiap pasangan verteks menjamin bahwa G terhubung. Suatu cycle di G (dengan dua atau lebih verteks) secara tidak langsung menyatakan bahwa terdapat paling sedikit satu pasangan verteks a, b sehingga terdapat dua path yang berbeda antara a dan b. Karena G hanya memiliki satu path diantara setiap pasangan verteks, maka G tidak bisa memiliki cycle. Oleh karena itu, G merupakan tree.
Teorema 2.7 Suatu tree dengan n verteks memiliki n − 1 edge.
Bukti: Hasilnya akan diperlihatkan dengan induksi. Andaikan ek menjadi edge Universitas Sumatera Utara tidak ada path lain di T dengan verteks ujung vi dan vj , berdasarkan teorema 2.3,
13 diantara vi dan vj , kecuali ek . Oleh karenanya jika ek dihapus, maka T menjadi graph tak terhubung. Selanjutnya, T − ek akan membentuk dua komponen, dan karena tidak ada cycle di T , maka masing-masing komponen tersebut merupakan tree. Kedua tree t1 dan t2 , masnning-masing memiliki lebih sedikit dari n verteks, oleh karenanya dengan induksi, masing-masing memiliki edge lebih sedikit dari jumlah verteks di dalamnya. Dengan demikian T − ek mengandung n − 2 edge. Hal ini berakibat T memiliki tepat n − 1 edge.
Teorema 2.8 Untuk sebarang graph terhubung dengan n verteks dan n − 1 edge merupakan tree.
Bukti: Berdasarkan definisi graph terhubung, terdapat paling sedikit satu path di G, berdasarkan teorema 2.3 tidak ada path lain diantara vi dan vj , kecuali ek , berdasarkan definisi suatu tree merupakan graph terhubung tanpa adanya cycle. karenanya berdasarkan teorema 2.5, suatu tree dengan n verteks memiliki n − 1 edge. Hal ini berakibat graph terhubung dengan n verteks dan n − 1 edge merupakan tree.
Teorema 2.9 Suatu graph merupakan tree jika dan hanya jika terhubung.
Bukti: Andaikan graph G merupakan tree, berdasarkan definisi suatu tree merupakan graph terhubung tanpa adanya cycle. Andaikan G tidak terhubung, maka berdasarkan teorema 2.1 graph bukanlah tree. Hal ini berakibat bahwa untuk graph yang merupakan tree, haruslah graph terhubung.
Teorema 2.10 Suatu graph G dengan n verteks, n − 1 edge, dan tanpa cycle adalah terhubung.
Bukti: Andaikan bahwa ada sedikit cycle graph G dengan n verteks dan n − 1 Universitas Utara edge yang tak terhubung. Pada kasus ini, G akan mengandung duaSumatera atau lebih
14 sedikit komponen cycle. Tanpa kehilangan sifat umumnya, andaikan G memiliki komponen g1 dan g2 . Lalu tambahkan sebuah edge e dintara suatu verteks v1 di g1 , dan v2 di g2 . Karena tidak ada path diantara v1 dan v2 di G, tambahkan e tanpa membentuk cycle. Dengan demikian G∪ e memiliki cycle sedikit, graph terhubung dari n verteks dan n edge, yang tidak mungkin trejadi. Hal ini berakibat graph G dengan n verteks, n − 1 edge, dan tanpa cycle adalah terhubung. Berdasarkan teorema-teorema diatas, dapat disimpulkan bahwa suatu graph G dengan n verteks disebut tree, jika:
1. G terhubung dan tanpa cycle, atau 2. G terhubung dan memiliki n − 1 edge, atau 3. G tanpa cycle dan memiliki n − 1 edge, atau 4. Tepat terdapat satu path diantara setiap pasangan verteks di G, atau 5. G paling tidak merupakan graph terhubung.
2.2.1 Verteks Ujung dalam Tree Verteks ujung merupakan verteks dengan jumlah degree adalah 1.
Teorema 2.11 Pada sebarang tree (dengan dua atau lebih verteks), terdapat paling sedikit dua verteks ujung.
Bukti: Karena tree yang memiliki n verteks dan n − 1 edge, maka 2(n − 1) degree terbagi diantara n verteks. Karenanya tidak akan bisa ada verteks yang tidak memiliki degree, paling tidak harus memiliki dua verteks yang berdegree 1 dalam degree. Tentu saja ini hanya berlaku jika n ≥ 2. 2.2.2 Spanning tree Suatu tree T dikatakan spanning tree dari graph G terhubung, jika T adalah suatu
Universitas Sumatera Utara
15 subgraph G dan T mengandung seluruh verteks G. Dengan kata lain, T dikatakan spanning tree jika T terhubung, mengandung n verteks G dan n − 1 edge. Contoh 2.2.2: Berikut diberikan representasi dari spanning tree.
G:
s
s
s
s
s
s
T2 :
s
s
s
s
s
s
T1 :
s
s
s
s
s
s
T3 :
s
s
s
s
s
s
Gambar 2.10 : Spanning tree dari G
Dari gambar 2.9, untuk (6,7) graph menghasilkan spanning tree dengan 6 verteks dan 5 edge. Untuk menemukan spanning tree dari graph G terhubung dapat dilakukan dengan cara yang sederhana. Jika G tidak memiliki cycle, maka G merupakan spanning tree itu sendiri. Jika G memiliki cycle maka hapus semua edge yang membentuk cycle, dengan G masih terhubung.
Proposisi 2.12 Setiap graph terhubung memiliki paling sedikit satu spanning tree.
Bukti: Andaikan G adalah suatu graph terhubung. Jika G bebas cycle, maka G itu sendiri merupakan spanning tree. Jika tidak, G memiliki paling sedikit satu cycle C1. Dengan teorema 1.8 subgraph G tetap terhubung meski satu edge C1 dihapus. Jika subgraph bebas cycle, maka subgraph tersebut merupakan spanning tree. Jika tidak, maka paling sedikit ada satu cycle di C2, dan seperti sebelumnya, hapus edge di C2 untuk memperoleh spanning tree. Jika tidak, lakukan seperti sebelummya hingga diperoleh subgraph T dari G yang terhubung dan bebas cycle. Universitas Sumatera Utara T juga mengandung seluruh verteks G karena tidak ada verteks di G yang dihapus.
16 Oleh karenanya T merupakan spanning tree untuk G.
2.3 Degree Constrained Minimum Spanning Tree Andaikan G merupakan graph terhubung, T merupakan subgraph dari G, dT (vi ) merupakan degree dari verteks vi yang ada di T , dan bi merupakan batasan degree di T . Degree constrained spanning tree T adalah menemukan spanning tree T di G, sehingga dT (vi ) ≤ bi , untuk setiap verteks vi di T . Contoh 1.2.4 Berikut diberikan graph G dimana T merupakan DCST dari G. s s
s
T2 :
s
s
s s
G s
s
T1 :
s
dT (vi) ≤ 3
s
s
s
dT (vi) ≤ 2 s
s
T3 :
s
s s
s s
dT (vi ) ≤ 4
Gambar 2.11 : DCST dari G
Andaikan G = (V, E) adalah suatu graph berbobot terhubung tak berarah dimana V = {v1 , v2, ..., vn} adalah himpunan verteks dan E = {e1, e2, ..., em} himpunan edge di G. Andaikan W = {w1 , w2, ..., wm} mewakili bobot dari setiap edge, dimana bobot merupakan bilangan real nonnegatif. Subgraph dari G bisa dideskripsikan menggunakan vektor X = {x1, x2, ..., xm}, dimana setiap element
Universitas Sumatera Utara
17 xi didefenisikan oleh: xi =
1, jika edge terpilih
0, jika tidak terpilih.
Andaikan T menjadi subgraph G, T dikatakan spanning tree dari G jika T terhubung, mengandung seluruh verteks G, dan tidak cycle. Kemudian anggap d(vi ) degree dari verteks vi di G dan K(vi ) himpunan degree pada G serta bi merupakan batasan degree dT (vi) di T , permasalahan degree constrained minimum spanning tree dapat diformulasikan ke dalam program integer sebagai berikut: Fungsi Tujuan: Min
z(x) =
m X
wi xi
i=1
Kendala: m X
xi = |V | − 1
(1)
i=1 m X
xi ≤ |N| − 1,
∀N ⊂ V, |N | ≥ 3
(2)
i=1
X
xi ≤ bi , 1 ≤ bi ≤ |V | − 1, i = 1, 2, ..., n
(3)
xi ∈K(vi )
xi ∈ {0, 1},
xi ∈ E
(4)
Dari formulasi diatas, kendala pertama menyatakan bahwa hanya ada n − 1 edge yang terpilih, karenanya kendala kedua menjamin bahwa edge yang diperoleh akan menghubungkan seluruh verteks tanpa terjadi cycle, sedangkan kendala ketiga merupakan batas degree yang dikehendaki. Untuk menyelesaikan DCMST yang diformulasikan diatas, maka untuk graph lengkap akan ada 2n − 1 − n2 kendala. Bagaimanapun, untuk n = 30, cara ini sangat tidak praktis. Misalnya untuk graph lengkap dengan 30 verteks akan Universitas Utara ∼ kendalaSumatera yang ada ada 230 − 1 − 30 = 1, 07 × 109 kendala. Jika untuk setiap 2
18 dapat ditemukan dalam sepersepuluh detik, maka paling tidak akan dibutuhkan waktu 3,4 tahun untuk dapat menuliskan seluruh kendala sebelum perhitungan dilakukan. Pada dasarnya persoalan DCMST merupakan perkembangan dari permasalahan minimum spanning tree dengan syarat memenuhi batasan degree yang diberikan. Karenanya algoritma yang biasa digunakan untuk menyelesaikan minimum spanning tree dapat pula digunakan untuk menyelesaikan permasalahan DCMST. Salah satunya adalah algoritma Kruskal. Ning, Ma, dan Xiong (2008) menggunakan algoritma Kruskal untuk menyelesaikan permasalahan DCMST dengan terlebih dahulu menggunakan teknik reduksi untuk mengurangi ukuran graph dengan cara menghilangkan edge yang dianggap tidak perlu. Algoritma Kruskal pertama kali diperkenalkan pada tahun 1956 oleh Joseph Kruskal untuk menyelesaikan minimum spanning tree. Algoritma Kruskal ditulis kembali pada tahun 1957 oleh Loberman dan Weinberger, namun pencantuman nama mereka ditolak (Erickson, 2011). Pada algoritma Kruskal, awalnya seluruh edge diurutkan mulai bobot terkecil hingga terbesar. Lalu pemilihan edge dimulai dari bobot yang terkecil tersebut. Seluruh verteks vi yang ada di G dimasukkan ke T tanpa memasukkan edge, dengan kata lain pada awalnya tidak ada edge di T . Karena pemilihan edge berdasarkan nilai dari bobot setiap edge, maka pada prosesnya akan dihasilkan beberapa tree (forest). Untuk setiap edge (vj , vk ) yang telah terurut dilakukan hal berikut, jika verteks vj dan vk berada pada dua tree yang berbeda, maka tambahkan (vj , vk ) ke forest, kombinasikan dua tree ke dalam tree tunggal. Proses dihentikan jika edge (vj , vk ) tepat berjumlah |V | − 1.
Universitas Sumatera Utara
19 Berikut diberikan algoritma Kruskal(Erickson, 2011): KRUSKAL (V , E): Mulai: 1. Urutkan ei ∈ E berdasarkan ukuran bobot 2. T ← (V, ∅) 3. untuk setiap verteks vi ∈ V MASUKKANHIMPUNAN(V ) 4. untuk i←1 ke |E| a. (vj , vk ) ← tandai edge ke i di E b. jika PENEMUAN(vj )6= PENEMUAN(vk ) GABUNGKAN(vj , vk ) tambahkan (vj , vk ) ke T c. jika |(vj , vk )| = |V | − 1 hasil T
Akhir Waktu terburuk yang diperlukan algoritma Kruskal untuk melakukan proses dari tahap awal hingga menghasilkan minimum spanning tree adalah O(E log V ).
Teorema 2.13 Untuk graph G berbobot terhubung, algoritma Kruskal menghasilkan minimum spanning tree.
Bukti: Andaikan G graph berbobot terhubung dengan p edge, dan andaikan T subgraph yang dihasilkan oleh algoritma Kruskal. Pasti, T merupakan spanning tree G (karenanya memiliki p − 1 edge), katakanlah: E(T ) = {e1, e2, ..., ep−1}. dimana w(e1 ) ≤ w(e2 ) ≤ ... ≤ w(ep−1 ). Sehingga bobot T adalah: w(T ) =
p−1 X i=1
w(ei ).
Universitas Sumatera Utara
20 Andaikan sebaliknya, bahwa T bukan merupakan minimum spanning tree. Maka di G masih terdapat minimum spanning tree, pilih salah satu, katakanlah H yang memiliki jumlah edge paling mirip dengan T . Ini berarti tree H dan T tidak identik. Jadi, terdapat paling sedikit satu edge di T yang tidak ada di H. Andaikan ei (1 ≤ i ≤ p − 1) menjadi edge pertama T yang tidak di H, dan definisikan G0 = H + ei, maka G0 memiliki tepat satu cycle C. Karena T tidak cycle, maka terdapat e0 di C yang tidak ada di T . Graph T0 = G0 − e0 juga spanning tree di G dan w(T0) = w(H) + w(ei ) − w(e0) Karena w(H) ≤ w(T0 ), maka w(e0) ≤ w(ei ). Oleh algoritma Kruskal, ei merupakan edge dengan bobot paling minimum sehingga h{e1 , e2, ..., ei−1} ∪ {ei }i tidak cycle. Bagaimanapun h{e1 , e2, ..., ei−1, e0}i adalah subgraph H dan tidak cycle, sehingga w(ei ) = w(e0 ). Hal ini berakibat w(T0 ) = w(H), yang secara tidak langsung menyatakan bahwa T0 juga minimum spanning tree G. Akan tetapi T0 memiliki lebih banyak edge yang sama dengan T daripada H dengan T , yang .
kontradiksi dengan asumsi.
Karena permasalahan dari DCMST merupakan permasalahan menemukan spanning tree T di G dengan total panjang edge minimum dan degree dari setiap verteks memenuhi batas maksimum yang diberikan, maka untuk menyelesaikan DCMST dengan algoritma Kruskal perlu dilakukan modifikasi.
Universitas Sumatera Utara
