Flow network

Flows and cuts in networks are structures graph theory, which have many uses.

• 2.1 Max -flow algorithms after publication

• 5.1 Practical Applications
• 5.2 Theoretical Applications

Definitions of important terms and characteristics

Network

A network (English network) consists of a directed graph with two distinguished nodes ( engl. vertex / vertices ), a source (german source) and a sink (English target) of, and a capacity function that each edge a non-negative capacity assigns. Has the capacity function only integer values ​​, then there exists a maximum flow function (as defined below ), which also has only integer values.

Flow

Example of a residual network. On the path, can the river to augment the value 2.

A flow is a function, which assigns to each edge on the network a non-negative flow value. The following condition must be met:

The flow rate value on an edge is at most as large as the capacitance of the edge, that is, it is:

.

If in addition the following condition is fulfilled, ie the river - River:

Apart from the source s and the sink t in each node must flow into just as much as it flows, that is:

It is

The amount of and leading into

The amount of the addition of leading edges.

Also applies river receipt in and, you have a flow or circulation. One can show that the incidence vectors corresponding to a circulation if they are in the cycle space of.

Value

The value of - is the excess flux in the node or the amount of the surplus in the node.

In formulas:

For all - rivers of the surplus down to zero for all nodes. For all circulations he is also zero.

Excess

The excess of a node, also called net or flow or excess, is the difference between the sum of the flow values ​​of the incoming edges, and the sum of the flow rates of the outgoing edges.

Section

A proper subset of the nodes in a network, but does not contain, is called a - section. Under a section is often also the set of all edges understood that extend between the partitions. The capacity of a section is the sum of the capacities of the edges extending from to.

Sections give an upper bound on the value of the - rivers. The Max -flow min-cut theorem states that reversed flow values ​​are a lower bound for sectional capacities. So both concepts correspond to each other in a natural way.

Residual network

The residual network, or residual network, to the river with Residualgraphen and Residualkapazitäten indicates the remaining capacity of the network. The Residualgraph has the same vertex set as and consists of the complements of underutilized edge to rear edge: For each edge contains a back edge. The Residualkapazitäten provide for an edge on how much of the flow can be increased to her, and for a return edge to how much of the flow may be reduced to the corresponding Hinkante. So:

If

Algorithmic construction of a Residualnetzwerks

Initialize; ; 1 for all edges 2 if () 3 Add in a 4 Set 5 if () 6 Add in a 7 Set 8 give out Layer network

The level of a node is the number of edges of a shortest path from the residual network according to the river. The -th level of a graph is the set of all nodes at level so. An edge with flow value is called useful from to, if. If true, it's called useful from to. An edge is useful in an amount, if the amount of an element is useful for an element outside the set. Analogously, explains useful in a lot. The network layer or network level to the river is a subgraph of with

Layer and residual network can be computed in linear runtime.

Special paths and rivers

An xy - path or path is a sequence of edges, the output node of each edge of the end nodes of its predecessor. The length of a path, and the number of edges in the path.

The distance between and the length of a shortest path, if one exists, and "infinite" if not. A Walk in the residual network is called augmenting path; the names -improving path or enhancing road are also common. Everyone - River can be divided into rivers - paths and disassemble circles. Just when in a network to a - River there is no augmenting path, the river has maximum value. These facts make use of the algorithm of Ford and Fulkerson and the algorithm of Edmonds and Karp.

A flow in a network is called nonblocking if every - blocked path in an edge, or saturated, is, that.

- > Requirements: has excess, and -> Description: Slide                Units of flow by 1 2 3 4 5 Lift procedure Requirements: has excess and it applies to any:                    Description: increment the amount of 1 Präflüsse

- Präflüsse, or Vorflüsse, (English Preflow ) are a generalization of - rivers. This term is only in more complex ( and much more efficient ) flow algorithms of importance.

A - Präfluss is a function of capacity conformity as above and the following weakening of the flow preservation:

This means that only the nodes may leave more river when reached him. A - Präfluss has surplus in a knot, or even overflow if its surplus (as above) is strictly greater than zero. The residual network is formed analogously to above.

The height function or distance marker in a network - Präfluss with an image and for all edges.

Furthermore, it explains the operations push and lift algorithmically, as described on the right. By these means one can create and examine Preflow -push algorithms, such as the Goldberg - Tarjan algorithm ( according to Andrew Goldberg and Robert Tarjan ). These algorithms can be the data structures while the algorithm does not run as - River interpret. The method of Goldberg and Tarjan initializes a Präfluss and terminate if certain manipulations of a structure - supply flow. That's always there after finitely many steps the case, and this - flow is then always maximum.

Algorithms

The algorithm of Ford and Fulkerson studied gradually augmenting paths, ie paths in the residual network, and increases along there. This method works if and only if this algorithm terminates, so come into the situation, that there is indeed no augmenting paths more. Then we can consider the maximum achievable by Residualnetz from the node-set. This defines a - cut whose capacity equals the flow value.

To secure the scheduling but, one can use an argument about the algebraic structure of the capacitance values ​​. Are there non-negative integers, the value of a maximum is - the river is an integer. In addition, there are at least a maximum st- flow that only accepts integer values ​​edgewise. For each maximum st- flow must not be the case. Because each augment along a - the value of the path - increased flow by an integer step, ie at least 1, the termination is secured after finitely many steps in the case. An upper limit of the running time of the algorithm can then depend on the values ​​of the capacitances. The running time can be arbitrary large in terms of number of nodes and edges, depending on the capacity are given on the edges. Are non-negative rational number capacity, Ford- Fulkerson algorithm terminates also because the network is then algorithmically equivalent to a network, wherein the capacity is multiplied by the denominator, that occur only integer capacity. For real, irrational capacities of the algorithm, however, does not have to terminate and not even against a maximum - converging flow.

The Edmonds - Karp algorithm is a further development of the method of Ford and Fulkerson is: It works quite analogous, but look for augmenting paths, the number of edges are minimal with respect. That goes with a breadth-first search, respectively in linear runtime. The Edmonds - Karp algorithm terminates even with arbitrary real edge capacities. In addition, its duration, so is generally an order of magnitude significantly better than the Ford - Fulkerson algorithm.

The Dinic algorithm is based on a further observation. If you search the residual network after an augmenting path, it may happen that one gets into dead ends, ie to a node from which could not be reached. The idea is to stratify the network, ie to group together to have the same distance, ie those dead ends are eliminated. In this layer networks, you would try out, furthermore, that a search not only provides a way but always without any extra effort a Wegbaum. Along this tree you can then send the river and block the network. This is all elementary in a modified depth-first search. In the next iteration is then the situation requiring at least one more layer, because the old layering is blocked. The argument for limiting the number of layers to a maximum piece provides a bound on the number of so-called phase runs of the algorithm, ie the number of loop iterations. This results in a term of.

The following table gives an overview of the flow algorithms developed and their maturities:

Max - Flow algorithms after publication

• "Number of nodes "
• " Number of edges "
• "Maximum capacity function"

Formulations as a linear program

The problem is to maximize the flow value can be also described as a linear optimization problem. If one chooses, for example, a variable for each edge, which measures the flow on the edge, the result is the following program:

An alternative formulation is obtained when for each - introduces a variable path, which refers to the river on the appropriate path. It results from the following program:

It denotes the set of all paths from to.

The second formulation will initially unfavorable because the number of - paths generally grows exponentially with the number of nodes and edges. Nevertheless, this formulation can be more efficient, ie solved by column generation in polynomial time.

The two formulations have the additional property that the matrices which describe the constraints, are totally unimodular. Thus any optimal solution of the two programs is an integer, if the capacities are integers.

It is also instructive to look at the Dualisierungen the above programs. For the path-based formulation, the dual program is, for example, is given by:

The dual program is also totally unimodular. This implies that the optimal solution of the dual program is a vector with entries. For each admissible vector also corresponds to the amount of one - cut. Thus, the optimal solution of the dual program corresponds to a - average minimum capacity. It follows from the strong duality theorem of linear programming, the Max -Flow Min -Cut Theorem.

Generalizations

There are some significant generalizations to the problem. First, you can instead of flows between a source or sink such regard between areas. To this is added a certain amount of suppliers and a lot of receivers before, as well as a graph and capacities. The problem is not harder than Max - flow and can be reduced by either pre-and downstream connection of additional node or transition to the quotient graph on Max - Flow.

On the other hand, one can extend the validity of the edges assigned capacity at a certain vicinity of the edge, for a detained an environment is the set of nodes and edges, the elements of the edge are removed. The Spezielfall just corresponds to the maximum flow problem. The case corresponds to the maximum flow problem with node capacities. This can be reduced to Max - Flow by the nodes are replaced by a structure as shown in Fig. The number of edges is not changed constantly, so increases the complexity of the problem. However, there are solutions for Max- Flow, whose complexity strictly dependent on the node, the number of which varies at most by a constant factor of 2.

In the event you can prove that the problem is NP-complete, and therefore probably not in polynomial time solvable (unless ). In the case of a polynomial-time algorithm has been found.

Application

Practical Applications

This last generalization is motivated by problems in the wiring of VLSI chips, where it is expensive to put in a certain proximity of cables down further.

The flow theory has developed historically from problems from the application. In general, it is assumed that the situation is a fluid, ie an arbitrarily decomposable into sub- objects subject to shift spatially through a world in various ways - for example electrical energy via a power network from a source to a required site, or data through a data network from a sender to a receiver. " Know each other " too abstract objects as can be modeled. By maximal flows in a social network you can then obtain a measure of how strongly two ( sets of) individuals are linked to each other.

Theoretical applications

An obvious and natural applications, the flow theory in the Transversalentheorie that can be embedded in the theory of flows in a very natural way. A comprehensive approach to do that, Ford in 1962 formulated in a standard work.

Many combinatorial problems on graphs, such as bipartite matching, can be easily converted into a suitable flow problem (see picture) and trigger quickly. Another application is the efficient determination of the context node number, edge-connectivity number or arc connection speed. By the lemma of Tutte (after William Thomas Tutte ) applications also extended flow theory ( so-called gruppenwertigen rivers ) and Färbbarkeitsaussagen become clear. Some guesses of it to the existence of k-flows in planar graphs have strong theoretical implications.