But, in A) why tree is necessary??

It can be a graph, but not tree. right??

It can be a graph, but not tree. right??

Dark Mode

329 views

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??

2 votes

Best answer

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.

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.