I'm not sure if this is the right place to post this, as I just came across this while grading some homework for a finite math class. It had to do with directed graphs, and finding the adjacency matrix and number of 3-step paths from one of four cities to another of the four cities. I had no prior knowledge on the procedure, so I looked it up and soon caught onto the basics.(adsbygoogle = window.adsbygoogle || []).push({});

After a while it I was interested in other applications for directed graphs, so I looked up some more info online. It reminded me of a doodling game I used to play very often in class. The goal was to draw a little house like in the attachment, with the only nodes located on the exterior of the house (five in total).

The trick was to draw each edge of the house in one sitting, with no repeats (so once you draw an edge you can't go back).

I constructed the adjacency matrix (I hope I have the terminology right):

[itex]\left[ \begin{array}{ccccc} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{array} \right][/itex]

So here the first row is the roof node, the second row is the top right, third is top left, fourth is bottom left, and fifth is bottom right.

I mistakenly thought that multiplying the adjacency matrix, say [itex]A[/itex], by itself eight times (so [itex]A^8[/itex]) would yield the number of possible paths you can take, but each element was in the thousands. So I concluded that this calculation considers repeated paths.

Now my question: Is there a method along these lines to find the number of non-repeating paths?

Thanks.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Non-repeating paths in a digraph?

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - repeating paths digraph | Date |
---|---|

Diff eqs with eigenvectors: double roots, but 2nd eigenvector? | Nov 15, 2015 |

Matrix with repeated eigenvalues is diagonalizable...? | Nov 5, 2015 |

Derive an expression to find how many times an eigen value is repeated | Feb 20, 2013 |

Repeated eigenvalues of a symmetric matrix | Dec 21, 2012 |

More docile dfn of local path-connectedness? | Apr 11, 2007 |

**Physics Forums - The Fusion of Science and Community**