Minimum Spanning Trees

Question 1

what type of problems use MST ?

Answer 1

problems with roads anc cities

Question 2

what is the psdoeocde code for genric mst ?

Answer 2

GENERIC-MST.G; w/
A= empty queue
while A does not form a spanning tree
find an edge (u,v) that is safe for A
A = A U {(u,v)}
return A

Question 3

what is a safe edge ?

Answer 3

The edge connects two disconnected components of the graph.

Adding the edge will not create a cycle in the partial spanning tree.

Question 4

pedoucode for Prim’s

Answer 4

Prim(g,s,w)
Initlaize-single-source
r.key=0;
Q=G.V
While Q=empty
u = ExtractMin(Q)
for all v E G.Adj[u]
if v.key > w(u,v) & v E Q
v.pi=u
v.key=w(u,v)

Question 5

Key Pair, Root Queue, Extract, Visit, Update

Answer 5

“Key Pair”: Initialize each vertex’s key to ∞ and predecessor (π) to NIL.

“Root”: Set the starting vertex (r) key to 0.

“Queue”: Add all vertices to the priority queue (Q).

“Extract”: Extract the minimum key vertex u from the queue.

“Visit”: For each neighbor v of u, check the edge condition (w(u, v) < v:key).

“Update”: If the edge is better, update v’s key and predecessor.

Question 6

do example of page 656

Question 7

what is running time of prim’s ?

Answer 7

O(E log V)

Question 8

prove path relatzation propety ?

Question 9

what is the covergence property ?