Question

Suppose you are given a connected graph G, with edge costs that you may assume are all distinct. G has n vertices and m edges. A particular edge e of G is specified. Give an algorithm with running time O(m + n) to decide whether e is contained in a minimum spanning tree of G.

Answer 1

Algorithm:

1. First of all, assume that edge e of G is connecting the vertices named x and y and has weight w.
2. Then pick any one of the two vertices, we will take x.
3. Then start DFS from vertex x and consider only the edges having weight less than w.
4. At the end of DFS, if we find these two vertices x,y disconnected then edge e is a part of some MST otherwise not.

Theory to prove that it is true:

To understand this, we need to recall the Kruskal's algorithm for MST where we first sort the edges in non decreasing order and then start adding the edges to the solution which does not form the cycle progressively and we take first n-1 edges.

So we can conclude from the Kruskal's algorithm that we can take the edges only which are not a part of cycle and the edge which is the smallest one connecting those two vertices (x,y). That's exactly why we are doing DFS (with considering only the edges weight less than of the given edge) to find that this is the edge(e) which is having minimum weight to connect those two vertices and does not make cycle. Disconnection of the vertices in DFS shows that it does not make cycle.

Note: DFS is Depth First Search and MST is Minimum Spanning Tree.

Answer 2

Solution:

The first question is done as per HOMEWORKLIB RULES, please repost others.

The Kruskal algorithm is best for finding the minimum spanning tree here.

Please have a look at below screenshot which explains the Kruskal with it's running time as well as the correctness proof.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)​