Problem 1: Shortest Path 40 points
1. If p = fv1; ; vng is the shortest path between v1 and vn, then prove that any subpath
pij = fvi; ; vj g in p is the shortest path between vi and vj . (20 points)
Write the pseudocode to find a negative weight cycle in a directed graph G = (V; E) with the weight function w : E ! R. (20 points)
Bonus Problem (20 points):
Demonstate Dijkstra’s algorithm on the following graph.
Implement Dijkstra’s algorithm in Python, and validate your code on the following graph.
1
Part 5: Graph Algorithms (Part II) & NP Completeness
2
Problem 2:
Flow Networks
20 points
Define slack (residual flow) in an edge (u; v) 2 E in a the residual graph of a given graph G = (V; E). (10 points)
Demonstrate the Ford-Fulkerson algorithm on this following flow network, where each edge is labeled with its flow capacity. (10 points)
Bonus Problem (10 points):
Implement Edmonds-Karp algorithm in Python, and test your code on the given graph.
Part 5: Graph Algorithms (Part II) & NP Completeness
3
Problem 3:
NP Completeness
40 points
Prove that there are uncountable number of unsolvable binary decision problems. Further-more, give an example of an unsolvable binary decision problem. (10 points)
Define NP, NP-Hard and NP-Complete classes, and give one problem in each of these com-plexity classes. (10 points)
Assuming that Hamiltonian circuit problem is NP-Complete, prove that traveling salesman problem is NP-Complete via reduction. (20 points)
