Az oldal tölt...

Keresés

Legújabb cikkek

Támogató

Fazekas

Szabványok

Valid XHTML 1.0 Strict

Valid CSS!

Szerkesztő
Kategória: Megoldás - Feladat Évfolyam: 9.
Kulcsszó: Irányított gráfok Lektorálás: Nem lektorált

A Ford-Fulkerson-probléma

Megoldás

Kiválasztunk egy tetszőleges utat a fúrótoronyból az olajfinomítóig. Az úton szereplő legkisebb számot kivonjuk az útban szereplő élekből, és az eredetihez hasonló gráfban (eredetileg itt mindegyik élre 0-t írunk) ezeket a számokat hozzáadom.
Az algoritmust addig csinálom, ameddig létezik út a fúrótoronyból az olajfinomítóba. A második, általunk létrehozott gráf megadja a feladat megoldását.
A gráfot egy vonallal elvágom. Megnézem, hogy az elvágott vezetékeken keresztül mennyi olaj folyik. Ennél több nem mehet az olajfinomítóba. Ezek közül megkeresem a legkevesebbet. A következő algoritmus erre ad példát.
Főgombok VisszaElőreFrissítHibát találtál? Jelentsd!NyomtatMutat