minimum spanning tree

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d₁(u, v) and d₂(u, v) be the shortest distances...

The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________. (answer in integer)

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the sho...

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following state...

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

Let G be a connected undirected weighted graph. Consider the following two statements. S 1 : There exists a minimum weight edge in G which is present in every minimum spanning tree...

Consider a graph G = (V, E), where V = {v 1 , v 2 , ...., v 100 }, E = {(v i , v j ) | 1 ≤ i < j ≤ 100}, and weight of the edge (v i , v j ) is |i - j|. The weight of the minimum s...

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) $$ \in $$ V $$ \t...

Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if...

Let $$G$$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements...

$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning...

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G...

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W(ij) in the matrix W below is the weight of the edge {i, j}. $$$w = \left( {\matrix{ 0 & 1 & 8 & 1 & 4...

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1...

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ such that the weight of the edge $$\left( {{v_i},\,\,\,\,{v_j}}...

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i-j|$$. The weight of a minimum spanning tree of G is:

If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices and has minimum total weight is a

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements...

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of: