Condition nécessaire et suffisante pour un arbre couvrant unique unique

8

Il s'agit d'un problème d'exercice (Ex.3) de l'excellente note de conférence de Jeff Erickson Conférence 20: Minimum Spanning Trees [Fa'13] .

Démontrer qu'un graphe pondéré sur les bords a un arbre couvrant minimal unique si et seulement si les conditions suivantes sont réuniesG

  • Pour toute partition des sommets de en deux sous-ensembles, l'arête de poids minimum avec un point d'extrémité dans chaque sous-ensemble est unique.G

  • Le bord de poids maximum dans n'importe quel cycle de est unique.G

Considérons le « direction » et le graphique suivant .⇒G

mst

G a un MST unique. Cependant, pour la partition et , le bord de croisement de poids minimum n'est pas unique.{A}{B,C}

Ai-je mal compris certains points? Ou s'il y a des défauts dans le théorème, comment pouvons-nous le corriger?

graph-theory spanning-trees hengxin
la source
3
Oui, cela semble être une erreur. Essayez de déterminer quelle version de l'exercice est correcte. Par exemple, il semble que la deuxième condition soit effectivement nécessaire.
Yuval Filmus
2
À moins que je ne comprenne mal, la deuxième condition n'est pas non plus nécessaire. Considérez le graphique {(A, B, 1), (A, C, 1), (A, D, 1), (B, D, 10), (D, C, 10)}. Il a également un arbre couvrant minimum composé d'arêtes connectées à A. Mais il y a un cycle avec 2 arêtes de poids maximum (et la première condition n'est pas remplie non plus). CC @YuvalFilmus
babou
@jeffe, qu'en pensez-vous? ;)
Luke Mathieson
Je pense que le second devrait être dans "dans n'importe quel cycle sans accord " (donc un cycle minimal dans le sens où il n'inclut pas les plus petits comme sous-graphes induits). La première condition semble significativement erronée. Par exemple, prenez pour n'importe quel arbre où tous les poids de bord sont , alors a un MST unique (lui-même), mais toute partition avec plus d'un bord le traversant a plusieurs bords de poids minimum. G1G
Luke Mathieson
1
Oops! Oui, c'est un bug. (Note à soi-même: changez chaque instance de "Prove" en "Prove or disprove".)
JeffE

Réponses:

0

Répondez à ma propre question en copiant simplement le commentaire de @JeffE, l'auteur de la note de cours:

Oops! Oui, c'est un bug. (Note à soi: changer chaque instance de "Prove" en "Prove or disprove".) - JeffE

hengxin
la source