The idea with this problem set is that you should practice on the following things:
Exercises:
The edge set E of a graph G = (V, E) can be seen as a relation R between nodes, by defining that u R v iff (u, v) ∈ E.
Design an algorithm which decides if the edge set of a directed, unweighted graph represents an equivalence relation. Explain why the algorithm is correct and analyse its time complexity.
Assume that V₁ and V₂ partition the vertex set V of some connected, undirected, weighted graph G = (V, E). Let us define the spacing of this partition as
min {cv₁, v₂ | v₁ ∈ V₁, v₂ ∈ V₂, (v₁, v₂) ∈ E},
where cv₁, v₂ is the cost of the edge (v₁, v₂). (In other words, the spacing is the cost of any of the cheapest edges connecting the two partitions.)
Design an algorithm which, given a connected, undirected, weighted graph G = (V, E) with ∣V∣ ≥ 2, calculates
max {spacing of (V₁, V₂) | V₁, V₂ partition V}.
In other words, the algorithm should find the largest possible spacing. Explain why the algorithm is correct and analyse its time complexity.
Hint: Consider using a minimum spanning tree.
Think of a real-world problem which can be solved using some graph algorithm (possibly in combination with other algorithms). Solve the problem, explain why your solution is correct, and analyse the time complexity of your solution.