# Tag Info

23

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 does not create cycles, include it in the MST Two edges cannot construct a cycle in a simple graph By the correctness of Kruskal’s algorithm, the two ...

18

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 $k$. In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.

13

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 trees starting with $u$. The algorithms of Prim and Kruskal make choices in a greedy way. Once the choice is made, it will not be reconsidered. We show how this ...

13

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$. If there exists an edge $e=\{v,w\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest ...

13

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 produce the same result.

11

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 functions on all edges (to real numbers) are defined as (weakly) comparison-compatible (to each other) if we can extend the strict weak ordering on the edges ...

8

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; assume it is, let $X$ be the MST with the heavy edge, and call that heavy edge $e := \{u,v\}$. Now there is some other MST $Y$ that doesn't contain edges that are ...

8

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$.

7

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$ be its neighbors. Draw a small circle of radius $\epsilon$ around $x$, and "project" each $y_i$ to a point $z_i$ on the circle: the point $z_i$ is just the ...

7

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 highlighted in red) is minimum. Its total cost is 7 and the diameter is equal to 5. In contrast, the spanning tree on the right is not minimum (since its total cost ...

7

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 same algorithm can), but the total weights will be identical. In this case, the MST is a misnomer.

7

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 absolute 1-center is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $T(v)$ a ...

6

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 $(V_1, V_2)$, which is a cut of $V$. Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V_1, V_2)$ at $e$, it must ...

5

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. (This is not required, but it is easier to reason about correctness in this case.) Now think about what would happen if we ran Prim's on the full graph after ...

5

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$ is not the unique heaviest edge in that cycle. That algorithm is likely to run in $O(|E||V|)$ time. A simpler algorithm to determine whether there are multiple ...

5

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 weight of $e$ by $\epsilon$ then it belongs to all MSTs. Proof. We first show that if $e$ belongs to some MST then for every $\epsilon > 0$, if we reduce the ...

5

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 to move from one position to the other. The edge lengths can be computed using the A* algorithm or any other pathfinding algorithm. Now I think you want a ...

5

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.

5

If $G$ is a tree, it has a unique MST whatever its weights are. The weights could be unique, all the same, anything.

5

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). Proposition 1: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS ...

5

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 resulting MST. Notice that this definition depends solely on the chosen edge and on $G$. Notice also that it does not depend on the edge weights in any way. The ...

4

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, here is my solution to the question. Let $G$ be a weighted undirected (finite) graph. An edge $e$ is called superheavy if it is the unique heaviest edge in some ...

4

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 in a graph equals twice the number of edges; in particular, it is even. A minimum spanning tree is a graph in its own right. If it had an odd number of odd-...

4

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 shows. First, in a general graph, the algorithm might get stuck: you might end up at a vertex where you've already visited all the neighbours. For example, ...

4

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$ partitions the vertex set of the graph into two parts $(S, V-S)$, where $u \in S$ and $v \in V-S$. If $e$ was not a lightest edge between $S$ and $V-S$, then $e$ can ...

4

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 edge will cross the cut $(S,V-S)$. There is absolutely no requirement that $e$ not cross the cut.

4

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 noticing that they cannot induce any cycle and hence they must be selected by Kruskal's algorithm. Alternatively, you can notice that each cycle must contain at ...

3

The best exposition on how to count the number of minimum spanning trees is, as far as I have seen, a stackoverflow answer by j_random_hacker. In the course to answer a different question, that answer explains very well an algorithm that counts the number of MSTs. It establishes that Kruskal's algorithm can find every MST. It breaks up the Kruskal's ...

3

This is a nice exercise. You should probably do it yourself, to get the learning benefit. I suggest that you enumerate all non-isomorphic graphs with 3 vertices or 4 vertices, and for each such graph, try playing with the weights to try to find a counter-example. Basically, keep trying what you've been doing, but be more systematic and exhaustive about it....

3

All spanning trees have the same number of edges of each weight, as shown by Raphael as an answer to a question in that direction (thanks hengxin). How to we count the number of heavy edges, of weight $C$, without computing the MST explicitly? First ignore the heavy edges. Also ignore the weights of the remaining edges. Determine the number $k$ of ...

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