9
votes

Y a-t-il un arbre au minimum étendu qui ne contient pas le bord minf pondéré min / max?

Si nous avons un graphique non attribué (arbitraire) connecté g, dont les bords ont poids distincts ,

Chaque MST de G contient le bord pondéré minimum?
Y a-t-il un mst de G qui ne contient pas le bord pondéré maximum?
En outre, je suis plus reconnaissant si quelqu'un peut donner une idée des éléments clés, il faut garder à l'esprit lorsqu'il s'agit de telles questions de MST.
Ceci est un problème de devoirs. Merci.

algorithm minimum-spanning-tree

0 commentaires

4 Réponses :

8
votes

Y a-t-il un MST de G qui ne contient pas le bord pondéré maximum?
Il peut y avoir, mais il n'y a pas à être. Considérons un graphique à 4 sommets comme suit: xxx
L'arborescence minimale s'étend sur le jeu de bord {CA, AB, BD}. Le poids de bord maximum est de 50, le long de {cd}, mais cela ne fait pas partie du MST. Mais si G était déjà égal à son propre MST, alors évidemment, il serait contenir son propre bord maximum.

Chaque mst de G contient le bord pondéré minimum?
Oui. Les MST ont une propriété Couper . Un Cut est simplement une partition des sommets du graphique en deux ensembles disjoints. Pour toute coupe, vous pouvez faire, si le poids d'un bord de cette coupe est plus petit que les poids des autres bords de la coupe, ce bord appartient à tous les MST dans le graphique. Parce que vous avez garanti que les poids des bords sont distincts, vous avez également garanti qu'il y a un bord inférieur à tous les autres bords.

En outre, je suis plus reconnaissant si quelqu'un peut donner une idée des éléments clés, il faut garder à l'esprit lorsqu'il s'agit de telles questions de MST.
Votre meilleur pari est de raisonner sur les choses utilisant les propriétés de MSTS en général, et d'essayer de construire des contre-échantillons spécifiques que vous pensez prouver votre cas. J'ai donné un exemple de chaque ligne de raisonnement ci-dessus. En raison des propriétés de coupe et de cycle, vous pouvez toujours déterminer exactement quels bords sont dans un MST. Vous pouvez donc tester systématiquement chaque bord pour déterminer s'il est ou non dans le MST.

0 commentaires

0
votes

Pour votre première question, la réponse est non, et L'algorithme de Kruskal le prouve. Il sélectionnera toujours le bord de coût minimum.
Pour la deuxième question, la réponse est oui, et il est trivial de trouver un exemple de graphique: xxx
Le troisième bord ne sera jamais être sélectionné car il introduit un cycle. Donc, fondamentalement, si le bord avec le coût maximal créerait un cycle si inséré dans le MST, il ne sera pas inséré.

0 commentaires

6
votes

Chaque mst de G contient le bord pondéré minimum?
Oui. Supposons que nous avons un MST qui ne contient pas le bord du poids min. Maintenant, l'inclusion de ce bord vers le MST entraînera un cycle . Maintenant, il y aura toujours un autre bord dans le cycle qui peut être supprimé pour supprimer le cycle et maintenir toujours le graphique ( MST ) connecté.
Y a-t-il un MST de G qui ne contient pas le bord pondéré maximum? dépend du graphique. Si le graphique est lui-même est un arbre, nous devons inclure tous les bords N-1 dans le MST , de sorte que le bord de poids maximum ne peut pas être exclu. Également si le bord de poids maximum est un coupé de sorte que son exclusion n'entraînera jamais la connectivité, le bord de poids maximum ne peut pas être exclu. Mais si le bord de poids maximum fait partie d'un cycle , il est possible d'exclure à partir du MST .
0 commentaires
0 votes Je vois que vous étudiez aussi pour le CSC263 à travers le test de 2009? (Pareil ici!) Une autre façon de voir que le minimum est toujours dans le MST consiste à regarder simplement à ce bord minimum (appelez-le e): P> e v1 ---------------- v2 0 commentaires

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?