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
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
2
votes
2
answers
2k
views
minimum spanning tree and minimum heavyweight spanning tree [duplicate]
a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible.
Formally,
input : given connected undirected weighted graph, $G$.
output : a spanning tree $T$...
- 29
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
0
votes
1
answer
1k
views
Is it possible for a graph to have two different minimum spanning tree
I am suppose to create a minimum spanning tree from this graph below
I got this answer
However this is my textbook answer
Based on what i have learnt , I think my answer and the textbook answer ...
- 639
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
1
vote
1
answer
178
views
Choosing spanning trees to maximise node connectivity
Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints.
...
- 11
-1
votes
1
answer
125
views
Find MST based upon new definition
Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the ...
- 23
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
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
2
votes
1
answer
703
views
Question about spanning trees and creating them through BFS and/or DFS algorithms
The question is as follows:
True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the ...
- 83
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
1
vote
2
answers
550
views
Applications of Depth-First Spanning Tree
I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
- 111
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
1
vote
2
answers
415
views
Spanning Tree - Equivalent Properties
I am working on the following problem:
Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') \geq ...
-1
votes
2
answers
2k
views
Proof of Correctness of Prim's algorithm [duplicate]
what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case?
Is it because of after any number of steps, $S$ might not be in a sub ...
- 65
-1
votes
1
answer
2k
views
Minimal Spanning tree and Prim's Algorithm
Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
- 65
-1
votes
1
answer
264
views
Satisfying condition to be in minimum spanning tree of an edge (maximum weight)
Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always ...
- 35
0
votes
1
answer
257
views
Find a diffrent minimal spanning tree for a graph
For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST:
Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$.
I want to find another minimum ...
- 111
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,431
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
1
vote
2
answers
325
views
Showing that graph of spanning trees are connected
Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$.
We create an edge between 2 vertices in $H$ if $ST_1$ (spanning tree) contains exactly one edge not in $...
- 11
1
vote
1
answer
678
views
Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?
I'm given this problem:
Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen ...
- 113
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
2
votes
1
answer
740
views
Upper bound on the number of edges relative to the height of a DFS tree
Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of ...
- 287
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
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,199
2
votes
1
answer
3k
views
DFS miniumum spanning tree
Just a quick question,
If i were to alter the general DFS algorithm to do this:
...
- 145
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
2
votes
1
answer
4k
views
Question about Prims algorithm where weights are between 1 and some constant W
I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of ...
- 121
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
2
votes
1
answer
5k
views
Depth First Search to find Minimum spanning tree
A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example ...
- 21
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
4
votes
1
answer
714
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
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
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
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
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
2
votes
1
answer
5k
views
NP-completeness of a spanning tree problem
I was reviewing some NP-complete problems on this site, and I meet one interesting problem from
NP completeness proof of a spanning tree problem
In this problem, I am interested in the original ...
- 273
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