View again

# O Autima i Slicno | Theoretical Computer Science | Physics & Mathematics

26 views
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

## Mathematical Analysis

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

### binart tree | Areas Of Computer Science | Theoretical Computer Science

View more... 