Untuk graf pada Gambar 12.20, gunakan algoritma Kruskal (“hindari siklus”) untuk mencari pohon rentang berbobot minimum. Jawaban Anda harus memuat daftar lengkap sisi, dengan menunjukkan sisi mana yang Anda pilih untuk pohon dan sisi mana (jika ada) yang Anda tolak selama algoritma dijalankan.
Untuk graf pada Gambar 12.20, gunakan algoritma Prim (“bangun pohon”) untuk mencari pohon rentang berbobot minimum. Jawaban Anda harus mencantumkan sisi-sisi yang dipilih algoritma menurut urutan pemilihannya.
Untuk graf pada Gambar 12.21, gunakan algoritma Kruskal (“hindari siklus”) untuk mencari pohon rentang berbobot minimum. Jawaban Anda harus memuat daftar lengkap sisi, dengan menunjukkan sisi mana yang Anda pilih untuk pohon dan sisi mana (jika ada) yang Anda tolak selama algoritma dijalankan.
Untuk graf pada Gambar 12.21, gunakan algoritma Prim (“bangun pohon”) untuk mencari pohon rentang berbobot minimum. Jawaban Anda harus mencantumkan sisi-sisi yang dipilih algoritma menurut urutan pemilihannya.
Untuk graf pada Gambar 12.22, gunakan algoritma Kruskal (“hindari siklus”) untuk mencari pohon rentang berbobot minimum. Jawaban Anda harus memuat daftar lengkap sisi, dengan menunjukkan sisi mana yang Anda pilih untuk pohon dan sisi mana (jika ada) yang Anda tolak selama algoritma dijalankan.
Untuk graf pada Gambar 12.22, gunakan algoritma Prim (“bangun pohon”) untuk mencari pohon rentang berbobot minimum. Jawaban Anda harus mencantumkan sisi-sisi yang dipilih algoritma menurut urutan pemilihannya.
Sebuah bank lokal baru sedang didirikan dan akan membangun kantor pusat \(h\text{,}\) dua kantor cabang \(b_1\) dan \(b_2\text{,}\) serta empat ATM \(a_1\text{,}\)\(a_2\text{,}\)\(a_3\text{,}\) dan \(a_4\text{.}\) Mereka perlu membangun jaringan komputer agar kantor pusat, kantor-kantor cabang, dan semua ATM dapat saling berkomunikasi. Selain itu, semuanya perlu terhubung ke Federal Reserve Bank of Atlanta, \(f\text{.}\) Biaya hubungan jaringan yang dapat dibangun (dalam satuan $10.000) dicantumkan di bawah ini:
\begin{align*}
h f \amp \quad 80 \amp
h b_1 \amp \quad 10\amp h b_2 \amp \quad 20\amp
b_1 b_2 \amp \quad 8\\
f b_1 \amp \quad 12\amp
f a_1 \amp \quad 20\amp b_1 a_1 \amp \quad 3\amp
a_1 a_2 \amp \quad 13\\
h a_2 \amp \quad 6\amp
b_2 a_2 \amp \quad 9\amp b_2 a_3 \amp \quad 40\amp
a_1 a_4 \amp \quad 3\\
a_3 a_4 \amp \quad 6
\end{align*}
Bank tersebut ingin meminimumkan biaya pembangunan jaringannya (yang harus memungkinkan hubungan, mungkin melalui titik-titik lain, dari setiap titik ke setiap titik lainnya). Namun, karena membutuhkan komunikasi berkecepatan tinggi, mereka wajib membayar pembangunan hubungan dari \(h\) ke \(f\) serta hubungan dari \(b_2\) ke \(a_3\text{.}\) Berikan daftar hubungan yang harus dibangun bank agar biaya totalnya minimum dengan memenuhi kendala tersebut. Jelaskan cara Anda memilih hubungan-hubungan itu dan alasan biaya totalnya benar-benar minimum.
Graf berbobot yang tidak terhubung jelas tidak memiliki pohon rentang. Namun, kita dapat mencari hutan rentang berbobot minimum dalam graf semacam itu. Jelaskan cara memodifikasi algoritma Kruskal dan algoritma Prim untuk melakukannya.
Dalam makalah tempat algoritma Kruskal pertama kali muncul, Kruskal menganggap algoritma tersebut sebagai jalan menuju bukti yang lebih baik bahwa setiap graf berbobot terhubung yang tidak memiliki dua sisi berbobot sama mempunyai pohon rentang berbobot minimum yang tunggal. Buktikan fakta ini menggunakan algoritma Kruskal.
Gunakan algoritma Dijkstra untuk mencari jarak dari \(a\) ke setiap simpul lain dalam digraf pada Gambar 12.23 beserta lintasan berarah yang memiliki panjang tersebut.
Gambar 12.24 memuat panjang sisi berarah \((x,y)\) pada perpotongan baris\(x\) dan kolom\(y\) dalam digraf dengan himpunan simpul \(\{a,b,c,d,e,f\}\text{.}\) Sebagai contoh, \(w(b,d)=21\text{.}\) (Di sisi lain, \(w(d,b)=10\text{.}\)) Gunakan data ini dan algoritma Dijkstra untuk mencari jarak dari \(a\) ke setiap simpul lainnya beserta lintasan berarah dari \(a\) yang memiliki panjang tersebut.
Gunakan algoritma Dijkstra untuk mencari jarak dari \(a\) ke setiap simpul lain dalam digraf pada Gambar 12.25 beserta lintasan berarah yang memiliki panjang tersebut.
Gambar 12.26 memuat panjang sisi berarah \((x,y)\) pada perpotongan baris\(x\) dan kolom\(y\) dalam digraf dengan himpunan simpul \(\{a,b,c,d,e,f\}\text{.}\) Sebagai contoh, \(w(b,d)=47\text{.}\) (Di sisi lain, \(w(d,b)=6\text{.}\)) Gunakan data ini dan algoritma Dijkstra untuk mencari jarak dari \(a\) ke setiap simpul lainnya beserta lintasan berarah dari \(a\) yang memiliki panjang tersebut.
Berikan contoh digraf yang mempunyai lintasan tak berarah di antara setiap pasangan simpul, tetapi mempunyai simpul akar \(r\) sedemikian sehingga algoritma Dijkstra tidak dapat menemukan lintasan berpanjang hingga dari \(r\) ke suatu simpul \(x\text{.}\)
Perhatikan bahwa dalam pembahasan algoritma Dijkstra, kita mensyaratkan bobot sisi nonnegatif. Jika bobot sisi merupakan panjang dan dimaksudkan untuk memodelkan jarak, syarat ini sangat masuk akal. Namun, dalam beberapa keadaan mungkin wajar untuk mengizinkan bobot sisi negatif. Sebagai contoh, misalkan bobot positif berarti ada biaya untuk melintasi sisi berarah, sedangkan bobot negatif berarti Anda memperoleh uang ketika melintasinya. Dalam keadaan ini, lintasan berarah berbobot total positif membuat Anda harus membayar untuk melintasinya, sedangkan lintasan berbobot total negatif menghasilkan keuntungan.
Berikan contoh yang menunjukkan bahwa algoritma Dijkstra tidak selalu menemukan lintasan berbobot total minimum apabila bobot sisi negatif diizinkan.
Bob dan Xing sedang mempertimbangkan keadaan ini, dan Bob menyarankan sedikit modifikasi algoritma untuk menyelesaikan masalah tersebut. Menurutnya, jika terdapat bobot negatif, mereka hanya perlu mencari bobot terkecil (i.e., bobot paling negatif), lalu menambahkan nilai mutlak bobot itu kepada setiap sisi berarah. Sebagai contoh, jika \(w(x,y)\geq -10\) untuk setiap sisi berarah \((x,y)\text{,}\) Bob menyarankan agar mereka menambahkan \(10\) kepada setiap bobot sisi. Xing merasa ragu, dan keraguannya beralasan. Berikan contoh yang menunjukkan mengapa modifikasi Bob tidak berhasil.
