51

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


47

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


46

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

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


14

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.


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


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


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.


10

Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph


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.


9

Just do a graph traversal algorithm, like DFS or BFS.


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

I think an example will make it clearer.. The spanning tree looks like below. This is because if we add up the edges in this configuration, we get the least total cost possible: 2+5+14+4=25. (1) (4) \ / (2) / \ (3) (5) By eyeballing the spanning tree you might falsely think that it gives you the shortest paths, but in practice it doesn't. ...


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

The difference lies in what is the ultimate goal of this algorithms- Dijkstra's - Here the goal is to reach from start to end. You are concerned about only this 2 points, and optimize your path accordingly. Krusal's - Here you can start from any point and have to visit all other points in the graph. So, you may not always choose the shortest path for any ...


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

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


6

Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: the one of the remaining vertices that has the cheapest connection to the tree already constructed. Here we only have to know whether there are still vertices ...


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

If $G$ is an undirected graph, it's a standard lemma that the following are equivalent: $G$ is a tree. $G$ is connected and has no cycles. $G$ is connected and the number of edges is one less than the number of vertices. Therefore, yes, your solution is also correct. (The authors' solution does have the benefit of giving you a relatively simple setting ...


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

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