\documentstyle[quietpsfig]{article}

\setlength{\textwidth6.5in}
\setlength{\textheight8.8in}
\setlength{\oddsidemargin0in}
\setlength{\topmargin-0.3in}
\setlength{\unitlength}{1cm}

\begin{document}
\section{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 {\it 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.

\begin{figure}[h]
\centerline{\psfig{file=fig3.ps,height=1in}} 
\caption{}
\end{figure}

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\footnote{CABSAAUG stands for
Could Also Be Seen As A Undirected Graph.} if $\forall (u,v) \in E, (v,u) \in E$
where $E$ is the edge set.

\begin{enumerate}
\item[(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. {\it (Hint: you
need no more than 3 transitions to give a picture of the entire
algorithm.)}

\begin{figure}[h]
\centerline{\psfig{file=fig4.ps,height=1in}} 
\caption{}
\end{figure}
{\bf Soln.} 

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

2. add (e,d) - done, and CABSAAUG  
 
\item[(b)] (2 points)
Show that for some graph D and {\bf some} start node v, the algorithm does not
yield a digraph which is CABSAAUG.

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

\begin{figure}[h]
\centerline{\psfig{file=fig5.ps,height=1in}} 
\caption{}
\end{figure}

\item[(c)] (3 points)
Show that for some graph D and {\bf 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.

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

\begin{figure}[h]
\centerline{\psfig{file=fig6.ps,height=1in}} 
\caption{}
\end{figure}

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

{\bf 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.)

\item[(d)] (4 points)
Prove that when the algorithm does terminate, the start node is part of
a {\it strongly connected component}\footnote{A strongly connected
component was defined in a previous problem.}

{\bf Soln.} A node $v$ is part of a strongly connected component if
$\forall u$ such that there is a path from $u$ to $v$, there is a path
from $v$ to $u$, and $\forall 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) \in R$ implies $(v,u_k) \in D$ and $(u_k,v)$ was
added, or else $(u_k,v) \in 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.

\end{enumerate}

\end{document}



