The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

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

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.

10

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

9

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

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

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

7

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

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.

6

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

6

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

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.

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

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

3

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

3

You state several beliefs but no reasoning. In math, if things are true then usually there is a good reason, namely a proof that the thing is true. Don't just make guesses, try to prove that your claims hold. Regarding your conjecture, consider Kruskal's algorithm, modified so that it arranges the weights in decreasing rather than increasing order. If we ...

3

A basic observation first: in any unweighted graph with a cycle, there is an MST that is not a shortest path tree for some source node. Proof: the tree must omit some edge on the cycle, and for either endpoint of that edge, the shortest path tree contains the edge. So if we fix the source node for the SSSP tree, then it'll be difficult to say more than that ...

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

3

If the answer is "yes", then there is an easy algorithm: just compute any MST and report the number of edges with weight $C$. If they all have the same number of edges with weight $C$, then the particular MST you compute won't change the answer. So now you want to know whether the answer is yes. To see that it is, observe that each MST is constructed by ...

3

The diameter of a graph is the longest shortest-path distance over all pairs of vertices. This distance can be measured in terms of edge weights or in terms of number of edges (which is known as geodesic distance). The measure that you choose depends on your particular application. In the paper that you mention, the authors focus on geodesic distance. When ...

3

That recursive algorithm is wrong, although it was an interesting attempt to improve established algorithms on specialized graphs. Here is a counterexample with $n=3$. The graph above was drawn at https://graphonline.ru/en All edges weigh 2 except that the rightmost two edges, $(v0,v3)$ and $(v2,v3)$ weigh 1. The recursive algorithm will pick only one ...

3

Claim : if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree True. It is the definition of MST on weighted (positive) graphs. Subset $S$ can't form a cycle due to minimum total weight condition. You can prove this by contradiction, assume $S$ is a MST and forms a cycle, as all weights are positive, ...

3

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

3

The "Cycle Property" helps (If you don't know it before, try to prove it first): Let $C$ be any cycle in $G$ and $e$ a heaviest (not necessarily unique) edge in $C$. Then there exists some MST which does not contain $e$. You are encouraged to answer the following questions: How to identify a cycle and then a heaviest edge $e$ in it? What to do with the ...

3

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.

3

By definition a spanning tree must have $n-1$ edges. If you remove edges and the graph remains connected, then again, a spanning tree must have $n-1$ edges. If you remove edges and the graph is disconnected then you will not be able to make a spanning tree for the whole graph but rather you will be able to get a Spanning Forest.

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