Dalam bagian ini, kita menguraikan algoritma pelabelan klasik Ford–Fulkerson untuk menemukan aliran maksimum dalam suatu jaringan. Algoritma ini dimulai dengan urutan linear pada himpunan simpul yang menetapkan suatu konsep prioritas. Biasanya, simpul pertama dalam urutan linear ini adalah sumber dan simpul kedua adalah muara. Setelah itu, simpul-simpul lain dapat dicantumkan dalam urutan apa pun. Dalam buku ini, kita menggunakan konvensi berikut: simpul-simpul diberi label dengan huruf kapital alfabet Inggris dan urutan linearnya adalah \((S,T,A,B,C,D,E,F,G,\dots)\text{,}\) yang akan kita sebut urutan pseudoalfabetis. Tentu saja, konvensi ini hanya berlaku bagi jaringan dengan paling banyak \(26\) simpul, tetapi batasan tersebut tidak akan menjadi kendala. Untuk masalah dunia nyata, komputer dapat menangani kunci bilangan bulat dengan hampir sebarang ukuran dengan mudah.
Sebelum memberikan uraian algoritma secara tepat, mari kita tinjau gambaran umumnya. Ketika menjalankan algoritma pelabelan, simpul-simpul diklasifikasikan sebagai berlabel atau tak berlabel. Mula-mula, hanya sumber yang diberi label, sedangkan semua simpul lain tidak berlabel. Menurut kriteria yang akan dijelaskan, kita secara sistematis meninjau simpul-simpul tak berlabel dan menentukan mana yang perlu diberi label. Jika muara berhasil diberi label, berarti kita telah menemukan lintasan penambah dan alirannya akan diperbarui dengan tepat. Setelah memperbarui aliran, kita memulai lagi dengan hanya sumber yang berlabel.
Proses ini diulangi hingga (dan akan kita lihat bahwa hal ini selalu terjadi) pelabelan berhenti dengan sebagian simpul berlabel, termasuk sumber, dan sebagian lainnya tak berlabel, termasuk muara. Kemudian kita akan melihat bahwa partisi \(V= L\cup U\) menjadi simpul-simpul berlabel dan tak berlabel (yang menjelaskan pilihan nama \(L\) dan \(U\)) merupakan potongan yang kapasitasnya tepat sama dengan nilai aliran saat ini. Hasil ini menyelesaikan perdebatan sebelumnya dalam bab ini: persoalan aliran maksimum dan potongan minimum lebih menyerupai antirantai dan partisi menjadi rantai daripada bilangan klik dan bilangan kromatik. Secara khusus, algoritma pelabelan akan memberikan bukti bagi teorema berikut.
Teorema13.10.Teorema Aliran Maksimum–Potongan Minimum.
Misalkan \(G=(V,E)\) suatu jaringan. Jika \(v_0\) adalah nilai maksimum suatu aliran dan \(c_0\) adalah kapasitas minimum suatu potongan, maka kapasitas tersebut, \(c_0\text{,}\) sama dengan nilai aliran maksimum: \(v_0=c_0\text{.}\)
Simpul-simpul diberi label berupa tripel simbol terurut. Setiap kali memulai proses pelabelan, kita terlebih dahulu memberi sumber label \((*,+,\infty)\text{.}\) Aturan pemberian label pada simpul akan dinyatakan secara eksplisit.
Misalkan \(u\) suatu simpul berlabel. Koordinat ketiga pada label \(u\) merupakan besaran positif—dan boleh bernilai tak hingga. Besaran ini disebut potensial pada \(u\) dan dinotasikan dengan \(p(u)\text{.}\) Potensial ini menyatakan besar pembaruan yang dapat dilakukan pada aliran. Perhatikan bahwa potensial pada sumber adalah tak hingga.
Algoritma pelabelan melibatkan pemindaian dari suatu simpul berlabel\(u\text{.}\) Urutan pemberian label pada simpul-simpul menentukan urutan linear lain. Sumber selalu menjadi simpul pertama dalam urutan ini. Setelah itu, urutan pelabelan simpul akan berubah dari waktu ke waktu. Aturan pentingnya ialah bahwa kita memindai simpul menurut urutan pemberian label—hingga muara diberi label. Sebagai contoh, jika pemindaian awal—yang selalu dilakukan dari sumber—memberi label pada simpul \(D\text{,}\)\(G\text{,}\) dan \(M\text{,}\) selanjutnya kita memindai dari simpul \(D\text{.}\) Jika pemindaian itu memberi label pada simpul \(B\text{,}\)\(F\text{,}\) dan \(Q\text{,}\) selanjutnya kita memindai dari \(G\text{,}\) sebab simpul itu diberi label sebelum \(B\text{,}\) walaupun \(B\) mendahului \(G\) dalam urutan pseudoalfabetis. Aspek algoritma ini menghasilkan pencarian melebar pada simpul-simpul untuk mencari cara memberi label pada simpul yang sebelumnya tak berlabel.
Setelah suatu simpul diberi label, kita tidak mengubah labelnya. Kita hanya memberi label pada simpul-simpul yang sebelumnya tak berlabel—sampai muara berhasil diberi label. Setelah aliran diperbarui dan nilainya meningkat, semua label dibuang, kecuali tentu saja label khusus pada sumber, lalu proses dimulai kembali.
Misalkan kita memindai dari simpul berlabel \(u\) yang mempunyai potensial \(p(u)>0\text{.}\) Dari \(u\text{,}\) kita meninjau tetangga-tetangga tak berlabel dari \(u\) menurut urutan pseudoalfabetis. Misalkan kita sedang meninjau tetangga \(v\) dari \(u\) dan sisi \((u,v)\) berada dalam jaringan. Artinya, sisi itu berarah dari \(u\) ke \(v\text{.}\) Jika \(e=(u,v)\) tidak penuh, beri simpul \(v\) label \((u,+,p(v))\text{,}\) dengan \(p(v)=\min\{p(u),c(e)-\phi(e)\}\text{.}\) Definisi ini digunakan karena aliran tidak dapat dinaikkan melebihi potensial sebelumnya maupun kapasitas sisa pada \(e\text{.}\) Perhatikan bahwa potensial \(p(v)\) positif karena \(p(v)\) merupakan nilai minimum dari dua bilangan positif.
Sekarang misalkan kita sedang meninjau tetangga \(v\) dari \(u\) dan sisi \((v,u)\) berada dalam jaringan. Artinya, sisi itu berarah dari \(v\) ke \(u\text{.}\) Jika \(e=(v,u)\) terpakai, beri simpul \(v\) label \((u,-,p(v))\text{,}\) dengan \(p(v)=\min\{p(u),\phi(e)\}\text{.}\) Potensial \(p(v)\) didefinisikan demikian karena aliran pada \(e\) tidak dapat diturunkan lebih dari \(\phi(e)\) maupun \(p(u)\text{.}\) Sekali lagi, potensial \(p(v)\) positif karena \(p(v)\) merupakan nilai minimum dari dua bilangan positif.
Algoritma pelabelan berhenti jika muara diberi label. Perhatikan bahwa kita selalu berusaha memberi label pada muara, sebab pada setiap pemindaian muara adalah simpul pertama yang ditinjau. Misalkan muara diberi label \((u,+,a)\text{.}\) Koordinat kedua pada label tersebut haruslah \(+\text{,}\) sebab semua sisi yang bersisian dengan muara berarah menuju muara.
Kita mengklaim bahwa dapat ditemukan lintasan penambah \(P\) yang meningkatkan aliran dengan \(\delta=a\text{,}\) yaitu potensial pada muara. Untuk melihatnya, kita cukup menelusuri label secara mundur. Muara \(T\) memperoleh labelnya dari \(u=u_1\text{,}\)\(u_1\) memperoleh labelnya dari \(u_2\text{,}\) dan seterusnya. Pada akhirnya, kita menemukan simpul \(u_m\) yang memperoleh labelnya dari sumber. Lintasan penambahnya adalah
Nilai \(\delta\) bagi lintasan ini adalah potensial \(p(T)\) pada muara, sebab kita telah memastikan bahwa \(p(u_m)\geq p(u_{m-1})\geq\cdots\geq p(u_1)\geq p(T)\text{.}\)
Sebaliknya, misalkan kita telah memindai dari setiap simpul berlabel, tetapi masih ada simpul tak berlabel, salah satunya adalah muara. Pada saat ini kita dapat menyatakan kemenangan. Jika \(L\) adalah himpunan simpul berlabel dan \(U\) adalah himpunan simpul tak berlabel, setiap sisi \(e=(x,y)\) dengan \(x\in L\) dan \(y\in U\) pasti penuh, i.e., \(\phi(e)=c(e)\text{.}\) Jika tidak, \(y\) memenuhi syarat untuk memperoleh label dengan \(x\) sebagai koordinat pertama. Perhatikan pula bahwa \(\phi(y,x)=0\) untuk setiap sisi \(e\) yang berarah dari U ke L, dengan \(x\in L\) dan \(y\in U\text{.}\) Dengan demikian, kapasitas potongan \(V=L\cup U\) tepat sama dengan nilai aliran saat ini. Jadi, kita memperoleh sekaligus aliran maksimum dan potongan minimum yang memberikan sertifikat keoptimalan.
