46

No, consider the complete graph $K_4$: It has the following edge-disjoint spanning trees:


37

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet ...


32

You are right that the two algorithms of Dijkstra (shortest paths from a single start node) and Prim (minimal weight spanning tree starting from a given node) have a very similar structure. They are both greedy (take the best edge from the present point of view) and build a tree spanning the graph. The value they minimize however is different. Dijkstra ...


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.


16

Claim: Yes, that statement is true. Proof Sketch: Let $T_1,T_2$ be two minimal spanning trees with edge-weight multisets $W_1,W_2$. Assume $W_1 \neq W_2$ and denote their symmetric difference with $W = W_1 \mathop{\Delta} W_2$. Choose edge $e \in T_1 \mathop{\Delta} T_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and ...


14

For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees. For example, the classical papers On the Problem of Decomposing a Graph into $n$ Connected Factors by W. T. Tutte and Edge-disjoint spanning trees of finite graphs by C. St.J. A. Nash-Williams provides a characterization of graphs that ...


12

Though Minimum Spanning Tree and Shortest Path algorithms computation looks similar they focus on 2 different requirements. In MST, requirement is to reach each vertex once (create graph tree) and total (collective) cost of reaching each vertex is required to be minimum among all possible combinations. In Shortest Path, requirement is to reach destination ...


12

It is possible to have different minimum spanning trees for a graph. Consider a simple example: a cycle graph with all weights equal. Removing any edge from the graph produces a minimum spanning tree for the cycle graph.


11

If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.


10

Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.


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

The complexity is derived as follows. The initialization phase costs $O(V)$. The $while$ loop is executed $\left| V \right|$ times. The $for$ loop nested within the $while$ loop is executed $degree(u)$ times. Finally, the handshaking lemma implies that there are $\Theta(E)$ implicit DECREASE-KEY’s. Therefore, the complexity is: $\Theta(V)* T_{EXTRACT-MIN} + \...


9

The question has been asked before on stackoverflow, where it has also been answered. The idea is to connect each vertex to $k-2$ new vertices. The new graph has a $k$-bounded spanning tree iff the original graph has a hamiltonian path. Mohit Singh and Lap Chi Lau gave a polytime algorithm which find a $(k+1)$-bounded spanning tree if a $k$-bounded spanning ...


9

First off to answer your main question: there is no flaw in the proof. The point where you are not following the reasoning of the proof is that: E belongs to a cycle in the graph and to the MST. Not every other edge of the cycle are in the MST. If you look at your drawing, then either one of the edges towards the rest of the MST is redundant. Because ...


9

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges. No, it's not true that any two spanning trees of a graph have common edges. Consider the wheel graph: You can make a spanning tree with edges "inside" the loop and another one from the outer loop.


8

One generalization of a tree in a directed graph is an arborescence. It is a directed tree with all edges directed from parent to child.


8

Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem. The problem can be solved using the Chu-Liu/Edmonds algorithm. The wikipedia entry is not as clear as I was expecting, but it does have links to the original papers.


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

Kapoor & Ramesh (proper SIAM J. Comput. version, free(?) personal website version) give an algorithm for enumerating all minimum spanning trees in both weighted and unweighted graphs. My understanding of the basic idea is that you start with one MST, then swap edges that lie along cycles in the graph (so as long as the weights are okay, you're replacing ...


7

No you wont. Suppose you have as graph the complete graph $K_n$ with $n\ge 4$, for simplicity we pick the $K_4$, but this construction works for all larger $n$. Every DFS-tree of a complete graph is a path, no matter how you order the edges. But clearly you can define the weights such that a non-path is the MST. See the example below (MST in red).


7

Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it. Consider the figures for an example: In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)<w(e=CE)$. So the claim "For ...


7

You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random edge. Similarly, if you choose the weights at random, the first edge that is chosen in Kruskal's algorithm is a uniformly random edge. What about the next edge? ...


7

Given a graph $G$, a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$. There can be many spanning trees for $G$. If you put weights on the edges, one of these spanning trees will have a minimal sum of weights. This is the minimal spanning tree. Regular (sub)tree is just subgraph which is a tree - it doesn't have ...


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


5

Yes $G$ has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After adding the two minimum edges, you can't have a cycle, therefore both are in the MST. Edit: As Paresh pointed out, this is not a complete proof, since there may be ...


5

What follows is taken from Tsuyoshi Ito's comment. If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)


5

Here is a slightly simpler argument that also works for other matroids. (I saw this question from another one.) Suppose that $G$ has $m$ edges. Without loss of generality, assume that the weight function $w$ takes on values in $[m]$, so we have a partition of $E$ into sets $E_i := w^{-1}(i)$ for $i\in [m]$. We can do induction on the number $j$ of non-...


5

It is possible to craft test cases for general graphs where your Borůvka's step wouldn't halve the number of edges in each step, even though it halves the number of vertices. An interesting note is that the optimization that you suggest works for planar graphs. This is because for planar graphs $|E| \leq 3*|V|-6 $ i,e $|E| = O(|V|)$. And in general it leads ...


5

Note that the initial graph $G$ needs to be connected or it has no spanning trees at all. (Though the same argument applied to each component would show that any graph has a spanning forest containing any chosen edge.) Let $G=(V,E)$ be a connected graph, let $T$ be any spanning subtree and let $e$ be any edgein $E$. We claim that there is a ...


5

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates ...


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