组合数学 (Fall 2011)/Flow and matching: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
No edit summary
Line 183: Line 183:


The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.
The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.
== Algorithms ==
=== The Hungarian algorithm ===
=== The Ford-Fulkerson algorithm ===
=== The Hopcroft-Karp Algorithm ===

Revision as of 03:52, 17 August 2011

Flow and Cut

Flows

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 (to be specific 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.

The maximum flow problem can be described as the following linear program.

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\ \begin{align} \text{subject to} \\ \\ \\ \\ \end{align} \quad & \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\ \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\ f_{uv}&\ge 0 &\quad& \forall (u,v)\in E \end{align} \end{align} }[/math]

Cuts

Definition
Let [math]\displaystyle{ (G(V,E),c,s,t) }[/math] be a flow network. Let [math]\displaystyle{ S\subset V }[/math]. We call [math]\displaystyle{ (S,\bar{S}) }[/math] an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut if [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\not\in S }[/math].
The value of the cut (also called the capacity of the cut) is defined as [math]\displaystyle{ \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math].

A fundamental fact in flow theory is that cuts always upper bound flows.

Lemma
Let [math]\displaystyle{ (G(V,E),c,s,t) }[/math] be a flow network. Let [math]\displaystyle{ f }[/math] be an arbitrary flow in [math]\displaystyle{ G }[/math], and let [math]\displaystyle{ (S,\bar{S}) }[/math] be an arbitrary [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut. Then
[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math],
that is, the value of any flow is no greater than the value of any cut.
Proof.
By the definition of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\not\in S }[/math].

Due to the conservation of flow,

[math]\displaystyle{ \sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,. }[/math]

On the other hand, summing flow over edges,

[math]\displaystyle{ \sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,. }[/math]

Therefore,

[math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,, }[/math]
[math]\displaystyle{ \square }[/math]

Augmenting paths

Definition (Augmenting path)
Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. An augmenting path to [math]\displaystyle{ u_k }[/math] is a sequence of distinct vertices [math]\displaystyle{ P=(u_0,u_1,\cdots, u_k) }[/math], such that
  • [math]\displaystyle{ u_0=s\, }[/math];
and each pair of consecutive vertices [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] in [math]\displaystyle{ P }[/math] corresponds to either a forward edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] or a reverse edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math], and
  • [math]\displaystyle{ f(u_i,u_{i+1})\lt c(u_i,u_{i+1})\, }[/math] when [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] corresponds to a forward edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math], and
  • [math]\displaystyle{ f(u_{i+1},u_i)\gt 0\, }[/math] when [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] corresponds to a reverse edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math].
If [math]\displaystyle{ u_k=t\, }[/math], we simply call [math]\displaystyle{ P }[/math] an augmenting path.

Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. Suppose there is an augmenting path [math]\displaystyle{ P=u_0u_1\cdots u_k }[/math], where [math]\displaystyle{ u_0=s }[/math] and [math]\displaystyle{ u_k=t }[/math]. Let [math]\displaystyle{ \epsilon\gt 0 }[/math] be a positive constant satisfying

  • [math]\displaystyle{ \epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1}) }[/math] for all forward edges [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] in [math]\displaystyle{ P }[/math];
  • [math]\displaystyle{ \epsilon \le f(u_{i+1},u_i) }[/math] for all reverse edges [math]\displaystyle{ (u_{i+1},u_i)\in E }[/math] in [math]\displaystyle{ P }[/math].

Due to the definition of augmenting path, we can always find such a positive [math]\displaystyle{ \epsilon }[/math].

Increase [math]\displaystyle{ f(u_i,u_{i+1}) }[/math] by [math]\displaystyle{ \epsilon }[/math] for all forward edges [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] in [math]\displaystyle{ P }[/math] and decrease [math]\displaystyle{ f(u_{i+1},u_i) }[/math] by [math]\displaystyle{ \epsilon }[/math] for all reverse edges [math]\displaystyle{ (u_{i+1},u_i)\in E }[/math] in [math]\displaystyle{ P }[/math]. Denote the modified flow by [math]\displaystyle{ f' }[/math]. It can be verified that [math]\displaystyle{ f' }[/math] satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow [math]\displaystyle{ f' }[/math]

[math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}\gt \sum_{v:(s,v)\in E}f_{sv} }[/math].

Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

Lemma
A flow [math]\displaystyle{ f }[/math] is maximum if and only if there are no augmenting paths.
Proof.
We have already proved the "only if" direction above. Now we prove the "if" direction.

Let [math]\displaystyle{ S=\{u\in V\mid \exists\text{an augmenting path to }u\} }[/math]. Clearly [math]\displaystyle{ s\in S }[/math], and since there is no augmenting path [math]\displaystyle{ t\not\in S }[/math]. Therefore, [math]\displaystyle{ (S,\bar{S}) }[/math] defines an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.

We claim that

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math],

that is, the value of flow [math]\displaystyle{ f }[/math] approach the value of the cut [math]\displaystyle{ (S,\bar{S}) }[/math] defined above. By the above lemma, this will imply that the current flow [math]\displaystyle{ f }[/math] is maximum.

To prove this claim, we first observe that

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} }[/math].

This identity is implied by the flow conservation constraint, and holds for any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut [math]\displaystyle{ (S,\bar{S}) }[/math].

We then claim that

  • [math]\displaystyle{ f_{uv}=c_{uv} }[/math] for all [math]\displaystyle{ u\in S,v\not\in S, (u,v)\in E }[/math]; and
  • [math]\displaystyle{ f_{vu}=0 }[/math] for all [math]\displaystyle{ u\in S,v\not\in S, (v,u)\in E }[/math].

If otherwise, then the augmenting path to [math]\displaystyle{ u }[/math] apending [math]\displaystyle{ uv }[/math] becomes a new augmenting path to [math]\displaystyle{ v }[/math], which contradicts that [math]\displaystyle{ S }[/math] includes all vertices to which there exist augmenting paths.

Therefore,

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math].

As discussed above, this proves the theorem.

[math]\displaystyle{ \square }[/math]

Max-Flow Min-Cut

The max-flow min-cut theorem

Max-Flow Min-Cut Theorem
In a flow network, the maximum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow equals the minimum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.
Proof.

Let [math]\displaystyle{ f }[/math] be a flow with maximum value, so there is no augmenting path.

Again, let

[math]\displaystyle{ S=\{u\in V\mid \exists\text{an augmenting path to }u\} }[/math].

As proved above, [math]\displaystyle{ (S,\bar{S}) }[/math] forms an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, and

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math],

that is, the value of flow [math]\displaystyle{ f }[/math] equals the value of cut [math]\displaystyle{ (S,\bar{S}) }[/math].

Since we know that all [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flows are not greater than any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, the value of flow [math]\displaystyle{ f }[/math] equals the minimum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.

[math]\displaystyle{ \square }[/math]

Flow Integrality Theorem

Flow Integrality Theorem
Let [math]\displaystyle{ (G,c,s,t) }[/math] be a flow network with integral capacity [math]\displaystyle{ c }[/math]. There exists an integral flow which is maximum.
Proof.

Let [math]\displaystyle{ f }[/math] be an integral flow of maximum value. If there is an augmenting path, since both [math]\displaystyle{ c }[/math] and [math]\displaystyle{ f }[/math] are integral, a new flow can be constructed of value 1+the value of [math]\displaystyle{ f }[/math], contradicting that [math]\displaystyle{ f }[/math] is maximum over all integral flows. Therefore, there is no augmenting path, which means that [math]\displaystyle{ f }[/math] is maximum over all flows, integral or not.

[math]\displaystyle{ \square }[/math]

Applications: Menger's theorem

Given an undirected graph [math]\displaystyle{ G(V,E) }[/math] and two distinct vertices [math]\displaystyle{ s,t\in V }[/math], a set of edges [math]\displaystyle{ C\subseteq E }[/math] is called an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, if deleting edges in [math]\displaystyle{ C }[/math] disconnects [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math].

A simple path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is called an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] path. Two paths are said to be edge-disjoint if they do not share any edge.

Theorem (Menger 1927)
Let [math]\displaystyle{ G(V,E) }[/math] be an arbitrary undirected graph and [math]\displaystyle{ s,t\in V }[/math] be two distinct vertices. The minimum size of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut equals the maximum number of edge-disjoint [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] paths.
Proof.

Construct a directed graph [math]\displaystyle{ G'(V,E') }[/math] from [math]\displaystyle{ G(V,E) }[/math] as follows: replace every undirected edge [math]\displaystyle{ uv\in E }[/math] that [math]\displaystyle{ s,t\not\in\{u,v\} }[/math] by two directed edges [math]\displaystyle{ (u,v) }[/math] and [math]\displaystyle{ (v,u) }[/math]; replace every undirected edge [math]\displaystyle{ sv\in E }[/math] by [math]\displaystyle{ (s,v) }[/math], and very undirected edge [math]\displaystyle{ vt\in E }[/math] by [math]\displaystyle{ (v,t) }[/math]. Then assign every directed edge with capacity 1.

It is easy to verify that in the flow network constructed as above, the followings hold:

  • An integral [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow corresponds to a set of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] paths in the undirected graph [math]\displaystyle{ G }[/math], where the value of the flow is the number of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] paths.
  • An [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in the flow network corresponds to an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in the undirected graph [math]\displaystyle{ G }[/math] with the same value.

The Menger's theorem follows as a direct consequence of the max-flow min-cut theorem.

[math]\displaystyle{ \square }[/math]

Applications: König-Egerváry theorem

Let [math]\displaystyle{ G(V,E) }[/math] be a graph. An edge set [math]\displaystyle{ M\subseteq E }[/math] is called a matching if no edge in [math]\displaystyle{ M }[/math] shares any vertex. A vertex set [math]\displaystyle{ C\subseteq V }[/math] is called a vertex cover if for any edge [math]\displaystyle{ uv\in E }[/math], either [math]\displaystyle{ u\in C }[/math] or [math]\displaystyle{ v\in C }[/math].

Theorem (König 1936)
In any bipartite graph [math]\displaystyle{ G(V_1,V_2,E) }[/math], the size of a maximum matching equals the size of a minimum vertex cover.

We now show how a reduction of bipartite matchings to flows.

Construct a flow network [math]\displaystyle{ (G'(V,E'),c,s,t) }[/math] as follows:

  • [math]\displaystyle{ V=V_1\cup V_2\cup\{s,t\} }[/math] where [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] are two new vertices.
  • For ever [math]\displaystyle{ uv\in E }[/math], add [math]\displaystyle{ (u,v) }[/math] to [math]\displaystyle{ E' }[/math]; for every [math]\displaystyle{ u\in V_1 }[/math], add [math]\displaystyle{ (s,u) }[/math] to [math]\displaystyle{ E' }[/math]; and for every [math]\displaystyle{ v\in V_2 }[/math], add [math]\displaystyle{ (v,t) }[/math] to [math]\displaystyle{ E' }[/math].
  • Let [math]\displaystyle{ c_{su}=1 }[/math] for every [math]\displaystyle{ u\in V_1 }[/math] and [math]\displaystyle{ c_{vt}=1 }[/math] for every [math]\displaystyle{ v\in V_2 }[/math]. Let [math]\displaystyle{ c_{uv}=\infty }[/math] for every bipartite edges [math]\displaystyle{ (u,v) }[/math].
Lemma
The size of a maximum matching in [math]\displaystyle{ G }[/math] is equal to the value of a maximum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow in [math]\displaystyle{ G' }[/math].
Proof.

Given an integral [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow [math]\displaystyle{ f }[/math] in [math]\displaystyle{ G' }[/math], let [math]\displaystyle{ M=\{uv\in E\mid f_{uv}=1\} }[/math]. Then [math]\displaystyle{ M }[/math] must be a matching since for every [math]\displaystyle{ u\in V_1 }[/math]. To see this, observe that there is at most one [math]\displaystyle{ v\in V_2 }[/math] that [math]\displaystyle{ f_{uv}=1 }[/math], because of that [math]\displaystyle{ f_{su}\le c_{su}=1 }[/math] and conservation of flows. The same holds for vertices in [math]\displaystyle{ V_2 }[/math] by the same argument. Therefore, each flow corresponds to a matching.

Given a matching [math]\displaystyle{ M }[/math] in bipartite graph [math]\displaystyle{ G }[/math], define an integral flow [math]\displaystyle{ f }[/math] as such: for [math]\displaystyle{ uv\in E }[/math], [math]\displaystyle{ f_{uv}=1 }[/math] if [math]\displaystyle{ uv\in M }[/math] and [math]\displaystyle{ f_{uv}=0 }[/math] if otherwise; for [math]\displaystyle{ u\in V_1 }[/math], [math]\displaystyle{ f_{su}=1 }[/math] if [math]\displaystyle{ uv\in M }[/math] for some [math]\displaystyle{ v }[/math] and [math]\displaystyle{ f_{su}=0 }[/math] if otherwise; for [math]\displaystyle{ v\in V_2 }[/math], [math]\displaystyle{ f_{vt}=1 }[/math] if [math]\displaystyle{ uv\in M }[/math] for some [math]\displaystyle{ u }[/math] and [math]\displaystyle{ f_{vt}=0 }[/math] if otherwise.

It is easy to check that [math]\displaystyle{ f }[/math] is valid [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow in [math]\displaystyle{ G' }[/math]. Therefore, there is an one-one correspondence between flows in [math]\displaystyle{ G' }[/math] and matchings in [math]\displaystyle{ G }[/math]. The lemma follows naturally.

[math]\displaystyle{ \square }[/math]

We then establish a correspondence between [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cuts in [math]\displaystyle{ G' }[/math] and vertex covers in [math]\displaystyle{ G }[/math].

Suppose [math]\displaystyle{ (S,\bar{S}) }[/math] is an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in [math]\displaystyle{ G' }[/math].

Lemma
The size of a minimum vertex cover in [math]\displaystyle{ G }[/math] is equal to the value of a minimum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in [math]\displaystyle{ G' }[/math].
Proof.

Let [math]\displaystyle{ (S,\bar{S}) }[/math] be an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut of minimum capacity in [math]\displaystyle{ G' }[/math]. Then [math]\displaystyle{ \sum_{u\in S, v\not\in S\atop (u,v)\in E'}c_{uv} }[/math] must be finite since [math]\displaystyle{ S=\{s\} }[/math] gives us an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut whose capacity is [math]\displaystyle{ |V_1| }[/math] which is finite. Therefore, no edge [math]\displaystyle{ uv\in E }[/math] has [math]\displaystyle{ u\in V_1\cap S }[/math] and [math]\displaystyle{ v\in V_2\setminus S }[/math], i.e., for all [math]\displaystyle{ uv\in E }[/math], either [math]\displaystyle{ u\in V_1\setminus S }[/math] or [math]\displaystyle{ v\in V_2\cap S }[/math]. Therefore, [math]\displaystyle{ (V_1\setminus S)\cup(V_2\cap S) }[/math] is a vertex cover in [math]\displaystyle{ G }[/math], whose size is

[math]\displaystyle{ |(V_1\setminus S)\cup(V_2\cap S)|=|V_1\setminus S|+|V_2\cap S|=\sum_{u\in V_1\setminus S}c_{su}+\sum_{v\in V_2\cap S}c_{ut}=\sum_{u\in S,v\not\in S\atop (u,v)\in E'}c_{uv} }[/math].

The last term is the capacity of the minimum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut [math]\displaystyle{ (S,\bar{S}) }[/math].

[math]\displaystyle{ \square }[/math]

The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.

Algorithms

The Hungarian algorithm

The Ford-Fulkerson algorithm

The Hopcroft-Karp Algorithm