Question

Let T be a minimum spanning tree of graph G obtained by Prim’s algorithm. Let Gnew...

Let T be a minimum spanning tree of graph G obtained by Prim’s algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges, with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T ? If you answer yes, explain how; if you answer no, explain why not.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Considering the above Graph, MST of Gnew is missing with an edge compared to the Graph G. Hence its uses the vertices of both the Graph G and Gnew.

Hence we conclude that this if possible in some cases and not possible in some cases. If we add new edges to Graph T, in some cases it is possible and in some cases it is not possible because it all depends on the weight of new edges which is being added, and in some cases MST of T will differ if the new weight is smaller than the weight in the original graph.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let G be a connected plane graph and let T be a spanning tree of G....
Let G be a connected plane graph and let T be a spanning tree of G. Show that those edges in G∗ that do not correspond to the edges of T form a spanning tree of G∗ . Hint: Use all you know about cycles and cutsets!
Consider a minimum spanning tree for a weighted graph G= (V, E)and a new edge e,...
Consider a minimum spanning tree for a weighted graph G= (V, E)and a new edge e, connecting two existing nodes in V. Explain how to find a minimum spanning tree of the new graph in O(n)time, where n is the number of nodes in the graph. Prove correctness of the algorithm and justify the running time
Let e be the unique lightest edge in a graph G. Let T be a spanning...
Let e be the unique lightest edge in a graph G. Let T be a spanning tree of G such that e ∉ T . Prove using elementary properties of spanning trees (i.e. not the cut property) that T is not a minimum spanning tree of G.
A spanning tree of connected graph G = (V, E) is an acyclic connected subgraph (V,...
A spanning tree of connected graph G = (V, E) is an acyclic connected subgraph (V, E0 ) with the same vertices as G. Show that every connected graph G = (V, E) contains a spanning tree. (It is the connected subgraph (V, E0 ) with the smallest number of edges.)
Let G = (V,E) be a graph with n vertices and e edges. Show that the...
Let G = (V,E) be a graph with n vertices and e edges. Show that the following statements are equivalent: 1. G is a tree 2. G is connected and n = e + 1 3. G has no cycles and n = e + 1 4. If u and v are vertices in G, then there exists a unique path connecting u and v.
Let G be a directed graph. In class, we saw an algorithm that uses the information...
Let G be a directed graph. In class, we saw an algorithm that uses the information obtained from a DFS to determine the strongly connected components of G. Make an argument for why using instead BFS will not work. Namely, focus on why the order in which we visit vertices in a BFS does not give us any information about the strongly connected component structure in G (note a BFS does not label vertices with pre and post values, so...
Let us consider Boruvka/Sollin's algorithm as shown . Note that Boruvka/Sollin algorithm selects several edges for...
Let us consider Boruvka/Sollin's algorithm as shown . Note that Boruvka/Sollin algorithm selects several edges for inclusion in T at each stage. It terminates when only one tree at the end of a stage or no edges to be selected. One Step of Boruvka/Sollin's Algorithm 1: Find minimum cost edge incident to every vertex. 2: Add to tree T. 3: Remove cycle if any. 4: Compress and clean graph (eliminate multiple edges). (a) Suppose that we run k phases of...
Show Proof of correctness and state, and solve the Recurrence using the Master Theorem. Let G...
Show Proof of correctness and state, and solve the Recurrence using the Master Theorem. Let G = G(V, E) be an arbitrary, connected, undirected graph with vertex set V and edge set E. Assume that every edge in E represents either a road or a bridge. Give an efficient algorithm that takes as input G and decides whether there exists a spanning tree of G where the number of edges that represents roads is floor[ (|V|/ √ 2) ]. Do...
You are given a directed acyclic graph G(V,E), where each vertex v that has in-degree 0...
You are given a directed acyclic graph G(V,E), where each vertex v that has in-degree 0 has a value value(v) associated with it. For every other vertex u in V, define Pred(u) to be the set of vertices that have incoming edges to u. We now define value(u) = ?v∈P red(u) value(v). Design an O(n + m) time algorithm to compute value(u) for all vertices u where n denotes the number of vertices and m denotes the number of edges...
a) Sam sees that he has a graph with negative weight edges and wants to find...
a) Sam sees that he has a graph with negative weight edges and wants to find a shortest path tree from a given source vertex. He determines that the smallest edge weight in the graph is -10, so he just adds 11 to every edge weight, then runs Dijkstra’s on the new graph. Is the shortest path tree he finds the same as the shortest path tree in the original graph? Explain why or why not. Note that by “the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT