of 33

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