snippetMinor
A procedure for Topological sort, proof for its correctness
Viewed 0 times
correctnessprocedureitstopologicalforsortproof
Problem
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$:
include $$.
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
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 $$ if there is a path from vertex $u$ to vertex $v$ that does not
include $$.
- Add edge $$ 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
Solution
b. As operation $1$ cannot be performed, $H$ must be a DAG. Consider a topological sort of $H$. As $3$ cannot be performed, if $u$ precedes $v$ in the topological sort, there is a path from $u$ to $v$. Start at the initial vertex in the sort and keep moving forward until we find a vertex which has more than one outgoing edges (if each vertex has only one outgoing, then it is a line graph). Let $u$ have edges to $v$ and $w$ and let $v$ precede $w$. Then there is path from $v$ to $w$, which gives a path from $u$ to $w$ that doesn't include $u \rightarrow w$, a contradiction as operation $2$ can be performed here.
c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.
d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.
e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are
$$
\begin{array}{cccc}
& s & e & p \\
\end{array}
$$
As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.
c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.
d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.
e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are
$$
\begin{array}{cccc}
& s & e & p \\
- & -1 & -1 & -n^2 \\
- & 0 & -1 & 0 \\
- & 0 & 1 & 1
\end{array}
$$
As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.
Context
StackExchange Computer Science Q#10720, answer score: 2
Revisions (0)
No revisions yet.