1 Graphs and state machines: 15 points

Theory Pig has gotten rather upset with all the abuse he’s received at the hands of the 6.042 staff. Theory Pig is working on world domination, and he’s decided that one of the first things he needs is an algorithm to convert an directed graph to an undirected graph through a novel concept called edge cloning.

Theory Pig’s algorithm is given below. It takes a directed graph D, and a start vertex v as an input.

On (D, v), for all vertices u such that there is an edge from v to u or an edge from u to v,

1. modify the graph by adding (u, v) or (v, u) if one of them doesn’t already exist.

2. repeat the algoithm on every (D, u).

3. When no future modifications will take place, halt.

Figure 1:

For example, on the input graph, {1,2,3,4}, {(1,2), (3,2), (3,4} and the start node 2, we first add in the edges (2,3) and (2,1), and then repeat the algorithm on nodes 1 and 3. There is nothing to do for 1, but at node 3 we find an opportunity to add (4,3).

We define a directed graph to be CABSAAUG^{1} if ∀(u, v) ∈ E, (v, u) ∈ E where E is the edge set.

(a) (2 points) Show that for the digraph, D = {a,b,c,d,e}, {(a,c),(a,d),(d,e)} the algorithm on instance (D, a) yields a CABSAAUG. (Hint: you need no more than 3 transitions to give a picture of the entire algorithm.)

Figure 2:

Soln.

1. add (c,a) , (d,a), recurse on c and d

2. add (e,d) - done, and CABSAAUG

(b) (2 points) Show that for some graph D and some start node v, the algorithm does not yield a digraph which is CABSAAUG.

Soln. Consider the digraph {a,b,c},{(a,b)} and the start node c.

1CABSAAUG stands for Could Also Be Seen As A Undirected Graph.

(c) (3 points) Show that for some graph D and every start node v, the algorithm does not yield a digraph which is CABSAAUG. Use at most four nodes, and indicicate which node is your start node.

Soln. Consider the digraph {a,b,c,d},{(a,b), (c,d)}.

(d) (4 points) Prove that the algorithm hits state 3. (I.e., prove termination.)

Soln. There are a finite number of possible edges in any grapoh of n nodes. In particular, there are at most n(n − 1) (excluding self-loops). Since the algorithm only adds edges, and the algorithm stops when it cannot add any more edges, the algorithm must eventually stop. (It may well stop before having added all n(n − 1) edges.)

(d) (4 points) Prove that when the algorithm does terminate, the start node is part of a strongly connected component^{2}

Soln. A node v is part of a strongly connected component if ∀u such that there is a path from u to v, there is a path from v to u, and ∀u such that there is a path from v to u, there is a path from u to v. Let our input be (D, v) and call the resulting graph R.

Let p be a path from u to v where v is our start node. Then there is a series of nodes u, u_{1}, u_{2}, ..., u_{k}, v such that (u, u_{1}), (u_{1}, u_{2}), ..., (u_{k}, v) are all in R. Suppose v, u_{k}, ..., u_{1}, u is not a path in R. We will show this is a contradiction.

(u_{k}, v) ∈ R implies (v, u_{k}) ∈ D and (u_{k}, v) was added, or else (u_{k}, v) ∈ D and (v, u_{k}) was added, or they both existed in D. In either case, R contains (v, u_{k}). Thus, if v, u_{k}, ..., u_{1}, u is not a path in R, then neither is u_{k}, ..., u_{1}, u. We continue inductively until we find that u_{1}, u in R. A similar proof works for the other direction.

2A strongly connected component was defined in a previous problem.

Figure 3: Figure 4: