ITPEC FE Morning October 2021 Question 4
An adjacency matrix is used to indicate which vertices of a directed or undirected graph are adjacent to each other. Which of the following is an appropriate matrix that represents the directed graph below?
Explanation
Rows A: 0 1 0, B: 1 0 1, C: 0 0 0 — put a 1 at row i, column j for each arc from i to j, and 0 everywhere else.
The graph has three arcs, A → B, B → A and B → C, no loops, and no arc leaving C.
The matrix is not symmetric because B → C has no reverse arc. Reading the columns as sources instead gives a matrix that is not among the options.
Answer (d)
Why not others:
- •(a) — also marks every vertex as adjacent to itself and adds A → C; that is reachability (A reaches C through B), not adjacency
- •(b) — the complement of the correct matrix: a 1 wherever there is no arc and a 0 where there is one
- •(c) — adds A → C, which is only a path through B, and a loop on C that the graph does not have
Key rule: An adjacency matrix records direct arcs only, row = start and column = end; a path through another vertex, or a loop not drawn, does not count.
Basic Theory · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.