# 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.

118 questions
Filter by
Sorted by
Tagged with
32 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 ...
45 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 ...
25 views

### Oriented spanning tree of a directed multi-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 ...
17 views

### Mathematics of the upper bound for the encoded input of an instance Kruskal's MWST problem

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the encoding of an instance of Kruskal's Mininum ...
39 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 ...
51 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 ...
99 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 ...
301 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 ...
59 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 ...
126 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 ...
21 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'...
32 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 ...
31 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 ...
68 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 ...
49 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 ...
145 views

144 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 ...
135 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 ...
32 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 ...
267 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 ...
84 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 ...
7k 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 ...
534 views

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{... 0answers 247 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? 1answer 116 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 ...
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 ...