605 views

Let $G = (V,E)$ be an undirected connected simple (i.e., no parallel edges or self-loops) graph with the weight function $w: E \rightarrow \mathbb{R}$ on its edge set. Let $w(e_{1}) < w(e_{2}) < · · · < w(e_{m})$, where $E = \left\{e_{1}, e_{2}, . . . , e_{m}\right\}$. Suppose $T$ is a minimum spanning tree of $G$. Which of the following statements is FALSE?

1. The tree $T$ has to contain the edge $e_{1}$.
2. The tree $T$ has to contain the edge $e_{2}$.
3. The minimum weight edge incident on each vertex has to be present in $T$.
4. $T$ is the unique minimum spanning tree in $G$.
5. If we replace each edge weight $w_{i} = w(e_{i})$ by its square $w^{2}_{i}$ , then $T$ must still be a minimum spanning tree of this new instance.
edited | 605 views
+4

Point to be noticed --> 'Edges weights belongs to real number'

Answer is E .  The catch here is Edges weights belongs to real number . Therefore  edge weight can be negative . In that case the minimum spanning tree may be different .

$\line(1,0){299}$

EDIT-

(Here every edge weight is distinct, therefore MST is unique. You do it using any algo.)

Option A is True. If we apply kruskal's algorithm then it will choose $e_1$

Option B is True. If we apply kruskal's algorithm then it will also choose $e_2$, and 2 edges can not forms a cycle. ($e_3$ is not guaranteed in MST, as it may form cycle.)

Option C is also true. If we apply prims also on any vertex (say u) then it chooses minimum

weight edge incident on vertex u.

Option D is true. Because every edge weight is distinct.

edited by
0
whats the meaning of c) option
0
if their is min cost edge from every vertex  then it always be in min cost spanning tree.

each vertex connected via one min cost edge.
0
ok , suppose there is pentagon and weight is in this way , that if consider min weighted edge then there will be cycle so i will left it ... so vertex having min edge but i did not consider it ...

so whats the actual meaning ...??
0

read definition all edge weight are distinct .

example

node 1 connect with 2 edge with edge weight 1,2,3 then choose 1 weight  edge

node 2 connect with 2 edge with edge weight 2,3 ,4 then choose 2 weight  edge

0
i considered as distinct .... by the way i got what are you saying ....thanks now clear... :)
0

@  sonam vyas  I ALSO HAVE SAME DOUBT ABOUT OPTION C. PLZ CLEAR MY DOUBT .....

0
If the min cost edge of any vertex forms a cycle then we don't consider it in MST. So option c is not true always.

I agree with option E
0

Here edge weights are distinct and using prims algo you can't skip min cost edge in a cycle....iinstead you will remove higher cost edges
0
Yes got it... Thnks