University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

44

Pages:

2
Author:

Haylee Hardin

Euler Tours in Directed Graphs. The outdegree of node j is the number of arcs emanating from node j. The indegree is the number of arcs entering node j. An euler tour of a directed graph is a closed walk that passes through each arc of the graph exactly once. Theorem. A directed graph G = (N, A) has an euler tour if and only if the indegree of each node is equal to its outdegree, and the graph is connected. This if part of the theorem will be proved in exercises 8 and 9. 8. Suppose that the indegree of each node of G is equal to its outdegree, and the undirected version of G is connected. Show that G is strongly connected, that is, for each pair of nodes i and j, there is a directed path from i to j. (HINT: Assume it is not strongly connected. By the cutset theorem, there is a subset S of nodes with at least one arc directed from N\S to S and no arcs directed from S to N\S. Use this result to show that the indegree cannot equal the outdegree for each node, assuming G is connected.) Let T be a tree such that there is a path in T from each node j ≠ 1 to node 1. We can find such a tree using breadth first search on the graph obtained from G by reversing the direction of each arc, or using depth first search on the reversal of G. Note that for each node j ≠ 1, there is exactly one arc in T emanating from node j. T is called an in-tree, and is illustrated in Figure 2.10 b on page 30 of AMO. Consider the following rule for constructing an eulerian tour in G = (N, A) begin W := {1}; unmark all arcs in A while there is an unmarked arc in A do begin let v be the last node on W if there is a non-tree arc (v,j), then W := W, (v,j), j else choose (v,j) ∈ T and let W := W, (v, j), j mark arc (v,j); end end 9. Show that the above algorithm constructs an eulerian tour. HINTS: • Show that the walk constructed by the algorithm must end at node 1. • Show that if (v,j) ∈ T, then all other arcs incident to v precede (v,j) on W. • Let pred(i) be the predecessor of node i in the tree. (pred(i) is the path following i on the path from i to the root node of T). Suppose that j = pred(i). Show that the algorithm puts arc (i,j) on the walk before it puts (j, pred(j)). • Put the above three facts together to show that this algorithm constructs an eulerian tour. 10. Consider a circulation problem on a network G = (N, A), with costs vector c and capacity vector u. a. Suppose that there is a feasible flow x such that cx < 0, that is, the cost of the flow is negative. Use flow decomposition to prove that there is a directed cycle in G whose cost is negative. b. Can you conclude the following: the flow x = 0 is optimal for a circulation problem if and only if there is no cycle in G with negative cost?