I'm working on a little extra credit for a problem-solving course.
Jack is heading home from work on his bike. His home is 3 blocks north and 4 blocks to the east. The intersection one block north-east of him is broken so he doesn't want to ride there.
The question asks “How many ways are there for him to travel 5 blocks and still make it home if he only travels north and east?”
We solved this problem by counting and by raising the adjacency matrix to the ^5 power.
Graph: https://drive.google.com/drive/u/0/folders/1mPPcHSZO8As7OT7KmlbewhrubeKEad74
Matrix: https://drive.google.com/drive/u/0/folders/1mPPcHSZO8As7OT7KmlbewhrubeKEad74
We also covered the fact that the broken vertex can be removed without affecting the result.
This problem led to some discussion and now my professor is curious: Is it possible to reduce the size of this matrix further and still be able to find the number of paths by raising it to a power?
For example, if we combined paths with only one way home, we could have a 7 x 7 matrix instead of an 11 x 11 or 12 x 12.
Simplified graph: https://drive.google.com/drive/u/0/folders/1mPPcHSZO8As7OT7KmlbewhrubeKEad74
However, we need some way to represent the fact that by reducing the size of the matrix, we eliminated 4 vertices and 5 edges.
I know there's a way to assign weight to graphs, which would basically mean instead of a simple graph, we have vertices with more than one edge connecting them.
I don't think it's possible to do this, but perhaps someone knows why.
Regards