Les arbres couvrant un minimum d'un graphique pondéré ont-ils le même nombre d'arêtes avec un poids donné?

21

Si un graphe pondéré G a deux arbres couvrant minimum différents T1=(V1,E1) et , alors est-il vrai que pour toute arête dans , le nombre d'arêtes dans avec le même poids que (y compris lui-même) est le même que le nombre d'arêtes dans avec le même poids que ? Si l'énoncé est vrai, comment pouvons-nous le prouver?T2=(V2,E2)E 1 E 1 e e E 2 eeE1E1eeE2e

Aden Dong
la source
Une approche délicate mais réalisable consiste à montrer 1) l'algorithme de Kruskal peut produire chaque arbre couvrant minimal et 2) tous les arbres couvrant minimal trouvés par Kruskal ont le même multiset de poids de bord.
Raphael

Réponses:

16

Allégation: oui, cette affirmation est vraie.

Esquisse de preuve: Soit T1,T2 deux arbres s'étendant sur un minimum avec des ensembles multiples de poids de bord W1,W2 . Supposons W1W2 et notons leur différence symétrique avec W=W1ΔW2 .

Choisissez l'arête eT1ΔT2 avec w(e)=minW , c'est-à-dire que e est une arête qui n'apparaît que dans l'un des arbres et a un poids de désaccord minimum. Un tel bord, qui est en particulier eT1ΔT2 , existe toujours: il est clair, tous les bords de poids minW peuvent être dans les deux arbres, sinon minWW . Wlog soit eT1 et supposons T1a plus d'arêtes de poids minW que T2 .

Considérons maintenant toutes les arêtes de T2 qui se trouvent également dans la coupe CT1(e) induite par e dans T1 . S'il y a un bord e en bas qui a le même poids que e , la mise à jour T1 à l'aide de e à la place de e ; notez que le nouvel arbre est toujours un arbre couvrant minimal avec le même multiset de poids de bord que T1 . Nous répétons cet argument, en rétrécissant W de deux éléments et en supprimant ainsi un bord de l'ensemble des candidats pour e à chaque étape. Par conséquent, nous obtenons après un nombre infini d'étapes un paramètre où tous les bordsT2CT1(e) (where T1 is the updated version) have weights other than w(e).

Now we can always choose eCT1(e)T2 such that we can swap e and e¹, that is we can create a new spanning tree

T3={(T1{e}){e},w(e)<w(e)(T2{e}){e},w(e)>w(e)

which has smaller weight than T1 and T2; this contradicts the choice of T1,T2 as minimal spanning trees. Therefore, W1=W2.


  1. The nodes incident of e are in T2 connected by a path P; e is the unique edge in PCT1(e).
Raphael
la source
3
In reference to Dave's comment, I came up with this proof after 0) believing I had a counter-example which I saw was wrong after TikZing it, 1) trying to prove the statement but failing, 2) trying to construct a counter-example based on where the proof failed and failing again, and finally 3) using the way these new examples failed to work for coming up with the proof. That's probably also why it is not as refined as it could be.
Raphael
yeas exactly, I don't understand what is meant by cyt induced by e in T1 I had only seen cut like (S,VS) cut
dragoboy
@dragoboy Removing e disconnects T1; one component forms S, the other the complement.
Raphael
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 Ei:=w1(i) for i[m]. We can do induction on the number j of non-empty Ei and number of vertices n in G; for j=1 and any n, the statement is obvious.

A standard fact about matroids is that for every MST T there is a linear extension of the ordering induced by w so that the greedy algorithm produces T.

To close the induction, take t to be the largest number so that Et is not empty. Set E=E1Et1. Observe that any linear extension of w puts every edge in E before any edge in Et. According to the fact, any MST consists of a spanning forest F of the subgraph induced by E and some edges from Et. By the inductive hypothesis, each connected component of F has the same number of edges from each Ei for i<t. Since all the choices of F have the same size, the number of edges from Et required to complete F to a spanning tree is independent of the choice of F and we are done.

Louis
la source
Can you give the matroid for the MST problem? I seem to remember that it is a tough thing to come up with, and I have yet to see it done (rigorously). Yes, we use greedy algorithms, but not the (canonical) greedy from matroid theory.
Raphael
That said, I think your core argument works (and does not need matroids at all): by correctness of Kruskal's algorithm and the fact that every MST can be obtained from a run of Kruskal with a specific (sorted) permutation of the weight multiset (rigorous proof pending), the claim follows. I write "proof pending" because it's neither trivial nor immediate: without using the claim itself it is not at all clear why Kruskal should find all MSTs. Clearly, if one had a different weight multiset, Kruskal would never find it!
Raphael
1. The matroid is the graphic matroid. Done!
Louis
2. You're confused. Abstractly, we are doing linear optimization over the basis polytope. One of the standard characterizations of matroids is that the greedy algorithm works for any choice of weights. All the w-minimal spanning trees are vertices of a face of this polytope. Now standard ideas from LP lead to the standard fact I mentioned.
Louis
1. Can you give a reference? I don't know the graphic matroid. 2. Now you drag LP into it, too! All I'm saying is that your answer lacks the matroid, and that without the matroid the line of reasoning seems to rely on the claim itself. If you have a way around that, please edit/clarify the answer.
Raphael