#self doubt #Algorithm #Spanning tree
in Algorithms
35 views
0 votes
0 votes
True/False

1) Multiplying all edge weight by a positive number might change the graph MST.

2) If all edge in a graph have distinct weight than the shortest path between two vertices is unique.

Please answer with reason.

Thanks
in Algorithms
by
9 points
35 views

1 Answer

0 votes
0 votes

 If all edge in a graph have distinct weight than the shortest path between two vertices is unique.
 

FALSE. Even if no two edges have the same weight, there could be two paths with the same weight. For example, there could be two paths from s to t with lengths 3 + 5 = 8 and 2 + 6 = 8. These paths have the same length (8) even though the edges (2, 3, 5, 6) are all distinct.

Or You can take a triangle graph (complete graph on three vertices) whose edge weights are 2,3,5. Now, you can see that there are two vertices such that there are two different shortest paths between those two vertices, One path is single edge path of weight 5, and another path is two edge path of length 5. 

 Multiplying all edge weight by a positive number might change the graph MST.

False. 

Kruskal’s algorithm only cares about the order of the edge weights, not their absolute values, and adding some fixed value to each edge OR multiplying each edge with a positive number, will not change the sorted order. So, MST will remain same But cost of MST will be changed. 

by
1.7k points
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.