All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

nesto o autima i slicno

Tags

Transcript

MAXIMUM FLOW
Max-Flow Min-
Cut Theorem (Ford Fukerson’s Algorithm)
What is Network Flow ?
Flow network is a directed graph G=(V,E) such that each edge has a non-negative capacity c(u,v)
≥0.
Two distinguished vertices exist in G namely :
ã
Source (denoted by s) : In-degree of this vertex is 0.
ã
Sink (denoted by t) : Out-degree of this vertex is 0. Flow in a network is an integer-valued function f defined On the edges of G satisfying 0
≤f(u,v)≤c(u,v), for every
Edge (u,v) in E.
What is Network Flow ?
ã
Each edge (u,v) has a non-negative capacity c(u,v).
ã
If (u,v) is not in E assume c(u,v)=0.
ã
We have source s and sink t.
ã
Assume that every vertex v in V is on some path from s to t. Following is an illustration of a network flow: c(s,v1)=16 c(v1,s)=0
c(v2,s)=0 …
Conditions for Network Flow
For each edge (u,v) in E, the flow f(u,v) is a real valued function that must satisfy following 3 conditions :
ã
Skew Symmetry : u,v
V, f(u,v)= -f(v,u)
ã
Capacity Constraint :
u,v
V, f(u,v)
c(u,v)
ã
Flow Conservation: u
V
–
{s,t}
f(s,v)=0
v
V
Skew symmetry condition implies that f(u,u)=0.

Related Search

Related Docs

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks