Practice Definition Of The Kth Matrix (20.3) - Warshall’s Algorithm for Computing Transitive Closure

Practice: Definition of the kth Matrix

Lesson 20.3Warshall’s Algorithm for Computing Transitive Closure

Practise this section

8 questions

Flashcard drill
2 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
2 questions · about 1 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
Define W(k) in your own words.
Show hintHide hint
Think about it as a way to show reachability in a graph.
Question 2.
What does W(i, j)(1) equal if there is a direct edge from i to j?
Show hintHide hint
Consider if a direct connection counts.
3Question 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.
Show hintHide hint
Focus on the definition of W(k).
4Question 4.
True or False: The length of the path is crucial for W(k).
- True
- False
Show hintHide hint
Remember what defines a path in this context.
Question 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.
Show hintHide hint
Consider how adding nodes modifies the pathways.
Question 6.
Given W(3) = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]; analyze the matrix and describe the possible paths.
Show hintHide hint
Use the entry values to find valid routes through the matrix.

4 more questions in this section. Enroll free to practise them all.