in Graph Theory
2,020 views
7 votes
7 votes

Which of the following statements related to graphs are True?

  1. Minimum Spanning Tree has ALWAYS Minimum weight edge included in it.
  2. Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it.
  3. Maximum Spanning Tree has ALWAYS Maximum weight edge included in it.
  4. Maximum Spanning Tree MIGHT have Minimum weight edge weight included in it.
  5. Shortest path from source to destination MAY OR MAY NOT have Minimum weight edge included in it.
  6. Shortest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
  7. Longest path from source to destination MAY OR MAY NOT have Minimum weight edge included in it.
  8. Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
in Graph Theory
2.0k views

1 comment

1,4,5,6,7,8
0
0

2 Answers

4 votes
4 votes
Best answer
Minimum Spanning Tree has ALWAYS Minimum weight edge included in it.
FALSE.
If all edge weights are same and the graph is complete then out of n(n-1)/2 edges only n-1 edges should be in MST but the weight of the rest of the edges are also minimum but these edges are not part of MST.

 

Minimum Spanning Tree MIGHT have Maximum weight edge weight included in it.
True
If  Maximum weight edge is a cut edge then it must be part of MST.

 

Maximum Spanning Tree has ALWAYS Maximum weight edge included in it.
False.
If all edge weights are same and the graph is complete then out of n(n-1)/2 edges only n-1 edges should be in Maximum weight Spanning Tree but the weight of the rest of the edges are also maximum but these edges are not part of Maximum weight Spanning Tree.

 

Maximum Spanning Tree MIGHT have Minimum weight edge weight included in it.
True
If  Minimum weight edge is a cut edge then it must be part of Maximum weight Spanning Tree.

 

Shortest path from source to destination MAY OR MAY NOT have Minimum weight edge included in it.
True
Minimum edge weight may be directed to some other node from which destination is unreachable (Many explanations possible).

 

Shortest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
True
Maximum edge weight may be directed to some other node from which destination is unreachable (Many explanations possible).

 

Longest path from source to destination MAY OR MAY NOT have Minimum weight edge included in it.
True
Minimum edge weight may be directed to some other node from which destination is unreachable (Many explanations possible).

 

Longest path from source to destination MAY OR MAY NOT have Maximum weight edge included in it.
True
Maximum edge weight may be directed to some other node from which destination is unreachable (Many explanations possible).
selected by

1 comment

in option 6, what if one of the weight is negative, then option 6 can also become false?  @   whats say??

0
0
–1 vote
–1 vote

all option are true.

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