Transitive closure
The transitive closure of a directed graph: reachability, reachability matrix, Warshall's algorithm and its cost, computing it by traversals and strongly connected components read off the matrix.
- 27 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Reachability: what is it?
Show the answer
A property of a vertex j with respect to a vertex i: the directed graph contains a path of at least one arc leading from i to j.
A direct arc is just a special case: A is reachable from B if several arcs can be chained. A vertex is reachable from itself only if it lies on a circuit.
What does this program print?
```python
r = [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0]]
for k in range(4):
for i in range(4):
for j in range(4):
r[i][j] = r[i][j] or (r[i][k] and r[k][j])
print(r[3])`[1, 1, 1, 0][1, 0, 0, 0][1, 1, 0, 0][1, 1, 1, 1]
Show the answer
[1, 1, 1, 0]Vertex 3 has an arc to 0, which goes to 1, which goes to 2: it reaches 0, 1 and 2. Nobody reaches vertex 3 itself, so cell (3, 3) stays 0.
[1, 0, 0, 0]is the starting row: the closure has not completed it.In the transitive closure there is an arc from i to j if and only if the starting graph contains a … from i to j.
Show the answer
In the transitive closure there is an arc from i to j if and only if the starting graph contains a path from i to j.
The path may have any length, one arc or several. The closure therefore holds all the graph's arcs and adds one for every shortcut.
Transitive closure: what is it?
Show the answer
The graph on the same vertices that contains an arc from i to j whenever a path leads from i to j in the starting graph.
It makes the relation transitive: if i reaches j and j reaches k, i reaches k directly. It answers every “can you get from i to j?” question at once.