Graph Algorithms

Single correct

• A$G_1 = (V, E_1)$ where $E_1 = \{(u, v) \mid (u, v) \notin E\}$
• B$G_2 = (V, E_2)$ where $E_2 = \{(u, v) \mid (v, u) \in E\}$
• C$G_3 = (V, E_3)$ where $E_3 = \{(u, v) \mid \text{there is a path of length} \leq 2 \text{ from } u \text{ to } v \text{ in } E\}$
• D$G_4 = (V_4, E)$ where $V_4$ is the set of vertices in $G$ which are not isolated

Single correct

• A$\Theta(n)$
• B$\Theta(n + m)$
• C$\Theta(n^2)$
• D$\Theta(m^2)$

Single correct

• AThe graph does not have any topological ordering.
• BBoth PQRS and SRQP are topological orderings.
• CBoth PSRQ and SPRQ are topological orderings.
• DPSRQ is the only topological ordering.

Single correct

• Athe shortest path between every pair of vertices.
• Bthe shortest path from W to every vertex in the graph.
• Cthe shortest paths from W to only those nodes that are leaves of T.
• Dthe longest path in the graph.

Numerical answer

Numerical answer