Made Easy Test Series:Algorithm- Minimum Weight Path

Question

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

Answer 1

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.

Comments

But, in A) why tree is necessary??

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

---

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.