The spanning tree of a connected undirected graph G is a tree having all the vertices and some number of edges of G.
8
votes
3answers
138 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 ...
4
votes
3answers
144 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 ...
2
votes
1answer
54 views
DFS miniumum spanning tree
Just a quick question,
If i were to alter the general DFS algorithm to do this:
...
3
votes
2answers
275 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
230 views
Question about Prims algorithm where weights are between 1 and some constant W
I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of ...
2
votes
0answers
99 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.
My motivation is to find what edges ...
2
votes
1answer
286 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 ...
11
votes
1answer
192 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 ...
4
votes
1answer
103 views
Why do the swap step in Prim's algorithm for minimum spanning trees?
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
5
votes
0answers
88 views
Minimum vertex-weight directed spanning tree where the weight function depends on the tree
Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.
The weight function assigns a ...
7
votes
1answer
173 views
Tighter analysis of modified Borůvka's algorithm
Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.
The pseudo-code is:
...
6
votes
1answer
551 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 ...
2
votes
1answer
318 views
NP-completeness of a spanning tree problem
I was reviewing some NP-complete problems on this site, and I meet one interesting problem from
NP completeness proof of a spanning tree problem
In this problem, I am interested in the original ...
3
votes
2answers
252 views
Does spanning tree make sense for DAG?
Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
