in Algorithms retagged by
329 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?? 

in Algorithms retagged by
by
329 views

1 Answer

2 votes
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.
selected by

2 Comments

But, in A) why tree is necessary??

It can be a graph, but not tree. right??
0
0
Any simple connected graph with no cycles is a tree . The thing is the graph must be free of cycles which means it must be a tree.
1
1

Related questions