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

how is statement iv always true??

in Algorithms by Boss (12.2k points) | 95 views
0
Yes 4 is not always true consider a triangle. all edges form cyclem
+1
and i think statement 3 is true as all the edges will be distinct when the first best MST is formed second best MST is formed by removing a edge with the next highest edge so the second best also will be unique

correct me if i'm wrong!!
–1
yes @pavan,i also think the same,dts y i marked that answr
0
@Akriti, even i marked same(C). but see option (4) it says edges that do not lie in any cycle must be in MST, it doesn't say what if they lie in cycle. So (4) is true.

And for (3) who knows maybe someone can draw a graph. But not sure. maybe it depends on how weights are distributed (1+4) = (3+2)
0
3rd sttement says that MST will include all edges not in cycle,it also means that we can include any edge not in ycle even if it is the maximum size edge,but thats not true..right??

anmd since,weights are unique,so second best will just not contain the minimum weight edge,rest all same.can u give nay counter example for 3rd??
0

no even if a max weight edge is not in cycle it is to be included, consider graph::

AC = 100,DC = 101,CB = CE = BE = 1

0
So, (4) is definitely true. And According to me (3) is also true, but i mean to say maybe there exists a counter example for option (iii) statement.
+1
alright..thanks @mcjoshi..:)

Please log in or register to answer this question.

Related questions

0 votes
0 answers
4
asked Aug 27, 2018 in Operating System by Avik Chowdhury Junior (627 points) | 16 views
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
49,984 questions
55,135 answers
190,487 comments
85,106 users