Ford-Fulkersonin lause

Ford - Fulkersonin lause on graafin maksimivirtauslause , joka liittyy läheisesti Mengerin lauseeseen .

Se kuulostaa tältä: maksimivirtauksen arvo polkukaaviossa on yhtä suuri kuin sen minimileikkauksen läpijuoksun arvo .

Riittävyys: mikä tahansa virtauspisteiden t ja s välillä on pienempi tai yhtä suuri kuin minkä tahansa leikkauksen arvo . Antaa jonkin verran virtausta ja osia. Tämän virtauksen arvo on "lastin" arvojen summa, joka kuljetetaan kaikkia mahdollisia polkuja pitkin kärjestä t pisteeseen s . Jokaisella tällaisella polulla on oltava yhteinen reuna tietyn osan kanssa. Koska osan kullekin reunalle on mahdotonta siirtää "kuormaa" enemmän kuin sen kantokyky, kaikkien kuormien summa on pienempi tai yhtä suuri kuin tämän osan reunojen kaikkien kantokykyjen summa. Väite on todistettu.

Tästä seuraa, että mikä tahansa virtaus on pienempi tai yhtä suuri kuin minimiosan arvo, ja näin ollen maksimivirtaus on pienempi tai yhtä suuri kuin minimiosan arvo.

Ford - Fulkerson-algoritmi graafin maksimivirtauksen löytämiseksi perustuu tähän lauseeseen, se on myös todiste tämän lauseen välttämättömyydestä, eli se on konstruktiivinen.

Toinen todiste (vahvistuksen kautta)

Vahvistakaamme Ford-Fulkersonin lausetta seuraavasti. Verkolle, jolla on virtaus f, todistamme seuraavan kolmen tosiasian vastaavuuden kerralla: $G(V,E)$

1° Virtaus f maksimi

2° Minimileikkauksen kapasiteetti on yhtä suuri kuin virtauksen f arvo

3° Kuvaajassa ei ole täydentävää polkua $G$

1° → 3°. Olettaen päinvastoin saamme ristiriidan, joka on kuvattu kuljetusgraafin komplementtipolun tiedoissa .

3° → 2°. On selvää, että virtauksen f arvo ei ylitä minimileikkauksen kapasiteettia . Anna . Harkitse sitten leikkausta, jossa joukko sisältää kaikki kärjet paitsi . Silloin sen läpijuoksu ei ole pienempi kuin minimileikkauksen läpimeno, joka puolestaan on suurempi kuin virtauksen f arvo. Näin ollen on suunta kohteesta kohteeseen , sellainen, että . Otetaan nyt kaikki nämä ja siirretään ne osoitteeseen . Ottaen huomioon tuloksena olevan leikkauksen, huomaamme, että sen läpijuoksu on myös suurempi kuin virtausarvo. Suurennamme joukkoa uudelleen ja teemme niin, kunnes joukossa on vain kärkipiste . Se on myös ensimmäinen huippu tiellä, jota olemme luomassa. Nyt katsomme, minkä parin valitsimme viimeksi. Olkoon se pari . Sitten lisäämme polkuun kärkipisteen . Seuraavaksi katsotaan parista, minkä kärjen kanssa kärkipiste oli alun perin . Anna sen . Sitten edelleen polulle lisäämme kärkipisteen . Teemme tätä kunnes saavutamme huipulle . Rakenteen mukaan tämä polku on kuitenkin jäännös, mikä on ristiriidassa oletuksen kanssa. $(S,T)$ $c(S,T)>f$ $S$ $t$ $(u,t)$ $S$ $T$ $f(u,t)<c(u,t)$ $u$ $T$ $T$ $S$ $s$ $(s,u)$ $u$ $u$ $(u,v)$ $v$ $t$

2° → 1°. Kuten jo mainittiin, on selvää, että minkään virtauksen arvo ei ylitä minimileikkauksen läpimenokykyä ja virtauksen arvo on sama. Tällöin virtauksen arvo ei ole pienempi kuin minkä tahansa muun virtauksen arvo verkossamme, eli virtaus on maksimi. $f$ $f$ $f$

Tämä todiste on hyvä, koska se ei käytä monimutkaista algoritmia maksimivirran löytämiseen mielivaltaisessa siirtoverkossa.

Esimerkki

Oikealla on verkko, jossa on 6 kärkeä , ja kokonaisvirtaus lähteestä viemäriin on 5. Tämä virtaus on tämän verkon enimmäismäärä. $V = \{s,o,p,q,r,t\}$ $s$ $t$

Tässä verkossa 2 minimileikkausta on mahdollista:

Viilto	Virtaus
$S=\{s,o,p\},T=\{q,r,t\}$	$c(o,q)+c(p,r)=3+2=5$
$S=\{s,o,p,q,r\},T=\{t\}$	$c(q,t)+c(r,t)=2+3=5$

Kirjallisuus

Novikov F. A. Diskreetti matematiikka ohjelmoijille . - 3. - Pietari. : Peter , 2009. - S. 277 -279. — 384 s. - ISBN 978-5-91180-759-7 .

Linkit

Ford-Fulkerson-algoritmi osoitteessa algolist.manual.ru.
Verkot, virtaukset verkoissa. Ford-Fulkersonin lause Mini-Soft.ru:ssa