14 Digraphs and Networks

Theorem 14.1

In a general digraph the sum of the indegrees of the vertices equals the sum of the outdegrees, and each is equal to the number of arcs.

Theorem 14.2

Let \(D\) be a connected digraph. Then \(D\) has a closed Eulerian directed trail if and only if the indegree of each vertex equals the outdegree.

Theorem 14.3

Let \(D\) be a connected digraph and let \(x\) and \(y\) be distinct vertices of \(D\). Then there is a directed Eulerian trail from \(x\) to \(y\) if and only if (i) the outdegree of \(x\) exceeds its indegree by 1 ; (ii) the indegree of \(y\) exceeds its outdegree by 1 ; (iii) for each vertex \(z \neq x, y\), the indegree of \(z\) equals its outdegree.

Theorem 14.4

Let \(D\) be a strongly connected digraph without any loops. If, for each vertex \(x\), we have

\[ (\text{ outdegree of } x)+(\text{ indegree of } x) \geq n, \]

then \(D\) has a directed Hamilton cycle.

Theorem 14.5

Every tournament has a Hamilton path.

Theorem 14.6

Let \(G = (V, E)\) be a connected graph. Then \(G\) has a strongly connected orientation if and only if \(G\) does not have any bridges.

Lemma 14.7

Let \(D\) be a digraph in which each vertex has outdegree at least \(l\). Then there is a directed cycle in \(D\).

Corollary 14.8

Let \(X\) be a set of \(n\) elements and let \(f: X \rightarrow X\) be a one-to-one function. Let \(D_f=\left(X, A_f\right)\) be the digraph whose set of arcs is

\[ A_f=\{ (x, f(x)): x \text{ in } X\} \]

Then the arcs of \(D_f\) can be partitioned into directed cycles with each vertex belonging to exactly one directed cycle.

Theorem 14.9

Every trading problem has a core allocation.

Lemma 14.10

Let \(f\) be a flow in the network \(N=(V, A, s, t, c)\) and let \(U\) be a set of vertices containing the source \(s\) but not the target \(t\). Then

\[ \sum \limits _{\alpha \in \vec{U}} f(\alpha )-\sum \limits _{\alpha \in \overleftarrow {U}} f(\alpha )=\sum \limits _{\iota (\alpha )=s} f(\alpha )-\sum \limits _{\tau (\alpha )=s} f(\alpha ) \]

Lemma 14.11

Let \(N=(V, A, s, t, c)\) be a network with \(C\) a minimal cut. Let U be the set of all vertices \(x\) for which there exists a path from the source \(s\) to \(x\) thal contains no arc in \(C\). Then \(\vec{U}\) is a cut and \(C=\vec{U}\).

Theorem 14.12

Let \(N=(V, A, s, t, c)\) be a network. Then the maximum value of a flow in \(N\) equals the minimum capacity of a cut in \(N\). In other words, the value of a maximum flow equals the capacity of a minimum cut. If the capacities of all the arcs are integers, then there is a maximum flow all of whose values are integers as well.

Theorem 14.13

Let \(s\) and \(t\) be distinct vertices of a digraph \(D = (V, A)\). Then the maximum number of pairwise arc-disjoint paths from \(s\) to \(t\) equals the minimum number of arcs in an st-separating set.

Theorem 14.14

Let \(G\) be a bipartite graph. Then \(\rho (G) =c(G)\).

Theorem 14.15

Let \(M\) be a matching in the bipartite graph \(G\). Then \(M\) is a max-matching if and only if there does not exist an \(M\)-alternating path.

Theorem 14.16

Assume that nonbreakthrough has occured in the matching algorithm. Let \(X^{u n}\) consist of all the unlabeled vertices of \(X\), let \(Y^{\text{lab }}\) consist of all the labeled vertices of \(Y\), and let \(S=X^{u n} \cup Y^{l a b}\). Then both of the following hold: (i) \(S\) is a min-cover of the bipartite graph \(G\); (ii) \(|M|=|S|\) and \(M\) is a max-matching.