Spanning Tree minimum: Quelle est exactement la propriété Cut?

Question

J'ai passé beaucoup de temps à lire des présentations en ligne et des manuels sur la propriété de coupe d'un arbre recouvrant minimum. Je ne comprends pas vraiment ce que c'est supposé illustrer ou même pourquoi c'est pratique. Supposément, il aide à déterminer les bords à ajouter à un MST, mais je ne vois pas comment il accomplit cela. Ma compréhension de la propriété cut jusqu'ici est que vous divisez un MST en deux sous-ensembles arbitraires. Toute aide ici? Merci!

Answer 1

Une coupe d'un graphe connexe est un ensemble minimal d'arêtes dont le retrait sépare le graphe en deux composants (pièces). La propriété de coupe minimale dit que si l'un des bords de la coupe a un poids plus petit que tout autre bord de la coupe, il est dans le MST. Pour le voir, supposons qu'il existe un MST ne contenant pas le bord. Si nous ajoutons le bord au MST, nous obtenons un cycle qui coupe la coupe au moins deux fois, de sorte que nous pouvons casser le cycle en supprimant l'autre bord du MST, créant ainsi un nouvel arbre avec un poids plus petit, contredisant ainsi la minimalité du MST.