20.5. Examples of W Matrices

Try these first

1. 1.

   Define what a W Matrix is.

   Hint

   Think about how these matrices are structured.

2. 2.

   What does it mean if W[k][i,j] = 1?

   Hint

   Consider the conditions for marking entries in the matrix.

3. 3.

   What does a W Matrix represent?

   • Reachability between nodes
   • Direct connection only
   • No connections at all

   Hint

   Think about how paths are formed in a graph.

4. 4.

   True or False: W(n)[i,j] can be set to 1 regardless of the path length.

   • True
   • False

   Hint

   Review the conditions for setting entries in the matrix.

5. 5.

   Given a directed graph with nodes A, B, C, and D where edges are A->B, B->C, C->D, and A->C, derive W(2) and W(3). Explain reasoning in each step.

   Hint

   Use systematic checking across intermediate nodes for accuracy.

6. 6.

   Identify potential issues in using Warshall's Algorithm on a graph with cycles and discuss implications in reachability.

   Hint

   Consider how paths can loop back and affect matrix entries.