Combinatorics (Fall 2010)/Flow and matching: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Flow == === Maximum Flow Problem === An instance of the maximum flow problem consists of: * a directed graph <math>G(V,E)</math>; * two distinguished vertices <math>s</math> …'
 
imported>WikiSysop
Line 1: Line 1:
== Flow ==
== Flow ==


=== Maximum Flow Problem ===
=== The maximum flow problem ===
An instance of the maximum flow problem consists of:
An instance of the maximum flow problem consists of:
* a directed graph <math>G(V,E)</math>;
* a directed graph <math>G(V,E)</math>;
Line 14: Line 14:


The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>. Given a flow network, the maximum flow problem asks to find the flow of the maximum value.
The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>. Given a flow network, the maximum flow problem asks to find the flow of the maximum value.
=== Cuts ===
=== The augmenting paths ===
=== The max-flow min-cut theorem ===
== Unimodularity ==
=== Integrality of polytopes ===
=== Unimodularity and total unimodularity ===

Revision as of 09:31, 18 December 2010

Flow

The maximum flow problem

An instance of the maximum flow problem consists of:

  • a directed graph [math]\displaystyle{ G(V,E) }[/math];
  • two distinguished vertices [math]\displaystyle{ s }[/math] (the source) and [math]\displaystyle{ t }[/math] (the sink), where the in-degree of [math]\displaystyle{ s }[/math] and the out-degree of [math]\displaystyle{ t }[/math] are both 0;
  • the capacity function [math]\displaystyle{ c:E\rightarrow\mathbb{R}^+ }[/math] which associates each directed edge [math]\displaystyle{ (u,v)\in E }[/math] a nonnegative real number [math]\displaystyle{ c_{uv} }[/math] called the capacity of the edge.

The quadruple [math]\displaystyle{ (G,c,s,t) }[/math] is called a flow network.

A function [math]\displaystyle{ f:E\rightarrow\mathbb{R}^+ }[/math] is called a flow (or an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow) in the network [math]\displaystyle{ G(V,E) }[/math] if it satisfies:

  • Capacity constraint: [math]\displaystyle{ f_{uv}\le c_{uv} }[/math] for all [math]\displaystyle{ (u,v)\in E }[/math].
  • Conservation constraint: [math]\displaystyle{ \sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw} }[/math] for all [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].

The value of the flow [math]\displaystyle{ f }[/math] is [math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv} }[/math]. Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

Cuts

The augmenting paths

The max-flow min-cut theorem

Unimodularity

Integrality of polytopes

Unimodularity and total unimodularity