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.
257 questions
1 vote
0 answers
55 views
Smallest hop-count tree of minimum weight?
Let $G = (V, E)$ be a graph, and $s \in V$. We say that a spanning tree $T$ is of $s$-efficient if for all $v \in V$, $d_T(s, v) = d_G(s, v)$, where $d_X(a, b)$ counts the number of edges in a ...
- 133
2 votes
1 answer
71 views
Given an MST of a graph after removing one vertex, find the MST of the original graph in O(E + V log V)
Let G = (V, E) be a connected undirected graph with real edge weights. Let v ∈ V be a fixed vertex such that the graph G' = G[V \ {v}] (i.e., the subgraph of G induced by removing v and all edges ...
-2 votes
1 answer
162 views
Kruskal's Algorithm Minimum Spanning Tree (Disjoint Set data structure)
I want to generate a minimum spanning tree for the graph shown below. I am using the disjoint set data structure and having trouble with the union (Union Rank) operation. The edges get sorted as ...
5 votes
3 answers
278 views
Why can we always apply at least one of the Red or Blue rules in the generic minimum spanning tree (MST) algorithm?
I am learning about algorithms for finding minimum spanning trees (MST) in a graph. As it is the standard, I learned about a variation of the generic MST finding algorithm, specifically, I learned ...
- 151
0 votes
1 answer
87 views
Not recognizing the data structure that stores the computed MST
I am using the code for computing the Minimal Spanning Tree of a graph (https://github.com/stanojevic/Fast-MST-Algorithm). The Python code outputs the MST in the form of an array of integers, e.g.: ...
- 111
2 votes
1 answer
368 views
If an edge e doesn't belong to any mst, then what can we say about e?
I'm trying to prove a statement "given a graph G=(V,T) and that no cycle C exists that contains only edge "e" and other edges that their weight is smaller than that of "e", ...
- 33
0 votes
1 answer
128 views
Can the MST's "cut property" be derived from the "cycle property" and vice versa?
The cut and cycle properties of the minimum spanning tree are well-known. It is easy to use similar arguments to prove them. But I wonder if one property be derived from the other. Cut property: ...
- 109
0 votes
2 answers
401 views
Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST
In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor: Let $T$ be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best ...
- 765
3 votes
2 answers
147 views
How does the half-integer spanning-tree problem contain the TSP?
I am trying the understand the following statement from the book of Grotschel, Lovasz and Schrijver: Here, $\delta(W)$ is the set of edges incident to a set of vertices $W$. They define an ...
- 6,087
1 vote
0 answers
50 views
MST algorithms worst scenarios for circular graph/complete graph
Consider a circular graph $G_1$ with $n$ vertices and a complete graph $G_2$ with $m$ vertices. What is the maximum attainable ratio when determining the Minimum Spanning Tree (MST) using Boruvka, ...
0 votes
1 answer
63 views
Edge being in the MST
Does an edge never being the largest weight in any cycle imply that it is included in the MST? I believe the answer is not, but can't think of a counterexample. I know that one guarantees an edge is ...
- 195
0 votes
1 answer
220 views
Visiting all nodes of a directed graph exactly once (not dfs)
Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
- 67
0 votes
1 answer
148 views
supplying water for all houses of a city with either a well or pipe
Consider $n$ houses in a city which each house's water can be supplied with either a well or pipes from other houses. Constructing a well in a house $i$ costs $w_i$ and connecting a pipe from house $i$...
- 67
0 votes
1 answer
87 views
Proving heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree?
How to prove that the heaviest edge in mst is not heavier than heaviest edge of any possible spanning tree? by heaviest edge of any Spanning tree i mean considering any possible Spanning tree, we have ...
- 67
3 votes
0 answers
102 views
Minimum spanning tree between blobs
We have a binary raster image in which we consider the white blobs (connected components). We define a distance between two blobs to be the length of the shortest path between any two respective ...
user16034