47
votes
Accepted
Do any two spanning trees of a simple graph always have some common edges?
No, consider the complete graph $K_4$:
It has the following edge-disjoint spanning trees:
14
votes
Do any two spanning trees of a simple graph always have some common edges?
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$ ...
- 38.6k
13
votes
Accepted
When is the minimum spanning tree for a graph not unique
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$.
...
- 558
11
votes
Minimum spanning tree vs Shortest path
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.
...
- 373
10
votes
Accepted
Algorithm to get any spanning tree not necessarily a minimum spanning tree
Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph
- 11.5k
10
votes
Algorithm to get any spanning tree not necessarily a minimum spanning tree
Just do a graph traversal algorithm, like DFS or BFS.
- 12.5k
9
votes
Do any two spanning trees of a simple graph always have some common edges?
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 ...
- 520
8
votes
Diameter-constrained Minimum Spanning Tree Problem
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$.
- 275k
7
votes
Accepted
Diameter-constrained Minimum Spanning Tree Problem
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 ...
- 3,674
6
votes
Accepted
How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?
In modern terms, this problem is called Minimum Spanning Tree: Find the subtree of the input graph that minimizes the total weight of its edges. The algorithm here suggested by Dijkstra is today known ...
- 802
5
votes
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$ ...
- 38.6k
5
votes
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
5
votes
Determining if an undirected connected graph is minimally connected
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 ...
D.W.♦
- 156k
5
votes
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, ...
- 38.6k
5
votes
Accepted
Is every edge of a graph included in some spanning tree?
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 ...
- 81.4k
5
votes
Accepted
Christofides algorithm (by hand) (suboptimal solution - is it my fault?)
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 ...
- 38.6k
5
votes
How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?
The tree of minimum total length is nothing but the minimum spanning tree. The algorithm that you are talking about is nothing but Prim's algorithm, also called Prim–Dijkstra algorithm.
Answer to Your ...
- 5,827
5
votes
Accepted
Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex
First, verify that $G$ is indeed connected, otherwise say no.
Second, if $G - v$ (the graph after deleting $v$) has more than $k$ components, we can say no.
Pick any $k$ neighbors of $v$ with the ...
- 15.5k
4
votes
Minimum spanning tree vs Shortest path
The key is to understand that they are different problems: The spanning tree looks to visit all nodes in one "tour", while shortest paths focuses on the the shortest path to one node at a time.
As ...
4
votes
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 ...
- 275k
4
votes
Accepted
Min spanning tree that preserves total weight of original graph
Let us represent the people involved by numbers $1,\ldots,n$. For person $i$, let $\delta_i$ be the total amount that person $i$ is owed minus the total amount that she owes; notice that $\sum_{i=1}^n ...
- 275k
4
votes
Accepted
Kirchhoff's Spanning Tree Algorithm
It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial.
It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian ...
- 3,252
4
votes
Accepted
Prove finding a spanning tree with no more than 50 leaves is NP-hard
Yes, this problem is indeed $\text{NP}$-hard.
Here is a hint of proof. Draw several trees with 2 leaves. What kind of graphs are they?
- 38.6k
4
votes
Spanning tree - minimum difference between smallest and largest weight
You can solve the problem in $O(m \log n)$ time. For the sake of simplicity assume that all edge weights are distinct (this assumption can be easily removed).
Let $e_1, e_2, \dots, e_m$ be the edges ...
- 28.4k
4
votes
Accepted
Spanning tree - minimum difference between smallest and largest weight
I realized that my answer is similar to Steven's answer but maybe suitable for someone.
Based on increasing values of weights, sort the edges; e.g. $e_1,...,e_m$.
For $i=1,...,m-n+1$ (we need atleast $...
3
votes
Spanning tree with chosen leaves NP-Complete proof
The question you link to shows that the problem can be solved in polynomial time. If the problem was NP-complete, then this would prove that P = NP. Of course, it's a famous open problem to prove ...
D.W.♦
- 156k
3
votes
Find a graph for which Kruskal's algorithm achieves worst-case running time
Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$
Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$.
Now ...
- 1,198
3
votes
When is the minimum spanning tree for a graph not unique
Let $G$ be a (simple finite) edged-weighted undirected connected graph with at least two vertices. Let ST mean spanning tree and MST mean minimum spanning tree. Let me define some less common terms ...
- 38.6k
3
votes
Accepted
Maximum Spanning Tree vs Maximum Product Spanning Tree
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 ...
- 275k
3
votes
Accepted
Minimum Spanning Tree over Vertices Proof
It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$,
$$
\begin{align*}
\sum_{(i,j) \in T} m(e_{ij}) &= \sum_{(i,j) \in T} w(v_i) + w(v_j) ...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible