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
22 votes
2 answers
15k 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 ...
Aden Dong's user avatar
  • 1,131
2 votes
2 answers
842 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 ...
sooobus's user avatar
  • 133
29 votes
3 answers
45k 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 ...
Keiwan's user avatar
  • 477
4 votes
2 answers
6k 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....
The-Q's user avatar
  • 149
6 votes
2 answers
10k 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 ...
Aden Dong's user avatar
  • 1,131
72 votes
10 answers
115k 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 ...
flashburn's user avatar
  • 1,223
9 votes
3 answers
21k 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 ...
TheNotMe's user avatar
  • 571
8 votes
1 answer
3k 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 ...
hengxin's user avatar
  • 9,511
5 votes
3 answers
9k 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 lightest ...
Dave's user avatar
  • 121
-1 votes
1 answer
2k views

Minimal Spanning tree and Prim's Algorithm

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
fudu's user avatar
  • 65
15 votes
4 answers
11k views

Graph Has Two / Three Different Minimal Spanning Trees?

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
itamar's user avatar
  • 293
9 votes
2 answers
8k 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 ...
LiorGolan's user avatar
  • 203
6 votes
3 answers
5k views

Minimal spanning tree with degree constraint

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of ...
user3670's user avatar
5 votes
3 answers
4k views

Does spanning tree make sense for DAG?

Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
zell's user avatar
  • 374
5 votes
3 answers
10k 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 ...
gprime's user avatar
  • 467
4 votes
4 answers
1k 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 ...
The_Ben's user avatar
  • 163
4 votes
3 answers
5k views

How many minimal spanning trees are there when all edge costs are distinct?

Suppose all costs on edges are distinct. How many minimal spanning trees are possible? I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal'...
Mirrana's user avatar
  • 4,259
4 votes
2 answers
1k 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 ...
Teodorico Levoff's user avatar
3 votes
2 answers
5k views

Find an MST in a graph with edge weights from {1,2}

I've been asked the following question: Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph. After ...
TheNotMe's user avatar
  • 571
2 votes
1 answer
4k views

DFS miniumum spanning tree

Just a quick question, If i were to alter the general DFS algorithm to do this: ...
racketball's user avatar
2 votes
1 answer
5k views

Depth First Search to find Minimum spanning tree

A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example ...
raskolnikov's user avatar
1 vote
1 answer
499 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 ...
Edward's user avatar
  • 131
0 votes
0 answers
304 views

Wrong Solution for `Spanning tree with chosen leaves` 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 lightest spanning tree in which the nodes of $U$ ...
Robert's user avatar
  • 1