Questions tagged [spanning-trees]
The spanning tree of a connected undirected graph G is a tree having all the vertices and some number of edges of G.
139
questions
69
votes
10
answers
111k
views
Minimum spanning tree vs Shortest path
What is the difference between minimum spanning tree algorithm and a shortest path algorithm?
In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
- 1,183
28
votes
3
answers
43k
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 ...
- 467
25
votes
7
answers
5k
views
Do any two spanning trees of a simple graph always have some common edges?
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
- 1,263
21
votes
2
answers
14k
views
Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
- 1,121
15
votes
4
answers
11k
views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
- 293
13
votes
2
answers
17k
views
Why is the k-bounded spanning tree problem NP-complete?
The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$.
I ...
- 131
12
votes
2
answers
2k
views
Minimal Spanning Tree With Double Weight Parameters
Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
- 1,505
11
votes
1
answer
1k
views
Tighter analysis of modified Borůvka's algorithm
Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.
The pseudo-code is:
...
- 4,037
9
votes
3
answers
20k
views
If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?
If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time?
Intuitively this sounds correct, as ...
- 571
9
votes
2
answers
4k
views
MST: Prim's algorithm complexity, why not $O(EV \lg V)$?
According to CLRS, the Prim's algorithms is implemented as below --
$\mathtt{\text{MST-PRIM}}(G,w,r)$
for each $u \in V[G]$ do
$\mathtt{\text{key}}[u] \leftarrow \infty$
$\pi[u] ...
- 541
9
votes
2
answers
8k
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 ...
- 203
8
votes
1
answer
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?
- 93
8
votes
0
answers
186
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 ...
8
votes
1
answer
3k
views
Necessary and sufficient condition for unique minimum spanning tree
This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13]
.
Prove that an edge-weighted graph $G$ has a unique minimum spanning ...
- 9,441
7
votes
1
answer
795
views
Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution
Let G = (V,E) be a unit-capacity graph with n vertices and m edges.
Let T denote all the spanning trees in G.
If we run Karger's algorithm, we will get a random spanning tree in T formed by the ...
- 305
6
votes
3
answers
5k
views
Minimum spanning tree and its connected subgraph
This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:
The accepted answer at [2] is still in dispute.
The proof given by ...
- 9,441
6
votes
2
answers
9k
views
How to find spanning tree of a graph that minimizes the maximum edge weight?
Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
- 1,121
6
votes
1
answer
3k
views
Determining if an undirected connected graph is minimally connected
I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused. The question is to determine if an undirected connected graph is minimally connected.
...
- 61
6
votes
1
answer
124
views
Min spanning tree that preserves total weight of original graph
I have a directed, weighted graph with no double edges. Each node represents a person, and each edge represents a debt. I want to reduce the total number of transactions required to settle all debt, i....
- 227
6
votes
3
answers
5k
views
Minimal spanning tree with degree constraint
I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of ...
- 61
6
votes
0
answers
774
views
Minimum vertex-weight directed spanning tree where the weight function depends on the tree
Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.
The weight function assigns a non-...
- 61
5
votes
3
answers
4k
views
Does spanning tree make sense for DAG?
Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
- 374
5
votes
3
answers
10k
views
Minimum spanning tree with two minimum edge weights
Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree?
I know the proof for if all edge weights are ...
- 467
5
votes
1
answer
288
views
5
votes
0
answers
167
views
MST that contains a shortest $s,t$-path
Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
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 ...
- 409
4
votes
3
answers
5k
views
How many minimal spanning trees are there when all edge costs are distinct?
Suppose all costs on edges are distinct. How many minimal spanning trees are possible?
I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal'...
- 4,219
4
votes
1
answer
5k
views
Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?
On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows:
Cycle Property:
For any cycle C in the graph, if the weight of an edge e of C is
larger than the ...
- 781
4
votes
2
answers
961
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 ...
- 71
4
votes
3
answers
6k
views
Difference between spanning tree and a tree?
Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem ...
4
votes
3
answers
8k
views
Spanning tree with chosen leaves
I'm working on the following problem:
Suppose that we're given a connected, undirected graph $G = (V, E)$ with
edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
the lightest ...
- 111
4
votes
4
answers
1k
views
Find a MST such that it's mostly red (original graph's edges are colored red and blue)
Consider the following problem:
Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight).
Find an ...
- 163
4
votes
1
answer
1k
views
Find a graph for which Kruskal's algorithm achieves worst-case running time
I am working on a problem in which I must find a graph with edge weights on n vertices, for which Kruskal's algorithm achieves worst-case running time. I am using a UNION-FIND data structure, but ...
4
votes
1
answer
715
views
Why do the swap step in Prim's algorithm for minimum spanning trees?
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
- 1,181
4
votes
3
answers
1k
views
Algorithms for procedural generated mazes
For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important).
There are many Maze generation algorithms, but they only work on a ...
- 766
4
votes
1
answer
540
views
Can a shortest-path tree be a also maximum spanning tree?
If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example!
I ...
4
votes
1
answer
59
views
Count bridging edges in a family of two component forests
I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two ...
- 141
4
votes
1
answer
137
views
Survival algorithm for Network deterministic failures
Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
- 41
3
votes
2
answers
5k
views
Find an MST in a graph with edge weights from {1,2}
I've been asked the following question:
Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph.
After ...
- 571
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....
- 139
3
votes
2
answers
840
views
Is every edge of a graph included in some spanning tree?
Let's say we have a graph $G$. We pick one edge from it (any edge). Will there always be such a spanning tree that contains that very edge?
I think the answer is yes, because no matter what we do we ...
- 205
3
votes
1
answer
521
views
Kirchhoff's Spanning Tree Algorithm
Recently I have studied Kirchhoff's spanning tree algorithm to count the number of spanning trees of a graph, which has the following steps:
Build an adjacency matrix
Replace the diagonal entries ...
- 1,180
3
votes
1
answer
150
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 ...
- 31
3
votes
1
answer
2k
views
Is maximum-leaves spanning tree np-complete?
How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base?
(maximum-leaves spanning tree: does G have a spanning tree with at ...
- 33
3
votes
1
answer
668
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 ...
- 31
3
votes
2
answers
2k
views
Prim's Algorithm - Building the Priority Queue
Suppose we were using a priority queue (PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then ...
- 181
3
votes
1
answer
273
views
Computational complexity of finding a spanning tree in planar hybergraphs
Using a bipartite graph to represent hypergraphs as described by Wikipedia :
A hypergraph $H$ may be represented by a bipartite graph $BG$ as follows:
the sets $X$ and $E$ are the partitions of $...
- 141
3
votes
1
answer
183
views
Show that the diameter of a MST is sometimes larger by a factor $\Omega(n)$ than the diameter of the graph $G$
As my title points out, I don't understand how do you show that, in general, the diameter of a MST (minimal spanning tree) can be bigger than the diameter of G, by the factor $\Omega(n)$. $(n:= |V|, G ...
- 219
3
votes
0
answers
4k
views
Applications of min spanning trees
What are the significant applications of minimum spanning trees?
After doing some research online and in several textbooks, I have found three real-world applications:
Building a connected network. ...
D.W.♦
- 152k
2
votes
3
answers
1k
views
Algorithm to get any spanning tree not necessarily a minimum spanning tree
Is there an algorithm to find a spanning tree. I know that there are $n^{n-2}$ of them and we have algorithms to find a minimum spanning tree.
But what if I just want any spanning tree? It doesn't ...
- 659