A directed graph, also called a digraph, is a graph in which the edges have a direction. This is usually indicated with an arrow on the edge; more formally, if \(v\) and \(w\) are vertices, an edge is an unordered pair \(\\), while a directed edge, called an arc, is an ordered pair \((v,w)\) or \((w,v)\). The arc \((v,w)\) is drawn as an arrow from \(v\) to \(w\). If a graph contains both arcs \((v,w)\) and \((w,v)\), this is not a "multiple edge'', as the arcs are distinct. It is possible to have multiple arcs, namely, an arc \((v,w)\) may be included multiple times in the multiset of arcs. As before, a digraph is called simple if there are no loops or multiple arcs. We denote by \(E\strut_v^-\) the set of all arcs of the form \((w,v)\), and by \(E_v^+\) the set of arcs of the form \((v,w)\). The indegree of \(v\), denoted \(\text^-(v)\), is the number of arcs in \(E\strut_v^-\), and the outdegree, \(\text^+(v)\), is the number of arcs in \(E_v^+\). If the vertices are \(v_1,v_2,\ldots,v_n\), the degrees are usually denoted \(d^-_1,d^-_2,\ldots,d^-_n\) and \(d^+_1,d^+_2,\ldots,d^+_n\). Note that both \(\sum_^n \text^-_i\) and \(\sum_^n \text^+_i\) count the number of arcs exactly once, and of course \(\sum_^n \text^-_i=\sum_^n \text^+_i\). A walk in a digraph is a sequence \(v_1,e_1,v_2,e_2,\ldots,v_,e_,v_k\) such that \(e_k=(v_i,v_)\); if \(v_1=v_k\), it is a closed walk or a circuit. A path in a digraph is a walk in which all vertices are distinct. It is not hard to show that, as for graphs, if there is a walk from \(v\) to \(w\) then there is a path from \(v\) to \(w\). Many of the topics we have considered for graphs have analogues in digraphs, but there are many new topics as well. We will look at one particularly important result in the latter category.
A network is a digraph with a designated source \(s\) and target \(t\not=s\). In addition, each arc \(e\) has a positive capacity, \(c(e)\).
Networks can be used to model transport through a physical network, of a physical quantity like oil or electricity, or of something more abstract, like information.
A flow in a network is a function \(f\) from the arcs of the digraph to \(\mathbb\), with \(0\le f(e)\le c(e)\) for all \(e\), and such that \[\sum_
We wish to assign a value to a flow, equal to the net flow out of the source. Since the substance being transported cannot "collect'' or "originate'' at any vertex other than \(s\) and \(t\), it seems reasonable that this value should also be the net flow into the target. Before we prove this, we introduce some new notation. Suppose that \(U\) is a set of vertices in a network, with \(s\in U\) and \(t\notin U\). Let \(\overset<\longrightarrow>\) be the set of arcs \((v,w)\) with \(v\in U\), \(w\notin U\), and \(\overset<\longleftarrow>\) be the set of arcs \((v,w)\) with \(v\notin U\), \(w\in U\).
For any flow \(f\) in a network, the net flow out of the source is equal to the net flow into the target, namely, \[\sum_
The value of a flow, denoted \(\text(f)\), is \(\sum_
We next seek to formalize the notion of a "bottleneck'', with the goal of showing that the maximum flow is equal to the amount that can pass through the smallest bottleneck.
A cut in a network is a set \(C\) of arcs with the property that every path from \(s\) to \(t\) uses an arc in \(C\), that is, if the arcs in \(C\) are removed from the network there is no path from \(s\) to \(t\). The capacity of a cut, denoted \(c(C)\), is \[\sum_
Note that a minimum cut is a minimal cut. Clearly, if \(U\) is a set of vertices containing \(s\) but not \(t\), then \(\overset<\longrightarrow>\) is a cut.
Suppose \(C\) is a minimal cut. Then there is a set \(U\) containing \(s\) but not \(t\) such that \(C=\overset<\longrightarrow>\). Proof Let \(U\) be the set of vertices \(v\) such that there is a path from \(s\) to \(v\) using no arc in \(C\). Suppose that \(e=(v,w)\in C\). Since \(C\) is minimal, there is a path \(P\) from \(s\) to \(t\) using \(e\) but no other arc in \(C\). Thus, there is a path from \(s\) to \(v\) using no arc of \(C\), so \(v\in U\). If there is a path from \(s\) to \(w\) using no arc of \(C\), then this path followed by the portion of \(P\) that begins with \(w\) is a walk from \(s\) to \(t\) using no arc in \(C\). This implies there is a path from \(s\) to \(t\) using no arc in \(C\), a contradiction. Thus \(w\notin U\) and so \(e\in \overset<\longrightarrow>\). Hence, \(C\subseteq \overset<\longrightarrow>\). Suppose that \(e=(v,w)\in \overset<\longrightarrow>\). Then \(v\in U\) and \(w\notin U\), so every path from \(s\) to \(w\) uses an arc in \(C\). Since \(v\in U\), there is a path from \(s\) to \(v\) using no arc of \(C\), and this path followed by \(e\) is a path from \(s\) to \(w\). Hence the arc \(e\) must be in \(C\), so \(\overset<\longrightarrow>\subseteq C\). We have now shown that \(C=\overset<\longrightarrow>\).
Now we can prove a version of the important max-flow, min cut theorem.When this terminates, either \(t\in U\) or \(t\notin U\). If \(t\in U\), there is a sequence of distinct vertices \(s=v_1,v_2,v_3,\ldots,v_k=t\) such that for each \(i\), \(1\le i< k\), either \(e=(v_i,v_)\) is an arc with \(f(e)< c(e)\) or \(e=(v_,v_i)\) is an arc with \(f(e)>0\). Update the flow by adding \(1\) to \(f(e)\) for each of the former, and subtracting \(1\) from \(f(e)\) for each of the latter. This new flow \(f'\) is still a flow: In the first case, since \(f(e)< c(e)\), \(f'(e)\le c(e)\), and in the second case, since \(f(e)>0\), \(f'(e)\ge 0\). It is straightforward to check that for each vertex \(v_i\), \(1< i< k\), that \[\sum_
Eventually, the algorithm terminates with \(t\notin U\) and flow \(f\). This implies that for each \(e=(v,w)\) with \(v\in U\) and \(w\notin U\), \(f(e)=c(e)\), and for each \(e=(v,w)\) with \(v\notin U\) and \(w\in U\), \(f(e)=0\). The capacity of the cut \(\overset<\longrightarrow>\) is \[\sum_
The max-flow, min-cut theorem is true when the capacities are any positive real numbers, though of course the maximum value of a flow will not necessarily be an integer in this case. It is somewhat more difficult to prove, requiring a proof involving limits.
We have already proved that in a bipartite graph, the size of a maximum matching is equal to the size of a minimum vertex cover, Theorem 4.6.4. This turns out to be essentially a special case of the max-flow, min-cut theorem.
In a bipartite graph \(G\), the size of a maximum matching is the same as the size of a minimum vertex cover.
Proof
Suppose the parts of \(G\) are \(X=\
Let \(C\) be a minimum cut. If \((x_i,y_j)\) is an arc of \(C\), replace it by arc \((s,x_i)\). This is still a cut, since any path from \(s\) to \(t\) including \((x_i,y_j)\) must include \((s,x_i)\). Thus, we may suppose that \(C\) contains only arcs of the form \((s,x_i)\) and \((y_i,t)\). Now it is easy to see that \[K=\\cup\\nonumber\] is a vertex cover of \(G\) with the same size as \(C\).
Let \(f\) be a maximum flow such that \(f(e)\) is an integer for all \(e\), which is possible by the max-flow, min-cut theorem. Consider the set of edges \[M=\\vert f((x_i,y_j))=1\>.\nonumber\] If \(\\) and \(\\) are both in this set, then the flow out of vertex \(x_i\) is at least 2, but there is only one arc into \(x_i\), \((s,x_i)\), with capacity 1, contradicting the definition of a flow. Likewise, if \(\\) and \(\\) are both in this set, then the flow into vertex \(y_j\) is at least 2, but there is only one arc out of \(y_j\), \((y_j,t)\), with capacity 1, also a contradiction. Thus \(M\) is a matching. Moreover, if \(U=\
This page titled 5.11: Directed Graphs is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.
