| dbo:abstract
|
- Ford és Fulkerson maximális folyam-minimális vágás tétele (angolul: max-flow-min-cut theorem), más néven a Ford–Fulkerson tétel azt mondja ki, hogy egy irányított gráfban a maximális folyam nagysága egyenlő a minimális vágás méretével. Legyen D=(V,A) irányított gráf, s,t két kijelölt pont D-ben. Legyen adva a g kapacitásfüggvény D élein. A megengedett folyamok nagysága egyenlő az S halmaz összes kiáramlásának minimumára, ahol a az összes olyan S halmazra megy, ami tartalmazza s-t, de t-t nem. Ha még az is teljesül, hogy g egész, akkor a maximális folyam is választható egész értékűnek. (hu)
- Ford és Fulkerson maximális folyam-minimális vágás tétele (angolul: max-flow-min-cut theorem), más néven a Ford–Fulkerson tétel azt mondja ki, hogy egy irányított gráfban a maximális folyam nagysága egyenlő a minimális vágás méretével. Legyen D=(V,A) irányított gráf, s,t két kijelölt pont D-ben. Legyen adva a g kapacitásfüggvény D élein. A megengedett folyamok nagysága egyenlő az S halmaz összes kiáramlásának minimumára, ahol a az összes olyan S halmazra megy, ami tartalmazza s-t, de t-t nem. Ha még az is teljesül, hogy g egész, akkor a maximális folyam is választható egész értékűnek. (hu)
|
