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
1
vote
1
answer
35
views
Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?
I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ such that $T_1$ and $...
- 665
1
vote
1
answer
134
views
Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex
Given an undirected graph $G=(V,E)$, and vertex $v\in V$ and a number $k\in \mathbb{N}$, find an algorithm to find whether there exists a spanning tree of $G$ in which $v$ satisfies $d(v)=k$
I've ...
- 304
1
vote
1
answer
26
views
What is the time complexity of the EMST problem in 3D space
We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ?
The tree is made of $N-1$ edges and can be ...
- 7,718
1
vote
1
answer
33
views
safe edge theorem proof clarification
I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A":
See: https://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html ...
- 55
0
votes
0
answers
47
views
Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?
As in the question stated, I am interested in the approximation factor of the greedy approach to compute the arboricity of the graph.
My intuition tells me the factor should not be bigger than $2$, ...
- 294
1
vote
1
answer
49
views
Recreate a spanning tree in a grid graph given vertex descriptions
Let's assume I have graph above with spanning tree pointed out by blue edges.
Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1.
Vertex at position (4,2) (...
- 165
4
votes
2
answers
898
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
0
votes
0
answers
171
views
Wrong Solution for `Spanning tree with chosen leaves` 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 spanning tree in which the nodes of $U$ ...
- 1
2
votes
0
answers
34
views
The Roskind-Tarjan Algorithm
I am going through the paper https://pubsonline.informs.org/doi/abs/10.1287/moor.10.4.701 which is
A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees and the authors are James Roskind and ...
- 53
2
votes
0
answers
43
views
Edmond's theorem for k-disjoint arborescences in digraphs
Recently while studying arborescences in graph theory, I came across Edmond's theorem for $k$ edge-disjoint arborescences in digraphs
if a finite digraph is $k$ edge-connected from a vertex r for ...
- 53
2
votes
1
answer
111
views
Spanning tree that maximizes all-pairs bandwidth => Maximum spanning tree?
Let $G = (V, E)$ be a weighted, undirected graph, with $f: E \to \mathbb{R}$ its weight function. Given a path $P = (e_1, \dots, e_k)$, we call $\operatorname{bwd}(P) = \min_{1 \le i \le k} f(e_i)$ ...
- 123
2
votes
1
answer
153
views
Prove finding a spanning tree with no more than 50 leaves is NP-hard
This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard?
I think it is and I'm trying to ...
- 115
1
vote
1
answer
84
views
Linear deterministic algorithm for finding spanning tree T with minimal maximum edge
Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ).
I need to find a ...
- 11
2
votes
2
answers
1k
views
How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?
In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by ...
- 123
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
1
vote
2
answers
213
views
Is the inverse of MST cut property true? Why?
If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?
- 37
1
vote
1
answer
171
views
Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree
CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have
...
- 808
1
vote
1
answer
167
views
Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints
I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that ...
0
votes
1
answer
180
views
Undirected graph whose BFS and DFS trees have roots of degree 2
Draw a graph on $5$ vertices that satisfies all of the following conditions:
$G$ is an undirected connected graph.
For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$.
For ...
- 167
0
votes
1
answer
120
views
Number of spanning arborescences with a specific root in a directed graph
I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:
where there are 5 spanning arborescences. Note that there is an edge ...
- 131
0
votes
1
answer
320
views
Finding minimum possible cost of road network between cities with distance from capital condition
I have a graph G containing cities (vertices V) connected by distanced roads (weighted undirected edges E).
Characteristics of the graph:
Each city is connected to the rest of the graph
Each city ...
- 1
-1
votes
1
answer
246
views
maximum spanning tree in a complete graph
Given a complete graph how do I find maximum weight spanning tree.
where $weight(u, v) = \sum_{i=1}^{k} |w_{i,u} - w_{i,v}|$
assuming $k \lt 7$ and $n \le 500000$.
$n$ number of nodes
$weight(u,v)$ ...
-1
votes
1
answer
91
views
Prove following statement about Kruskal Algorithm
Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
2
votes
0
answers
60
views
Total weight of all spanning trees
Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
- 141
1
vote
1
answer
412
views
Minimum spanning tree of multi directed graph
I have problem of inferring a rooted tree out of a connected simple graph.
The inference can be done by finding its minimum spanning tree, but the result is restricted by additional two types of ...
- 131
0
votes
3
answers
55
views
Variation to spanning tree called Group Spanning Tree
Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree ...
- 1
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
8
votes
0
answers
182
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 ...
1
vote
2
answers
1k
views
Graph with exactly 2 Minimum Spanning Trees
Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs).
Given this condition stipulated, prove that any cycle formed by all
the edges in both the MSTs (i.e., the union of the edges in ...
user114429
3
votes
1
answer
140
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
490
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,170
0
votes
1
answer
27
views
Finding most likely tree over a semilattice
If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees.
Now assume that each semilattice edge is annotated with a transition probability. In addition, let'...
- 177
2
votes
1
answer
103
views
Number of spanning trees in undirected simple graph
What is the number of spanning trees in an undirected simple graph?
My attempt:
Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices.
Then number of spanning ...
0
votes
1
answer
39
views
Name for Turning DAG into redundant tree
I am looking for a term:
How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
- 177
1
vote
1
answer
226
views
Average branching factor of an undirected graph
I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every ...
- 447
0
votes
2
answers
139
views
First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS
I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true?
What I ...
- 111
1
vote
1
answer
563
views
Do the minimum spanning trees of a graph have the same number of edges with a given weight?
I'm asking about the answer here:
Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
I didn't understand the best answer here
Choose edge $e \in ...
- 159
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
0
votes
0
answers
19
views
Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?
The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem.
Imagine a row of commands:
...
1
vote
1
answer
104
views
The role of the root switch after Spanning Tree Protocol has established a tree network in a LAN?
In Spanning Tree Protocol, a root switch is selected at first, and then somehow, the shortest path from each other switch to the root is obtained. Thus we established a tree network.
My questions ...
- 632
0
votes
2
answers
984
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 ...
- 35
2
votes
1
answer
7k
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 ...
- 35
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
2
votes
2
answers
695
views
Christofides algorithm (by hand) (suboptimal solution - is it my fault?)
I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)
$\alpha$ denotes the start and end vertex of ...
0
votes
1
answer
81
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 ...
- 457
1
vote
0
answers
210
views
Form a Tree having minimum diameter
I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.
However, I looked for the solution, and the solution goes like this.
If the diameter of ...
- 147
2
votes
1
answer
125
views
How to find MST for each source
Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost.
The image bellow is an example of a possible ...
- 33
1
vote
0
answers
165
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, ...
- 215
1
vote
0
answers
70
views
Spanning tree with equally separated edge weights
I have a fully-connected graph $G=(V,E)$ with edge weights $w(v)\in\mathbb{R};v\in V$ and I need to find a spanning tree $T=(V_t\subseteq V,E_t\subseteq E)$ where the set of edge weights in the tree ...
- 141
1
vote
1
answer
82
views
Transforming undirected maximum spanning tree into directed augmented network
I am having trouble transforming a maximum weighted spanning tree into a directed tree such that each node is allowed at most one parent node. Taken from page 141 Friedman et. al (1997), the outline ...
- 13