Grafik Residual dalam Aliran Maksimum

Saya membaca tentang Masalah Aliran Maksimum di sini . Saya tidak dapat memahami intuisi di balik Grafik Residual. Mengapa kita mempertimbangkan tepi belakang saat menghitung aliran?

Adakah yang bisa membantu saya memahami konsep Grafik Sisa?

Bagaimana perubahan Algoritma pada Grafik Tidak Terarah?

Intuisi mengenai grafik residual dalam masalah aliran Maksimum disajikan dengan sangat baik dalam kuliah ini . Penjelasannya sebagai berikut.

Misalkan kita mencoba untuk memecahkan masalah aliran maksimum untuk jaringan berikut (di mana setiap label f e / c e Menandakan kedua aliran f e didorong melalui keunggulan e dan kapasitas c e dari tepi ini):$G$$f_e/c_e$$f_e$$e$$c_e$

Salah satu pendekatan serakah yang mungkin adalah sebagai berikut:

1. Pilih jalur augmentasi yang berubah-ubah yang bergerak dari titik sumber s ke titik puncak t sehingga ∀ $P$$s$$t$ ); yaitu semua tepi dalam P memiliki kapasitas yang tersedia.$\forall e \: (e \in P \rightarrow f_e \lt c_e$$P$
2. Dorong aliran maksimum yang dimungkinkan melalui jalur ini. Nilai Δ ditentukan oleh bottleneck dari P ; yaitu tepi dengan kapasitas minimum yang tersedia. Secara formal, Δ = min e ∈ P ( c e - f e ) .$\Delta$$\Delta$$P$$\Delta=\min_{e \in P} (c_e-f_e)$
3. Lanjutkan ke langkah 1 hingga tidak ada jalur penambahan.

Yaitu, temukan jalur dengan kapasitas yang tersedia, kirim aliran di sepanjang jalur itu, dan ulangi.

Dalam , salah satu eksekusi mungkin di atas penemuan heuristik tiga jalur augmenting P 1 , P 2 , dan P 3 , dalam urutan ini. Jalur ini masing-masing mendorong 2, 2, dan 1 unit aliran, untuk total aliran 5:$G$$P_1$$P_2$$P_3$

Memilih jalur dalam urutan ini mengarah ke solusi optimal; Namun, apa yang terjadi jika kita memilih pertama (yaitu, sebelum P 1 dan P 2 )?$P_3$$P_1$$P_2$

Kami mendapatkan apa yang disebut aliran pemblokiran : tidak ada lagi jalur tambahan. Dalam hal ini, total aliran adalah 3, yang tidak optimal. Masalah ini dapat diatasi dengan mengizinkan operasi undo (yaitu, dengan memungkinkan aliran dikirim secara terbalik, membatalkan pekerjaan iterasi sebelumnya): cukup tekan 2 unit aliran mundur dari titik ke titik v seperti ini:$w$$v$

Pengkodean operasi pembatalan yang diizinkan ini adalah tujuan utama dari grafik residual .

Grafik residual dari jaringan G memiliki set simpul yang sama dengan G dan termasuk, untuk setiap sisi e = ( u , v ) ∈ G :$R$$G$$G$$e=(u,v) \in G$

• Tepi maju dengan kapasitas c e - f e , jika c e - f e > 0 .$e'=(u,v)$$c_e-f_e$$c_e-f_e \gt 0$

• Tepi mundur dengan kapasitas f e , jika f e > 0 .$e''=(v,u)$$f_e$$f_e \gt 0$

Sebagai contoh, perhatikan sisa grafik yang diperoleh setelah iterasi pertama dari heuristik serakah ketika menyeleksi heuristik P 3 pertama (yaitu, ketika mendapat aliran pemblokiran):$R$$P_3$

Perhatikan bahwa operasi undo yang mendorong 2 unit aliran dari ke v dikodekan sebagai jalur maju (penambahan) dari s ke t di R :$w$$v$$s$$t$$R$

Secara umum:

Ketika jalur augmentasi dipilih dalam grafik residual R :$P'$$R$

• Setiap tepi dalam yang sesuai dengan tepi ke depan dalam G meningkatkan aliran dengan menggunakan tepi dengan kapasitas yang tersedia.$P'$$G$
• Setiap sisi dalam yang berhubungan dengan sisi yang mundur dalam G membatalkan aliran yang didorong ke arah maju di masa lalu.$P'$$G$

Ini adalah ide utama di balik metode Ford-Fulkerson .

Metode Ford – Fulkerson berproses dengan cara yang persis sama dengan pendekatan serakah yang dijelaskan di atas, tetapi hanya berhenti ketika tidak ada lagi jalur tambahan dalam grafik residual (bukan di jaringan asli). Metode ini benar (yaitu, ia selalu menghitung aliran maksimum) karena grafik residual menetapkan kondisi optimalitas berikut :

$G$$f$$G$$s-t$

$A$$B$$B$$A$$A$$B$