How to find a dead end in a graph? For a project about GPS systems, I'm trying to understand how can we see that there is a dead end thanks to an adjacency matrix.



I know that the adjacency matrix definition is  


  Assumed that $G=(V,E)$ is a simple graph, where $\left|V\right|=n$. Assumed also that the vertices number are arbitrarily numbered $v_1,\ldots,v_n$. The adjacency matrix $A$ of $G$ of this set of vertices is A with
  $$a_{ij}=\left\{\begin{array}{rl} 1 &amp; \mbox{if } (v_i,v_j)\in E \\        0 &amp; \mbox{else.}\end{array}\right.$$


Here is the adjacency matrix I found corresponding on the top and on the side to the vertices $[1,2,9,10,11,12]$:
\begin{pmatrix}
   1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\
   1&amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
   0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0 \\
   0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0 \\
   0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\
   1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
\end{pmatrix}

How can I know that some are dead end?

To my mind we can only know that thanks to the
The correct adjacency matrix is (observe that this is a directed graph)
$$\begin{pmatrix}0&amp;1&amp;0&amp;0&amp;0&amp;1\\
0&amp;0&amp;0&amp;0&amp;0&amp;0\\
0&amp;0&amp;0&amp;1&amp;1&amp;0\\
0&amp;0&amp;0&amp;0&amp;1&amp;0\\
0&amp;1&amp;1&amp;0&amp;0&amp;1\\
0&amp;0&amp;0&amp;0&amp;0&amp;0\end{pmatrix} $$
The rows corresponding to $2$ and $12$ are all zero, indicating that there is no way out.
120002
010000
011221
011121
022112
000001

matrix C 'could' or 'might' apply where:

a. each number (from 1 to 12) is independently self sufficient (i.e. 'on')
b. access to corresponding figures in 'the chain' is possible (via other numbers) - to constitute 'on'
c. a ternary introduction can be applied for direct value relationships. i.e. self sufficient independency (value: 1/on) + direction of travel (using direct access) to another chain figure = 2 (value)

there is probably a better way to express the unique 9 to 11 or 11 to 9 relationship (dual direction / exchange) but i don't have sufficient time to explore that right now.

ta.