retagged by
449 views
0 votes
0 votes

Consider the following statement:

$A)$ If all edge weight of a graph are positive then any subset of edges that connect all vertices and has minimum total weight is a tree.

$B)$ Let $p=<V_{0},V_{1},V_{2},........V_{k} >$ be the shortest path from vertex $V_{0}$ to $V_{k}$ for all $i,j$ such that $0\leq i\leq j\leq k$ let $p_{ij}$ be subpath of. $p$ from vertex $V_{i}$ to $V_{j}$. Then $p_{ij}$ be the shortest path from $V_{i}$ to $V_{j}$

Which statement is correct?


My question is , is tree always needed for minimum weight graph??

and what about B)?? Is it just saying each minimum path between $2$ vertices makes total shortest path?? 

retagged by

1 Answer

Best answer
2 votes
2 votes
For A, assume that any subset of edges that connect all vertices and has minimum total weight is not a tree, i.e it consists a cycle, since it contains a cycle, so you can remove the edge which is creating the cycle and still cover all the vertices , and the total weight also decreased, hence our assumption that the sum of the weight of the subset of edges which we initially chose was minimum is false.

There is a contradiction.

$\therefore$ ,we can say that any subset of edges that connect all vertices and has minimum total weight is a tree.

For B, this is what is the invariant for Dijkstra Algorithm, this is also true. You can see the proof of correctness of Dijkstra algorithm from any book.
selected by

Related questions

1 votes
1 votes
1 answer
1
Souvik33 asked Dec 19, 2022
675 views
If a -ve weight cycle is reachable from source, the Dijkstra's algorithm gets into an infinite loop TRUEFALSE
0 votes
0 votes
0 answers
3
Vaishnavi01 asked Nov 19, 2018
290 views
0 votes
0 votes
1 answer
4
saumya mishra asked Nov 6, 2018
270 views
Can shortest path contains positive weight cycle???Please explain with examples.