Looking for some help with starting points more so than solutions here. How can I go about proving 1, 2, and 3? I don't understand exactly what is? Just an array of all basically? Additionally I don't understand vs. ?
Design and analyze a minimum spanning tree recursive algorithm that only uses the adjacency list representation of the graph and no other data structures. Assume that edge costs are distinct.
- For each vertex , let be the minimum-cost edge adjacent to . Let be the union of all such edges. Prove that is acyclic.
- Show that you can find in time, where is the number of edges in the graph.
- We contract an edge by creating a new vertex , connecting to all of ’s neighbours and all of ’s neighbours and deleting and and all the edges adjacent to and . Let be the graph obtained by contracting all the edges in . Show that one can build from and in time.
- Show that the number of vertices in is at most one half of the number of vertices in .
- Use the above ideas to give pseudocode for a recursive algorithm to find a minimum spanning tree. The algorithm should take as input a graph with edge costs and return the set of edges forming the minimum spanning tree.
- Give a recurrence relation for the running time of this algorithm. Solve the recurrence relation.