Question

Consider the following graph. V(G) = {v1, v2, v3, v4}, e(G) = {e1, e2, e3, e4, e5}, E(G) = {(e1,[v1,v2]),(e2,[v2,v3]),(e3,[v3,v4]), (e4, (v4,v1)), (e5,[v1,v3])} Draw a picture of the graph on scratch paper to help you answer the following two questions. How many edges are in a spanning tree for graph G? What is the weight of a minimum-weight spanning tree for the graph G if the weight of an edge is defined to be W (ei) L]?

Answer 1

-> The graph for the given information is,

here we are having 4 vertices and 5 edges as given.

еч vu РЬ ei ез SY ер V3

Now , we need to construct a spanning tree for this graph.

-> Spanning tree is nothing but it should contain all the vertices of the graph with minimum number of edges.

-> therefore the spanning tree for the above garph is,

VI Vy el ez V2 ez V3

here you can see we have all the 4 vertices.

Question 1:

Three edges(e1,e2,e3) are there in the spanning tree for graph G.

Question 2:

To calculate the weight of a spanning tree we are given a formula.

Wlei)= [] we are having 3 edges, e, , 22, 23 W(ei) = [] w(ez)= [ 31 = 1 W(ez)= 3 need to sum all these weights, Weeilt wlez)+w(13) = {+1+3 2 1+ 2+ 3 6 2 2 Therefore, weight of the Spanning tree la

Therefore the weight is 3.