In: Computer Science
Given an undirected graph G=(V, E) with weights and a vertex , we ask for a minimum weight spanning tree in G where is not a leaf (a leaf node has degree one). Can you solve this problem in polynomial time? Please write the proof.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.A single graph can have many different spanning trees • They all must have the same number of edges, but if it is a weighted graph, they may differ in the total weight of their edges • Of all spanning trees in a weighted graph, one with the least total weight is a minimum spanning tree (MST) • It can be useful to find a minimum spanning tree for a graph: this is the least-cost version of the graph that is still connected, i.e. that has a path between every pair of vertices
Finding a minimum spanning tree: Prim’s algorithm • As you know, minimum weight paths from a start vertex can be found using Djikstra’s algorithm • At each stage, Djikstra’s algorithm extends the best path from the start vertex (priority queue ordered by total path cost) by adding edges to it • To build a minimum spanning tree, you can modify Djikstra’s algorithm slightly to get Prim’s algorithm • At each stage, Prim’s algorithm adds the edge that has the least cost from any vertex in the spanning tree being built so far (priority queue ordered by single edge cost) • Like Djikstra’s algorithm, Prim’s algorithm has worst-case time cost O(|E| log |V|) • We will look at another algorithm: Kruskal’s algorithm, which also is a simple greedy algorithm • Kruskal’s has the same big-O worst case time cost as Prim’s, but in practice it can be made to run faster than Prim’s, if efficient supporting data structures are used