L'arborescence minimale de Spanning ne doit-il pas avoir que ces bords spécifiés par la propriété de cycle?[dupliquer]

Question

Cette question a déjà une réponse ici :

Quels bords ne sont dans aucun MST? (1 réponse)

fermée Il y a 4 mois .

Je viens de commencer à comprendre les "arbres minimums étendus" (MSTS) et a rencontré la propriété du cycle. Je parle de la conception du livre - Algorithme de Jon Kleinberg et d'Eva Tardos. La déclaration de la propriété telle que écrite dans le livre est la suivante:

suppose que tous les coûts de bord sont distincts. Soit C être n'importe quel cycle en g et laisse Edge E= (V, W) être le bord le plus coûteux appartenant à C. Alors E n'appartient pas à un arbre minimum étendu.

Maintenant, mon doute est: sont les bords d'un graphique (graphique non dirigé avec des bords ayant des poids positifs distincts) qui ne satisfont pas la propriété cyclable les seuls qui ne sont pas présents dans le MST ou qu'il y aura d'autres bords qui n'appartiennent pas au MST et ne sont pas couverts par cette propriété?

Je suis incapable de trouver une preuve pour discuter de savoir si de tels arêtes existent ou non. Certains peuvent-ils donner une preuve pour cela?

Answer 1

laissez-nous dire qu'un bord $ e $ in $ g $ est mauvais < / Strong> S'il existe un cycle dans $ g $ dans lequel $ E $ a du poids maximal.

définir $ {\ cal b}={e ~ | ~ e $ est mauvais dans $ g \} $ pour être la collection de toutes les bords mauvaises.

Votre question est de savoir si le graphique $ (g - {\ cal b}) $ Le MST de $ g $ (en supposant que tous les poids de bord sont distincts). La réponse est oui!

Pour prouver cela, il suffit de montrer que $ (g - {\ cal b}) $ est acyclique.

suppose au contraire que $ (g - {\ cal b}) $ contient un cycle, dites $ C $ . Observez que $ C $ est un cycle dans $ g $ aussi. Laissez $ E ^ * $ être le bord du poids maximum dans le cycle $ C $ . Maintenant $ E ^ * $ est un edge Bad , il n'aurait donc pas dû être graphique $ (G - {\ cal b}) $ sur la première place. Cela montre que $ (g - {\ cal b}) $ est acyclique.

Answer 2

Désolé si je ne comprenais pas votre question, mais ce que je pense que vous vouliez dire, c'est que cela soit possible pour un bord de ne pas être dans un MST si ce bord n'est pas dans un cycle.

Voici ma réponse.

laissez-nous supposer que nous avons un bord (U, V) dans un graphique G, qui ne fait pas partie d'un cycle.Cela signifierait qu'il n'y a pas de chemin de vous à V à V qui n'est pas le bord (U, V). Si le bord (U, V) n'était pas dans le MST, cela signifierait qu'il n'y a pas de chemin de vous à V à V dans ce MST, ce qui signifie que le MST serait déconnecté et donc pas du tout. Par conséquent, si un bord ne fait pas partie d'un cycle, il doit être dans le MST du graphique.