Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
2answers
88 views

Minimum Distance Spanning Tree Dijkstra

I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below: MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)} Is my ...
1
vote
1answer
33 views

DFS & BFS Spanning Trees

I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one. DFS: My understanding that to the ...
1
vote
2answers
21 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 ...
0
votes
1answer
35 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 ...
3
votes
2answers
81 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$ (...
0
votes
1answer
37 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 ...
1
vote
1answer
24 views

Why does the cut $(V_C,V-V_C)$ respect $A$?

Corollary 23.2 Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree ...
2
votes
3answers
36 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: ...
1
vote
1answer
78 views

MST Of An Almost Tree

A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given ...
0
votes
1answer
32 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 ...
0
votes
1answer
26 views

Finding Euclidean Minimum Spanning Tree

Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization. We can solve this problem with Prim's algorithm in $O(n^2)...
1
vote
1answer
52 views

Minimum spanning subgraph of even degree

I have an unusual problem that I am struggling to solve. I have a set of nodes (with positive distances between them) that I want to connect into a single component. In particular, I want to form a ...
0
votes
1answer
39 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?
3
votes
1answer
119 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: $...
-1
votes
1answer
69 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.
2
votes
1answer
43 views

Mimimum spanning tree with a constraint on number of certain types of edges

I have the the following problem. Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
0
votes
0answers
33 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?
0
votes
1answer
304 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 ...
2
votes
1answer
110 views

How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?

I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression. Now there is a theorem for the last structure above: The ...
5
votes
2answers
218 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 ...
-2
votes
1answer
108 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.
3
votes
1answer
73 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 ...
12
votes
1answer
601 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 ...
2
votes
1answer
76 views

Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?

I am trying to prove the algorithm for Question 5 in this practice exam. I am trying to prove this algorithm with the following three claims: Suppose we have a graph G, a minimum spanning tree T, ...
1
vote
0answers
67 views

Build transportation system to travel between cities

Given $n$ cities, I'm looking to build a transportation system that allows travelling between every two cities. For every two cities $i$ and $j$, a road can be paved in the cost of $c_{ij}$. Also, ...
3
votes
1answer
55 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
1answer
179 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
1answer
57 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
1answer
108 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 ...
0
votes
1answer
91 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$ ...
0
votes
1answer
82 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?
1
vote
1answer
79 views

Minimum sub-tree of a graph that covers each color at least once

I have a connected graph $G$ with $k$ different colors assigned to $n$ nodes where $k<n$. All edges have unit weight. I want to figure out an algorithm to find a minimum sub-tree of $G$ that ...
1
vote
1answer
315 views

Finding missing edge weights in the context of minimum spanning tree

I came across following problem: Problem 1 Suppose that minimum spanning tree of the following edge weighted graph contains the edges with weights $x$ and $z$, then what are $x$ and $z$? The ...
0
votes
3answers
398 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 ...
1
vote
1answer
274 views

Prim's algorithm - misunderstanding

I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I ...
0
votes
2answers
799 views

Is it possible for a maximum weight edge of a cycle being included in MST?

Let C be a cycle in a simple connected weighted undirected graph. Let "e" be an edge of maximum weight on C Which of the following is TRUE? (A) No minimum weight spanning tree contains e. (B) There ...
1
vote
0answers
52 views

n'th cheapest MST in a graph, with multiple edges that can have the same weight

I'm trying to think about an algorithm for this problem. I know there is an algorithm for the second cheapest MST in a graph, but if I understood it correctly it only solves cases in which every ...
3
votes
1answer
187 views

If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?

I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed? Given a directed graph between V ...
2
votes
2answers
359 views

Does MST exclude the edge belongs to the cycle of the graph?

For any simple, connected, undirected graph $G(V,E,w)$ with each carrying distinct positive edge weights, is it true that MST will contain all the edges which do not lie in any cycle of $G$? I think ...
2
votes
1answer
229 views

NP-hardness of existence of spanning tree with given maximal degree

I am trying to solve the following exercise: Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard: $G$ has a spanning tree where every node has at most $k$ neighbors,...
0
votes
1answer
83 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 ...
0
votes
1answer
251 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 ...
2
votes
1answer
95 views

Expected Linear time Minimum Spanning Tree algorithm

I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST". My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture ...
1
vote
1answer
100 views

How to restore a broken minimal spanning tree?

We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be ...
8
votes
3answers
4k 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?
0
votes
1answer
99 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 ...
1
vote
0answers
39 views

Is a spanning tree an MST if its weight can't be decreased by adding an edge and removing one? [duplicate]

My gut says it's true and I have tested it on a few examples. However, I can't prove it. I thought of using contradiction; suppose there exists another tree T' with smaller weight which has m edges ...
1
vote
0answers
29 views

Graph of MSTs of a graph - 2 msts connected if differ by 1 edge - is this single-component? [duplicate]

Suppose we take all MSTs of a graph and build a new graph where each vertex corresponds to a MST of the first graph and two vertices are connected if their corresponding spannings trees differ by only ...
0
votes
2answers
333 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 ...
1
vote
1answer
121 views

Minimum spanning tree of a connected induced subgraph

I'm doing an online course in which I'm struggling with the following multiple-choice question: I don't understand the explanation why this answer is not correct: Suppose G is a triangle and H is ...