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

128 questions
Filter by
Sorted by
Tagged with
20 views

### Spanning tree as set comprehension

My attempt- spanning tree <==> (root(v) and forall v2(Path(v,v2) and v != v2)) connected graph<==> for all v for all v2( Path(v,v2) and v!=v2) Root(v) Is it correct.Please point out the ...
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 ...
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 ...
59 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?
55 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 ...
63 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 ...
66 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 ...
39 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 ...
18 views

### Maximizing a spanning tree in an undirected graph with double weighted edges

I would like to have help in developing the algorithm for this problem.
125 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 ...
194 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)$ ...
71 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 ...
49 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 ...
231 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 ...
48 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 ...
53 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 ...
147 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 ...
859 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 ...
81 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 ...
285 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 ...
24 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'...
46 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 ...
34 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 ...
143 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 ...
65 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 ...