Quand l'arborescence minimale d'un graphique n'est-elle pas unique

Étant donné un graphique pondéré et non orienté G: Quelles conditions doivent être remplies pour qu'il y ait plusieurs arbres couvrant minimum pour G?

Je sais que le MST est unique lorsque tous les poids sont distincts, mais vous ne pouvez pas inverser cette affirmation. S'il y a plusieurs arêtes avec le même poids dans le graphique, il peut y avoir plusieurs MST mais il peut aussi y en avoir un seul:

Dans cet exemple, le graphique de gauche a un MST unique mais pas celui de droite.

Le plus proche que j'ai pu trouver pour trouver les conditions de non-unicité du MST était le suivant:

Considérez tous les cycles sans accords (cycles qui ne contiennent pas d'autres cycles) dans le graphique G. Si dans l'un de ces cycles le bord pondéré maximal existe plusieurs fois, alors le graphique n'a pas d'arbre couvrant minimal unique.

Mon idée était que pour un cycle comme celui-ci

avec n sommets, vous pouvez omettre exactement l'un des bords et toujours avoir tous les sommets connectés. Par conséquent, vous avez plusieurs choix pour supprimer le bord avec le poids le plus élevé pour obtenir un MST, de sorte que le MST n'est pas unique.

Cependant, j'ai ensuite trouvé cet exemple:

Vous pouvez voir que ce graphique a un cycle qui correspond à ma condition: (E, F, G, H) mais pour autant que je puisse voir, l'arborescence minimale est unique:

Il semble donc que mon état ne soit pas correct (ou peut-être tout simplement pas complètement correct). J'apprécierais beaucoup toute aide pour trouver les conditions nécessaires et suffisantes pour la non-unicité de l'arbre couvrant minimum.

dans la première image: le graphique de droite a un MST unique, en prenant les bords et avec un poids total de 2.( F , G $(F,H)$$(F,G)$

Etant donné un graphe et laisser un arbre couvrant minimal (MST) dans .M = ( V , F ) $G=(V,E)$$M=(V,F)$$G$

S'il existe un bord avec un poids tel que l'ajout de à notre MST donne un cycle , et soit aussi le poids de bord le plus bas à partir de , alors nous pouvons créer un deuxième MST en échangeant un bord de avec le poids de bord avec . Ainsi, nous n'avons pas d'unicité.w ( e ) = m e C $e=\{v,w\}\in E \setminus F$$w(e)=m$$e$$C$$m$F ∩ C m $F\cap C$$F\cap C$$m$$e$

Une réponse précédente indique un algorithme pour déterminer s'il existe plusieurs MST qui, pour chaque bord non dans , trouvent le cycle créé en ajoutant à un MST précalculé et vérifient si n'est pas le bord le plus lourd unique de ce cycle. Cet algorithme est susceptible de fonctionner en temps .G e e O ( | E | | V |$e$$G$$e$$e$$O(|E||V|)$

Un algorithme plus simple pour déterminer s'il y a plusieurs de G en MST temps complexité$O(|E|\log(|V|))$ .

$\ $ 1. Exécutez l'algorithme de Kruskal sur pour trouver un MST .$G$$m$

$\ $ 2. Essayez d' exécuter l'algorithme de Kruskal sur à nouveau. Dans cette exécution, chaque fois que nous aurons le choix entre des arêtes de poids égaux, nous essaierons d'abord les arêtes non en , après quoi nous essaierons les arêtes en . Chaque fois que nous avons trouvé un bord qui n'est pas dans connecte deux arbres différents, nous affirmons qu'il existe plusieurs MST, mettant fin à l'algorithme.m m $G$$m$$m$$m$

$\ $ 3. Si nous sommes arrivés ici, nous affirmons que a un MST unique.$G$

Une exécution ordinaire de l'algorithme de Kruskal prend le temps . La sélection supplémentaire d'arêtes qui ne sont pas en peut être effectuée en temps . Ainsi, l'algorithme atteint la complexité temporelle .m O ( | E | ) O ( | E | log ( | V | ) $O(|E|\log(|V|))$$m$$O(|E|)$$O(|E|\log(|V|))$

Pourquoi cet algorithme peut-il déterminer s'il existe plusieurs MST?

Supposons que nous ayons un MST de . Il suffit de montrer que l'algorithme fonctionnant sur n'atteindra pas l'étape 3, car le bord trouvé à la fin de l'étape 2, qui n'est pas en et reliant deux arbres différents aurait été inclus dans le MST résultant si nous avions exécuté Kruskal algorithme à la fin. Soit le poids le plus grand tel que pour tout bord pesant moins que , il est en si et seulement s'il est en . Parce que et ont le même nombre d'arêtes de poids , il existe des arêtes de poids qui sont en m G m w w m m ′ m m ′ w w m ′ m e ′ S S ⊂ m w m e ′ w m m ′ e ′$m'$$m$$G$$m$$w$$w$$m$$m'$$m$$m'$$w$$w$$m'$ mais pas en . Si l'algorithme est sorti avant de traiter les bords de ces bords, nous avons terminé. Sinon, supposons que l'algorithme va maintenant traiter le premier bord parmi ces bords. Soit l'ensemble de toutes les arêtes qui ont été conservées jusqu'à présent pour être incluses dans le MST résultant. . Puisque l'algorithme n'a pas terminé le traitement des bords de poids non en tels que , il ne doit pas avoir commencé à traiter les bords de poids en . Les arêtes en pèsent donc moins que w . Cela signifie que S ⊂ m ′$m$$e'$$S$$S\subset m$$w$$m$$e'$$w$$m$$S$$w$et l'algorithme se termine à ce point.$S\subset m'.$Rappelons que est en m ' . Puisque { e ′ } ∪ S ⊂ m ′ , où est un arbre, doit connecter deux arbres différents dans$e'$$m'$$\{e'\}\cup S\subset m'$$m'$$e'$$S$

Remarque sur les développements ultérieurs Les
étapes 1 et 2 peuvent être entrelacées afin que nous puissions terminer l'algorithme le plus tôt possible sans traiter des arêtes de poids plus importants.
Si vous souhaitez calculer le nombre de MST, vous pouvez vérifier une réponse sur la façon de calculer le nombre de MST .

Soit un graphe connexe non orienté (simple fini) pondéré par les bords avec au moins deux sommets. Soit ST signifie arbre couvrant et MST signifie arbre couvrant minimum. Permettez-moi de définir d'abord quelques termes moins courants.$G$

• Un bord est plus lourd d'un cycle unique s'il est le bord le plus lourd unique d'un cycle.
• Un bord n'est pas le plus lourd du cycle s'il n'est jamais le plus lourd d'un cycle.
• Un bord est unique-coupé-le plus léger s'il est le bord le plus léger unique pour traverser une coupe.
• Un bord n'est pas le plus léger s'il n'est jamais le plus léger pour traverser une coupe.
• Deux ST sont adjacentes si chaque ST a exactement un bord qui n'est pas dans l'autre ST.
• Un MST est un MST isolé s'il n'est pas adjacent à un autre MST (lorsque les deux MST sont considérés comme des ST).

Quand y a-t-il plus d'un arbre couvrant minimum?

$G$

• Il y a deux MST adjacents.
• Il n'y a pas de MST isolé.
• Il existe une ST qui est aussi légère ou plus légère que toutes les ST adjacentes et qui est aussi légère qu'une ST adjacente.
• Il y a un bord qui n'est ni le plus lourd du cycle ni le plus lourd du cycle.
• Il y a un bord qui n'est ni unique, plus léger ni non coupé

La nouveauté de cette réponse réside principalement dans les deux dernières caractérisations. L'avant-dernière caractérisation peut être considérée comme la toute prochaine étape de l'approche du PO . Les trois premières caractérisations ensemble peuvent être considérées comme une version légèrement améliorée de la réponse de dtt .

$G$

Quand le nombre minimal d'arbres couvrant est-il unique?

$G$

• Unicité du MST : il existe un MST unique.
• Pas de MST adjacent : il n'y a pas de MST adjacent.
• Un MST isolé : il existe un MST isolé.
• Un ST minimum local : il y a un ST qui est plus léger que tous les ST adjacents.
• Bord de cycle extrême : chaque bord est soit le cycle le plus lourd, soit le cycle le plus lourd.
• Bord de coupe extrême : chaque bord est soit le plus léger de coupe unique ou le plus léger non coupé

Voici ma preuve.

"Unicité de MST" => "Pas de MST adjacent": évident.

"Pas de MST adjacents" => "Un MST isolé": évident.

"Un MST isolé" => "Un ST local minimum": Un MST isolé est plus léger que tous les ST adjacents.

$m$

• $m$$l$$m$$l$$l$$c$$l$$m$$m$$m_1$$m_2$$m_1$$m_2$$l$$c$$m_1$$m_2$$l'$$m'$$m_1$$m_2$$l'$$G$$m$$m'$$m$$m'$$l$$l'$$l$ pas le cycle le plus lourd.
• $m$$h'$$m$$h'$$m$$c$$h$$c$$h'$$m'$$m$$h$$h'$$m$$m'$$m$$m'$ . Cela signifie,$h$$h'$$h'$$c$$h'$

"Local minimum ST" => "Extreme cut edge": La preuve est laissée en exercice.

$m$$e$$e$$m$$e$$m$$m$ est exactement l'ensemble des arêtes non cycliques les plus lourdes.

"Extreme cut edge" => "Unicité de MST": La preuve est laissée comme exercice.

Les chaînes d'implications ci-dessus prouvent le théorème.

Encore une fois, la nouveauté de ces réponses est principalement la propriété "bord de cycle extrême" et la propriété "bord de coupe extrême", qui utilise les concepts, non cyclique le plus lourd et non coupé le plus léger. Je n'ai pas vu ces concepts ailleurs, bien qu'ils soient tout à fait naturels.

Voici deux observations intéressantes connexes.

• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$ est dans chaque MST
• $e$$e$$\Leftrightarrow$ $e$$\Leftrightarrow$ $e$

Deux conditions suffisantes mais non nécessaires pour un MST unique

$ab\rightarrow 1, bc\rightarrow 1, cd\rightarrow 1, da\rightarrow 2, ac\rightarrow 2$

$1,1,2$