TIFR CSE 2018 | Part B | Question: 13

Question

Let $n\geq 3,$ and let $G$ be a simple, connected, undirected graph with the same number $n$ of vertices and edges. Each edge of  $G$ has a distinct real weight associated with it. Let $T$ be the minimum weight spanning tree of $G.$ Which of the following statements is NOT ALWAYS TRUE ?

• A. The minimum weight edge of $G$ is in $T.$
• B. The maximum weight edge of $G$ is not in $T.$
• C. $G$ has a unique cycle $C$ and the minimum weight edge of $C$ is also in $T.$
• D. $G$ has a unique cycle $C$ and the maximum weight edge of $C$ is not in $T.$
• E. $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$

Comments

According to me, T can be found in O(n) time. None of the answers below talk about option E. please verify Arjun sir.

---

We have to choose "Not true" rt?

---

YES! but one of the answers below says option E is always FALSE. But since it is a special kind of graph we can do it in O(V+E) time correct??

Answer 1

Take 2 Random graph with same number of vertices and edges:

Now check option one by one:

1. The minimum weight edge of $G$ is in $T.$ Always true
2. The maximum weight edge of $G$ is not in $T.$ True in 1st graph but false in 2nd graph Maximum weight edge will be in $T$ if it is not part of the cycle.
3. $G$ has a unique cycle $C$ and the minimum weight edge of $C$ is also in $T.$ Always true
4. $G$ has a unique cycle $C$ and the maximum weight edge of $C$ is not in $T.$ Always true
5. $T$ can be found in $O(n)$ time from the adjacency list representation of $G.$ Always true. The given graph is actually a tree with one extra edge. So, using BFS we can find the cycle in the graph and just eliminate the maximum edge weight in it. Time complexity will be $O(n).$

Hence, B is the answer.

Comments

Let's run Kruskal's algorithm. then

1. We will get minumum edge at 1st iteration. True.
2. There are $n$ vertices & $n$ edges. only $1$ edge to be discarded. The maximum will get chance to be in MST iff it is not in the cycle. Not necessarily true always.
3. While running Kruskal's, algo won't detect cycle while adding 1st edge from the cycle (which is the smallest). Always true.
4. Maximum edge would be encountered by the Kruskal at very last (among the cycle edges), then it will realize adding it will result in the cycle, so won't get added. Always true

---

Since its a tree, that is a sparse graph E=O(v). Therefore using bfs,

Time complexity =O(V+E)=O(V+V) =O(V)

---

For option 5 explanation:

Using BFS we can detect cycle, but how we can find max weight edge of that cycle so that it can be removed in O(n) time?

If we again run BFS from the vertex which reported cycle and calculate the maximum weight of any edge occurring in the path, then it may be possible that the max weight edge reported is the weight of non cycle edge.

https://stackoverflow.com/questions/47960655/finding-the-heaviest-edge-in-the-graph-that-forms-a-cycle

This uses the union-find data structure in a manner similar to Kruskal's MST algorithm, but its complexity is O(nlog(n))

 

Answer 2

Option b

If the graph contains bridge with maximum weight.

Then we must include it .

Comments

yes b is correct one

Answer 3

Can Anyone explain how D is always TRUE?

Comments

Firstly, we can use BFS to detect the cycle in an undirected graph. You can use 3 flags to keep track

-1 - initialization, 0 - when you put some node into queue, 1 - when you dequeue the node from the queue(visit)

Cycle condition - if some node which you have dequeued has a neighbour whose flag is 0(is in queue also neighbour of current node), means it has been added to the queue by some other node. So you have detected the cycle. Since there will be only one edge which is extra in the cycle which has max weight, you can just exclude that while traversing and you have got the tree. It can be done in O(V+E) time and E = V-1 so O(V)/O(n) time.

---

Please ask questions in comment section.