What is the transitive closure of the following digraph ? To find reach-ability matrix and adjacency matrix.
My approach:
The adjacency matrix is \begin{bmatrix} 0 &1 &0 &0 \\ 0 & 0&0 &1 \\ 0 & 0 &0 &0 \\1 & 0 & 1 & 0 \end{bmatrix}.
Using Warshall's algorithm, the reach-ability matrix for transitive closure is \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 & 1 & 1& 1\\ 0 & 0 & 0 & 0\\1 & 1 & 1 & 1 \end{bmatrix}.
So the transitive closure is the graph:
Am I right ?
Please help
Not quite. Here's the transitive closure graph:
Recall that the transitive closure of graph $g$ has the same vertices as $g$ but with (directed) edges between vertices $u$ and $v$ if there is a path—any path—between $u$ and $v$ in $g$. Just examine your graph and you can construct the transitive closure "by hand." Notice, for instance, there is no path from $c$ to $b$ in $g$... and hence no edge between those vertices in the transitive closure graph. But there is a (long) path from $a$ to $c$ in $g$, and hence there is an edge from $a$ to $c$ in the transitive closure.
You can check all the others...
A note to the specialist: Transitive closures are most properly defined on directed acyclic graphs (DAGs). If one admits cycles ("loops") then there will be some vertices with paths to themselves, and thus a transitive closure should include a "self loop."