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.

Filter by
Sorted by
Tagged with
3
votes
1answer
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. ...
4
votes
3answers
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 ...
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
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 ...
2
votes
3answers
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 ...
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 ...
-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....
21
votes
2answers
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 ...
0
votes
1answer
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 ...
48
votes
7answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 (...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
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 ...
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 ...
0
votes
2answers
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 ...
1
vote
1answer
65 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
2answers
200 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
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
49 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 ...
1
vote
1answer
2k views

What edges are not in any MST?

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed. Consider a weighted undirected graph....
7
votes
3answers
12k views

If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as ...
1
vote
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 ...
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 ...
3
votes
1answer
166 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 $...
8
votes
2answers
4k views

MST: Prim's algorithm complexity, why not $O(EV \lg V)$?

According to CLRS, the Prim's algorithms is implemented as below -- $\mathtt{\text{MST-PRIM}}(G,w,r)$ for each $u \in V[G]$ do $\mathtt{\text{key}}[u] \leftarrow \infty$ $\pi[u] ...
1
vote
0answers
51 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 ...
1
vote
1answer
134 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 ...
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
1answer
776 views

How do deal with the following situations using Prim's algorithm?

Consider the following Graph We want to generate the MST using Prim's algorithm. Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other ...
5
votes
3answers
8k views

Minimum spanning tree with two minimum edge weights

Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree? I know the proof for if all edge weights are ...
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
97 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
53 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 ...
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 ...
12
votes
2answers
10k views

Why is the k-bounded spanning tree problem NP-complete?

The $k$-bounded spanning tree problem is where you have an undirected graph $G(V,E)$ and you have to decide whether or not it has a spanning tree such that each vertex has a degree of at most $k$. I ...
6
votes
2answers
5k views

How to find spanning tree of a graph that minimizes the maximum edge weight?

Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
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 ...
3
votes
3answers
3k views

Difference between spanning tree and a tree?

Strictly in the context of computer science, what is the difference between a spanning tree, and minimum spanning tree? I read this posts but was unsatisfied with the answer because it did not seem ...
1
vote
0answers
36 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 ...
12
votes
2answers
1k views

Minimal Spanning Tree With Double Weight Parameters

Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
1
vote
1answer
834 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 ...
4
votes
3answers
696 views

Find a MST such that it's mostly red (original graph's edges are colored red and blue)

Consider the following problem: Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight). Find an ...
6
votes
1answer
97 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 $-:$ ...
0
votes
0answers
135 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 ...
8
votes
1answer
1k views

Necessary and sufficient condition for unique minimum spanning tree

This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13] . Prove that an edge-weighted graph $G$ has a unique minimum spanning ...
0
votes
0answers
113 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 ...