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.
110
questions
2
votes
1answer
64 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 ...
0
votes
1answer
20 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'...
2
votes
1answer
31 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
1answer
30 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 ...
0
votes
1answer
42 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 ...
0
votes
0answers
11 views
Is Edmonds' Matroid partitioning algorithm optimal w.r.t lexicographical order?
We all know that, given a matroid $(E, \mathcal{I})$, Edmonds' Matroid partitioning algorithm will result in a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with optimal (...
0
votes
2answers
46 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 ...
1
vote
1answer
73 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 ...
2
votes
1answer
398 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 ...
0
votes
0answers
14 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:
...
0
votes
1answer
53 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 ...
0
votes
2answers
364 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 ...
2
votes
1answer
2k 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 ...
24
votes
6answers
4k 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 ...
2
votes
2answers
206 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
1answer
45 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 ...
1
vote
0answers
52 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 ...
2
votes
1answer
65 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 ...
1
vote
0answers
99 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, ...
1
vote
0answers
55 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 ...
1
vote
1answer
45 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 ...
3
votes
1answer
105 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. ...
1
vote
1answer
142 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 ...
3
votes
2answers
175 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 ...
4
votes
3answers
336 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 ...
1
vote
0answers
37 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 ...
1
vote
1answer
883 views
Number of rooted labelled trees
According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2
If the tree is rooted then in each tree we can ...
-1
votes
2answers
4k views
Minimum spanning tree using DFS and BFS
Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs?
I have gone through many answers but each answer says something different and I am not convinced....
6
votes
1answer
98 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....
2
votes
1answer
3k views
safe edge for Minimum spanning tree
I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$
...
3
votes
1answer
170 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 $...
0
votes
0answers
138 views
Spanning-Tree-Protocol and BFS? (Distributed Computing)
Given is graph with networks and bridges/switches. We know, the root
Bridge is the bridge with the minimal Bridge-ID. The connections between every bridge and network is 1.
In the lecture slides they ...
0
votes
0answers
115 views
Distributed MST in $O(n \log \log n)$
I'm facing the following problem:
Describe a distributed MST algorithm in time $O(n \log \log n)$
I've managed to think of the following,
Run GHS(Gallager, Humblet and Spira) algorithm, till there ...
0
votes
1answer
31 views
Find the maximum (longest) delay to last user in a multicast T. NP complete proof
Given a un-directed weighted graph G=(V,E) where V is the set of vertices and E is the set of edges between vertices, and weights are the time delays on each link between two user. The goal is to ...
0
votes
0answers
261 views
How to efficiently find a minimum spanning tree?
I found this question from CSLR that I'm trying to figure out before my final.
You are given a weighted, connected, undirected graph G = (V, E) and
one of its minimum spanning trees T ⊆ E. Now ...
1
vote
0answers
80 views
Why a random minimum spanning tree is not an uniform spanning tree? [closed]
A spanning tree chosen randomly from among all the spanning trees with equal probability is called a uniform spanning tree.
A model for generating spanning trees randomly but not uniformly is the ...
1
vote
2answers
6k views
How to find total number of minimum spanning trees in a graph with n edges?
I had this question on my final exam so sadly I don't have the question but as far as I remember, the question was saying:
How many minimum spanning trees does a graph with 20 edges have.
I know ...
1
vote
1answer
498 views
Prim's algorithm on graph with weights of only $1$ and $2$ on each edge
I have this version of Prim's algorithm
Prim$(G=(V,E),s\in V,w)\\
1.\ d(s)\leftarrow 0;\forall u \neq s:d(u)\leftarrow \infty\quad \color{red}{O(|V|)}\\
2.\ \forall u \in V:p(u)\leftarrow \text{...
0
votes
0answers
227 views
spanning tree of a DAG (directed acyclic graph) with less forward arcs
I am new to this algorithm and graphs. Just started learning. Could someone help me which algorithm is best suited to find the spanning tree of a Directed Acyclic Graph with less forward edges?
3
votes
1answer
92 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 ...
4
votes
2answers
660 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 ...
4
votes
1answer
356 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 ...
0
votes
1answer
58 views
Spanning tree display conventions
On page two of this discussion of spanning trees there are two different tree structures shown, one labeled DFS tree starting from a as the root and the other labeled Spanning tree created by DFS. If ...
22
votes
3answers
19k 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 ...
1
vote
2answers
293 views
Equivalent definition of minimal spanning tree
Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$.
It's my attempt to prove $\Rightarrow$:
Consider the cycle ...
4
votes
0answers
149 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$...
6
votes
1answer
4k 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 ...
4
votes
1answer
824 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 ...
1
vote
1answer
137 views
Prize collecting Steiner tree on graph without weights on edges
I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is ...
1
vote
1answer
211 views
Spanning tree with chosen leaves NP-Complete proof
I want to prove that the problem described here
Spanning tree with chosen leaves
is NP-Complete.
Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how ...
