Editing Maximum flow problem (section)

===Airline scheduling===
In the airline industry a major problem is the scheduling of the flight crews. The airline scheduling problem can 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.

To solve this problem one uses a variation of the [[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 {{math|''s'',''t'' ∈ ''V''}} as the source and the sink nodes. For the source and destination of every flight ''i'', one adds 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''. One also adds the following edges to ''E'':
# An edge with capacity [0, 1] between ''s'' and each ''s''<sub>''i''</sub>.
# An edge with capacity [0, 1] between each ''d''<sub>''i''</sub> and ''t''.
# An edge with capacity [1, 1] between each pair of ''s''<sub>''i''</sub> and ''d''<sub>''i''</sub>.
# An edge with capacity [0, 1] between each ''d''<sub>''i''</sub> and ''s''<sub>''j''</sub>, if source ''s''<sub>''j''</sub> 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.<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 = 978-0-262-03293-3 | pages=643–668| title-link=Introduction to Algorithms }}</ref>

Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph {{math|1={{var|G'}} = (''A'' ∪ ''B'', ''E'')}} is created where each flight has a copy in set ''A'' and set ''B''. If the same plane can perform flight ''j'' after flight ''i'', {{math|''i''∈''A''}} is connected to {{math|''j''∈''B''}}. A matching in {{mvar|G'}} induces a schedule for ''F'' and obviously maximum bipartite matching in this graph produces 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.