5
$\begingroup$

Let $G$ be a connected graph with $N$ nodes, $B$ the set of the nodes and $V$ the set of the edges of $G$.

For all edges $e \in V$, there is an associate positive weight $\nu_e > 0$ on this edge ($\nu_e=0$ if there is no connection). We suppose that there are no self-connecting edges (an edge that connects a node to himself) and that all the edges have different weigth.

It is very easy, using Kruskal or Prim's algorithm, to find a maximal spanning tree $T_{max} \subseteq V$ that is the spanning tree that maximizes the graph sum $$\sum_{e \in T_{max}} \nu_e.$$

Now, I want to operate on $G$ following this instruction :

  • For every cycle $c$, I remove the edge of the cycle that have the most minimal weight (and I do nothing if this edge has already been removed before).

At the end of this simple algorithm, we get a spanning tree $T$ that covers every edges, and by definition of the maximal spanning tree we have :

$$\sum_{e \in T} \nu_e \leq \sum_{e \in T_{max}} \nu_e.$$

However, on all the examples I've tried, I always end up with both sums being equal... (I end up with $T=T_{max}$)

Is their a counter-example that would verify the following $$\sum_{e \in T} \nu_e <\sum_{e \in T_{max}} \nu_e.$$

Or maybe the tree $T$ constructed using this method has to be a maximal spanning tree ?

Any help or ideas are welcomed.

$\endgroup$

2 Answers 2

4
$\begingroup$

The tree you get this way is guaranteed to be a maximal spanning tree.

If $T_\max$ is a maximal spanning tree, and $C$ is any cycle, then $T_\max$ can't possibly include the minimal-weight edge $e$ of $C$. Suppose it did. Deleting $e$ leaves $T_\max$ in two components, and since $C$ contains at least one edge crossing from one component to the other (the edge $e$) it must contain at least two. So there's some other edge $e'$ lying on $C$ which crosses from one component to the other, and which we can add to $T_\max - e$ to make it connected again.

But this is an improvement: we've deleted $e$, and added $e'$ which has higher weight than $e$. This contradicts our assumption that $T_\max$ was a maximal spanning tree.

As a result, $T_\max$ already can't include any minimal-weight edge of any cycle. If we go through the cycles and delete their minimal-weight edges, we never lose any edges of $T_\max$, so the remaining subgraph must contain $T_\max$. However, the remaining subgraph is a tree (it doesn't have any cycles, we ensured that) and so it must be $T_\max$.

$\endgroup$
2
  • $\begingroup$ Note that this solution uses the assumption that the edge weights are distinct, though not in an essential way. (And at any rate, the algorithm is only specified precisely for distinct edge weights.) $\endgroup$
    – Dániel G.
    Feb 8, 2021 at 18:02
  • $\begingroup$ If the edge weights are not distinct, then the algorithm is only guaranteed to work if it consistently breaks ties between equal edges. (Say that edges $e_1$ and $e_2$ have the same weight, and both lie on cycles $C$ and $D$. Then if $C$ deletes $e_1$, $D$ shouldn't delete $e_2$; we might not even get a tree if that's allowed.) Once we have established a consistent tie-breaking procedure, we're essentially back in the distinct-weight case. $\endgroup$ Feb 8, 2021 at 18:05
3
$\begingroup$

Let $e_1, e_2,\dots,e_m$ be an ordering of the edges such that $\nu_{e_1} \leq \nu_{e_2} \leq \dots \leq \nu_{e_m}$. If you run Kruskal's algorithm according to this ordering, the edges of the tree you get will be precisely those $e_i$ which are not in a cycle in the subgraph $G_i = (B, \{e_j, j \geq i\})$ of $G$. (Equivalently, those $e_i$ whose endpoints lie in different connected components of $G_{i+1}$.) On the other hand, your algorithm will delete those edges $e_i$ which are in a cycle in $G_i$. So the two algorithms actually give the same spanning tree!

Although this might not be useful to you right now, I can't resist adding a note about this question from the point of view of matroid theory. The above observations actually work in any matroid to show that your algorithm gives a maximum weight basis. There is actually a deeper underlying reason for this. The complement of a maximum weight basis is a minimum weight basis in the dual matroid. So running the greedy algorithm in the dual matroid to find a minimum weight basis and then taking the complement gives a maximum weight basis in the original matroid, and this is exactly what your algorithm does!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.