Disons que nous avons un graphique $ G $. Nous en choisissons un bord (n’importe quel bord). Y aura-t-il toujours un arbre couvrant contient ce même bord?
Je pense que la réponse est oui, car quoi que nous fassions, nous pouvons toujours créer un tel arbre couvrant afin que le bord même que nous avons choisi soit inclus. Bien sûr, une preuve plus formelle serait nécessaire?
Commentaires
- Vous ' navez même pas écrit une preuve informelle: essentiellement, vous ' avez dit " Je pense que la réponse est oui, car la réponse est oui. "
Réponse
Notez que le graphique initial $ G $ doit être connecté ou il na pas du tout darbre couvrant (bien que le même argument appliqué à chaque composant montre que tout graphe a une forêt englobante contenant nimporte quelle arête choisie.)
Soit $ G = (V, E) $ un graphe connexe, soit $ T $ est nimporte quel sous-arbre couvrant et soit $ e $ nimporte quel bord dans $ E $. Nous affirmons quil existe un arbre couvrant qui inclut $ e $. Si $ e \ in T $, nous avons terminé. Sinon, $ T + e $ contient un cycle. Ce cycle contient nécessairement au moins une arête $ e « \ neq e $ (en fait, il en contient au moins deux). $ T + ee » $ est un arbre couvrant qui contient $ e $.
Vous devriez vous prouver que $ T + ee « $ est vraiment un arbre couvrant.
Réponse
Lajout dun bord à un arbre provoque un cycle unique. Vous pouvez supprimer nimporte quel bord de ce cycle (différent de celui que vous avez ajouté) pour récupérer un arbre. Ce nouvel arbre contient le bord qui a été ajouté.
Commentaires
- Cest ' exactement ce que jai dit!
- Oui, mais Je lai dit avec moins de mots. 🙂
- Parce que mes sept phrases vraiment doivent être résumées en trois. Nous avons cinq mille questions sans réponse sur le site – il serait bien préférable de répondre à certaines d’entre elles plutôt que de publier des réponses en double aux questions dont ' n’a pas besoin.
- Alors sil vous plaît lire la réponse existante s avant de publier lun des vôtres.
- Rien nest vraiment requis – comment pourrions-nous le faire appliquer, de toute façon? Mais on sattend généralement à ce que les réponses apportent quelque chose de nouveau, et comment pouvez-vous savoir que vous ' faites cela si vous ' ne savez pas Quest-ce que ' a déjà dit? Avoir plusieurs réponses qui disent toutes la même chose ne fait quencombrer la page, bien que de toute évidence, ' nest pas un problème avec seulement deux. Publier une réponse courte et de style résumé peut certainement être utile lorsque les réponses existantes sont longues; Je ne pense que ' que cela ajoute quoi que ce soit dans ce cas particulier.