Tag Info

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 ...
• 13.3k
Accepted

• 34.9k
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

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, ...
• 34.9k

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$ ...
• 34.9k
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 ...
• 270k

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 ...
• 143k

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.
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.
• 80.4k

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). ...
• 34.9k

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 ...
• 23.9k
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. ...
• 23.9k
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 ...
• 2,148
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 ...
• 80.4k
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,100
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 ...
• 270k
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). ...
• 34.9k
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 ...
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 ...