Technical Terms:
adjacent, arc, bridge, closed walk, component, condensation, cut, cycle, directed graph, distance, flow, indegree, length of walk, mixed multigraph, multigraph, mutually reachable, outdegree, path, reachable, semicycle, semipath, semiwalk, sink, source, spanning walk, strongly connected, strongly orientable, subgraph, underlying multigraph, unilaterally connected, walk, weakly connected, weight.
Link to Chapter 3.
A particularly useful property that a graph can have is that of being connected. The basic structure of connected and disconnected directed graphs is developed below. A directed graph D, or digraph, consists of a finite set V of nodes and a collection of ordered pairs of distinct nodes. Any such pair (u,v) is called an arc and is generally denoted as uv. The arc uv goes from u to v and is incident with u and v. To reflect the orientation, we say that u is adjacent to v and v is adjacent from u. The outdegree od(v) of a node v is the number of nodes adjacent from it, and the indegree id(v) is the number of nodes adjacent to it.
Each walk is directed from the first node v0 to the last vt. A concept for directed graphs that is free from orientation is that of the "semi" routes:
Unlike a graph, which is either connected or it is not; a digraph may be connected in one of three different ways.
Theorem 3c.1. (Digraph Connectivity Theorem)
Proof: The ‘if’ parts of each of a), b), c) are clear. It remains to prove the ‘only if’ parts.
c) Suppose D is weak. Let the nodes of D be v1, ..., vn, chosen in such an order that there is a semipath from v1 to v2, from v2 to v3, ..., and vn-1 to vn. Joining the semipaths gives a spanning semiwalk from v1 to vn.
b) Now suppose D is unilateral. This time choose an ordering v1, ..., vn for the nodes of D so there is a path from vi to vi+1 for i = 1, ..., n-1. Joining these paths gives a spanning walk.
a) Let D have nodes v1, ..., vn. Choose paths from vi to vi+1 for i = 1, ..., n-1 and a path from vn to v1. Join them together to get the required closed walk.
There are three different kinds of components of a digraph corresponding to the three different styles of connectivity in a digraph.
Note that every node and arc of a digraph lies in exactly
one weak component and in at least one unilateral component. Each node lies in
exactly one strong component, and an arc lies in some strong component or none,
depending on whether or not it is part of a cycle.
Strong components can be used to produce a new, simpler, digraph that retains some of the structural properties of the original digraph. The interested reader might consider underlying similarities between graphical and meteorological condensation.
Suppose a digraph D has strong components S1, S2, ..., Sn. A new graph D*, called the condensation of D, has nodes S1, ..., Sn and arcs SiSj whenever there is an arc in d from a node of Si to a node of Sj.
Since strong components are maximal, D* can have no cycles. Also, if D is strong, then D* is trivial.
Theorem 3c.2. A digraph D is unilateral if and only if its condensation D* has a spanning path.
Since D* has no cycles, any such spanning path must be unique. Hence
Corollary 3c.2.1. A digraph is unilateral if and only if its condensation has a unique spanning path.
Proof of Theorem 3c.2.
⇐ Suppose there exists a unique spanning path in D*, the condensation of D. Without loss of generality suppose the path is S1, e1, S2, e2, ..., Sn-1, en-1, Sn where ei is the arc uivi.
Now let u, v be nodes of D. If u, v are in the same strong component, each is reachable from the other. So suppose u∈ Sa, v ∈ Sb, a < b.
Then there are paths from
u to ua (both are in Sa),
ua to va (an arc)
va to ua+1 (both are in Sa+1)
...
vb-1 to v (both are in Sb).
Joining these paths together shows v is reachable from u.
⇒ Now suppose the digraph D is unilaterally connected. The proof is by induction on the number n of components in D*.
If n = 1, D* is trivial, and so is the result.
Suppose n = 2. Let u∈S1, v∈S2. Since D is unilateral, one is reachable from the other. Suppose, without loss of generality, that v is reachable from u. The path from u to v must contain at least one arc a,b with a∈S1, b∈S2, since u and v are in different components. Thus there is a path of length 1 from S1 to S2 in D*.
Now suppose the theorem is true for all digraphs with fewer than n components, and suppose D* has n > 2 components. Without loss of generality, assume there is a path P from S1 to Sn-1, and that the components have been ordered so that the nodes on the path occur in the order S1, S2, ..., Sn-1. Let u∈Sn.
Case 1. Suppose u is reachable from some node in Sn-1. Then there is some edge a, b on the path with a∈ Sn-1, b∉Sn-1. If b∈ Si for some i, 1 ≤ i < n-1, then there is an edge in D* from Sn-1 to Si, contradicting the fact that D* has no cycles. Thus b∈ Sn, and there is an arc from Sn-1 to Sn. Joining this arc to the end of P gives the desired spanning path.
Case 2. Suppose some node in S1 is reachable from u. A similar argument to Case 1 shows that there is an arc from Sn to S1, and joining it to the beginning of P gives the desired spanning path.
Case 3. Suppose neither of Cases 1 and 2 happen, and that i is the smallest integer for which an element of Si is reachable from u (since Case 1 is excluded, i ≤ n, and since Case 2 is excluded, i > 1).
Then u is reachable from any element of Si-1. As in Cases 1 and 2, there is an arc from Si-1 to Sn, and there is an arc from Sn to Si. Replacing the arc Si-1,Si in P by the path Si-1,Sn,Si gives the desired spanning path.
When this latter theorem is used on the digraphs labeled D1 and D2 (click here to see map), each has a single strong component and each then has a condensation composed of a unique spanning path: one with one edge and the other with two edges. Chirality was seen to be critical in avoiding collisions between flows in such unilateral digraphs (see animated figure).
When football games end at The University of Michigan, there is a need to move 100,000 fans away from the stadium at one time, as swiftly as possible through Ann Arbor (a city of just over 100,000 population). Harold Robbins was interested in the following problem: Can some streets be turned one-way to aid in funneling traffic out of town without destroying the ability to get anywhere in town?
A multigraph G is called strongly orientable if each edge of the multigraph can be given a direction in such a way that the resulting multidigraph is strongly connected. A bridge is an edge whose removal would disconnect the graph (multigraph).
Theorem 3c.3. Robbins's Theorem. A multigraph G is strongly orientable if and only if it is connected and has no bridges.
In fact, the city of Ann Arbor, Michigan only turns some streets one way, not all of them. So the graph that results has both directed and undirected edges. Boesch and Tindell (1980) generalized Robbins's ideas to this situation with what is called a mixed multigraph. Robbins's Theorem will be a corollary to the generalization.
The Boesch-Tindell generalization of Robbins's Theorem considers under what circumstances a strongly connected orientation of a mixed multigraph exists.
A mixed multigraph is connected if every pair of its nodes is mutually accessible from each other. If one fails in the attempt to strongly orient a graph, one might well be left with a mixed multigraph.
In the following figure (Figure 3c.1), six edges are oriented. When the process stops, the third edge from b to c could be oriented in either direction without affecting connectedness. However, there is no way to orient the edge from c to d without destroying two-way connectedness. Notice that the edge cd is a bridge of the underlying multigraph.
Figure 3c.1.
Theorem 3c.4. Robbins-Boesch-Tindell Theorem. Let e be an undirected edge of a connected mixed multigraph G. Then e may be directed to produce another connected mixed multigraph if and only if e is not a bridge of the underlying multigraph of G.
Proof: (Boesch and Tindell, 1980)
⇒ Clearly if e can be directed to produce a connected multigraph, e cannot be a bridge, since if e = uv and the orientation (u,v) leaves G connected, there must be another path from v to u.
⇐ The proof is of the contrapositive. That is, we show that if e cannot be oriented, then e is a bridge. Let e = uv.
Step 1. There are no walks from u to v in G - e. Suppose there were a walk W from u to v in G - e. Then setting the orientation of e as (v,u) would leave G strongly connected, since any occurrence of u,e,v in a walk of G could be replaced by W, so that e need not be traversed from u to v.
Step 2. Analogously, there are no walks from v to u in G - e.
Now let U be the set of nodes in G that are accessible from u in G - e. Let x∈U. Then u is accessible from x in G - e, since x is accessible from u in G, and were e required for this accessibility, v would be accessible from u in G - e, but that was excluded by Step 1.
If V is the set of all nodes in G, let Y = V - U. Notice that Y≠ Ø, since v∈Y.
It remains to show that e is the only edge of the underlying multigraph with one endnode in U and the other in Y. For then e will be a bridge.
Thus, the proof is concluded.
Applying this theorem recursively gives:
Theorem 3c.5. Robbins's Theorem for Mixed Multigraphs. A mixed multigraph G has a strongly connected orientation if and only if its underlying multigraph is connected and bridgeless.
Theorem 3c.3 is of course a special case of this theorem.
Consider a digraph that has no directed cycles. Such a digraph is called a acyclic.
Define a network N = (D,e) as follows.
For example, consider the following network (Figure 3c.2).
Figure 3c.2. This figure illustrates a network showing v as a source and w as a sink.
The weighted indegree of a node t is the sum of the weights of the arcs with terminal node t; similarly, the weighted outdegree of t is the sum of the weights of the arcs with initial node t. Thus, for example, S has weighted indegree 3, weighted outdegree 7.
A flow in N is a function f which assigns a new weight f(x) to each arc x in N so that
Here are two examples of flows for the network of Figure 3c.2.
The usual problem is to maximize flow. That is, one wants f(w) to be as large as possible. It seems that our second assignment maximized flow for this network. The outdegree (v) was only 8. All eight reached w: how could one achieve maximum flow in an arbitrary network? This was the problem solved by Ford and Fulkerson in 1956. A cut in a network is a set of arcs whose removal would disconnect the source from the sink. The capacity of a cut is the sum of the capacities of the arcs in the cut. A minimal cut is a cut of smallest possible capacity. For example, the cut {(u,w),(s,w)} has capacity 12 in Figure 5c.2. The minimal cut {(v,u),(v,r),(v,s)} has capacity 8.
Theorem 3c.6. Max-flow Min-cut Theorem. The value of the maximum flow through a network is equal to the capacity of a minimum cut.
While Ford and Fulkerson proved this theorem directly in 1956, it will be proved here in Chapter 4c (Wilson, 1972) as a Corollary to the much earlier Menger's Theorem. Many real-world problems involving networks consider the movement of flow across a network from a source to a sink. In the case of the Parisian Pneumatique, one might be interested in knowing what is the maximum flow, through tubing constructed as two-way tubing, across the river from the central office on the Left Bank to the central office on the Right Bank. Reasons for wishing to know this information might involve giving advice on increasing redundancy in connection, in order to increase transmission security, to municipal authorities. Figure 3c.3 shows the bidirectional connections in the Parisian Pneumatique as they were in 1907. We assign weights to direct paths from the central office on the Left Bank to the central office on the Right Bank. These weights are a function of size of offices (nodes) incident with edges: the larger the nodes, the larger the weight (assuming that larger offices can handle a larger volume of messages). The volume of flow that apparently can leave the left bank office (outdegree) has a weight of 4+3+3+3+3+=16. The volume of flow that apparently can enter the right bank office (indegree) has a weight of 3+4+3+3+4=17. However, the minimum cut contains edges with weights of 4, 1, 3, 3, 2 for a total of 13. Thus (by the Max-flow, Min-cut Theorem), the maximum flow is 13, and not 16 or 17 as one might have thought. Therefore, advice to municipal authorities might center on installing extra or expanded tubing to replace all tubes currently coded with a weight of 1 or 2; enlarging an already large tube incident with a central office would not supply the needed redundancy with optimum flow.
Figure 3c.3. This figure illustrates an application of the Max-flow, Min-cut Theorem to the Parisian Pneumatique of 1907.