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

The Gateway to Computer Science Excellence

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,382 answers

198,530 comments

105,323 users