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 ...
user avatar
  • 13.3k
18 votes
Accepted

Does a graph always have a minimum spanning tree that is binary?

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $...
user avatar
  • 22.1k
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 ...
user avatar
  • 27.7k
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$. ...
user avatar
  • 548
13 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 ...
user avatar
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 ...
user avatar
  • 34.9k
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; ...
user avatar
  • 1,999
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$.
user avatar
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$ ...
user avatar
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 ...
user avatar
7 votes

Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

If the MST is unique, all algorithms will perforce produce it. If the MST is not unique, the outputs might differ due to different node processing orders (even two distinct implementations of the ...
user avatar
  • 4,601
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 ...
user avatar
  • 22.1k
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 $(...
user avatar
  • 34.9k
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. ...
user avatar
  • 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, ...
user avatar
  • 34.9k
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$ ...
user avatar
  • 34.9k
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 ...
user avatar
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 ...
user avatar
  • 143k
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.
user avatar
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.
user avatar
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). ...
user avatar
  • 34.9k
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 ...
user avatar
  • 23.9k
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. ...
user avatar
  • 23.9k
4 votes
Accepted

Christofides algorithm: why must an MST have even number of odd-degree vertices?

Every edge in a graph is incident with exactly two vertices. The degree of a vertex is the number of edges incident with it. From this you get the standard fact that the sum of all the vertex degrees ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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). ...
user avatar
  • 34.9k
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 ...
user avatar
  • 23.9k
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 ...
user avatar
  • 34.9k

Only top scored, non community-wiki answers of a minimum length are eligible