Question

Consider an undirected graph G = (V, E) with an injective cost function c: E →...

Consider an undirected graph G = (V, E) with an injective cost function c: E → N. Suppose T is a minimum spanning tree of G for cost function c. If we replace each edge cost c(e), e ∈ E, with cost c'(e) = c(e)2 for G, is T still a minimum spanning tree of G? Briefly justify your answer.

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

Homework Answers

Answer #1

YES. The MST of G will not change as all the edges belong to the set of Natural numbers and suppose, if we square the set of sorted natural numbers, then the set will again be sorted.

Example: Suppose we have a set of Natural Numbers, {1,2,3,4,5,6}, if we square each entry of this set, then the set becomes {1,4,9,16,25,36}, which is again sorted, hence, the MST is not bound to change.

But the MST can change if our graph contains negative weights. For example, refer to the image below:

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
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 G = (V, E) be an undirected and connected graph with Laplacian matrix L. (a)...
Let G = (V, E) be an undirected and connected graph with Laplacian matrix L. (a) How are the eigenvalues of L2 related to the eigenvalues of L? (b) If instead of running the consensus protocol, x ̇ = −Lx, one runs the protocol from Homework 1, given by x ̇ = −L2x, will consensus still be achieved? Justify your answer. (c) Assuming both x ̇ = −Lx and x ̇ = −L2x converge, which protocol converges faster? Justify your...
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.)
Suppose that we generate a random graph G = (V, E) on the vertex set V...
Suppose that we generate a random graph G = (V, E) on the vertex set V = {1, 2, . . . , n} in the following way. For each pair of vertices i, j ∈ V with i < j, we flip a fair coin, and we include the edge i−j in E if and only if the coin comes up heads. How many edges should we expect G to contain? How many cycles of length 3 should we...
Consider the graph G = K4 consisting of a single undirected cycle (a, b, c, d,...
Consider the graph G = K4 consisting of a single undirected cycle (a, b, c, d, a) of length 4. Let n be a positive integer. Give an explicit formula for the number of paths in G of length n from a to b.
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.
we consider a graph G= (V, E), with n=|V| and m=|E|. Describe an O(n+m) time algorithm...
we consider a graph G= (V, E), with n=|V| and m=|E|. Describe an O(n+m) time algorithm to find such a vertex w. Hint: a depth-first search from u might be helpful.
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.
Problem 2. Consider a graph G = (V,E) where |V|=n. 2(a) What is the total number...
Problem 2. Consider a graph G = (V,E) where |V|=n. 2(a) What is the total number of possible paths of length k ≥ 0 in G from a given starting vertex s and ending vertex t? Hint: a path of length k is a sequence of k + 1 vertices without duplicates. 2(b) What is the total number of possible paths of any length in G from a given starting vertex s and ending vertex t? 2(c) What is the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT