Recent questions tagged minimum-spanning-tree

Consider the following statement:For every connected weighted graph $G$, there exists some vertex $v$ such that a shortest path tree rooted at $v$ is identical to a minim...

Let, $G=(V,E)$ be a connected undirected graph. Edge weights may be negative.We want to choose, $E'\subseteq E$ such that $G'=(V,E')$ is connected and: $\sum_{e\in E'}w(e...

Consider the following statements.Let $M$ be an MST of a connected undirected graph with positive edge weights. If $7$ is added to every edge weight, $M$ is guaranteed to...

Let $G=(V,E)$ be a connected weighted undirected graph in which all edge weights are distinct.Let, $e=(u,v)$ be an edge of weight $w(e)$.Construct a graph $G'$ containing...

Consider the statement:The minimum spanning tree of a connected weighted graph $G$ is unique if and only if all edge weights in $G$ are distinct.True False

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason RAssertion A: Kruskal's algorithm and Prim's algorithm always produce m...

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...

Let $\mathrm{G}(\mathrm{V}, \mathrm{E})$ be a simple, undirected, edge-weighted graph with unique edge weights.Which of the following statements about MST (minimum spanni...

guys can anyone suggest something on how to count the number of minimum spanning trees?? 

Which of the following algorithms is used to find the minimum spanning tree in a graph?Dijkstra's AlgorithmKruskal's AlgorithmBellman-Ford AlgorithmFloyd-Warshall Algorit...

Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...

​​​​Let $\text{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...

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, ...

The maximum value of $\text{x}$ such that the edge between the nodes $\text{B}$ and $\text{C}$ is included in every minimum spanning tree of the given graph is _________....