23
votes
Does the Minimum Spanning Tree include the TWO lowest cost edges?
For simple graphs*, it is true for the following reason:
Kruskal’s algorithm is correct
Kruskal’s algorithm works as follows:
sort the edges by increasing weight
repeat: pop the cheapest edge, if it ...
- 15k
14
votes
Accepted
Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?
Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily ...
13
votes
Accepted
When is the minimum spanning tree for a graph not unique
in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2.
Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$.
...
- 558
13
votes
Accepted
Why do we have different algorithm for MST when graphs are directed?
Your question was already asked before it seems, but got no explicit examples. I try to give these here.
First note the question only makes sense if we consider a node $u$, and there exist spanning ...
- 29.6k
11
votes
Accepted
Are all MST minimum spanning trees reachable by Kruskal and Prim?
As indicated by Raphael's comment and j_random_hacker's comment, the answer is positive. In fact, any MST is reachable by any MST algorithm with some minor exceptions.
For a graph $G$, two weight ...
- 38.5k
8
votes
Accepted
Are all minimum spanning trees optimized for fairness?
is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.
No, it isn't; ...
- 2,009
8
votes
Diameter-constrained Minimum Spanning Tree Problem
Consider the complete graph $K_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.
- 274k
7
votes
Accepted
Diameter-constrained Minimum Spanning Tree Problem
There is no direct relationship between the diameter of a (minimum) spanning tree and the total cost of the tree1. Consider the following example:
The spanning tree on the left (whose edges are ...
- 3,634
7
votes
Accepted
Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)
Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small.
Let $y_1,\ldots,y_d$ ...
- 274k
7
votes
Minimum diameter spanning tree problem
The answer is given in the paper that you link to. Specifically, there is a $O(mn+n^2 \log n)$-time algorithm for the problem (with positive edge weights, as required) that works as follows.
The ...
- 22.4k
7
votes
Accepted
Edge exchange property of two Minimum Spanning Trees
Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.
If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(...
- 38.5k
5
votes
Accepted
Is the inverse of MST cycle property always true? Why?
If you want to test whether a specific edge belongs to some MST, you can use the following property.
Claim. An edge $e$ belongs some MST if and only if for every $\epsilon > 0$, if we reduce the ...
- 274k
5
votes
When is the minimum spanning tree for a graph not unique
A previous answer indicates an algorithm to determine whether there are multiple MSTs, which, for each edge $e$ not in $G$, find the cycle created by adding $e$ to a precomputed MST and check if $e$ ...
- 38.5k
5
votes
Accepted
Finding MST after adding a new vertex
As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$.
For the sake of simplicity, let's assume that $T$ is the unique MST. ...
- 166
5
votes
What edges are not in any MST?
A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, ...
- 38.5k
5
votes
Minimum path - robot motion problem combined with freeze tag problem
Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot ...
D.W.♦
- 154k
5
votes
If a graph has a unique MST, then its edge weights are distinct. True or false ? Justify your answer.
The answer is: not necessarily.
Counterexample: consider a graph that is a tree with all of its edges the same weight. Then the only MST is the entire graph and none of the edge weights are distinct.
- 230
5
votes
Accepted
Uniqueness of minimum spanning tree
If $G$ is a tree, it has a unique MST whatever its weights are. The weights could be unique, all the same, anything.
- 81.4k
5
votes
Can Edge Belong to a cycle if it is part of multiple BFS products
As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS).
...
- 38.5k
5
votes
Two definitions of Safe Edge
They are two different definitions.
The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from $G$ without disconnecting it, thus changing the ...
- 27.4k
5
votes
Accepted
Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)
The MST of $G$ is not well-defined since there might be multiple MSTs of a graph. However, it can be shown that:
Claim 1: either all MSTs use only edges with integer weights or none of them does.
...
- 27.4k
4
votes
Accepted
Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?
Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question ...
- 81.4k
4
votes
Accepted
MST: Are all safe edges, light edges?
Yes, all safe edges (edges which are part of some MST) must be the lightest edge for some partition $(S, V-S)$ of the graph. For if $e=uv$ is a safe edge, it is part of some MST $T$, and $T-e$ ...
- 1,168
4
votes
Accepted
safe edge for Minimum spanning tree
For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is safe if $A \cup \{e\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe ...
- 274k
4
votes
Accepted
Is it possible for a maximum weight edge of a cycle being included in MST?
The answer to the question in the title, "is it possible for a maximum weight edge of a cycle being included in MST?", is "not necessarily".
The correct answer to the multiple-choice question is (B).
...
- 38.5k
4
votes
Does the Minimum Spanning Tree include the TWO lowest cost edges?
Assuming that the graph has at least $3$ vertices, is connected, and edges have distinct weights you can see that the two edges with the lowest weights must belong to the (unique) MST of the graph by ...
- 27.4k
4
votes
Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)
A simple algorithm
Here is the simplest and fastest algorithm to determine the MST of $G$ only uses edges with an integer weight. It runs in $O(E\,\alpha(V))=O(n\,\alpha(n))$ time.
Define weight ...
- 38.5k
4
votes
Spanning tree - minimum difference between smallest and largest weight
You can solve the problem in $O(m \log n)$ time. For the sake of simplicity assume that all edge weights are distinct (this assumption can be easily removed).
Let $e_1, e_2, \dots, e_m$ be the edges ...
- 27.4k
4
votes
Accepted
Spanning tree - minimum difference between smallest and largest weight
I realized that my answer is similar to Steven's answer but maybe suitable for someone.
Based on increasing values of weights, sort the edges; e.g. $e_1,...,e_m$.
For $i=1,...,m-n+1$ (we need atleast $...
Only top scored, non community-wiki answers of a minimum length are eligible