Minimum spanning tree with small set of possible edge weights

Given a undirected graph which only has two different edge weights $ x$ and $ y$ is it possible to make a faster algorithm than Prim’s algorithm or Kruskal’s algorithm?

I saw on Kruskal’s algorithm that it already assumes that the edges can be sorted in linear time with count sort, so then can we gain any benefit by knowing the weights of all of the edges ahead of time?

I don’t think there is any benefit, but I am not sure…

Variation to spanning tree called Group Spanning Tree

Suppose we have a complete graph with say 100 nodes. We divide the nodes in the graphs into groups for example 10 nodes in each group identified by color. We want to obtain an optimal spanning tree that operates under the constraint that at least one node will be present from each group. The resulting spanning tree can be called a group spanning tree. How to write an efficient algorithm for this making sure it is a tree(no cycles) and not looping over the entire node set on every pass to check presence of cycles and also making sure at least one node from each group is represented.

Graph with exactly 2 Minimum Spanning Trees


Say that a graph, $ G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in of the 2 MSTs) that at minimum, 2 of the edges in the set which is the union of the edges have equal weight. Also show that either this edge is the largest weight in the cycle, or not the largest weight in the cycle.

Overall am pretty stuck on this question.

My initial thoughts are the following: In any graph with more than 1 MST, clearly this means that the edge weights can’t be distinct, otherwise there wouldn’t be multiple MSTs. Also the graph $ G$ must contain cycles, otherwise, it wouldn’t have multiple MSTs.

My idea for proving that any cycle formed by the union of the edges of the two MSTs would be that in $ MST_1$ there is some edge, $ e$ that is not in $ MST_2$ and there is also some edge $ f$ that is not in $ MST_1$ . Using the cut property if $ e$ was not placed in $ MST_2$ and $ f$ was not placed in $ MST_1$ then then we have that the weight of $ f$ , and $ e$ , $ w(f) = w(e)$ .

Having trouble formalizing this though, and wondering if its actually a correct deduction. I feel that it makes sense given some examples and drawing, but not quite certain that’s actually true. Then from there I felt that there had to be some node, $ z$ such that $ z$ had 2 edges with the same weights, and when we combine the edges from $ MST_1$ and $ MST_2$ we end up with both the edges from $ z$ forming a cycle, and the edges are the same weights, so we know at least 2 of the edges form a cycle… Or the union of the edges could form a cycle graph itself which would then show that the 2 edges with the same weights are part of a cycle, I think? Is this somewhat on the right track? Is there some sort of condition for a graph, $ G$ , in order for it to have exactly 2 MSTs? Or is there some property I’m missing?

If someone could please provide a bit of guidance in the right direction, it would be extremely appreciated. Thanks.

How can Kruskal’s algorithm return different spanning trees?

We assume that we have the same graph G.

In introduction to Algorithms by Cormen it’s said that it`s possible depending on how it breaks ties when the edges are sorted into order.

I have trouble visualizing the answer given:

Suppose that A is an empty set of edges. Then, make any cut that has (u, v) crossing it. Then, since that edge is of minimal weight, we have that (u, v) is a light edge of that cut, and so it is safe to add. Since we add it, then, once we finish constructing the tree, we have that (u, v) is contained in a minimum spanning tree.

What does it mean to make a cut? I`m familiar with Kruskal’s algorithm but nowhere in the process do I see cuts being made. It’s either we unite two trees and add the edge to A or we reject the edge and continue on.

Kirchoff’s Spanning Tree Algorithm

Recently I have studied $ Kirchhoff’s$ $ spanning$ $ tree$ $ algorithm$ , which has the following steps–>

  • Build an adjacency matrix

  • Replace the diagonals with their respective degrees

  • Replace all the other ones excluding the one’s included in the
    diagonal by $ -1$

  • Then find $ minor$ of any one of the element to get your ans

These all steps looks like magic to me. can anyone explain how Kirchhoff derived this to obtain the minimum number of Spanning tree, I want to know the logic behind how this algorithm works, but all I can find in YouTube is the above steps only.

Minimum spanning tree formulation

Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree?

To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $ x_e$ with every edge $ e \in E$ . Each spanning tree $ T$ corresponds to its incidence vector $ x^T$ , which is defined by $ x^T_e = 1$ if $ T$ contains $ e$ and $ x^T_e = 0$ otherwise. Let $ \Pi$ denote the set of all partitions of the vertex set $ V$ , and suppose that $ \pi \in \Pi$ . The rank $ r(\pi)$ of $ \pi$ is the number of parts of $ \pi$ . Let $ E_\pi$ denote the set of edges whose ends lie in different parts of $ \pi$ . Consider the following LP: $ $ \begin{align*} \min &\sum_{e \in E} c_ex_e \ \text{s.t. } &\sum_{e \in E_\pi} x_e \geq r(\pi) – 1 \quad \forall \pi \in \Pi, \ & x \geq 0. \ \end{align*} $ $