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'

Navigate

Let G = (V, E) be a graph with |V| = n, and let k be an integer, where 1 lesstha

Let G = (V, E) be an undirected connected graph and let c : E R + be a function

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let G = (V, E) be a weighted undirected, connected graph. Let (u, v) be an edge

Question

Explanation / Answer

Related Questions

Navigate