L10 - Kruskal and Proof Flashcards
When should Kruskal we used instead of Prims?
When the complexity of Prims is known to be too high.
What is the problem, input, output, input-output relation of Kruskal?
Problem -
Input - Weighted graph.
Output - Tree
I-O Relation - The smallest MST found.
What are the 3 steps of the Kruskal algorithm?
1 - Sort all edges from lowest to highest weight.
2 - Instantiate an edge set
3 - Add edges to the edge set from lowest to highest weight, ensuring no cycles occur in the tree.
4 - Repeat until MST is created ( no more edges can be added ).
What is the overall time complexity of Kruskal?
O( E log V )
Give proof of the time complexity of Kruskals…
Sorting edges = O ( E log E )
While loop over edge set = O ( E )
Within while loop, group edges = O ( log V )
Total = O(E log E ) + O(E) * O(log V)
= O(E log E) + O(E log V)
= O(E log V) since there are always more vertices than edges.
Define and explain Lemma…
Lemma is the property that given any subset X of a tree T, the shortest edges e from T connecting to each vertex v in X must be in the MST.
What does the correctness of both Kruskals and Prims rely on?
The Lemma of each tree.
Give the proof of correctness for Kruskal…
During Kruskal, we have subgraphs K or the graph G. Each K is a cycle free group of shortest edges.
By the Lemma, we can connect each group to one another, ensuring they are connected by the shortest edge possible.
This results in the MST, and proves that Kruskal’s in totally correct.
Give the proof of correctness of Prims…
At any point in Prims, we are adding the vertex with the lowest edge to the MST being constructed.
By the Lemma, any vertex added to the tree is known to have the lowest cost edge.
Prims terminates when all vertices have been visited. Thus, we know that the MST is correct.
What are some caveats of Prims proof of correctness?
- Relies on the assumption that no 2 edges have the same weight within the graph. If this is not the case, the MST is not unique.
What does it mean if a problem is NP-Complete?
A problem can’t be broken into sub-problems, and no feasible solution exists.
Rather than finding an absolute solution, what is best practice for solving NP-Complete problems…?
Use heuristic algorithms to find a ‘good enough’ solution, since the solution space is infeasibly large. For example, nature inspired algorithms such as ACO.
How can we use MST to answer TSP?
Using round tour technique.
However, each vertex is visited twice.
When using round-tour to solve the TSP, what can we guarantee about the ouput?
The output circuit is less than 2x the MST of the graph.
This provides a good enough solution.
Give 2 uses of MST….
Image segmentation
Cluster analysis
