Subbab 13.5 Contoh Konkret

Mari kita terapkan Algoritma Pelabelan pada aliran jaringan dalam Gambar 13.2. Kita mulai dari sumber:

Karena sumber \(S\) merupakan simpul pertama yang diberi label, simpul itu juga yang pertama dipindai. Jadi, kita meninjau tetangga-tetangga \(S\) menurut urutan pseudoalfabetis pada simpul. Simpul pertama yang ditinjau adalah \(B\text{.}\) Karena sisi \((S,B)\) tidak penuh, kita memberi \(B\) label

Selanjutnya, kita meninjau simpul \(E\) dan memberinya label

Berikutnya adalah simpul \(F\text{,}\) yang diberi label

Pada tahap ini, pemindaian dari \(S\) selesai.

Simpul pertama setelah \(S\) yang diberi label adalah \(B\text{,}\) sehingga sekarang kita memindai dari \(B\text{.}\) Tetangga-tetangga tak berlabel dari \(B\) yang ditinjau secara berurutan adalah \(A\text{,}\) \(C\text{,}\) dan \(D\text{.}\) Hasilnya adalah label-label berikut:

Simpul berikutnya yang dipindai adalah \(E\text{,}\) tetapi \(E\) tidak mempunyai tetangga tak berlabel. Karena itu, kita beralih ke \(F\text{,}\) yang juga tidak mempunyai tetangga tak berlabel. Terakhir, kita memindai dari \(A\text{.}\) Menurut urutan pseudoalfabetis, mula-mula kita meninjau muara \(T\text{,}\) yang dalam kasus ini merupakan satu-satunya simpul tak berlabel yang tersisa. Hasilnya adalah label berikut bagi \(T\text{:}\)

Karena muara sekarang berlabel, kita mengetahui bahwa terdapat lintasan penambah. Lintasan ini ditemukan dengan menelusuri label secara mundur. Muara \(T\) memperoleh labelnya dari \(A\text{,}\) \(A\) dari \(B\text{,}\) dan \(B\) dari \(S\text{.}\) Jadi, lintasan penambahnya adalah \(P=(S,B,A,T)\) dengan \(\delta=8\text{.}\) Semua sisi pada lintasan ini maju. Selanjutnya, aliran diperbarui dengan menaikkan aliran pada sisi-sisi \(P\) sebesar \(8\text{.}\) Hasilnya adalah aliran pada Gambar 13.12, yang bernilai \(38\text{.}\)

Berikut adalah urutan label yang ditemukan ketika algoritma pelabelan diterapkan pada aliran yang telah diperbarui; bacalah ke bawah setiap kolom. Perhatikan bahwa pada pemindaian dari \(S\text{,}\) simpul \(B\) tidak akan diberi label karena sisi \((S,B)\) sekarang penuh.

Pelabelan ini menghasilkan lintasan penambah \(P=(S,F,A,T)\) dengan \(\delta=12\text{.}\)