Lewati ke konten utama

Subbab 13.2 Aliran dan Potongan

Dengan mempertimbangkan penerapan yang dikemukakan pada awal bab, wajar jika kita mencari nilai maksimum suatu aliran dalam jaringan tertentu. Dengan kata lain, kita ingin menemukan bilangan terbesar \(v_0\) sehingga terdapat aliran \(\phi\) bernilai \(v_0\) dalam jaringan tersebut. Tentu saja, kita bukan hanya ingin menemukan nilai maksimum \(v_0\text{,}\) melainkan juga aliran \(\phi\) yang memiliki nilai itu. Meskipun mungkin sedikit mengejutkan, kita akan mengembangkan algoritma efisien yang sekaligus menemukan aliran bernilai maksimum dan menemukan sertifikat yang membuktikan klaim keoptimalannya. Sertifikat ini menggunakan konsep penting berikut.
Partisi \(V=L\cup U\) dari himpunan simpul \(V\) suatu jaringan dengan \(S\in L\) dan \(T\in U\) disebut potongan.
 1 
Pemilihan \(L\) dan \(U\) sebagai nama bagi kedua bagian partisi akan menjadi lebih masuk akal pada bagian selanjutnya dalam bab ini.
Kapasitas suatu potongan \(V=L\cup U\text{,}\) yang dinotasikan dengan \(c(L,U)\text{,}\) didefinisikan oleh
\begin{equation*} c(L,U) = \sum_{x\in L,y\in U} c(x,y). \end{equation*}
Dengan kata lain, kapasitas potongan \(V=L\cup U\) adalah kapasitas total semua sisi dari \(L\) ke \(U\text{.}\) Perhatikan bahwa ketika menghitung kapasitas potongan \(V=L\cup U\text{,}\) kita hanya menjumlahkan kapasitas sisi-sisi dari \(L\) ke \(U\text{.}\) Kita tidak menyertakan sisi-sisi dari \(U\) ke \(L\) dalam jumlah ini.

Contoh 13.3.

Mari kita kembali melihat jaringan pada Gambar 13.2. Pertama-tama, tinjau potongan \(V=L_1\cup U_1\) dengan
\begin{equation*} L_1 = \{S,F,B,E,D\}\qquad\text{dan} \qquad U_1= \{A,C,T\}. \end{equation*}
Di sini kita melihat bahwa kapasitas potongan tersebut adalah
\begin{equation*} c(L_1,U_1) = c(F,A) + c(B,A) + c(B,C)+ c(D,C) = 24+15+20+42 = 101. \end{equation*}
Namun, kita harus sedikit lebih berhati-hati ketika meninjau potongan \(V=L_2\cup U_2\) dengan
\begin{equation*} L_2 = \{S,F,B,E\}\qquad\text{dan} \qquad U_2=\{A,D,C,T\}. \end{equation*}
Di sini kapasitas potongan tersebut adalah
\begin{equation*} c(L_2,U_2) = c(F,A) + c(B,A) + c(B,C) + c(E,D) = 24+15+20+20=79. \end{equation*}
Perhatikan bahwa kita tidak menyertakan \(c(D,B)\) dalam perhitungan karena sisi berarah \((D,B)\) mengarah dari \(U_2\) ke \(L_2\text{.}\)
Hubungan antara aliran dan potongan bertumpu pada teorema mendasar berikut.

Bukti.
Dalam bukti ini (dan di seluruh bab), kita menggunakan konvensi yang sangat wajar bahwa \(\phi(x,y)=0\) jika \((x,y)\) bukan sisi berarah suatu jaringan \(\bfG\text{.}\)
Misalkan \(\phi\) suatu aliran bernilai \(v_0\) dan \(V=L\cup U\) suatu potongan. Pertama, perhatikan bahwa
\begin{equation*} v_0 = \sum_{y\in V} \phi(S,y) - \sum_{z\in V}\phi(z,S), \end{equation*}
karena penjumlahan kedua bernilai \(0\text{.}\) Selain itu, berdasarkan hukum kekekalan aliran yang kedua, untuk setiap simpul selain sumber dan muara kita memperoleh
\begin{equation*} \sum_{y\in V}\phi(x,y) -\sum_{z\in V}\phi(z,x) = 0. \end{equation*}
Sekarang kita memperoleh
\begin{align*} v_0 \amp = \sum_{y\in V} \phi(S,y) - \sum_{z\in V}\phi(z,S)\\ \amp = \sum_{y\in V} \phi(S,y) - \sum_{z\in V}\phi(z,S) + \sum_{\substack{x\in L\\x\neq S} }\left[\sum_{y\in V} \phi(x,y) - \sum_{z\in V}\phi(z,x)\right]\\ \amp = \sum_{x\in L}\left[\sum_{y\in V} \phi(x,y) - \sum_{z\in V}\phi(z,x)\right] \end{align*}
Pada tahap ini, mari kita berhenti sejenak untuk mencermati baris terakhir. Perhatikan bahwa jika \((a,b)\) merupakan sisi berarah dengan kedua titik ujung di \(L\text{,}\) maka ketika penjumlahan luar dilakukan untuk \(x=a\text{,}\) kita memperoleh sumbangan keseluruhan sebesar \(\phi(a,b)\text{.}\) Sebaliknya, ketika dilakukan untuk \(x=b\text{,}\) kita memperoleh sumbangan sebesar \(-\phi(a,b)\text{.}\) Dengan demikian, suku-suku tersebut saling meniadakan dan semuanya menyederhana menjadi
\begin{equation*} \sum_{\substack{x\in L\\y\in U} } \phi(x,y) - \sum_{\substack{x\in L\\ z\in U} } \phi(z,x)\leq \sum_{\substack{x\in L\\y\in U} } \phi(x,y)\leq \sum_{\substack{x\in L\\y\in U} } c(x,y)=c(L,U). \end{equation*}
Jadi, \(v_0\leq c(L,U)\text{.}\)

Diskusi 13.5.

Bob sedikit merasakan déjà vu setelah membaca Teorema 13.4. Ia ingat dari Bab 5 bahwa ukuran maksimum klik dalam suatu graf selalu tidak lebih besar daripada jumlah minimum warna yang diperlukan untuk mewarnai graf itu secara tepat. Namun, ia juga ingat bahwa terdapat graf tanpa klik berukuran tiga tetapi dengan bilangan kromatik yang dapat sebesar apa pun, sehingga ia tidak terlalu berharap teorema ini akan banyak membantu di sini. Yolanda ikut mengingatkan mereka tentang Bab 6, tempat mereka mempelajari bahwa ukuran maksimum antirantai dalam suatu poset sama dengan jumlah minimum rantai yang dapat digunakan untuk mempartisi himpunan dasar poset itu. Alice menunjukkan bahwa pernyataan Yolanda tetap benar jika kata “rantai” dan “antirantai” dipertukarkan. Hal ini memicu perdebatan sengit mengenai apakah nilai maksimum suatu aliran dalam jaringan selalu sama dengan kapasitas minimum suatu potongan dalam jaringan tersebut. Setelah beberapa lama, Carlos menyarankan bahwa melanjutkan membaca mungkin merupakan cara terbaik untuk menyelesaikan perdebatan mereka.
SblmKe AtasLnjt