Comment est un minimum goulot d'étranglement de l'arbre recouvrant différents à partir d'un minimum spanning tree?

Un minimum de goulot d'étranglement de l'arbre recouvrant d'un graphe pondéré G est un arbre recouvrant de G tels que minimise le poids maximum de tout bord dans le spanning tree. Un MBST n'est pas nécessairement une MST (minimum spanning tree).

Veuillez donner un exemple où ces déclarations font sens.

InformationsquelleAutor Nikunj Banka | 2013-01-12
  1. 40

    Regarder la MST exemple sur Wikipédia pour référence:

    Comment est un minimum goulot d'étranglement de l'arbre recouvrant différents à partir d'un minimum spanning tree?

    Un goulot d'étranglement dans un spanning tree est un maximum de poids à la pointe de l'arbre. Il peut y avoir plusieurs goulots d'étranglement (tout de même poids, bien sûr) dans un arbre recouvrant. Dans le Wikipedia MST il y a deux goulots d'étranglement de poids 8.

    Maintenant, prenez un minimum spanning tree d'un graphique donné (il peut y avoir plusieurs MSTs, tous avec le même total de l'arête de poids bien sûr) et d'appeler le maximum de pondération de bord B. Dans notre exemple B = 8.

    Tout spanning tree qui dispose également d'un goulot d'étranglement de B = 8 est un MBST. Mais il ne peut pas être une MST (parce que le total de la pondération de bord est plus grande que la meilleure possible).

    Alors, prenez le Wikipedia de MST et de le modifier (ajouter /enlever des arêtes), de sorte que

    1. il reste un arbre recouvrant, et
    2. ça ne fonctionne toujours pas utiliser tout poids > 8, encore
    3. vous augmentez le montant total de pondération de bord

    Par exemple de changer juste le sous-arbre "à gauche" de la Wikipédia MST (composé de poids {2, 2, 3}) à {2, 3, 6}, augmentant ainsi le total de la pondération de bord par 4 sans changer le goulot d'étranglement de 8. Bingo, vous avez créé un MBST qui n'est pas une MST.

    • tu veux dire l'édition de l'longueurs de bord {2,2,3} qui sont sur la gauche et pas à droite ?
    • Bien sûr que non, si vous MODIFIEZ le poids que vous avez un autre graphique. Regardez les EXISTIG figure, il y a des arêtes avec des poids {2, 2, 3} sur le côté droit de l'en gras MST. Supprimer ceux du gras de l'arbre et de les remplacer avec de l'EXISTANT bords marqués 2, 3, et 6. Si j'ai un sentiment que vous ne pouvez pas comprendre les bases...
    • Oh... j'ai mélangé en haut à gauche et à droite, j'ai été à l'origine à la recherche à un autre sous-arbre. Fixe.
    • Si le bord le poids aurait été distincts alors MST est le MBST. Et vice-versa.
    • Est-ce forcément vrai? Le MBST n'est pas unique encore droit?
    • Si les poids sont uniques alors à la fois le MST et MBST serait la même et unique
    • Pas vrai. Prendre quatre sommets, connecter trois d'entre eux dans un cycle avec les arêtes de poids 1,2,3, puis connectez le quatrième sommet de l'un sur le cycle avec une arête de poids 4. Vous devez prendre le bord de poids 4, et qui vous donne trois MBSTs, dont l'une seulement est un MST. Seulement le MST est toujours unique dans les graphiques avec toutes les différentes pondérations de bords. Une famille de contre-exemples sont cliques avec le tout-autre bord poids, plus un autre sommet qui se connecte à la clique avec un super-lourds bord; chaque MBST consiste en ce que le bord, plus un découpage arbitraire de l'arbre de la clique.
    • Si je considère un goulot d'étranglement spanning tree et un minimum spanning tree, puis est la MST d'un graphe un Goulot d'étranglement spanning tree? Notez que je parle d'un goulot d'étranglement spanning tree et pas un MBST.

    InformationsquelleAutor dan3
  2. 34

    Avant de répondre à votre question, permettez-moi de définir certains termes qui sont utilisés ici...

    1), Spanning Tree : arbre recouvrant d'un graphe est un arbre qui couvre tous les sommets de ce graphe.

    2) Minimum spanning tree (MST) : MST d'un graphe est un arbre recouvrant dont la longueur est minimale parmi tous les arbres de recouvrement de ce graphe. Plus clairement, pour un graphique donné, la liste de tous les possibles couvrant les arbres (qui peut être très grand) et de choisir celui dont la somme de l'arête de poids minimum.

    3) Minimum Goulot d'étranglement spanning tree (MBST) : MBST d'un graphe est un arbre recouvrant dont le maximum de l'arête de poids minimal parmi tous les arbres de recouvrement. Plus clairement, pour un graphique donné, la liste de tous les possibles couvrant les arbres et le bord maximum de poids pour chacun des arbres de recouvrement. Parmi ces choisir le spanning tree dont le maximum de l'arête de poids minimum.

    Maintenant, penchons-nous sur l'image ci-dessous avec un quatre nœud graphique...

    Comment est un minimum goulot d'étranglement de l'arbre recouvrant différents à partir d'un minimum spanning tree?

    Graphique-Un est le graphique d'origine. Si je liste tous les arbres de recouvrement de ce graphe et de choisir celui dont la somme des pondérations de bords est minimale, alors j'aurai le Graphique-B.
    Donc Graph-B est le Minimum Spanning Tree(MST). Notez que son poids total est de 1+2+3=6.

    Maintenant, si je choisis un arbre recouvrant dont le maximum de l'arête de poids minimum (j'.e MBST), puis j'ai peut finir par ramasser soit Graphique-B (ou) Graphique-C. Notez que ces deux arbres de recouvrement maximum de bord de poids 3, qui est minimale parmi tous les arbres de recouvrement.

    À partir du Graphique-B et Graphique-C, il est clair que, même si le Graphique, C est un MBST, il n'est pas MST. En raison de son poids total est de 1+3+3=7, ce qui est plus grand que le poids total de la MST tracées dans le Graphique-B (j'.e 6).

    Donc MBST pas nécessairement être une MST d'un graphique donné. Mais le MST doit être MBST.

    InformationsquelleAutor Nagakishore Sidde