The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
153 views

Consider the following undirected graph with some edge costs missing.

Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold?

  1. $cost(a,b)\geq 6$.
  2. $cost(b,e)\geq 5$.
  3. $cost(e,f)\geq 5$.
  4. $cost(a,d)\geq 4$.
  5. $cost(b,c)\geq 4$.

Please someone solve and explain :)

in Graph Theory by Loyal (7.8k points)
edited by | 153 views
+2
apply Kruskal algo for every option and check if it is satisfying the the minimum spanning tree or not

answer is d) because if cost(a,d) is 4 then (a,d) will be in minimum spanning tree rather than (d,e) and we want (d,e) so option d need not hold

1 Answer

+4 votes
Best answer

option d

if you put the cost of enequalities then  minimum cost spanning tree must be a all weavy edges.

then we put the  cost of edges one by one if mst is only weavy edges then it is right otherwise it is wrong

by Boss (34.9k points)
selected by
+1
Thanks :)

Related questions

+7 votes
1 answer
7
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,742 answers
192,221 comments
90,464 users