20.3. Definition of the kth Matrix

Try these first

1. 1.

   Define W(k) in your own words.

   Hint

   Think about it as a way to show reachability in a graph.

2. 2.

   What does W(i, j)(1) equal if there is a direct edge from i to j?

   Hint

   Consider if a direct connection counts.

3. 3.

   What does W(i, j)(k) = 1 mean?

   • There is a direct edge from i to j.
   • There exists a path from i to j with intermediates only from 1 to k.
   • i is not connected to j.

   Hint

   Focus on the definition of W(k).

4. 4.

   True or False: The length of the path is crucial for W(k).

   • True
   • False

   Hint

   Remember what defines a path in this context.

5. 5.

   Create a directed graph with at least six nodes and present the W(k) matrices for k=1, 2, 3. Then explain how k affects connectivity.

   Hint

   Consider how adding nodes modifies the pathways.

6. 6.

   Given W(3) = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]; analyze the matrix and describe the possible paths.

   Hint

   Use the entry values to find valid routes through the matrix.