imported>WikiSysop |
imported>Macdonald-ross |
Line 1: |
Line 1: |
| == Flow and Cut==
| | '''William Donald Hamilton''' [[Royal Society|FRS]] (1 August 1936 – 7 March 2000) was an [[English people|English]] [[evolutionary biology|evolutionary biologist]] whom [[Richard Dawkins]] praised as one of the greatest [[evolution]]ary theorists of the 20th century.<ref>[http://www.edge.org/3rd_culture/hamilton/hamilton_index.html Obituary by Richard Dawkins – ''The Independent'' – 10 March 2000]</ref> |
|
| |
|
| === Flows ===
| | Hamilton became famous through his [[Theory|theoretical]] work on [[kin selection]] and [[altruism]]. He explained its [[Genetics|genetic]] basis, and this was a key part of the gene-centered view of [[evolution]]. In doing this, he became one of the forerunners of [[sociobiology]], as popularized by [[E.O. Wilson]]. Hamilton was certainly a big influence on Dawkins. He also published important work on [[sex ratio]]s and the [[evolution of sex]]. From 1984 to his death in 2000, he was the [[Royal Society]] Research Professor at [[Oxford University]]. He died of [[malaria]] contracted in the [[Democratic Republic of the Congo]]. |
| An instance of the maximum flow problem consists of:
| |
| * a directed graph <math>G(V,E)</math>;
| |
| * two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
| |
| * the '''capacity function''' <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.
| |
|
| |
|
| The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.
| | == Hamilton's equation == |
| | Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.<ref>Hamilton W.D. 1996. ''Narrow roads of geneland: the collected papers of W.D. Hamilton'', vol 1. Freeman, Oxford.</ref> The gene will spread if '''r'''x'''b''' is greater than '''c''': |
| | :<math>rb > c \ </math> |
| | where: |
| | * <math>c \ </math> is the reproductive cost to the altruist, |
| | * <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and |
| | * <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness". |
|
| |
|
| A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
| | == Collected papers == |
| * '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
| | Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors. |
| * '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.
| |
|
| |
|
| The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.
| | * Hamilton W.D. 1996. ''Narrow roads of gene land vol. 1: Evolution of social behaviour''. Freeman, Oxford. ISBN 0-7167-4530-5 |
| | * Hamilton W.D. 2002. ''Narrow roads of gene land vol. 2: Evolution of sex''. Oxford University Press, Oxford. ISBN 0-19-850336-9 |
| | * Hamilton W.D. 2005. ''Narrow roads of gene land, vol. 3: Last words'' (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5 |
|
| |
|
| Given a flow network, the maximum flow problem asks to find the flow of the maximum value.
| | == References == |
| | {{Reflist}} |
|
| |
|
| The maximum flow problem can be described as the following linear program.
| | {{DEFAULTSORT:Hamilton, William Donald}} |
| :<math>
| | [[Category:1936 births]] |
| \begin{align}
| | [[Category:2000 deaths]] |
| \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
| | [[Category:English mathematicians]] |
| \begin{align}
| | [[Category:Geneticists]] |
| \text{subject to} \\
| | [[Category:English evolutionary biologists]] |
| \\
| | [[Category:Fellows of the Royal Society]] |
| \\
| |
| \\
| |
| \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 ===
| |
| {{Theorem|Definition|
| |
| :Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
| |
| :The '''value''' of the cut (also called the '''capacity''' of the cut) is defined as <math>\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.
| |
| | |
| {{Theorem|Lemma|
| |
| :Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
| |
| ::<math>\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>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.
| |
| | |
| Due to the conservation of flow,
| |
| :<math>\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>\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>\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>
| |
| }}
| |
| | |
| === Augmenting paths ===
| |
| {{Theorem|Definition (Augmenting path)| | |
| :Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that | |
| :* <math>u_0=s\,</math>;
| |
| :and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
| |
| :* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and | |
| :* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
| |
| :If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
| |
| }}
| |
| | |
| Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
| |
| *<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
| |
| *<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
| |
| Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.
| |
| | |
| Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>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>f'</math>
| |
| :<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\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.
| |
| | |
| {{Theorem|Lemma|
| |
| :A flow <math>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>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.
| |
| | |
| We claim that
| |
| :<math>\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>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.
| |
| | |
| To prove this claim, we first observe that
| |
| :<math>\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>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.
| |
| | |
| We then claim that
| |
| *<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
| |
| *<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
| |
| If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.
| |
| | |
| Therefore,
| |
| :<math>\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.
| |
| }}
| |
| | |
| == Max-Flow Min-Cut ==
| |
| | |
| === The max-flow min-cut theorem ===
| |
| {{Theorem|Max-Flow Min-Cut Theorem|
| |
| :In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
| |
| }}
| |
| | |
| {{Proof|
| |
| Let <math>f</math> be a flow with maximum value, so there is no augmenting path.
| |
| | |
| Again, let
| |
| :<math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>.
| |
| As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
| |
| :<math>\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>f</math> equals the value of cut <math>(S,\bar{S})</math>.
| |
| | |
| Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
| |
| }}
| |
| | |
| === Flow Integrality Theorem ===
| |
| {{Theorem|Flow Integrality Theorem|
| |
| :Let <math>(G,c,s,t)</math> be a flow network with integral capacity <math>c</math>. There exists an integral flow which is maximum.
| |
| }}
| |
| {{Proof|
| |
| Let <math>f</math> be an integral flow of maximum value. If there is an augmenting path, since both <math>c</math> and <math>f</math> are integral, a new flow can be constructed of value 1+the value of <math>f</math>, contradicting that <math>f</math> is maximum over all integral flows. Therefore, there is no augmenting path, which means that <math>f</math> is maximum over all flows, integral or not.
| |
| }}
| |
| | |
| === Applications: Menger's theorem ===
| |
| Given an undirected graph <math>G(V,E)</math> and two distinct vertices <math>s,t\in V</math>, a set of edges <math>C\subseteq E</math> is called an '''<math>s</math>-<math>t</math> cut''', if deleting edges in <math>C</math> disconnects <math>s</math> and <math>t</math>.
| |
| | |
| A simple path from <math>s</math> to <math>t</math> is called an '''<math>s</math>-<math>t</math> path'''. Two paths are said to be '''edge-disjoint''' if they do not share any edge.
| |
| | |
| {{Theorem|Theorem (Menger 1927)|
| |
| :Let <math>G(V,E)</math> be an arbitrary undirected graph and <math>s,t\in V</math> be two distinct vertices. The minimum size of any <math>s</math>-<math>t</math> cut equals the maximum number of edge-disjoint <math>s</math>-<math>t</math> paths.
| |
| }}
| |
| {{proof|
| |
| Construct a directed graph <math>G'(V,E')</math> from <math>G(V,E)</math> as follows: replace every undirected edge <math>uv\in E</math> that <math>s,t\not\in\{u,v\}</math> by two directed edges <math>(u,v)</math> and <math>(v,u)</math>; replace every undirected edge <math>sv\in E</math> by <math>(s,v)</math>, and very undirected edge <math>vt\in E</math> by <math>(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>s</math>-<math>t</math> flow corresponds to a set of <math>s</math>-<math>t</math> paths in the undirected graph <math>G</math>, where the value of the flow is the number of <math>s</math>-<math>t</math> paths.
| |
| *An <math>s</math>-<math>t</math> cut in the flow network corresponds to an <math>s</math>-<math>t</math> cut in the undirected graph <math>G</math> with the same value.
| |
| The Menger's theorem follows as a direct consequence of the max-flow min-cut theorem.
| |
| }}
| |
| | |
| === Applications: König-Egerváry theorem ===
| |
| Let <math>G(V,E)</math> be a graph. An edge set <math>M\subseteq E</math> is called a '''matching''' if no edge in <math>M</math> shares any vertex. A vertex set <math>C\subseteq V</math> is called a '''vertex cover''' if for any edge <math>uv\in E</math>, either <math>u\in C</math> or <math>v\in C</math>.
| |
| | |
| {{Theorem|Theorem (König 1936)|
| |
| :In any bipartite graph <math>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>(G'(V,E'),c,s,t)</math> as follows:
| |
| * <math>V=V_1\cup V_2\cup\{s,t\}</math> where <math>s</math> and <math>t</math> are two new vertices.
| |
| * For ever <math>uv\in E</math>, add <math>(u,v)</math> to <math>E'</math>; for every <math>u\in V_1</math>, add <math>(s,u)</math> to <math>E'</math>; and for every <math>v\in V_2</math>, add <math>(v,t)</math> to <math>E'</math>.
| |
| * Let <math>c_{su}=1</math> for every <math>u\in V_1</math> and <math>c_{vt}=1</math> for every <math>v\in V_2</math>. Let <math>c_{uv}=\infty</math> for every bipartite edges <math>(u,v)</math>.
| |
| | |
| {{Theorem|Lemma|
| |
| :The size of a maximum matching in <math>G</math> is equal to the value of a maximum <math>s</math>-<math>t</math> flow in <math>G'</math>. | |
| }}
| |
| {{proof|
| |
| Given an integral <math>s</math>-<math>t</math> flow <math>f</math> in <math>G'</math>, let <math>M=\{uv\in E\mid f_{uv}=1\}</math>. Then <math>M</math> must be a matching since for every <math>u\in V_1</math>. To see this, observe that there is at most one <math>v\in V_2</math> that <math>f_{uv}=1</math>, because of that <math>f_{su}\le c_{su}=1</math> and conservation of flows. The same holds for vertices in <math>V_2</math> by the same argument. Therefore, each flow corresponds to a matching.
| |
| | |
| Given a matching <math>M</math> in bipartite graph <math>G</math>, define an integral flow <math>f</math> as such: for <math>uv\in E</math>, <math>f_{uv}=1</math> if <math>uv\in M</math> and <math>f_{uv}=0</math> if otherwise; for <math>u\in V_1</math>, <math>f_{su}=1</math> if <math>uv\in M</math> for some <math>v</math> and <math>f_{su}=0</math> if otherwise; for <math>v\in V_2</math>, <math>f_{vt}=1</math> if <math>uv\in M</math> for some <math>u</math> and <math>f_{vt}=0</math> if otherwise.
| |
| | |
| It is easy to check that <math>f</math> is valid <math>s</math>-<math>t</math> flow in <math>G'</math>. Therefore, there is an one-one correspondence between flows in <math>G'</math> and matchings in <math>G</math>. The lemma follows naturally.
| |
| }}
| |
| | |
| We then establish a correspondence between <math>s</math>-<math>t</math> cuts in <math>G'</math> and vertex covers in <math>G</math>.
| |
| | |
| Suppose <math>(S,\bar{S})</math> is an <math>s</math>-<math>t</math> cut in <math>G'</math>.
| |
| {{Theorem|Lemma|
| |
| :The size of a minimum vertex cover in <math>G</math> is equal to the value of a minimum <math>s</math>-<math>t</math> cut in <math>G'</math>. | |
| }}
| |
| {{proof|
| |
| Let <math>(S,\bar{S})</math> be an <math>s</math>-<math>t</math> cut of minimum capacity in <math>G'</math>. Then <math>\sum_{u\in S, v\not\in S\atop (u,v)\in E'}c_{uv}</math> must be finite since <math>S=\{s\}</math> gives us an <math>s</math>-<math>t</math> cut whose capacity is <math>|V_1|</math> which is finite. Therefore, no edge <math>uv\in E</math> has <math>u\in V_1\cap S</math> and <math>v\in V_2\setminus S</math>, i.e., for all <math>uv\in E</math>, either <math>u\in V_1\setminus S</math> or <math>v\in V_2\cap S</math>. Therefore, <math>(V_1\setminus S)\cup(V_2\cap S)</math> is a vertex cover in <math>G</math>, whose size is
| |
| :<math>|(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>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.
| |
| }}
| |
| | |
| The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.
| |