The concept of flow is, like that of matching, another of the major concepts of graph theory. It has an interesting algebraic aspect and has many major applications, such as transportation problems.

1.1 Flows in transportation networks

A transportation network R is defined as: a strict connected digraph G =(X,A) with two disjoint sets, S ⊆ X, the set of the sources and T ⊆ X, the set of the sinks, and a weighting of the arcs, c : A → N (natural numbers), called the capacity. We will also allow the (positive) value ∞ as the capacity of an arc.

Let us specify a few points of terminology and notation. For a ∈ A, c(a) is the capacity of arc a. The vertices of X (S ∪ T) are called intermediate vertices. For Z ⊆ X we denote as ω+(Z) the set of the arcs of G of the form (x, y)with x ∈ Z and y/ ∈ Z, and ω−(Z) the set of the arcs of the form  (x, y) with x/ ∈ Z and y ∈ Z. The arcs of ω+(Z) are the arcs exiting from Z and those of ω−(Z) are the arcs entering into Z. When Z = {x},we talk of arcs entering into x and exiting from x.

A flow in a transportation network R is a mapping f : A → N verifying:

This second condition is called the law of flow conservation for each intermediate vertex, also known in electricity as Kirchhoff’s law.

For the general case

Let us specify that if ω⁺(Z)= ∅ then f⁺(Z) = 0, likewise for ω⁻(Z)and f⁻(Z). Furthermore, in the case Z = {x} we will write f⁺(x)  instead of f⁺({x}), and likewise for f⁻(x). Condition 2 can also be written as:

We add the following condition which assigns the vertices of S as “sources” and the vertices of T as “sinks” with regard to the flow:

Figure 1.1 gives an example of a flow in a transportation network.

Figure 8.1. In this representation of a transportation network, the capacities of the arcs are given between brackets. We have here S = {s₁,s₂,s₃} and T = {t₁,t₂}. A flow is given by the values indicated to the left of the capacities of each arc. These representation conventions also apply to the figures which follow

Note. In any network, there is always what is called the zero flow, meaning the flow taking value 0 on each arc.

1.1.1 Interpretation

A network such as the one in Figure 1.1 can be interpreted as, for example, a network for transporting goods or a water transportation system.

Sources s₁, s₂,and s₃ are then production or supply centres, from which the flow starts (and to which it may return). Sinks t₁ and t₂ are centers where some flow is consumed (it may also start again from there). The following result, very intuitive but not completely self-evident to prove, introduces the concept of the value of flow transiting in the network.

Lemma 1.1. We have, using the previous notations:

Proof. We can write successively:

The sum over X (S ∪ T) is zero according to condition 2’ of the definition of flows. The equality

of course has to be verified (which is easy) as well as the equivalent one for T.

We can verify in the example in Figure 8.1 that we really have this equality.

        Let us call net flow out of Z ⊂ X the quantity f⁺(Z) − f⁻(Z), and net flow into Z the quantity f⁻(Z)−f⁺(Z). Lemma 1.1 states that the net flow out of S is equal to the net flow into T. This result is obviously based on the property of conservation of the flow at the intermediate vertices. This common value f⁺(S) − f⁻(S)= f⁻(T) − f⁺(T) is called the value of flow f, and denoted as v(f). The problem dealt with in this chapter is that of maximum flow, that is, of finding in a network a flow with the greatest possible value.

1.1.2 Single-source single-sink networks

Assume that |S| = |T| = 1. We will denote by s the single source and by t the single sink of the network. In fact, we can, without losing generality,  always suppose that this is the case. In addition, it is also possible to impose the condition that there are no arcs entering into s, nor exiting from t, so that s is a single source vertex and t a single sink vertex in the digraph of the network. Let us justify this.

         Let R be a network such as that defined above. Let us put S = {s₁,s₂,...,s_p} and T = {t₁,t₂,...,t_q}. Let us add to this network a vertex s with an arc (s, s_i) of capacity ∞ for each of the vertices s_i (i =1, 2,...,p), and a vertex t with an arc (t_j ,t) of capacity ∞ for each of the vertices t_j  (j =1, 2,...,q). Let us denote by Rthe network thus obtained with sets of sources and of sinks S^/= {s} and T^/= {t}. Therefore it is a single-source single-sink network. It is possible to verify that any flow of R corresponds to a flow of Rof the same value and vice versa. Indeed, if f is a flow of R,

let us define f^/in the following way:

Thus, the vertices of S and T in R become in R^/intermediate vertices, where the flow conservation law is respected. For all the other arcs of R^/ the value of f^/is taken to be equal to that of f. It is easy to verify that a flow f of R^/is thus truly defined, and that this flow has an equal value  to that of f. Note in particular that the values of f^/ are reall y ≥ 0 on the arcs added to R as a result of condition 3 of the definition of flows.

     Conversely, given a flow R^/, we can directly deduce from it a flow in R, of the same value, by considering its restriction to the arcs of R.

In the case of a flow in a network with a single source s and a single sink t, the value of flow f is v(f)= f⁺(s)= f⁻(t) because, since there are no arcs entering into s nor exiting from t, we have f⁻(s)=0and f⁺(t)=0.

Figure 1.2. Network of Figure 1.1 modified to become a single-source single-sink network

Figure 1.2 gives network R corresponding to network R of Figure 1.1.

Note. By adding to the network an arc (t, s), of capacity ∞, we obtain a network in which the law of conservation of the flow applies at any vertex.

__________________________________________________________________________________

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(173-177)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength