Homework: Homework 7. Graphs

Assigned

• November 3, 2026

Due

• November 13, 2026 10:00pm

Collaboration

Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\) If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

1. 20.2-5 Argue that in BFS u.d is independent of the order in which vertices appear. However, using figure 20.3 show that bfs trees can depend on the ordering within adjacency lists

2. 20.3-10 Explain how a vertex u of a directed graph can end up in a depth first tree containing only u, even though u has both incoming and outgoing edges in G

3. 20.4-5 Alternative Topological Sorting: Find a vertex of in-degree 0, output it, remove it and all outgoing edges from the graph. Implement in O(V+E) and explain what happens if G has cycles

4. 21.1-1 Let (u,v) be a minimum weight edge of a connected graph G, show that (u,v) belongs to some MST of G

5. 21.1-4 Give a simple example of a connected graph such that the edges (u,v): there exists a cut (S,V-S) such that (u,v) is a light edge crossing (S,V-S) does not form an MST

Bonus. 21.2-4,21.2-5 Faster Algorithms if we add constraints