2,031 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.

2 Answers

Best answer
4 votes
4 votes
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

Related questions

2 votes
2 votes
0 answers
2
Na462 asked Nov 14, 2018
1,473 views
2 votes
2 votes
1 answer
3