Recent questions tagged minimum-spanning-tree

II. if an edge (u,v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph.III. If (u,v) is a light edge connecting CC(conne...

How many of following are correct statements ?(i) A graph where all edge weights are distinct can have more than one shortest path between two vertices u and v(ii)adding...

consider a graph G given below, if the edges are having weight 1,2,3,4,5,6,7,8,9,10; then maximum possible weight a minimum weight spanning tree of G can have isaccording...

consider the following graph in which x represents the number of minimum cost spanning tree and y represents the number of 2nd minimum cost spanning tree.which of the fo...

A Spanning tree T(V,E) has bottleneck edge, means all edges present in T with the greatest cost would be bottleneck edges.Now they have said, A spanning tree T of G is a...

Let us assume that $G$($V$, $E$) is a weighted complete graph such that weight of the edge <$V_K$,$V_L$>=2|$K$-$L$|. The weight MST of $G$ with 100 vertices is __________...

Let $T$ be a minimum weight spanning tree of graph $G = (V, E)$, and let $V’$ be a subset of $V$ . Let $T'$ be a sub-graph of $T$ induced by $V'$ and let $G’$ be a sub-gr...