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

109 questions
Filter by
Sorted by
Tagged with
101 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. ...
312 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 ...
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'...
30 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 ...
2k 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 ...
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 ...
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....
8k views

### Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
34 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 ...
70k views

### Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...
441 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 ...
10 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 (...
339 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 ...
161 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 ...
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 ...
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 ...
337 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 ...