in Algorithms edited by
4,518 views
7 votes
7 votes

 

Consider a simple undirected weighted graph $\textit{G},$ all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of $\textit{G}$ is/are $\text{TRUE}?$

  1. The edge with the second smallest weight is always part of any minimum spanning tree of $\textit{G}.$
  2. One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of $\textit{G}.$
  3. Suppose $S \subseteq V$ be such that $S \neq \phi$ and $S \neq V$. Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V \setminus S.$ Such an edge will always be part of any minimum spanning tree of $\textit{G}.$
  4. $\textit{G}$ can have multiple minimum spanning trees.
in Algorithms edited by
by
4.5k views

2 Comments

The question says all of whose edge weights are distinct.

Here it's written "weights" that means graph has 2 or more edges(means at least 3 vertices)

Therefore option A will be correct in every case.

 

But if we have a graph K3 in that case third smallest and the fourth smallest weights are not possible in the minimum spanning tree.

 

Please correct me if I'm wrong. 

0
0

@Captain Cold

Well, we also use plural for zero, because plural is anything not equal to one. Atleast that is what I found on the internet. So, it’s always 0 rupees, 0 busses, 0 cars, 0 “edges”. The question allows there to be 0 “edges”. Therefore option A becomes wrong.

Unless assuming the options as implications is correct, in which case options A,B,C is the right combination.

This question is very poorly defined. If there is any rectification, it will be declaring it ambiguous.

2
2

1 Answer

4 votes
4 votes
Best answer

Answer : A,B,C

In the given undirected weighted graph, All the edge weights are distinct, hence, there will be Exactly One Minimum Spanning Tree for the graph.

Option A :

The edge with the second smallest weight is always part of any minimum spanning tree of $G$.

Since $G$ has Exactly One MST, the above statement can be written as “The edge with the second smallest weight is always part of the minimum spanning tree of $G$.”

This can be proven by “Kruskal Algorithm” to find MST. Minimum Edge, Second Minimum Edge, both will be added in the MST by Kruskal Algorithm (Two edges cannot bring cycle)

Option B :

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.

Since $G$ has Exactly One MST, the above statement can be written as “One or both of the edges with the third smallest and the fourth smallest weights are part of the minimum spanning tree of $G$.”

This is True. Minimum Edge, Second Minimum Edge, both will be added in the MST by Kruskal Algorithm (Two edges cannot bring cycle), BUT third minimum edge might introduce cycle in the MST, and if so happens, we do not include third minimum edge in the MST and add fourth minimum edge in the MST.

Option D :

$G$ can have multiple minimum spanning trees : False (Because all edge weights are distinct)

Option C :

Suppose $S \subseteq V$ be such that $S \neq \phi$ and $S \neq V$ . Consider the edge with the minimum weight such that one of its vertices is in $S$ and the other in $V- S $ . Such an edge will always be part of any minimum spanning tree of $G.$

This is True. This is a popular and basic property of Minimum Spanning Tree, known as “Cut Property.” The cut property is the basis for the algorithms that we consider for the MST problem.  “Cut Property” and “Cycle Property” are basic theorems in the study of MST, and must be understood by all, with proof.

$\color{red}{\text{ Cut property }}$ :

Given any cut in an edge-weighted graph (with all edge weights distinct), the crossing edge of minimum weight is in the MST of the graph. 

Given a cut $(S, V-S)$ of $G$, recall that an edge $(u, v) \in E$ is said to cross the cut if exactly one of $u$ and $v$ is in $S$. An edge $e = (u, v)$ is a minimum weight edge crossing the cut $(S, V-S)$ if its weight is the smallest of any edge crossing $(S, V-S).$ 

Then $e = (u,v)$ must be included in the minimum spanning trees of $G.$

Let $G = (V, E, w)$ be a connected undirected weighted graph with distinct edge weights. For any cut $(U,V-U)$ of G, the minimum weight edge that crosses the cut is in the minimum spanning tree $MST(G)$ of $G.$

We can prove it as following :

$\color{blue}{\text{ Proof :}}$

The proof is by contradiction. Assume the minimum-weighted edge $e = (u, v)$ is not in the MST. Since the MST spans the graph and is a connected tree, there must be a unique simple path $P$ connecting $u$ and $v$ in the MST (i.e., consisting of just edges in the MST). The path must cross the cut between $U$ and $V - U$ at least once since $u$ and $v$ are on opposite sides. Let $e’$ be an edge in $P$ that crosses the cut. By assumption the weight of $e’$ is larger than that of $e$. Now, insert $e$ into the graph—this gives us a cycle that includes both $e$ and $e’$—and remove $e’$ from the graph to break the only cycle and obtain a spanning tree again. Now, since the weight of $e$ is less than that of $e’$ , the resulting spanning tree has a smaller weight. This is a contradiction and thus $e$ must have been in the tree.

Hence Proved.

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/assignments/MIT6_046JS12_ps2_sol.pdf

https://algs4.cs.princeton.edu/43mst/

http://www.cs.cmu.edu/afs/cs/academic/class/15210-s15/www/lectures/mst-notes.pdf

$\color{red}{\text{ Cycle property :}}$  Let $G$ be a connected directed weighted graph in which All edge weights are distinct.

Let $C$ be any cycle in $G$, and let $f$ be the max cost(weight) edge belonging to $C.$ Then the MST does not contain $f.$

https://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf

http://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html

https://stackoverflow.com/questions/53057955/is-the-cut-property-two-way

edited by

4 Comments

@Subhajit Panday

when p2 is false.... then p1 and p2 must result false. So conclusion must be true. Conclusion not change

0
0

@Shaik Masthan sir

the logical validity of the conclusion wont change , I agree.

I am saying Conclusion statement may change since if P2 is false ( i.e n<=3 ) , how can you say about fourth minimum ( since it does not exist )  and if n=3 graph is cycle graph , then 3rd minimum is also not a part  of the MST .

and also one more doubt why cant we assume the FOL interpretation in the form of P1 → C

P1→ simple connected graph ( “n” can be any positive integer ) // as in Question 

now conclusion is not always TRUE right ? ( for graph with 1 edge ) 

0
0
If (p1 and p2) becomes false, then all the options result in the implication being true.
0
0