Question

Extra Credit: Suppose you are given an undirected, connected, weighted graph G. You want to find the heaviest weight set of edges that you can remove from G so that G is still connected. Propose an optimal greedy al- gorithm for this problem and prove that it is optimal. (Hint: use matroid theory!).

PLEASE INCLUDE EXPLANATION AND DONT COPY FROM OTHER CHEEG ANSWERS

Answer 1

We can use minimum spanning tree method in this. we create a MST ( Minimum spanning tree ) , and whosoever are the edges not in MST remove them . As MST is connected so the graph after removal would also be,

If we are last with MST then its sure that its optimal to remove those edges which have been removed , Now lets just prove the optimality of MST using kruskal algorithm.

Algo :

ARRANGE THE EDGES IN INCREASING ORDER OF THE WEIGHTS.

TAKE THE EDGE :

JOIN IN THE MST , IF THERE ARISES A CYCLE DON'T USE IT

REPEAT TILL WE GET A TREE OF N-1 EDGES.

PROOF :

We’ll prove this in a similar manner to the general proofs for matroids.

Suppose you had a tree whose cost is strictly less than that of MST.

Pick the minimal weight edge $e \in T$ that is not in MST. Adding to MST introduces a unique cycle in MST.

This cycle has some interseting properties. First, has the highest cost of any edge on . Otherwise, Kruskal’s algorithm would have chosen it before.

Second, there is another edge in that’s not in because T was also a tree with no cycle .Call such an edge .

Now we can remove from MST and add , to make an improved version of MST.

This can only increase the total cost of MST, but this transformation produces a tree with one more edge in common with than before.

This contradicts that had strictly lower weight than MST, because repeating the process we described would eventually transform MST into exactly, while only increasing the total cost.

Thus our chosen algorithm gives the optimal result .