# Questions tagged [minimum-spanning-tree]

Use this tag whenever your question is related to minimum spanning tree (MST). An MST of a connected edge-weighted graph G is a spanning tree whose sum of edge weights is as small as possible. We usually assume $G$ is finite, simple and undirected.

228 questions
Filter by
Sorted by
Tagged with
39k views

### When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
6k views

### Are all MST minimum spanning trees reachable by Kruskal and Prim?

I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for ...
18k views

### Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?
2k views

### Does a graph always have a minimum spanning tree that is binary?

I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?
8k views

### Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
7k views

### Finding MST after adding a new vertex

Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to some of the vertices. Find a new MST for the new ...
161 views

### MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
8k views

### Why do we have different algorithm for MST when graphs are directed?

What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not ...
2k views

### Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words $$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\... 6 votes 2 answers 4k views ### Counting Minimum Spanning Trees I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph G=(V,E) given by When running ... 6 votes 2 answers 3k views ### Find all critical edges for minimum spanning tree This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne. 4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to ... 5 votes 2 answers 1k views ### Is the inverse of MST cycle property always true? Why? I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees. I have found many potential ... 5 votes 2 answers 903 views ### MST with half the edges the maximum weight I have been cracking my head over the following question - You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with ... 5 votes 2 answers 613 views ### Minimum spanning tree formulation as integer program The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ... 5 votes 0 answers 114 views ### Minimum spanning tree and Hamiltonian path For a graph G(V,E), under what conditions is a minimum spanning tree of G equal to a hamiltonian path on G? IS there any body of literature connecting these two? 4 votes 2 answers 1k views ### Diameter-constrained Minimum Spanning Tree Problem The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph G = (V,E) of different weights where V is the set of vertices and E is the set of ... 4 votes 2 answers 591 views ### Spanning tree - minimum difference between smallest and largest weight I am given an undirected, weighted graph G, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the ... 4 votes 2 answers 126 views ### Can Edge Belong to a cycle if it is part of multiple BFS products Given a simple connected undirected graph. with V vertices and E edges. Let e be some edge from E. If I perform |V| different BFS runs - meaning started each time from a different vertex - and in ... 4 votes 1 answer 351 views ### Are all minimum spanning trees optimized for fairness? I know by definition that a minimum spanning tree (MST) of a weighted, connected graph has the lowest global value for for sum of all edges in a path that connects all vertices. I'm curious if all ... 4 votes 1 answer 1k views ### Minimum diameter spanning tree problem Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph G(V, E), weight function w: E \rightarrow R, w(e) > 0\ \forall e \in E, find the ... 4 votes 1 answer 119 views ### Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1) There is a finite set of points S in the plane with  |S| = n. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of S, so the MST is the ... 4 votes 2 answers 446 views ### Edge exchange property of two Minimum Spanning Trees Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T' Then I want to prove ... 4 votes 2 answers 3k views ### Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree? I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST). From my understanding: The ... 4 votes 1 answer 191 views ### Is a perfect matching's weight less than MST of a metric graph? This is part of a bigger proof I'm trying to solve, which eventually came down to one thing: Let G=(V,E) an un-directed, complete, metric graph (maintains the triangle inequality) with an even ... 4 votes 1 answer 290 views ### Between every two MST's there's a series of "nearby" MST's Given undirected connected graph G=(V,E) and a weight function w:E\to\mathbb{R}, two MST's T_1, T_2 are nearby if there exists e\in T, e'\in T' such that T'=(T-\{e\})\cup\{e'\}. Prove that ... 4 votes 3 answers 1k views ### Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree? Let G be an undirected connected weighted graph, and let T be a minimum spanning tree of G with edge weights: w_1 \le w_2 \le ... \le w_{n-1}. Now let T' be some other spanning tree of G (... 4 votes 1 answer 625 views ### Alternative algorithm for minimum spanning tree construction Let \textit{G(V,E)} be an undirected connected graph with distinct costs on its edges. Initialize \textit{T} to be any spanning tree of \textit{G}. Consider an algorithm which replaces an ... 3 votes 2 answers 443 views ### Minimum path - robot motion problem combined with freeze tag problem Alright, I am not entirely sure if this is the right place to ask this, but here goes: I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and ... 3 votes 2 answers 5k views ### What edges are not in any MST? This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. Consider a weighted undirected graph.... 3 votes 3 answers 452 views ### Need Help Understanding MST Cutset Formulation I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: An ... 3 votes 2 answers 225 views ### Finding MST for connected graph with |E|=|V|+87 Given G=(V,E) undirected, connected graph and weights given by w:E \to \mathbb R. We also know that |E|=|V|+87. Find Minimum spanning tree of G. Obviously we can use Prim in O(|V| \cdot \... 3 votes 3 answers 944 views ### MST: Is there such an example of a graph with unique mst and not unique light edge? The problem is the following: Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut. I am trying to ... 3 votes 2 answers 395 views ### What is the best way to merge cycles to minimise total weight? Suppose I have a vertex-disjoint set S of simple cycles in a weighted undirected graph. So no vertex v is contained in more than one cycle. A cycle c is a closed path with no repeated vertices: ... 3 votes 1 answer 7k views ### MST: Are all safe edges, light edges? Following are some definitions from CLRS: DEFINITIONS : 1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides ... 3 votes 1 answer 609 views ### Maximal Minimum Spanning Tree by Removing k Edges The problem is as follows: Consider a connected, undirected, and weighted graph G = (V, E, w) and an integer 0 < k < |E| - |V| + 1. Describe and analyze and efficient algorithm to remove ... 3 votes 1 answer 1k views ### What is the formal way to prove this is still a minimum spanning tree? I don't get the formal way of proving the following cases: Suppose I have a minimum spanning tree T in a graph G(V, E), with positive edge weights w, I want to prove the following: 1) If I ... 3 votes 1 answer 160 views ### Algebraic (spectral) algorithms for the minimum spanning tree problem Are there any algorithms that use the spectral properties of a graph to solve the minimum spanning tree problem? To clarify further what I have in mind, starting with the Laplacian matrix I want to ... 3 votes 1 answer 85 views ### Finding minimum spanning tree of a special form graph I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm ... 3 votes 1 answer 450 views ### Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree? Let G be a connected weighted undirected graph. Let T be a minimum spanning tree (MST) of G. Consider removing an edge e=(a,b) from T, which will give two subtrees T_a and T_b, where Ta... 3 votes 1 answer 111 views ### how to generate all spanning trees from one spanning tree If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must ... 3 votes 1 answer 346 views ### Constructing a minimum spanning tree from an all-shortest path graph? Given an n \times n shortest path distance matrix D. And a complete graph G(D) on n nodes, where edge (i, j) has weight D_{ij}. Furthermore, the distance matrix D is computed for a ... 3 votes 1 answer 646 views ### Local search to find minimum degree spanning tree Suppose for a graph G=(V,E) and a spanning tree T of G, \Delta(T) is the largest degree of a vertex in T, and let \Delta^* be the smallest such quantity over all spanning trees of G. We have ... 3 votes 1 answer 140 views ### Find all edges of G contained in some MSP I have the following question in a homework: Let G = (V,E) be an undirected graph, and let$$A = \{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\}.$$We were asked to find A in O(m ... 3 votes 1 answer 347 views ### Algorithm for MST connecting a subgraph I already know how to find the MST of a connected graph. This MST will have the least total weight and will connect all nodes in the graph. However, this is a problem I have to deal with: Given a ... 3 votes 0 answers 58 views ### What is the name for this minimal satisfying set covering problem? [duplicate] Preface Hello! I have a problem here that's difficult for me to Google, and I don't know if there's a name for it. It feels like a set cover problem of some kind, but I'm very unfamiliar with ... 3 votes 0 answers 74 views ### A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path The problem. Given an undirected, connected, edge-weighted graph G=(V, E_G; w) and a minimum spanning tree (MST) T=(V, E_T) of G, the MST sensitivity analysis problem asks to find, for each ... 3 votes 1 answer 112 views ### Proof that "local" minimum spanning tree is "global" minimum spanning tree I'm trying to understand a proof from the book "Graph Theory with Application to Engineering & Computer Science" by Narsingh Deo. The chapter is about trees in non oriented graphs. A bit ... 3 votes 0 answers 52 views ### Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm I have a graph algorithm that runs in:$$ T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
Given the following statement: For a graph $G$, consider its minimum spanning tree $T$ and let $e = (a,b)$ be an edge that is not a light edge for a given cut $C$. Then $e$ never belongs to $T$. ...