Subbab 12.1 Pohon Rentang Berbobot Minimum

Dalam bagian ini, kita meninjau pasangan \((\bfG,w)\text{,}\) dengan \(\GVE\) suatu graf terhubung dan \(w\colon E\rightarrow\nonnegints\text{.}\) Untuk setiap sisi \(e\in E\text{,}\) besaran \(w(e)\) disebut bobot dari \(e\text{.}\) Untuk suatu himpunan sisi \(S\text{,}\) kita mendefinisikan bobot dari \(S\text{,}\) yang dilambangkan dengan \(w(S)\text{,}\) dengan menetapkan \(w(S)=\sum_{e\in S} w(e)\text{.}\) Khususnya, bobot pohon rentang \(T\) adalah jumlah bobot sisi-sisi dalam \(T\text{.}\)

Graf berbobot muncul dalam banyak konteks. Salah satu yang paling wajar ialah ketika bobot sisi menyatakan jarak atau biaya. Sebagai contoh, tinjau graf berbobot pada Gambar 12.1. Misalkan simpul-simpulnya mewakili titik-titik suatu jaringan dan sisi-sisinya mewakili kemungkinan membangun hubungan fisik langsung di antara titik-titik tersebut. Bobot pada sisi menyatakan biaya membangun hubungan itu (misalnya dalam ribuan dolar). Perusahaan yang membangun jaringan tersebut hanya berkepentingan agar data dapat dikirimkan di antara setiap pasangan titik. Hubungan tambahan akan menimbulkan redundansi yang belum mereka perlukan. Pohon rentang dari graf menjamin bahwa setiap titik dapat berkomunikasi dengan setiap titik lainnya tanpa redundansi, sebab penghapusan sisi mana pun akan memutus graf tersebut. Jadi, untuk meminimumkan biaya pembangunan jaringan, kita ingin mencari pohon rentang berbobot (atau berbiaya) minimum.

dijelaskan secara terperinci setelah gambar — Gambar 12.1. Graf berbobot

Untuk itu, bagian ini membahas masalah berikut:

Soal 12.2.

Carilah pohon rentang berbobot minimum \(\bfT\) dari \(\bfG\text{.}\)

Untuk menyelesaikan masalah ini, kita akan mengembangkan dua algoritma graf yang efisien, masing-masing dengan kelebihan dan kekurangan komputasional tertentu. Sebelum mengembangkan algoritma tersebut, kita perlu menetapkan beberapa fakta pendahuluan mengenai pohon rentang dan hutan rentang.

Subbagian 12.1.1 Pendahuluan

Proposisi berikut tentang banyaknya komponen dalam hutan rentang dari graf \(\bfG\) mempunyai bukti induktif yang mudah. Anda diminta menyusun buktinya dalam latihan.

Proposisi 12.3.

Misalkan \(\GVE\) suatu graf dengan \(n\) simpul dan \(\bfH=(V,S)\) suatu hutan rentang. Maka \(0\le |S|\le n-1\text{.}\) Selanjutnya, jika \(|S|= n-k\text{,}\) maka \(\bfH\) memiliki \(k\) komponen. Khususnya, \(\bfH\) merupakan pohon rentang jika dan hanya jika memuat \(n-1\) sisi.

Proposisi berikut memberikan cara untuk mengambil sebuah pohon rentang dari suatu graf, menghapus satu sisinya, lalu menambahkan sisi graf yang tidak berada dalam pohon rentang itu sehingga terbentuk pohon rentang baru. Pada dasarnya, proses ini mempertukarkan dua sisi untuk membentuk pohon rentang baru; karena itu kita menyebutnya prinsip pertukaran.

Proposisi 12.4. Prinsip Pertukaran.

Misalkan \(\bfT=(V,S)\) suatu pohon rentang dalam graf \(\bfG\text{,}\) dan misalkan \(e=xy\) suatu sisi \(\bfG\) yang tidak termasuk dalam \(\bfT\text{.}\) Maka

Terdapat lintasan tunggal \(P=(x_0,x_1,x_2,\dots,x_t)\) yang memenuhi (a) \(x=x_0\text{;}\) (b) \(y=x_t\text{;}\) dan (c) \(x_ix_{i+1}\in S\) untuk setiap \(i=0,1,2,\dots,t-1\text{.}\)
Untuk setiap \(i=0,1,2,\dots,t-1\text{,}\) misalkan \(f_i=x_ix_{i+1}\text{,}\) lalu tetapkan

\begin{equation*} S_i = \{e\}\cup\{g\in S: g\neq f_i\}, \end{equation*}

i.e., kita mempertukarkan sisi \(f_i\) dengan sisi \(e\text{.}\) Maka \(\bfT_i=(V,S_i)\) merupakan pohon rentang dari \(\bfG\text{.}\)

Bukti.

Untuk fakta pertama, cukup perhatikan bahwa jika terdapat lebih dari satu lintasan berbeda dari \(x\) ke \(y\) dalam \(\bfT\text{,}\) kita dapat menemukan suatu siklus dalam \(\bfT\text{.}\) Hal ini mustahil karena graf tersebut adalah pohon. Untuk fakta kedua, perhatikan Gambar 12.5. Sisi-sisi hitam dan hijau pada graf sebelah kiri menyatakan pohon rentang \(\bfT\text{.}\) Jadi, \(f\) terletak pada lintasan tunggal dari \(x\) ke \(y\) dalam \(\bfT\text{,}\) sedangkan \(e=xy\) adalah sisi \(\bfG\) yang tidak berada dalam \(\bfT\text{.}\) Penambahan \(e\) ke \(\bfT\) menghasilkan graf dengan tepat satu siklus, sebab \(\bfT\) semula memiliki lintasan tunggal dari \(x\) ke \(y\text{.}\) Penghapusan \(f\) (yang dapat berupa sisi \(f_i\) mana pun pada lintasan tersebut, sebagaimana dinyatakan dalam proposisi) memutus siklus ini. Dengan demikian, \(\bfT_i\) merupakan subgraf terhubung dan asiklik dari \(\bfG\) dengan \(n-1+1-1=n-1\) sisi, sehingga merupakan pohon rentang.

Untuk kedua algoritma yang kita kembangkan, argumen yang menunjukkan optimalitas algoritma bertumpu pada lema teknis berikut. Untuk menghindari kasus sepele, kita mengasumsikan \(n\ge3\text{.}\)

Lema 12.6.

Misalkan \(\bfF\) suatu hutan rentang dari \(\bfG\) dan \(C\) suatu komponen dari \(\bfF\text{.}\) Misalkan pula \(e=xy\) suatu sisi berbobot minimum di antara semua sisi dengan satu titik ujung dalam \(C\) dan titik ujung lainnya di luar \(C\text{.}\) Maka, di antara semua pohon rentang dari \(\bfG\) yang memuat hutan \(\bfF\text{,}\) terdapat satu pohon berbobot minimum yang memuat sisi \(e\text{.}\)

Bukti.

Ambil sebarang pohon rentang \(\bfT=(V,S)\) yang berbobot minimum di antara semua pohon rentang yang memuat hutan \(\bfF\text{,}\) dan andaikan bahwa \(e=xy\) bukan sisi dalam \(\bfT\text{.}\) (Jika sisi itu berada dalam \(\bfT\text{,}\) pembuktian selesai.) Misalkan \(P=(x_0,x_1,x_2,\dots,x_t)\) lintasan tunggal dalam \(\bfT\) yang memenuhi (a) \(x=x_0\text{;}\) (b) \(y=x_t\text{;}\) dan (c) \(x_ix_{i+1}\in S\) untuk setiap \(i=0,1,2,\dots,t-1\text{.}\) Tanpa mengurangi keumuman, kita dapat mengasumsikan bahwa \(x=x_0\) merupakan simpul dalam \(C\text{,}\) sedangkan \(y=x_t\) tidak termasuk dalam \(C\text{.}\) Maka terdapat bilangan bulat nonnegatif terkecil \(i\) sedemikian sehingga \(x_i\) berada dalam \(C\) dan \(x_{i+1}\) tidak berada dalam \(C\text{.}\) Akibatnya, \(x_j\) berada dalam \(C\) untuk semua \(j\) dengan \(0\le j\le i\text{.}\)

Misalkan \(f=x_ix_{i+1}\text{.}\) Sisi \(e\) memiliki bobot minimum di antara semua sisi dengan satu titik ujung dalam \(C\) dan titik ujung lainnya di luar \(C\text{,}\) sehingga \(w(e)\le w(f)\text{.}\) Sekarang misalkan \(\bfT_i\) pohon yang diperoleh dengan mempertukarkan sisi \(f\) dengan sisi \(e\text{.}\) Dengan demikian, \(w(\bfT_i) = w(\bfT) - w(f) +w(e)\le w(\bfT)\text{.}\) Selain itu, \(\bfT_i\) memuat hutan rentang \(\bfF\) serta sisi \(e\text{.}\) Jadi, inilah pohon rentang berbobot minimum yang kita cari.

Diskusi 12.7.

Meskipun intuisi kombinatorial Bob telah meningkat selama perkuliahan, ia belum sepenuhnya memahami mengapa kita memerlukan algoritma khusus untuk mencari pohon rentang berbobot minimum. Menurutnya, jumlah pohon rentang tentu tidak mungkin terlalu banyak, jadi ia ingin menuliskan semuanya saja. Alice mengeluh karena menduga Bob pasti tidak hadir ketika materi pada Subbab 5.6 dibahas. Dalam bagian tersebut, kita mempelajari bahwa graf dengan \(n\) simpul dapat memiliki sebanyak \(n^{n-2}\) pohon rentang (atau, mengerikannya, mungkin pengajar tidak memasukkannya ke dalam silabus). Bagaimanapun, pendekatan menyeluruh ini sudah tidak dapat digunakan ketika \(n = 20\text{.}\) Dave bergumam tentang bersikap rakus: tambahkan sisi-sisi teringan satu demi satu, tetapi jangan pernah menambahkan sisi yang akan membentuk siklus. Zori ingat bahwa strategi serupa berhasil untuk mencari tinggi suatu poset, tetapi ia khawatir akan situasi buruk seperti yang kita jumpai ketika menggunakan FirstFit untuk mewarnai graf. Alice setuju bahwa rekam jejak algoritma rakus tidak konsisten, tetapi ia menduga Lema 12.6 cukup untuk menjamin keberhasilan strategi tersebut di sini.

Subbagian 12.1.2 Algoritma Kruskal

Dalam bagian ini, kita mengembangkan salah satu algoritma paling terkenal untuk mencari pohon rentang berbobot minimum. Algoritma ini dikenal sebagai Algoritma Kruskal, meskipun sebagian orang lebih menyukai nama deskriptif Hindari Siklus karena cara algoritma tersebut membangun pohon rentang.

Untuk memulai algoritma Kruskal, kita mengurutkan sisi-sisi menurut bobotnya. Lebih tepatnya, misalkan \(m\) menyatakan banyaknya sisi dalam \(\GVE\text{.}\) Beri label sisi-sisi itu sebagai \(e_1,e_2,e_3,\dots,e_m\) sedemikian sehingga \(w(e_1)\le w(e_2)\le \dots \le w(e_m)\text{.}\) Langkah ini dapat dilakukan dengan salah satu dari sekian banyak algoritma pengurutan yang efisien.

Setelah sisi-sisi diurutkan, algoritma Kruskal menjalankan langkah inisialisasi, lalu membangun pohon rentang \(\bfT=(V,S)\) secara induktif:

Algoritma 12.8. Algoritma Kruskal.

Inisialisasi.: Tetapkan \(S=\emptyset\) dan \(i=0\text{.}\)
Langkah Induktif.: Selama \(|S| \lt n-1\text{,}\) misalkan \(j\) bilangan bulat nonnegatif terkecil sedemikian sehingga \(j > i\) dan tidak terdapat siklus dalam \(S\cup\{e_j\}\text{.}\) Kemudian (dengan notasi kode semu) tetapkan

\begin{equation*} i = j\quad\text{dan} \quad S= S\cup\{e_j\}. \end{equation*}

Kebenaran Algoritma Kruskal mengikuti suatu argumen induktif. Mula-mula, himpunan \(S\) diinisialisasi sebagai himpunan kosong, sehingga tentu terdapat pohon rentang berbobot minimum yang memuat semua sisi dalam \(S\text{.}\) Sekarang andaikan bahwa, untuk suatu \(i\) dengan \(0\le i \lt n\text{,}\) berlaku \(|S|=i\) dan terdapat pohon rentang berbobot minimum yang memuat semua sisi dalam \(S\text{.}\) Misalkan \(\bfF\) hutan rentang yang ditentukan oleh sisi-sisi dalam \(S\text{,}\) dan misalkan \(C_1, C_2,\dots,C_s\) komponen-komponen dari \(\bfF\text{.}\) Untuk setiap \(k=1,2,\dots,s\text{,}\) misalkan \(f_k\) suatu sisi berbobot minimum dengan satu titik ujung dalam \(C_k\) dan titik ujung lainnya di luar \(C_k\text{.}\) Sisi \(e\) yang ditambahkan ke \(S\) oleh Algoritma Kruskal adalah sisi berbobot minimum di antara sisi-sisi dalam \(\{f_1,f_2,\dots,f_s\}\text{.}\) Dengan menerapkan Lema 12.6 dan hipotesis induksi, kita mengetahui bahwa masih terdapat pohon rentang berbobot minimum dari \(\bfG\) yang memuat semua sisi dalam \(S\cup\{e\}\text{.}\)

Contoh 12.9. Algoritma Kruskal.

Mari kita lihat cara kerja algoritma Kruskal pada graf berbobot di Gambar 12.1. Pertama-tama algoritma mengurutkan semua sisi menurut bobotnya. Kita tidak akan menuliskan kembali daftar itu karena tidak semuanya diperlukan. Sisi berbobot terkecil adalah \(ck\text{,}\) dengan bobot \(23\text{.}\) Algoritma kemudian terus menambahkan sisi berbobot terkecil, yaitu \(ag\text{,}\) \(fg\text{,}\) \(fi\text{,}\) \(fj\text{,}\) dan \(bj\text{.}\) Namun, setelah itu sisi berbobot terkecil berikutnya adalah \(fb\text{,}\) dengan bobot \(38\text{.}\) Sisi ini tidak dapat ditambahkan karena akan menjadikan \(fjb\) suatu siklus. Karena itu, algoritma melewatinya dan menambahkan \(bc\text{.}\) Sisi \(ai\) diperiksa berikutnya, tetapi sisi ini juga akan membentuk siklus sehingga dikesampingkan. Kemudian \(em\) ditambahkan, disusul \(dl\text{.}\) Sekarang terdapat dua sisi berbobot \(56\) yang harus dipertimbangkan: \(al\) dan \(dj\text{.}\) Algoritma pengurutan kita telah menempatkan salah satunya lebih dahulu; misalkan sisi itu adalah \(dj\text{.}\) Setelah \(dj\) ditambahkan, kita tidak dapat menambahkan \(al\) karena \(agfjdl\) akan membentuk siklus. Sisi \(dk\) dipertimbangkan berikutnya, tetapi sisi itu juga akan membentuk siklus. Sebaliknya, \(ek\) dapat ditambahkan. Selanjutnya sisi \(km\) dan \(dm\) dilewati. Terakhir, sisi \(ch\) ditambahkan sebagai sisi kedua belas sekaligus sisi terakhir bagi pohon rentang dengan \(13\) simpul ini. Daftar lengkap sisi yang ditambahkan (menurut urutan) ditampilkan di sebelah kanan. Bobot total pohon rentang ini adalah \(504\text{.}\)

c k 23
a g 25
f g 26
f i 29
f j 30
b j 34
b c 39
e m 49
d l 55
d j 56
e k 59
c h 79

Subbagian 12.1.3 Algoritma Prim

Sekarang kita mengembangkan Algoritma Prim untuk mencari pohon rentang berbobot minimum. Algoritma ini juga dikenal dengan nama yang lebih deskriptif: Bangun Pohon. Kita mulai dengan memilih simpul akar \(r\text{.}\) Sekali lagi, algoritma menjalankan langkah inisialisasi yang disusul serangkaian langkah induktif.

Algoritma 12.10. Algoritma Prim.

Inisialisasi.: Tetapkan \(W=\{r\}\) dan \(S=\emptyset\text{.}\)
Langkah Induktif.: Selama \(|W| \lt n\text{,}\) misalkan \(e\) suatu sisi berbobot minimum di antara semua sisi dengan satu titik ujung dalam \(W\) dan titik ujung lainnya di luar \(W\text{.}\) Jika \(e=xy\text{,}\) \(x\in W\text{,}\) dan \(y\not\in W\text{,}\) perbarui \(W\) dan \(S\) dengan menetapkan (dalam notasi kode semu)

\begin{equation*} W = W\cup\{y\}\quad\text{dan} \quad S = S\cup\{e\}. \end{equation*}

Kebenaran algoritma Prim langsung mengikuti Lema 12.6.

Contoh 12.11. Algoritma Prim.

Mari kita lihat cara kerja algoritma Prim pada graf berbobot di Gambar 12.1. Kita mulai dengan simpul \(a\) sebagai simpul akar. Sisi teringan yang menghubungkan \(a\) (satu-satunya simpul yang sejauh ini berada dalam pohon) dengan bagian graf lainnya adalah \(ag\text{.}\) Berikutnya, \(fg\) ditambahkan. Setelah itu ditambahkan \(fi\text{,}\) \(fj\text{,}\) \(bj\text{,}\) dan \(bc\text{.}\) Selanjutnya, algoritma mengenali \(ck\) sebagai sisi teringan yang menghubungkan \(\{a,g,i,f,j,b,c\}\) dengan simpul-simpul yang tersisa. Perhatikan bahwa sisi yang sama baru ditemukan jauh lebih lambat daripada oleh algoritma Kruskal. Algoritma kemudian menentukan bahwa \(al\) dan \(jd\text{,}\) yang keduanya berbobot \(56\text{,}\) merupakan sisi-sisi teringan yang menghubungkan simpul dalam pohon dengan simpul di luar pohon. Algoritma memilih salah satunya secara sebarang; misalkan yang dipilih adalah \(al\text{.}\) Berikutnya algoritma menemukan \(dl\text{,}\) kemudian \(ek\text{,}\) lalu \(em\text{.}\) Sisi terakhir yang ditambahkan adalah \(ch\text{.}\) Daftar lengkap sisi yang ditambahkan (menurut urutan) ditampilkan di sebelah kanan. Bobot total pohon rentang ini adalah \(504\text{.}\) Tidak mengherankan, bobot ini sama dengan yang kita peroleh menggunakan algoritma Kruskal. Akan tetapi, perhatikan bahwa pohon rentang yang ditemukan berbeda karena pohon ini memuat \(al\text{,}\) bukan \(dj\text{.}\) Tentu saja hal ini tidak menjadi masalah, sebab dalam kedua kasus dibuat pilihan sebarang di antara dua sisi berbobot sama.

a g 25
f g 26
f i 29
f j 30
b j 34
b c 39
c k 23
a l 56
d l 55
e k 59
e m 49
c h 79

Subbagian 12.1.4 Catatan tentang Efisiensi

Implementasi algoritma Kruskal tampaknya mengharuskan sisi-sisi diurutkan. Jika graf memiliki \(n\) simpul dan \(m\) sisi, pengurutan saja memerlukan \(m\log m\) operasi. Namun, setelah pengurutan selesai, prosesnya hanya memerlukan \(n-1\) langkah—asalkan kita terus mencatat komponen-komponen ketika hutan rentang bertumbuh. Bagaimanapun, mudah dilihat bahwa paling banyak diperlukan \(O(n^2\log n)\) operasi.

Di sisi lain, implementasi algoritma Prim mengharuskan program menyimpan informasi sisi-sisi yang bersisian dengan setiap simpul secara efisien dan selalu dapat mengenali sisi berbobot terkecil dalam suatu subhimpunan sisi tersebut. Dalam ilmu komputer, struktur data yang memungkinkan tugas ini dilakukan disebut heap.

Sblm Ke Atas Lnjt