Prove that prims algorithm produces a minimum spanning tree, Mathematics

Assignment Help:

Prove that Prim's algorithm produces a minimum spanning tree of a connected weighted graph.

Ans: Suppose G be a connected, weighted graph. At each iteration of Prim's algorithm, an edge should be found that connects a vertex in a subgraph to a vertex outside the subgraph. As G is connected, there will all time be a path to each vertex. The output T of Prim's algorithm is a tree, as the edge and vertex added to T are connected. Suppose T1 be a minimum spanning tree of G. If T1=T then T is a minimum spanning tree. If not, let e be the first edge added throughout the construction of T that is not in T1, and V be the set of vertices connected by the edges added previous to e. After that one endpoint of e is in V and the other is not. As T1 is a spanning tree of G, there is a path in T1 joining the two endpoints. As one travels along with the path, one should encounter an edge f joining a vertex in V to one that is not in V. Now here, at the iteration while e was added to T, f could as well have been added and it would be added in place of e if its weight was less than e. As f was not added, we conclude that w(f) ≥ w(e).

Suppose T2 be the graph acquired by removing f and adding e from T1. It is simple to show that T2 is connected, has similar number of edges as T1, and the total weights of its edges is not larger as compared to that of T1, therefore it is as well a minimum spanning tree of G and it consists of e and all the edges added before it throughout the construction of V. Repeat the steps above and we will eventually acquired a minimum spanning tree of G that is similar to T. This depicts T is a minimum spanning tree.

 


Related Discussions:- Prove that prims algorithm produces a minimum spanning tree

Separable differential equations, We are here going to begin looking at non...

We are here going to begin looking at nonlinear first order differential equations. The first type of nonlinear first order differential equations which we will see is separable di

Mathematical laboratory, how to reverse positive digit number using mod fun...

how to reverse positive digit number using mod function

Roman numerals, how to determine roman numerals to digits specially when it...

how to determine roman numerals to digits specially when it hundred thousands

NUMERABILITY, AFIGURE THIS OUT(3) (14) (17) (20) (25)= 8 WHAT ARE THE PROC...

AFIGURE THIS OUT(3) (14) (17) (20) (25)= 8 WHAT ARE THE PROCEDURES (-)(+)(x)(div) BETWEEN EACH NUMBER TO COME UP WITH 8 ?

Geometric applications to the cross product, Geometric Applications to the ...

Geometric Applications to the Cross Product There are a so many geometric applications to the cross product also.  Assume we have three vectors a → , b → and c → and we make

Multiplication and division should be learnt intermeshed, E1) Do you agree ...

E1) Do you agree that multiplication and division should be learnt intermeshed with each other, or not? Give reasons for your answer.  E2) How would you explain to children wh

Prove that ar= 3/7 ac of parallelogram , ABCD is a parallelogram in the giv...

ABCD is a parallelogram in the given figure, AB is divided at P and CD and Q so that AP:PB=3:2 and CQ:QD=4:1. If PQ meets AC at R, prove that AR= 3/7 AC. Ans:    ΔAPR ∼ Δ

Practical geometry, Ask question draw a line parallel to given line xy at a...

Ask question draw a line parallel to given line xy at a distance of 5cm from it #Minimum 100 words accepted#

Function, definition and examples and types

definition and examples and types

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd