Difference between revisions of "Maximum flow problem"
en>FelGru (→Baseball Elimination: add missing index j) |
en>JonMarkPerry |
||
Line 1: | Line 1: | ||
− | [[File:Max flow.svg|thumb|upright=1.5| | + | [[File:Max flow.svg|thumb|upright=1.5|A network with an example of maximum flow. The source is ''s'', and the sink ''t''. The numbers denote flow and capacity.]] |
In [[Optimization (mathematics)|optimization theory]], '''maximum flow problems''' involve finding a feasible flow through a single-source, single-sink [[flow network]] that is maximum. | In [[Optimization (mathematics)|optimization theory]], '''maximum flow problems''' involve finding a feasible flow through a single-source, single-sink [[flow network]] that is maximum. | ||
Line 25: | Line 25: | ||
==Solutions== | ==Solutions== | ||
− | We can define the '''Residual Graph''', which provides a systematic way to search for forward-backward operations in order to find the maximum flow. | + | We can define the '''Residual Graph''', which provides a systematic way to search for forward-backward operations in order to find the maximum flow. |
− | Given a flow network <math>\scriptstyle G</math>, and a flow <math>\scriptstyle f</math> on <math>\scriptstyle G</math>, we define the residual graph <math>\scriptstyle G_{f}</math> of <math>\scriptstyle G</math> with respect to <math>\scriptstyle f</math> as follows. | + | Given a flow network <math>\scriptstyle G</math>, and a flow <math>\scriptstyle f</math> on <math>\scriptstyle G</math>, we define the residual graph <math>\scriptstyle G_{f}</math> of <math>\scriptstyle G</math> with respect to <math>\scriptstyle f</math> as follows. |
− | 1. The node set of <math>\scriptstyle G_{f}</math> is the same as that of <math>\scriptstyle G</math>. | + | 1. The node set of <math>\scriptstyle G_{f}</math> is the same as that of <math>\scriptstyle G</math>. |
− | 2. Each edge <math>\scriptstyle e = (u, v)</math> of <math>\scriptstyle G_{f}</math> is with a capacity of <math>\scriptstyle c_{e} - f(e)</math>. | + | 2. Each edge <math>\scriptstyle e = (u, v)</math> of <math>\scriptstyle G_{f}</math> is with a capacity of <math>\scriptstyle c_{e} - f(e)</math>. |
− | 3. Each edge <math>\scriptstyle e' = (v, u)</math> of <math>\scriptstyle G_{f}</math> is with a capacity of <math>\scriptstyle f(e)</math>. | + | 3. Each edge <math>\scriptstyle e' = (v, u)</math> of <math>\scriptstyle G_{f}</math> is with a capacity of <math>\scriptstyle f(e)</math>. |
{{clear}} | {{clear}} | ||
Line 56: | Line 56: | ||
| A specialization of Ford–Fulkerson, finding augmenting paths with [[breadth-first search]]. | | A specialization of Ford–Fulkerson, finding augmenting paths with [[breadth-first search]]. | ||
|- | |- | ||
− | | [[ | + | | [[Dinic's blocking flow algorithm]] |
| ''O''(''V''<sup>2</sup>''E'') | | ''O''(''V''<sup>2</sup>''E'') | ||
| In each phase the algorithms builds a layered graph with [[breadth-first search]] on the [[residual graph]]. The maximum flow in a layered graph can be calculated in ''O''(''VE'') time, and the maximum number of the phases is ''n''-1. In networks with unit capacities, Dinic's algorithm terminates in <math>\scriptscriptstyle O(E\sqrt{V})</math> time. | | In each phase the algorithms builds a layered graph with [[breadth-first search]] on the [[residual graph]]. The maximum flow in a layered graph can be calculated in ''O''(''VE'') time, and the maximum number of the phases is ''n''-1. In networks with unit capacities, Dinic's algorithm terminates in <math>\scriptscriptstyle O(E\sqrt{V})</math> time. | ||
Line 68: | Line 68: | ||
| Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations until the excess is positive or there are admissible residual edges from this vertex. | | Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations until the excess is positive or there are admissible residual edges from this vertex. | ||
|- | |- | ||
− | | [[ | + | | [[Dinic's blocking flow algorithm| Dinic's algorithm]] |
| ''O''(''VE'' log(''V'')) | | ''O''(''VE'' log(''V'')) | ||
| The [[dynamic trees]] data structure speeds up the maximum flow computation in the layered graph to ''O''(''E''log(''V'')). | | The [[dynamic trees]] data structure speeds up the maximum flow computation in the layered graph to ''O''(''E''log(''V'')). | ||
Line 105: | Line 105: | ||
# ''V''<sub>''out''</sub> = {''v''∈''V'': ''v'' has positive out-degree}. | # ''V''<sub>''out''</sub> = {''v''∈''V'': ''v'' has positive out-degree}. | ||
# ''V''<sub>''in''</sub> = {''v''∈''V'': ''v'' has positive in-degree}. | # ''V''<sub>''in''</sub> = {''v''∈''V'': ''v'' has positive in-degree}. | ||
− | # ''E''<nowiki>'</nowiki> = {(''u'',''v'')∈ | + | # ''E''<nowiki>'</nowiki> = {(''u'',''v'')∈''V''<sub>''out''</sub>×''V''<sub>''in''</sub>: (''u'',''v'')∈''E''}. |
Then it can be shown, via [[König's theorem (graph theory)|König's theorem]], that ''G''<nowiki>'</nowiki> has a matching of size ''m'' if and only if there exists ''n''-''m'' paths that cover each vertex in ''G'', where ''n'' is the number of vertices in ''G''. Therefore, the problem can be solved by finding the maximum cardinality matching in ''G''<nowiki>'</nowiki> instead. | Then it can be shown, via [[König's theorem (graph theory)|König's theorem]], that ''G''<nowiki>'</nowiki> has a matching of size ''m'' if and only if there exists ''n''-''m'' paths that cover each vertex in ''G'', where ''n'' is the number of vertices in ''G''. Therefore, the problem can be solved by finding the maximum cardinality matching in ''G''<nowiki>'</nowiki> instead. | ||
Line 123: | Line 123: | ||
In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across <math>N</math>, we can transform the problem into the maximum flow problem in the original sense by expanding <math>N</math>. First, each <math>v\in V</math> is replaced by <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>, where <math>v_{\text{in}}</math> is connected by edges going into <math>v</math> and <math>v_{\text{out}}</math> is connected to edges coming out from <math>v</math>, then assign capacity <math>c(v)</math> to the edge connecting <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math> (see Fig. 4.4.1, but note that it has incorrectly swapped <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem. | In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across <math>N</math>, we can transform the problem into the maximum flow problem in the original sense by expanding <math>N</math>. First, each <math>v\in V</math> is replaced by <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>, where <math>v_{\text{in}}</math> is connected by edges going into <math>v</math> and <math>v_{\text{out}}</math> is connected to edges coming out from <math>v</math>, then assign capacity <math>c(v)</math> to the edge connecting <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math> (see Fig. 4.4.1, but note that it has incorrectly swapped <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem. | ||
− | ===Maximum independent path=== | + | ===Maximum edge-disjoint path=== |
+ | Given a directed graph ''G'' = (''V'', ''E'') and two vertices ''s'' and ''t'', we are to find the maximum number of edge-disjoint paths from | ||
+ | ''s'' to ''t''. This problem can be transformed to a maximum flow problem by constructing a network ''N'' = (''V'', ''E'') from ''G'' with ''s'' and ''t'' being the source and the sink of ''N'' respectively and assign each edge with unit capacity. | ||
+ | |||
+ | ===Maximum independent (vertex-disjoint) path=== | ||
Given a directed graph ''G'' = (''V'', ''E'') and two vertices ''s'' and ''t'', we are to find the maximum number of independent paths from ''s'' to ''t''. Two paths are said to be independent if they do not have a vertex in common apart from ''s'' and ''t''. We can construct a network ''N'' = (''V'', ''E'') from ''G'' with vertex capacities, where | Given a directed graph ''G'' = (''V'', ''E'') and two vertices ''s'' and ''t'', we are to find the maximum number of independent paths from ''s'' to ''t''. Two paths are said to be independent if they do not have a vertex in common apart from ''s'' and ''t''. We can construct a network ''N'' = (''V'', ''E'') from ''G'' with vertex capacities, where | ||
# ''s'' and ''t'' are the source and the sink of ''N'' respectively. | # ''s'' and ''t'' are the source and the sink of ''N'' respectively. | ||
Line 130: | Line 134: | ||
Then the value of the maximum flow is equal to the maximum number of independent paths from ''s'' to ''t''. | Then the value of the maximum flow is equal to the maximum number of independent paths from ''s'' to ''t''. | ||
− | === | + | ==Real world applications== |
− | |||
− | |||
− | |||
===Baseball Elimination=== | ===Baseball Elimination=== | ||
− | [[File:Baseball Elimination Problem.png|thumb|Construction of network flow for baseball elimination problem]]In the Baseball Elimination Problem there are ''n'' teams competing in a league. At a specific stage of the league season, ''w''<sub>i</sub> is the number of wins and ''r''<sub>i</sub> is the number of games left to play for team ''i'' and ''r''<sub>ij</sub> is the number of games left against team ''j''. A team is eliminated if it has no chance to finish the season in the first place. The task of Baseball Elimination Problem is to determine which teams are eliminated at each point during the season. Schwartz<ref>{{cite doi|10.1137/1008062}}</ref> proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team ''k'' is eliminated. | + | [[File:Baseball Elimination Problem.png|thumb|Construction of network flow for baseball elimination problem]]In the Baseball Elimination Problem there are ''n'' teams competing in a league. At a specific stage of the league season, ''w''<sub>i</sub> is the number of wins and ''r''<sub>i</sub> is the number of games left to play for team ''i'' and ''r''<sub>ij</sub> is the number of games left against team ''j''. A team is eliminated if it has no chance to finish the season in the first place. The task of Baseball Elimination Problem is to determine which teams are eliminated at each point during the season. Schwartz<ref>{{cite doi|10.1137/1008062}}</ref> proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team ''k'' is eliminated. |
− | Let ''G'' = (''V'', ''E'') be a network with ''s'',''t'' ∈ ''V'' being the source and the sink respectively. We add a game node {''i'',''j''} with ''i'' < ''j'' to ''V'' and connect each of them | + | Let ''G'' = (''V'', ''E'') be a network with ''s'',''t'' ∈ ''V'' being the source and the sink respectively. We add a game node {''i'',''j''} with ''i'' < ''j'' to ''V'', and connect each of them from ''s'' by an edge with capacity ''r''<sub>ij</sub> — which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {''i'',''j''} with to team nodes ''i'' and ''j'' to ensure one of them wins. We do not need to restrict the flow value on these edges. Finally, we make edges from team node ''i'' to the sink node ''t'' and set the capacity of ''w''<sub>k</sub>+''r''<sub>k</sub>–''w''<sub>i</sub> to prevent team ''i'' from winning more than ''w''<sub>k</sub>+''r''<sub>k</sub>. |
Let ''S'' be the set of all team participating in the league and let <math>\scriptstyle r(S - \{k\}) = \sum_{i,j \in \{S-\{k\}\}, i < j} r_{ij}</math>. In this method it is claimed team ''k'' is not eliminated if and only if a flow value of size ''r''(''S'' - {''k''}) exists in network ''G''. In the mentioned article it is proved that this flow value is the maximum flow value from ''s'' to ''t''. | Let ''S'' be the set of all team participating in the league and let <math>\scriptstyle r(S - \{k\}) = \sum_{i,j \in \{S-\{k\}\}, i < j} r_{ij}</math>. In this method it is claimed team ''k'' is not eliminated if and only if a flow value of size ''r''(''S'' - {''k''}) exists in network ''G''. In the mentioned article it is proved that this flow value is the maximum flow value from ''s'' to ''t''. | ||
===Airline scheduling=== | ===Airline scheduling=== | ||
− | In the airline industry a major problem is the scheduling of the flight crews. Airline scheduling problem could be considered as an application of extended maximum network flow. The input of this problem is a set of flights ''F'' which contains the information about where and when each flight departs and arrives. In one version of Airline Scheduling the goal is to produce a feasible | + | In the airline industry a major problem is the scheduling of the flight crews. Airline scheduling problem could be considered as an application of extended maximum network flow. The input of this problem is a set of flights ''F'' which contains the information about where and when each flight departs and arrives. In one version of Airline Scheduling the goal is to produce a feasible schedule with at most ''k'' crews. |
− | In order to solve this problem we use a variation of [[circulation problem]] called bounded circulation which is the generalization of [[flow network|network flow]] problems, with the added constraint of a lower bound on edge flows. | + | In order to solve this problem we use a variation of [[circulation problem]] called bounded circulation which is the generalization of [[flow network|network flow]] problems, with the added constraint of a lower bound on edge flows. |
Let ''G'' = (''V'', ''E'') be a network with ''s'',''t'' ∈ ''V'' as the source and the sink nodes. For the source and destination of every flight ''i'' we add two nodes to ''V'', node ''s''<sub>i</sub> as the source and node ''d''<sub>i</sub> as the destination node of flight ''i''. We also add the following edges to ''E'': | Let ''G'' = (''V'', ''E'') be a network with ''s'',''t'' ∈ ''V'' as the source and the sink nodes. For the source and destination of every flight ''i'' we add two nodes to ''V'', node ''s''<sub>i</sub> as the source and node ''d''<sub>i</sub> as the destination node of flight ''i''. We also add the following edges to ''E'': | ||
Line 154: | Line 155: | ||
# An edge with capacity [0, ''<big>∞</big>''] between ''s'' and ''t''. | # An edge with capacity [0, ''<big>∞</big>''] between ''s'' and ''t''. | ||
− | In the mentioned method, it is claimed and proved that finding a flow value of ''k'' in ''G'' between ''s'' and ''t'' is equal to finding a feasible schedule for flight set ''F'' with at most ''k'' crews{{ref | + | In the mentioned method, it is claimed and proved that finding a flow value of ''k'' in ''G'' between ''s'' and ''t'' is equal to finding a feasible schedule for flight set ''F'' with at most ''k'' crews.<ref name="ITA">{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title=[[Introduction to Algorithms]], Second Edition | chapter = 26. Maximum Flow | year = 2001 | publisher = MIT Press and McGraw-Hill | isbn = 0-262-03293-7 | pages=643–668}}</ref> |
+ | |||
+ | Another version of Airline Scheduling is finding the minimum needed crews to perform all the flights. In order to find an answer to this problem we create a bipartite graph ''G’'' = (''A'' ∪ ''B'', ''E'') where each flight has a copy in set ''A'' and set ''B''. If the same plane can perform flight ''j'' after flight ''i'', connect ''i''∈''A'' to ''j''∈''B''. A matching in ''G’'' induces a schedule for ''F'' and obviously maximum bipartite matching in this graph produces the an airline schedule with minimum number of crews.<ref name="ITA"/> As it is mentioned in the Application part of this article, the maximum cardinality bipartite matching is an application of maximum flow problem. | ||
+ | |||
+ | ===Circulation-demand problem=== | ||
+ | There are some factories that produce goods and some villages where the goods have to be delivered. They are connected by a networks of roads with each road having a capacity <math> c </math> for maximum goods that can flow through it. The problem is to find if there is a circulation that satisfies the demand. | ||
+ | This problem can be transformed into a max-flow problem. | ||
+ | # Add a source node <math> s </math> and add edges from it to every factory node <math> f_i </math> with capacity <math> p_i </math> where <math> p_i </math> is the production rate of factory <math> f_i </math>. | ||
+ | # Add a sink node <math> t </math> and add edges from all villages <math> v_i </math> to <math> t </math> with capacity <math> d_i </math> where <math> d_i </math> is the demand rate of village <math> v_i </math>. | ||
+ | Let ''G'' = (''V'', ''E'') be this new network. There exists a circulation that satisfies the demand if and only if : | ||
+ | :<math> Maximum flow value(G) = \sum_{i \in v} d_i </math> | ||
+ | If there exists a circulation, looking at the max-flow solution would give us the answer as to how much goods have to be send on a particular road for satisfying the demands. | ||
− | + | ===Fairness in car sharing (carpool)=== | |
+ | The problem exactly is that <math> N </math> people are pooling a car for <math> k </math> days. Each participant can choose if he participates on each day. We aim to fairly decide who will be driving on a given day.<br> | ||
+ | The solution is the following:<br> | ||
+ | We can decide this on the basis of the number of people using the car i.e.; if <math> m </math> people use the car on a day, each person has a responsibility of <math> 1/m </math>. Thus, for every person <math> i </math>, his driving obligation <math> D_i </math> as shown. Then person <math> i </math> is required to drive only <math> [D_i] </math> times in <math> k </math> days.<br> | ||
+ | Our aim is to ﬁnd if such a setting is possible. For this we try to make the problem as a network, | ||
+ | as we can see in the ﬁgure.<br> | ||
+ | Now, it can be proved that if a ﬂow <math> k </math> exists then such a fair setting exists and such a ﬂow of value <math> k </math> always exists. | ||
==See also== | ==See also== | ||
* [[Closure problem]] | * [[Closure problem]] | ||
− | * [[Minimum cost flow problem]] | + | * [[Minimum-cost flow problem]] |
==References== | ==References== | ||
{{reflist}} | {{reflist}} | ||
− | + | ==Further reading== | |
− | + | * {{cite journal | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == | ||
− | |||
| author = [[Joseph Cheriyan]] and [[Kurt Mehlhorn]] | | author = [[Joseph Cheriyan]] and [[Kurt Mehlhorn]] | ||
| title = An analysis of the highest-level selection rule in the preflow-push max-flow algorithm | | title = An analysis of the highest-level selection rule in the preflow-push max-flow algorithm | ||
Line 184: | Line 194: | ||
| issue = 5 | | issue = 5 | ||
}} | }} | ||
− | + | * {{cite journal | |
| author = [[Daniel D. Sleator]] and [[Robert E. Tarjan]] | | author = [[Daniel D. Sleator]] and [[Robert E. Tarjan]] | ||
| title = A data structure for dynamic trees | | title = A data structure for dynamic trees | ||
Line 196: | Line 206: | ||
| issue = 3 | | issue = 3 | ||
}} | }} | ||
− | + | * {{cite book | author = Eugene Lawler | authorlink = Eugene Lawler | title = Combinatorial Optimization: Networks and Matroids | chapter = 4. Network Flows | year = 2001 | publisher = Dover | isbn = 0-486-41453-1 | pages = 109–177}} | |
− | |||
{{DEFAULTSORT:Maximum Flow Problem}} | {{DEFAULTSORT:Maximum Flow Problem}} | ||
[[Category:Network flow]] | [[Category:Network flow]] | ||
[[Category:Mathematical problems]] | [[Category:Mathematical problems]] |
Latest revision as of 08:07, 17 December 2014
In optimization theory, maximum flow problems involve finding a feasible flow through a single-source, single-sink flow network that is maximum.
The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.
Contents
History
The maximum flow problem was first formulated in 1954 by T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow.^{[1]}^{[2]}^{[3]} In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm.^{[4]}^{[5]}
Over the years, various improved solutions to the maximum flow problem were discovered, notably the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the push-relabel algorithm of Goldberg and Tarjan; and the binary blocking flow algorithm of Goldberg and Rao. The electrical flow algorithm of Christiano, Kelner, Madry, and Spielman finds an approximately optimal maximum flow but only works in undirected graphs.^{[6]}^{[7]}
Definition
Let be a network with being the source and the sink of respectively.
- The capacity of an edge is a mapping , denoted by or . It represents the maximum amount of flow that can pass through an edge.
- The value of flow is defined by , where is the source of . It represents the amount of flow passing from the source to the sink.
The maximum flow problem is to maximize , that is, to route as much flow as possible from to .
Solutions
We can define the Residual Graph, which provides a systematic way to search for forward-backward operations in order to find the maximum flow.
Given a flow network , and a flow on , we define the residual graph of with respect to as follows.
1. The node set of is the same as that of .
2. Each edge of is with a capacity of .
3. Each edge of is with a capacity of .
The following table lists algorithms for solving the maximum flow problem.
Method | Complexity | Description |
---|---|---|
Linear programming | Constraints given by the definition of a legal flow. See the linear program here. | |
Ford–Fulkerson algorithm | O(E max| f |) | As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path.
The algorithm works only if all weights are integers. Otherwise it is possible that the Ford–Fulkerson algorithm will not converge to the maximum value. |
Edmonds–Karp algorithm | O(VE^{2}) | A specialization of Ford–Fulkerson, finding augmenting paths with breadth-first search. |
Dinic's blocking flow algorithm | O(V^{2}E) | In each phase the algorithms builds a layered graph with breadth-first search on the residual graph. The maximum flow in a layered graph can be calculated in O(VE) time, and the maximum number of the phases is n-1. In networks with unit capacities, Dinic's algorithm terminates in time. |
General push-relabel maximum flow algorithm | O(V^{2}E) | The push relabel algorithm maintains a preflow, i.e. a flow function with the possibility of excess in the vertices. The algorithm runs while there is a vertex with positive excess, i.e. an active vertex in the graph. The push operation increases the flow on a residual edge, and a height function on the vertices controls which residual edges can be pushed. The height function is changed with a relabel operation. The proper definitions of these operations guarantee that the resulting flow function is a maximum flow. |
Push-relabel algorithm with FIFO vertex selection rule | O(V^{3}) | Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations until the excess is positive or there are admissible residual edges from this vertex. |
Dinic's algorithm | O(VE log(V)) | The dynamic trees data structure speeds up the maximum flow computation in the layered graph to O(Elog(V)). |
Push-relabel algorithm with dynamic trees | O(VE log(V^{2}/E)) | The algorithm builds limited size trees on the residual graph regarding to height function. These trees provide multilevel push operations. |
Binary blocking flow algorithm^{[8]} | The value U corresponds to the maximum capacity of the network. | |
MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm | O(V^{3}) | Refer to the Original Paper. |
Jim Orlin's + KRT (King, Rao, Tarjan)'s algorithm | O(VE) | Orlin's algorithm solves max-flow in O(VE) time for while KRT solves it in O(VE) for |
For a more extensive list, see^{[9]}
Integral flow theorem
The integral flow theorem states that
- If each edge in a flow network has integral capacity, then there exists an integral maximal flow.
Application
Multi-source multi-sink maximum flow problem
Given a network N = (V,E) with a set of sources S = {s_{1}, ..., s_{n}} and a set of sinks T = {t_{1}, ..., t_{m}} instead of only one source and one sink, we are to find the maximum flow across N. We can transform the multi-source multi-sink problem into a maximum flow problem by adding a consolidated source connecting to each vertex in S and a consolidated sink connected by each vertex in T (also known as supersource and supersink) with infinite capacity on each edge (See Fig. 4.1.1.).
Minimum path cover in directed acyclic graph
Given a directed acyclic graph G = (V, E), we are to find the minimum number of paths to cover each vertex in V. We can construct a bipartite graph G' = (V_{out}∪V_{in}, E' ) from G, where
- V_{out} = {v∈V: v has positive out-degree}.
- V_{in} = {v∈V: v has positive in-degree}.
- E' = {(u,v)∈V_{out}×V_{in}: (u,v)∈E}.
Then it can be shown, via König's theorem, that G' has a matching of size m if and only if there exists n-m paths that cover each vertex in G, where n is the number of vertices in G. Therefore, the problem can be solved by finding the maximum cardinality matching in G' instead.
Maximum cardinality bipartite matching
Given a bipartite graph G = (X∪Y, E), we are to find a maximum cardinality matching in G, that is a matching that contains the largest possible number of edges. This problem can be transformed into a maximum flow problem by constructing a network N = (X∪Y∪{s,t}, E' }, where
- E' contains the edges in G directed from X to Y.
- (s,x)∈E' for each x∈X and (y,t)∈E' for each y∈Y.
- c(e) = 1 for each e∈E' (See Fig. 4.3.1).
Then the value of the maximum flow in N is equal to the size of the maximum matching in G.
Maximum flow problem with vertex capacities
Given a network , in which there is capacity at each node in addition to edge capacity, that is, a mapping , denoted by , such that the flow has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint
In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across , we can transform the problem into the maximum flow problem in the original sense by expanding . First, each is replaced by and , where is connected by edges going into and is connected to edges coming out from , then assign capacity to the edge connecting and (see Fig. 4.4.1, but note that it has incorrectly swapped and ). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem.
Maximum edge-disjoint path
Given a directed graph G = (V, E) and two vertices s and t, we are to find the maximum number of edge-disjoint paths from s to t. This problem can be transformed to a maximum flow problem by constructing a network N = (V, E) from G with s and t being the source and the sink of N respectively and assign each edge with unit capacity.
Maximum independent (vertex-disjoint) path
Given a directed graph G = (V, E) and two vertices s and t, we are to find the maximum number of independent paths from s to t. Two paths are said to be independent if they do not have a vertex in common apart from s and t. We can construct a network N = (V, E) from G with vertex capacities, where
- s and t are the source and the sink of N respectively.
- c(v) = 1 for each v∈V.
- c(e) = 1 for each e∈E.
Then the value of the maximum flow is equal to the maximum number of independent paths from s to t.
Real world applications
Baseball Elimination
In the Baseball Elimination Problem there are n teams competing in a league. At a specific stage of the league season, w_{i} is the number of wins and r_{i} is the number of games left to play for team i and r_{ij} is the number of games left against team j. A team is eliminated if it has no chance to finish the season in the first place. The task of Baseball Elimination Problem is to determine which teams are eliminated at each point during the season. Schwartz^{[10]} proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team k is eliminated.
Let G = (V, E) be a network with s,t ∈ V being the source and the sink respectively. We add a game node {i,j} with i < j to V, and connect each of them from s by an edge with capacity r_{ij} — which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {i,j} with to team nodes i and j to ensure one of them wins. We do not need to restrict the flow value on these edges. Finally, we make edges from team node i to the sink node t and set the capacity of w_{k}+r_{k}–w_{i} to prevent team i from winning more than w_{k}+r_{k}. Let S be the set of all team participating in the league and let . In this method it is claimed team k is not eliminated if and only if a flow value of size r(S - {k}) exists in network G. In the mentioned article it is proved that this flow value is the maximum flow value from s to t.
Airline scheduling
In the airline industry a major problem is the scheduling of the flight crews. Airline scheduling problem could be considered as an application of extended maximum network flow. The input of this problem is a set of flights F which contains the information about where and when each flight departs and arrives. In one version of Airline Scheduling the goal is to produce a feasible schedule with at most k crews.
In order to solve this problem we use a variation of circulation problem called bounded circulation which is the generalization of network flow problems, with the added constraint of a lower bound on edge flows.
Let G = (V, E) be a network with s,t ∈ V as the source and the sink nodes. For the source and destination of every flight i we add two nodes to V, node s_{i} as the source and node d_{i} as the destination node of flight i. We also add the following edges to E:
- An edge with capacity [0, 1] between s and each s_{i}.
- An edge with capacity [0, 1] between each d_{i} and t.
- An edge with capacity [1, 1] between each pair of s_{i} and d_{i}.
- An edge with capacity [0, 1] between each d_{i} and s_{j}, if source s_{j} is reachable with a reasonable amount of time and cost from the destination of flight i.
- An edge with capacity [0, ∞] between s and t.
In the mentioned method, it is claimed and proved that finding a flow value of k in G between s and t is equal to finding a feasible schedule for flight set F with at most k crews.^{[11]}
Another version of Airline Scheduling is finding the minimum needed crews to perform all the flights. In order to find an answer to this problem we create a bipartite graph G’ = (A ∪ B, E) where each flight has a copy in set A and set B. If the same plane can perform flight j after flight i, connect i∈A to j∈B. A matching in G’ induces a schedule for F and obviously maximum bipartite matching in this graph produces the an airline schedule with minimum number of crews.^{[11]} As it is mentioned in the Application part of this article, the maximum cardinality bipartite matching is an application of maximum flow problem.
Circulation-demand problem
There are some factories that produce goods and some villages where the goods have to be delivered. They are connected by a networks of roads with each road having a capacity for maximum goods that can flow through it. The problem is to find if there is a circulation that satisfies the demand. This problem can be transformed into a max-flow problem.
- Add a source node and add edges from it to every factory node with capacity where is the production rate of factory .
- Add a sink node and add edges from all villages to with capacity where is the demand rate of village .
Let G = (V, E) be this new network. There exists a circulation that satisfies the demand if and only if :
If there exists a circulation, looking at the max-flow solution would give us the answer as to how much goods have to be send on a particular road for satisfying the demands.
Fairness in car sharing (carpool)
The problem exactly is that people are pooling a car for days. Each participant can choose if he participates on each day. We aim to fairly decide who will be driving on a given day.
The solution is the following:
We can decide this on the basis of the number of people using the car i.e.; if people use the car on a day, each person has a responsibility of . Thus, for every person , his driving obligation as shown. Then person is required to drive only times in days.
Our aim is to ﬁnd if such a setting is possible. For this we try to make the problem as a network,
as we can see in the ﬁgure.
Now, it can be proved that if a ﬂow exists then such a fair setting exists and such a ﬂow of value always exists.
See also
References
- ↑ Template:Cite doi
- ↑ Template:Cite doi
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Cite doi
- ↑ Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
- ↑ Template:Cite doi
- ↑ Template:Cite web
- ↑ Template:Cite doi
- ↑ Template:Cite doi
- ↑ Template:Cite doi
- ↑ ^{11.0} ^{11.1} {{#invoke:citation/CS1|citation |CitationClass=book }}
Further reading
- {{#invoke:Citation/CS1|citation
|CitationClass=journal }}
- {{#invoke:Citation/CS1|citation
|CitationClass=journal }}
- {{#invoke:citation/CS1|citation
|CitationClass=book }}