Comments on Homework 12

• Cut vertices:

  • Identify the cut vertices.
  • The earliest reachable ancestor of v is the lowest-numbered of v, the vertices adjacent to v via back edges, and the earliest reachable ancestors of children of v. For degree 1 vertices (like I and J), there are no back edges from v or children of v in the DFS tree so the earliest reachable ancestor is v itself.

• Topological sort:

  • Identify the ordering of vertices.
  • Show both the entry and exit times.
  • If the DFS terminates, restart with a vertex with indegree 0.

• There were a couple of problems with the Bellman-Ford problem. A corrected version will be posted for the redo.

  • Go through all edges in each iteration — don't skip BA because AB was already visited. If both AB and BA are present, visit them both.
  • If there are negative edge weights, a directed graph is required &mdashs; an undirected edge is equivalent to having two directed edges, one in each direction, and so a negative weight undirected edge forms a negative weight cycle.