Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Non-repeating paths in a digraph?

  1. Oct 24, 2012 #1
    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.

    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?


    Attached Files:

  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted