2
$\begingroup$

Graph Theory: The question is to find the transitive closure.

Let $G$ be a graph. A directed path $v_1 \rightarrow v_3 \rightarrow v_4$ connects the vertex $v_1$ to $v_4$. $G$ has these additional directed edges: $v_2 \rightarrow v_1$, $v_3 \rightarrow v_2$, and $v_2 \rightarrow v_3$.

My answer is:

\begin{bmatrix}1&1&1&1\\1&1&1&1\\1&1&1&1\\0&0&0&0\end{bmatrix}

However, my professor's answer is:

\begin{bmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\0&0&0&0\end{bmatrix}

Can you explain how this can be? From what I understand there is a path from $v \rightarrow v_3 \rightarrow v_1$ thus the 1st column first row should be $1$.

Also there is a path from $v_2$ to $v_2$ as well so that is $1$.

And finally there is a path from $v_3$ to $v_3$ so that is $1$.

$\endgroup$
  • $\begingroup$ I think you are right.may be you overlooked something in your professor answer/question? or may be your professor is wrong (it happens some times. ..) $\endgroup$ – wece Feb 17 '16 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.