\problemdata     
{computation-3}           
{Graphs, Trees, State Machines, Counting, Well-order}
{F99 Q2 prob 4}              
{S02 in-class Week 5} 		
{S02 Meyer}        	




\begin{problem}
We apply the following operation to a simple graph $G$:
pick two vertices $u \neq v$ such that either
\begin{enumerate}
\item there is an edge of $G$ between $u$ and $v$ and there is also a path
from $u$ to $v$ which does \emph{not} include this edge; in this case,
delete the edge $\set{u,v}$.

\item there is no path from $u$ to $v$; in this case, add the edge
$\set{u,v}$.
\end{enumerate}

Keep repeating these operations until it is no longer possible to find two
vertices $u \neq v$ to which an operation applies.

Assume the vertices of $G$ are the integers $1,2,\dots,n$ for some $n \geq
2$.  This procedure can be modelled as a state machine whose states are
all possible simple graphs with vertices $1,2,\dots,n$.  $G$ is the start
state, and the final states are the graphs on which no operation is
possible.

\bparts

\ppart Let $G$ be the graph with vertices $\set{1,2,3,4}$ and edges
\[
\set{\set{1,2},\set{3,4}}
\]
Draw the possible final states are reachable from start state $G$?

\solution{It's not possible to delete any edge.  The procedure can only
add an edge connecting exactly one of vertices 1 or 2 to exactly one of
vertices 3 or 4, and then terminate.  So there are four possible final
states}

\ppart \label{derived} Below are three derived variables.  Indicate the
\emph{strongest} property from the list below that each variable is
guaranteed to satisfy, no matter what the starting graph $G$ is, and
justify your answer.  The properties are: \emph{constant}, \emph{strictly
increasing}, \emph{strictly decreasing} ,\emph{weakly increasing},
\emph{weakly decreasing}, \emph{none of these}

For any state, let $e$ be the number of edges in it, and let $c$ be the
number of connected components it has.  For example, since $e$ may
increase or decrease in a transition, it does not have any of the first
four properties, so it would be classified \emph{none of these}.  The
derived variables are i) $c$, \solution{weakly decreasing} ii) $c+e$,
\solution{weakly decreasing} iii) $2c+e$. \solution{strictly decreasing}

\ppart Conclude that the procedure terminates.

\solution{Because the derived variable iii) is a natural-number valued
variable and is decreasing.

To show that the variable iii) decreases, note that the rule for deleting
an edge ensures that the connectedness relation does not change, so
neither does the number of connected components; therefore the variable
decreases by one when an edge is deleted.  The rule for adding an edge
ensures that the number of connected components decreases by one, so the
variable changes by $-2$ for the reduced number of components and $+1$ for
the added edge, for a net decrease of 1.}

\ppart Prove that any final state must be a \emph{spanning
tree} on the vertices.

\solution{We use the characterization of a tree as a cycle-free,
connected, simple graph.

A final state must be connected, because otherwise there would be two
vertices with no path between them, and then a transition adding the edge
between them would be possible, contradicting finality of the state.

A final state can't have a cycle, because deleting any edge on the
cycle would be a possible transition.}

\eparts

\end{problem}
