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

Trignometry, how to find value of cos20 without using calculator

how to find value of cos20 without using calculator

#titldifference between cpm n pert operation research pdfe.., difference be...

difference between cpm n pert operation research pdfepted#

Matrix inverse, Here we need to see the inverse of a matrix. Provided a squ...

Here we need to see the inverse of a matrix. Provided a square matrix, A, of size n x n if we can get the other matrix of similar size, B that, AB = BA = I n after that we call

Calculus, I need help with my calculus work

I need help with my calculus work

Find out the slope of equations, Example:  find out the slope of equations ...

Example:  find out the slope of equations and sketch the graph of the line.                         2 y - 6x = -2 Solution To get the slope we'll first put this in slope

Variation, If p=10 when q=2,find p when q=5

If p=10 when q=2,find p when q=5

Word problem, Twins Olivia and Chelsea and their friend Rylee were celebrat...

Twins Olivia and Chelsea and their friend Rylee were celebrating their fourteenth birthdays with a party at the beach. The first fun activity was water games. As Nicole arrived, sh

Direction field for the differential equation, We require to check the deri...

We require to check the derivative thus let's use v = 60. Plugging it in (2) provides the slope of the tangent line as -1.96, or negative. Thus, for all values of v > 50 we will ha

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