Lewati ke konten utama

Latihan 13.7 Latihan

1.

Perhatikan diagram jaringan pada Gambar 13.14. Pada setiap sisi berarah, bilangan pertama menyatakan kapasitas dan bilangan kedua dimaksudkan sebagai nilai aliran \(\phi\) dalam jaringan. Namun, aliran yang diberikan tidak sah.
  1. Tentukan alasan mengapa \(\phi\) tidak sah.
  2. Tanpa mengubah kapasitas sisi mana pun, ubah \(\phi\) menjadi aliran sah \(\widehat{\phi}\text{.}\) Usahakan menggunakan sesedikit mungkin perubahan.
dijelaskan secara terperinci setelah gambar
Diagram jaringan dengan kapasitas dan nilai aliran yang tidak memenuhi semua syarat aliran.
Gambar 13.14. Aliran Tidak Sah dalam Suatu Jaringan

2.

Alice mengklaim telah menemukan aliran jaringan sah bernilai \(20\) dalam jaringan pada Gambar 13.15. Bob mengatakan bahwa klaim itu mustahil benar karena tidak ada aliran yang nilainya lebih besar daripada \(18\text{.}\) Siapa yang benar, dan mengapa?
dijelaskan secara terperinci setelah gambar
Diagram jaringan berkapasitas yang digunakan untuk membandingkan batas aliran Alice dan Bob.
Gambar 13.15. Sebuah Jaringan

3.

Temukan lintasan penambah \(P\) dengan sekurang-kurangnya satu sisi mundur bagi aliran \(\phi\) dalam jaringan pada Gambar 13.16. Berapakah nilai \(\delta\) untuk \(P\text{?}\) Perbarui \(\phi\) dengan menggunakan \(P\) untuk memperoleh aliran baru \(\hat{\phi}\text{.}\) Berapakah nilai \(\hat{\phi}\text{?}\)
dijelaskan secara terperinci setelah gambar
Diagram jaringan yang mencantumkan kapasitas dan aliran pada setiap sisi berarah.
Gambar 13.16. Jaringan dengan Aliran

4.

Buktikan Proposisi 13.7. Anda perlu memeriksa bahwa hukum kekekalan aliran berlaku pada setiap simpul di sepanjang lintasan penambah, selain \(S\) dan \(T\text{.}\) Ada empat kasus yang perlu ditinjau, bergantung pada status maju atau mundur dari kedua sisi lintasan penambah yang bersisian dengan simpul tersebut.

5.

Tentukan kapasitas potongan \((L,U)\) dengan
\begin{equation*} L=\{S,F,H,C,B,G,I\}\qquad\text{dan} \qquad U=\{A,D,E,T\} \end{equation*}
dalam jaringan pada Gambar 13.16.

6.

Tentukan kapasitas potongan \((L,U)\) dengan
\begin{equation*} L=\{S,F,D,B,A\}\qquad\text{dan} \qquad U=\{H,C,I,G,E,T\} \end{equation*}
dalam jaringan pada Gambar 13.16.

7.

Untuk masing-masing lintasan penambah \(P_1\text{,}\) \(P_2\text{,}\) \(P_3\text{,}\) dan \(P_4\) dalam Contoh 13.8, perbarui aliran pada Gambar 13.2. Perhatikan bahwa solusi latihan ini harus terdiri atas empat aliran jaringan. Jangan mencoba menggunakan keempat lintasan secara berurutan untuk menghasilkan satu aliran jaringan yang diperbarui.

8.

Lanjutkan algoritma pelabelan Ford–Fulkerson pada aliran jaringan dalam Gambar 13.12 hingga algoritma berhenti tanpa memberi label pada muara. Tentukan nilai aliran maksimum beserta sebuah potongan berkapasitas minimum.

9.

Gunakan algoritma pelabelan Ford–Fulkerson untuk menemukan aliran maksimum dan potongan minimum dalam jaringan pada Gambar 13.17, dengan memulai dari aliran saat ini yang ditampilkan di sana.
dijelaskan secara terperinci setelah gambar
Diagram jaringan dengan kapasitas dan aliran awal pada setiap sisi berarah.
Gambar 13.17. Jaringan dengan Aliran

10.

Gambar 13.18 menampilkan suatu jaringan. Mulailah dari aliran nol, i.e., aliran dengan \(\phi(e)=0\) untuk setiap sisi berarah \(e\) dalam jaringan. Gunakan algoritma pelabelan Ford–Fulkerson untuk menemukan aliran maksimum dan potongan minimum dalam jaringan tersebut.
dijelaskan secara terperinci setelah gambar
Diagram jaringan berkapasitas yang akan dianalisis mulai dari aliran nol.
Gambar 13.18. Sebuah Jaringan

11.

Perhatikan suatu jaringan yang sumbernya, \(S\text{,}\) mempunyai tepat tiga tetangga: \(B\text{,}\) \(E\text{,}\) dan \(F\text{.}\) Misalkan pula \(c(S,B)=30\text{,}\) \(c(S,E)=20\text{,}\) dan \(c(S,F)=25\text{.}\) Anda mengetahui bahwa terdapat aliran \(\phi\) pada jaringan, tetapi tidak mengetahui besar aliran pada sisi mana pun. Namun, Anda mengetahui bahwa ketika algoritma pelabelan Ford–Fulkerson dijalankan pada jaringan dengan aliran saat ini \(\phi\text{,}\) dua simpul pertama yang diberi label adalah \(S\) dengan label \((*,+,\infty)\) dan \(F\) dengan label \((S,+,15)\text{.}\) Gunakan informasi ini untuk menentukan nilai aliran \(\phi\) dan jelaskan cara Anda memperolehnya.
SblmKe AtasLnjt