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.
0
votes
2answers
88 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 ...
1
vote
1answer
33 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 ...
21
votes
5answers
3k 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
1answer
98 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
0answers
60 views
algorithm to find complementary spanning tree in dual graph
I have read from wikipedia, that for every spanning tree in a graph [primal] we have a spanning tree in the dual graph which consists of dual of the complementary set of edges [edges not used in the ...
0
votes
1answer
32 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 ...
0
votes
0answers
26 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
47 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
67 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
38 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
14 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
68 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
79 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 ...
1
vote
1answer
63 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 ...
2
votes
2answers
151 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
29 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
358 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
1answer
2k 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
89 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....
1
vote
1answer
1k 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
106 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
94 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
88 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
24 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
195 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
63 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
4k 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
401 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
182 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
55 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
441 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 ...
3
votes
1answer
203 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
55 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 ...
19
votes
3answers
11k 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
145 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 ...
5
votes
0answers
92 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$...
5
votes
1answer
3k 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
591 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
128 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
139 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 ...
5
votes
1answer
856 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.
...
0
votes
0answers
36 views
two connected graph - find linear spanning subgrap such that subgraph is still connected
Graph $G$ is 2-connected. It means that for each two edges there are exists at least to disjont (in terms of edges) paths.
Graph $G$ is not directed.
Our task is to find spanning subgraph $H$ of ...
0
votes
0answers
70 views
Why if $G$ has two spanning trees $A$ and $A'$, then every edge of $A'\cup \{e_i\}\in A'$
Theorem:
Let be $G$ a weighted graph in which every edge has a different weight.
Suppose that $G$ has two spanning trees $A$ and $A'$.
Let be $i$ the first index such that $e_i\ne e'_i$ ...
0
votes
2answers
26 views
Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?
I am studying the algorithm of Sollin and we recently studied a lemma:
Let be G a graph which values are diffferent on the edges.
We sort the edges $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$
Every ...
3
votes
1answer
330 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 ...
1
vote
1answer
1k views
Maximum Spanning Tree vs Maximum Product Spanning Tree
So I'm kind of wondering if I'm correct on something relating to an algorithms class. Let's say I want to, for whatever reason, find the maximum spanning tree of a graph such that the edge weight is ...
2
votes
1answer
67 views
Minimum Spanning Tree over Vertices Proof
This is the problem:
$d_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices.
The goal is an algorithm that finds a ...
0
votes
1answer
85 views
Karloff's algorithm applied to sparse graphs
I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c >0$. $G$ is called a $c$-dense graph.
Karloff [1, p.6] has given a map-reduce algorithm called "...
2
votes
1answer
170 views
What is the graph with $8$ vertices and $12$ edges that has the most spanning trees? [closed]
I'm not sure if this is an open question, but what is the graph with $8$ vertices and $12$ edges that has the most spanning trees?
2
votes
2answers
1k 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 ...
