Definition: A preserved invariant of a state machine is a predicate, $P$, on states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$, then $P(r)$ holds.
Definition: A line graph is a graph whose edges are all on one path.
Definition: Formally, a state machine is nothing more than a binary relation on a set, except that the elements of the set are called “states,” the relation is called the transition relation, and an arrow in the graph of the transition relation is called a transition. A transition from state $q$ to state $r$ will be written $q \rightarrow r$.
DAG: Directed Acylic Graph
The following procedure can be applied to any directed graph, $G$:
- Delete an edge that is in a cycle.
- Delete edge $<u \rightarrow v>$ if there is a path from vertex $u$ to vertex $v$ that does not include $<u \rightarrow v>$.
- Add edge $<u \rightarrow v>$ if there is no path in either direction between vertex $u$ and vertex $v$.
Repeat these operations until none of them are applicable.
This procedure can be modeled as a state machine. The start state is $G$, and the states are all possible digraphs with the same vertices as $G$.
(b) Prove that if the procedure terminates with a digraph, $H$, then $H$ is a line graph with the same vertices as $G$.
Hint: Show that if $H$ is not a line graph, then some operation must be applicable.
(c) Prove that being a DAG is a preserved invariant of the procedure.
(d) Prove that if $G$ is a DAG and the procedure terminates, then the walk relation of the final line graph is a topological sort of $G$.
Hint: Verify that the predicate $P(u,v)$:: there is a directed path from $u$ to $v$ is a preserved invariant of the procedure, for any two vertices $u, \ v$ of a DAG.
(e) Prove that if $G$ is finite, then the procedure terminates.
Hint: Let $s$ be the number of cycles, $e$ be the number of edges, and $p$ be the number of pairs of vertices with a directed path (in either direction) between them. Note that $p \leq n^2$ where $n$ is the number of vertices of $G$. Find coefficients $a,b,c$ such that as+bp+e+c is nonnegative integer valued and decreases at each transition.
I got stuck with problems $d$ and $e$ but solutions to other problems are welcome too.
At problem $d$, I could not understand the hint and why it is given, how it helps.
In my way for proving $d$, I am trying to show that given procedure always preserves the order of vertices, which are associated with edges, on the start graph $G$. So a line graph is automatically a topological sort since the "precedence order" of the vertices are preserved.
But procedure number $3$ is problematic, how to show it preserves precedence ?