Dalam bagian ini, kita mengembangkan algoritma pelabelan klasik Ford dan Fulkerson. Algoritma ini berawal dari sebarang aliran dalam suatu jaringan, lalu mengubah aliran tersebut—dengan selalu meningkatkan nilainya—hingga mencapai tahap ketika tidak ada perbaikan lebih lanjut yang mungkin dilakukan. Algoritma ini juga akan membantu menyelesaikan perdebatan Alice, Bob, Carlos, dan Yolanda pada bagian sebelumnya.
Penyajian algoritma pelabelan ini menggunakan beberapa istilah yang wajar dan cukup deskriptif. Misalkan kita mempunyai jaringan \(\GVE\) dengan aliran \(\phi\) bernilai \(v\text{.}\) Kita menyebut \(\phi\) sebagai aliran saat ini dan mencari cara untuk menambah \(\phi\) dengan melakukan relatif sedikit perubahan. Sisi \((x,y)\) dengan \(\phi(x,y)>0\) disebut terpakai, dan jika \(\phi(x,y)=c(x,y)>0\text{,}\) sisi itu disebut penuh. Jika \(\phi(x,y)\lt c(x,y)\text{,}\) sisi \((x,y)\) dikatakan mempunyai kapasitas sisa, dan jika \(0=\phi(x,y)\lt c(x,y)\text{,}\) sisi \((x,y)\) disebut kosong. Perhatikan bahwa kita mengabaikan saja sisi-sisi berkapasitas nol.
Alat utama untuk mengubah aliran jaringan ialah suatu jenis lintasan khusus yang tidak harus berupa lintasan berarah. Lintasan penambah adalah barisan \(P=(x_0,x_1,\dots,x_m)\) dari simpul-simpul berbeda dalam jaringan sedemikian sehingga \(x_0=S\text{,}\)\(x_m=T\text{,}\) dan untuk setiap \(i=1,2,\dots,m\text{,}\) berlaku salah satu dari kondisi berikut:
Jika kondisi (Butir a) berlaku, sisi \((x_{i-1},x_i)\) lazim disebut sisi maju dari lintasan penambah \(P\text{.}\) Demikian pula, jika kondisi (Butir b) berlaku, sisi tak berarah \((x_{i-1},x_i)\) disebut sisi mundur, sebab lintasan bergerak dari \(x_{i-1}\) ke \(x_i\text{,}\) berlawanan dengan arah sisi tersebut.
Mari kita lihat kembali jaringan dan aliran pada Gambar 13.2. Barisan simpul \((S,F,A,T)\) memenuhi kriteria lintasan penambah, dan setiap sisi di dalamnya merupakan sisi maju. Perhatikan bahwa menaikkan aliran pada masing-masing sisi \((S,F)\text{,}\)\((F,A)\text{,}\) dan \((A,T)\) sebesar sebarang nilai positif \(\delta \leq 12\) akan meningkatkan nilai aliran sekaligus mempertahankan hukum kekekalan.
Jika contoh pertama langsung tampak sebagai lintasan penambah, mungkin tidak sejelas itu bahwa \((S,E,D,C,B,A,T)\) juga merupakan lintasan penambah. Semua sisinya merupakan sisi maju kecuali \((C,B)\text{,}\) sebab sisi berarah yang sebenarnya terdapat dalam jaringan adalah \((B,C)\text{.}\) Jangan khawatir jika belum jelas bagaimana lintasan ini dapat digunakan untuk meningkatkan nilai aliran dalam jaringan; itulah pokok bahasan kita berikutnya.
Untuk sementara, abaikan persoalan menemukan lintasan penambah. Mari kita lihat bagaimana lintasan tersebut dapat digunakan untuk mengubah aliran saat ini sehingga nilainya bertambah sebesar suatu \(\delta > 0\text{.}\) Untuk lintasan penambah \(P=(x_0,x_1,\dots,x_m)\text{,}\) pertama-tama tetapkan \(\delta_1\) sebagai bilangan positif yang didefinisikan oleh
\begin{equation*}
\delta_1 =\min\{c(x_{i-1},x_i)-\phi(x_{i-1},x_i):(x_{i-1},x_i)
\text{ sisi maju dari } P.\}
\end{equation*}
Besaran \(c(x_{i-1},x_i)-\phi(x_{i-1},x_i)\) tidak lain adalah kapasitas sisa pada sisi \((x_{i-1},x_i)\text{.}\) Jadi, \(\delta_1\) merupakan nilai terbesar yang dapat ditambahkan pada aliran di semua sisi maju dari \(P\text{.}\) Perhatikan bahwa sisi \((x_0,x_1)\) dan \((x_{m-1},x_m)\) selalu merupakan sisi maju, sehingga besaran positif\(\delta_1\) terdefinisi untuk setiap lintasan penambah.
Jika lintasan penambah \(P\) tidak mempunyai sisi mundur, tetapkan \(\delta= \delta_1\text{.}\) Namun, jika \(P\) mempunyai satu atau lebih sisi mundur, tetapkan
\begin{equation*}
\delta_2 =\min\{\phi(x_{i},x_{i-1}):(x_{i-1},x_i)
\text{ sisi mundur dari } P\}.
\end{equation*}
Karena setiap sisi mundur terpakai, \(\delta_2>0\) setiap kali kita perlu mendefinisikannya. Selanjutnya, tetapkan \(\delta=\min\{\delta_1,\delta_2\}\text{.}\)
Dalam kedua kasus, sekarang kita mempunyai bilangan positif \(\delta\) dan memperoleh pengamatan dasar berikut, yang diminta untuk Anda buktikan dalam Latihan 13.7.4.
Misalkan kita mempunyai lintasan penambah \(P=(x_0,x_1,\dots,x_m)\) dengan \(\delta>0\) yang dihitung seperti di atas. Ubah aliran \(\phi\) dengan mengubah nilainya pada sisi-sisi lintasan \(P\) sebesar \(+\delta\) atau \(-\delta\) menurut aturan berikut:
Naikkan aliran pada sisi-sisi maju dari \(P\text{.}\)
Aliran jaringan pada Gambar 13.2 mempunyai banyak lintasan penambah. Kita telah melihat dua di antaranya dalam Contoh 13.6, yang di bawah ini disebut \(P_1\) dan \(P_3\text{.}\) Pastikan Anda memahami mengapa setiap lintasan berikut merupakan lintasan penambah dan bagaimana nilai \(\delta\) ditentukan untuk masing-masing lintasan.
\(P_1=(S,F,A,T)\) dengan \(\delta= 12\text{.}\) Semua sisinya maju.
Subbagian13.3.1Waspada dalam Memilih Lintasan Penambah
Bob sudah sangat mahir menggunakan lintasan penambah untuk meningkatkan nilai aliran jaringan. Ia belum tahu benar cara menemukannya, tetapi ia dapat mengenali sesuatu yang berguna. Ia cenderung berpikir bahwa sebarang lintasan penambah pasti menguntungkan dalam upayanya mencari aliran bernilai maksimum. Carlos senang melihat antusiasme Bob terhadap aliran jaringan, tetapi mulai merasa perlu memperingatkannya tentang bahaya memakai sembarang lintasan penambah untuk memperbarui aliran. Mereka sepakat bahwa keadaan terbaik ialah ketika banyaknya pembaruan kecil dibandingkan dengan banyaknya simpul dalam jaringan, serta bahwa besar kapasitas sisi dan nilai aliran maksimum tidak seharusnya memengaruhi banyaknya pembaruan.
Bob mengatakan bahwa ia tidak melihat bagaimana kapasitas sisi dapat membuat jaringan dengan hanya sedikit simpul memerlukan banyak pembaruan. Carlos merasa sebuah contoh diperlukan. Ia meminta Bob memilih bilangan bulat sangat besar yang disukainya dan menamainya \(M\text{.}\) Kemudian ia menggambar jaringan empat simpul pada Gambar 13.9. Bob segera melihat bahwa nilai maksimum aliran dalam jaringan tersebut adalah \(2M\text{.}\) Ia memperolehnya dengan aliran yang memenuhi \(\phi(S,A)=M\text{,}\)\(\phi(A,T)=M\text{,}\)\(\phi(S,B)=M\text{,}\)\(\phi(B,T)=M\text{,}\) dan \(\phi(A,B)=0\text{.}\) Carlos senang dengan pekerjaan Bob.
Karena jaringan ini sangat kecil, Bob mudah menemukan aliran maksimumnya. Namun, Bob dan Carlos sepakat bahwa sekadar “menaksir dengan mata” tidak akan bekerja dengan baik pada jaringan yang lebih besar. Karena itu, mereka memerlukan cara menemukan aliran tersebut dengan lintasan penambah. Bob meminta Carlos memberikan sebuah lintasan penambah dan ia sendiri yang akan melakukan pembaruannya. Carlos menyarankan lintasan penambah \((S,A,B,T)\text{,}\) dan Bob menentukan bahwa \(\delta=1\) untuk lintasan ini. Ia memperbarui jaringan mulai dari aliran nol, i.e., dengan \(\phi(e)=0\) untuk setiap sisi \(e\text{,}\) sehingga alirannya kini bernilai \(1\text{.}\) Bob meminta lintasan penambah lain, lalu Carlos memberinya \((S,B,A,T)\text{.}\) Sekarang \((B,A)\) merupakan sisi mundur, tetapi hal itu tidak membuat Bob gentar. Ia melakukan pembaruan dan memperoleh aliran bernilai \(2\text{,}\) dengan \((A,B)\) kembali kosong.
Meskipun Carlos berharap Bob sudah melihat arah persoalannya, Bob dengan bersemangat meminta lintasan penambah lain. Carlos segera memberinya \((S,A,B,T)\text{,}\) yang lagi-lagi mempunyai \(\delta=1\text{.}\) Pembaruan Bob menghasilkan aliran bernilai \(3\text{.}\) Sebelum Carlos sempat menyarankan lintasan lain, Bob menyadari masalahnya. Ia menunjukkan bahwa Carlos dapat memberinya \((S,B,A,T)\) lagi; lintasan itu tetap mempunyai \(\delta=1\) dan akan menaikkan nilai aliran menjadi \(4\text{.}\) Mereka dapat terus bergantian memakai kedua lintasan tersebut dan menaikkan nilai aliran sebesar \(1\) setiap kali, hingga melakukan \(2M\) pembaruan untuk akhirnya memperoleh aliran bernilai \(2M\text{.}\) Karena jaringan itu hanya mempunyai empat simpul dan \(M\) sangat besar, Bob menyadari bahwa memakai sembarang lintasan penambah jelas bukan gagasan yang baik.
Carlos membiarkan Bob mencari pendekatan yang lebih baik. Bob menyadari bahwa jika dimulai dari aliran nol, ia hanya memerlukan lintasan penambah \((S,A,T)\) dan \((S,B,T)\text{,}\) masing-masing dengan \(\delta=M\text{,}\) untuk segera memperoleh aliran maksimum. Namun, ia belum tahu mengapa suatu algoritma seharusnya lebih memilih kedua lintasan tersebut. Saat itu Dave kebetulan lewat dan bergumam bahwa lintasan penambah yang lebih baik hanya menggunakan dua sisi, sedangkan dua lintasan buruk Carlos masing-masing menggunakan tiga sisi. Bob merasa Dave mungkin menemukan petunjuk, sehingga ia kembali membaca buku teksnya.
