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

132 questions
Filter by
Sorted by
Tagged with
1answer
4k 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 ...
2answers
35 views

### Spanning trees on disconnected graphs

Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?
1answer
45 views

### Proving that a spanning tree of graph is not a minimum

Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$. Now I ...
3answers
772 views

### Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$ decreases by some positive number, how to prove the the MST is unchanged (still $T$) ? It seems obvious by ...
1answer
607 views

### Whether the 2 minimum spanning tree of same graph contains the lowest edges in common?

If two minimum spanning trees on the same graph only have 2 edges in common, then those two edges must be the lowest costs edges in the graph. True/false? and why? Because according to me if there ...
1answer
57 views

### Distance function such that we visit every “color region” once [closed]

Consider the following image: Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right. We must go through each color exactly once, and once we go outside a color, ...
1answer
39 views

### Proving equivalent definitions for MSTs

I am working on the following homework exercise: Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G. I need ...
1answer
297 views

### Time Complexity of the Kruskal Algorithm after sorting

In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
1answer
1k views

### Time complexity of kruskal using array data structure

I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps: Sort the edges as ...
1answer
162 views

### Two criteria for an edge to belong to all MSTs

Let $G$ be a connected undirected graph, with integral positive weights on the edges, and let $e_1$ be an edge of $G$. As part of an assignment I proved the following Lemma 1: The edge $e_1$ ...
1answer
138 views

### What is the maximum possible degrees of a vertex of an MST

What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?
1answer
240 views

### Turn MST of G to MST of G with one new edge

Given $T$, an MST of $G(V,E)$ connected and undirected. Assume we add an edge $e'$ with weight $w(e')$. Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i ...
2answers
404 views

### Questions on shortest path and minimum spanning tree

T/F Questions Adding a constant to every edge weight does not change the solution to the single-source shortest-paths problem. Solution - False I think this should be True, as Dijkstra's Algorithm ...
1answer
317 views

### Is this “cycle” condition sufficient for unique minimum spanning tree?

Given a connected, undirected, weighted graph $G$, the condition The maximum-weight edge in any cycle of $G$ is unique. is not necessary for $G$ to have a unique minimum spanning tree (MST). ...
1answer
484 views

### Proof required for edges in a minimum spanning tree

G=(V,E) is an undirected simple graph in which each edge e has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are ...
1answer
3k views

### Kruskal's and Prim's algorithm [duplicate]

Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's ...
2answers
330 views

### Understanding connection between minimum spanning tree, shortest path, breadth first and depth first traversal

In CLRS, in the later part of breadth first search topic, for unweighted graphs, it says: At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable ...
0answers
27 views

### Minimum spanning tree classification problem with adjacent neighbors

I am new to minimum spanning trees. But have used the last few days on a problem I think matches MST, but cannot really figure out the connection. The problem is a minimum cost problem where N ...
2answers
52 views

### MST Proof (Kleinburg & Tordos)

Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in ...
1answer
64 views

### Cost of the MST of the graph [closed]

Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated! Although the picture shows a directed graph, please treat it as ...
0answers
66 views

### How many roots are there in an undirected root

Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
1answer
133 views

### Boruvka MST algorithm using doubly linked lists

I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following: Develop an implementation of Boruvka's algorithm that uses doubly-linked ...
0answers
40 views

### N-Guest Table, Graph Problem

The Queen of England wants to organize a set of tables for n guests talking different languages. The tables have to be set in a way that every guest can speak to his neighbor on the right and his ...
0answers
106 views

### Distributed MST in $O(n \log \log n)$

I'm facing the following problem: Describe a distributed MST algorithm in time $O(n \log \log n)$ I've managed to think of the following, Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
0answers
537 views

### Using Prim's for finding minimum cost arborescence in a special setting

I have a complete graph G which is directed. In essence, a node is connected to all other nodes in the graph. Also, for every pair of nodes, say ...
0answers
215 views

### find all edges in a weighed tree that are heaviest edges in some cycle

Given an undirected graph $G=(V,E)$ and a weight function $w:E\to\{1,2,3,\dots,10\}$: Let $U\subseteq E$ the set of all edges $e\in E$ that has a cycle in $G$ such that the cycle contains $e$ and all ...
2answers
245 views

### Question about time-complexity for MST-like algorithm

I have got a problem with an excercise about graphs: Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has ...
1answer
101 views

### Minimum Spanning Tree with Kruskal - bounds on size

I am using Kruskal's algorithm to build minimum-spanning-trees. I would like to know, given that my total set of edges has size N, if there is a bounding number of ...
1answer
160 views

### Do we always get the same set of edges after running Kruskal's algorithm on a single graph?

I think it should be false because there may be more than one edge with the same weight.
1answer
3k views

### Minimum spanning tree using DFS and BFS

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs? I have gone through many answers but each answer says something different and I am not convinced....
1answer
142 views

### If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer. [closed]

If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer.
2answers
928 views

### How can I fix this pseudocode of Kruskal's algorithm? [closed]

So here, I am not sure what the while statement means. In the lecture note there is no definition for T or N or u or v. My guess is T is the minimum spinning tree, but is N the node? Why condition T ...