Graph Algorithms

Single correct

• A$\Theta(m + n)$
• B$\Theta(m + n\log(n))$
• C$\Theta(nm)$
• D$\Theta(n^3)$

One or more correct

• AA DFS tree of $G$ is a Shortest Path tree of $G$.
• BEvery non-tree edge of $G$ with respect to a DFS tree is a forward/back edge.
• CIf $(u, v)$ is a non-tree edge of $G$ with respect to a BFS tree, then the distances from the source vertex $s$ to $u$ and $v$ in the BFS tree are within $\pm 1$ of each other.
• DBoth BFS and DFS can be used to find the connected components of $G$.

Single correct

• AEvery MST remains an MST, and every SP remains an SP.
• BMSTs need not remain MSTs, and every SP remains an SP.
• CEvery MST remains an MST, and SPs need not remain SPs.
• DMSTs need not remain MSTs, and SPs need not remain SPs.

someAlgo(G)
  1. Let v be any vertex in G. Run BFS on G starting at v.
     Let u be a vertex in G at maximum distance from v as given by the BFS.
  2. Run BFS on G again with u as the starting vertex.
     Let z be the vertex at maximum distance from u as given by the BFS.
  3. Output the distance between u and z in G.

Numerical answer

One or more correct

• AAll edges in $G$ have even weight
• BAll edges in $G$ have even weight OR all edges in $G$ have odd weight
• CIn each cycle $C$ in $G$, all edges in $C$ have even weight
• DIn each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

Numerical answer

Single correct

• ABoth $S_1$ and $S_2$ are true.
• B$S_1$ is true and $S_2$ is false.
• C$S_1$ is false and $S_2$ is true.
• DBoth $S_1$ and $S_2$ are false.

Answer key coming soon

Numerical answer

Answer key coming soon

One or more correct

• AThe graph does not have a topological order.
• BA depth-first traversal starting at vertex S classifies three directed edges as back edges.
• CThe graph does not have a strongly connected component.
• DFor each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$.

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

• AMNOPQR
• BNQMPOR
• CQMNROP
• DPOQNMR

Answer key coming soon

Numerical answer

Answer key coming soon

Single correct

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

Answer key coming soon

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