Question

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.

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

Homework Answers

Answer #1

Question : To prove that T is not a minimum spanning tree of G.

Solution : A spanning tree is a tree with V -1 edges. i.e ; a tree that connects all vertices.

A minimum spanning tree is a tree of minimum total weight.

Edge inclusion lemma :

Let S be a subset of V , and suppose e = ( U,V ) is the minimum cost edge of E , with U in S and V in V - S .

e is in every minimum spanning tree of G , if e is not in T then T is not a minimum spanning tree.

Proof :

Suppose T is a spanning tree that does not contain e

Add e to T , this creates a cycle .

The Cycle must have some edge e1 = ( U1 , V1 ) with U1 in S and V1 in V - S .

T1 = T - { e1 } + {e} is a spanning tree with lower cost or a minimum spanning tree   

Hence T is not a minimum spanning tree , Since e is the unique lightest edge.

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
Show that an edge e of a connected graph G belongs to any spanning tree of...
Show that an edge e of a connected graph G belongs to any spanning tree of G if and only if e is a bridge of G. Show that e does not belong to any spanning tree if and only if e is a loop of G.
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!
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.
Given an undirected graph with no more than 2 vertices and unique edge weights between all...
Given an undirected graph with no more than 2 vertices and unique edge weights between all pairs of vertices, prove that the edge with the largest weight cannot be in a minimum spanning tree.
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.
(a) Let L be a minimum edge-cut in a connected graph G with at least two...
(a) Let L be a minimum edge-cut in a connected graph G with at least two vertices. Prove that G − L has exactly two components. (b) Let G an eulerian graph. Prove that λ(G) is even.
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.)
A Hamiltonian walk in a connected graph G is a closed spanning walk of minimum length...
A Hamiltonian walk in a connected graph G is a closed spanning walk of minimum length in G. PROVE that every connected graph G of size m contains a Hamiltonian walk of length at most 2m in which each edge of G appears at most twice.
Let G=(V,E) be a connected graph with |V|≥2 Prove that ∀e∈E the graph G∖e=(V,E∖{e}) is disconnected,...
Let G=(V,E) be a connected graph with |V|≥2 Prove that ∀e∈E the graph G∖e=(V,E∖{e}) is disconnected, then G is a tree.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT