Let G = (V, E) be a weighted undirected, connected graph. Let (u, v) be an edge
ID: 3573756 • Letter: L
Question
Let G = (V, E) be a weighted undirected, connected graph. Let (u, v) be an edge of G. We want to find a Minimum Spanning Tree of G subject to the constraint that it must contain (u, v). Given an efficient algorithm for this task, and analyze the running time of your algorithm. No justification needed. Let (u, v) and (u', v') be edges of G. We want to find a Minimum Spanning Tree of G subject to the constraint that it must contain exactly one of the edges (u, v) and (u', v'), but not both. Given an efficient algorithm for this task, and analyze the running time of your algorithm.Explanation / Answer
a).
In this algorithm we will recieve a graph, vertex set and then wee will traverse through the graph iand if the required edge is found then we will add that to graph.
MST (G,u,v)
G' <- Ø
for each vertex v' in V[G']
if E[v'] == u
do MAKE-SET(v')
sort the edge set in ascending order by weight
UNION(u,v)
Return G'
b).
MST (G,u,v,u',v')
G' <- Ø
for each vertex v" in V[G']
if E[v"] == u
do MAKE-SET(v")
sort the edge set in ascending order by weight
for each edge u,v and u',v' taken in ascending order
if FINDSET(u,u') == FINDSET(v,v')
the G'<- G{u,v}
UNION(u,v)
Return G'
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.