Nehmen wir an, wir haben ein Diagramm $ G $. Wir wählen eine Kante daraus (eine beliebige Kante). Wird es immer einen solchen Spannbaum geben, dass enthält genau diese Kante?
Ich denke, die Antwort lautet ja, denn egal was wir tun, wir können immer einen solchen Spannbaum erstellen, so dass genau die Kante, die wir ausgewählt haben, enthalten ist. Natürlich ein formellerer Beweis würde benötigt werden?
Kommentare
- Sie ' haben nicht einmal einen informellen Beweis geschrieben: im Wesentlichen Sie ' haben " gesagt. Ich denke, die Antwort ist ja, weil die Antwort ja ist. "
Antwort
Beachten Sie, dass das ursprüngliche Diagramm $ G $ muss verbunden sein oder es gibt überhaupt keine Spannbäume. (Obwohl das gleiche Argument für jede Komponente zeigen würde, dass jedes Diagramm einen Spanning Forest hat, der eine beliebige Kante enthält.)
Lassen Sie $ G. = (V, E) $ sei ein zusammenhängender Graph, sei $ T $ ist ein beliebiger überspannender Teilbaum und $ e $ ist eine beliebige Kante in $ E $. Wir behaupten, dass es einen Spanning Tree gibt, der $ e $ enthält. Wenn $ e \ in T $, sind wir fertig. Andernfalls enthält $ T + e $ einen Zyklus. Dieser Zyklus enthält notwendigerweise mindestens eine Kante $ e „\ neq e $ (tatsächlich enthält er mindestens zwei). $ T + ee“ $ ist ein Spanning Tree, der $ enthält e $.
Sie sollten sich selbst beweisen, dass $ T + ee „$ wirklich ein Spanning Tree ist.
Antwort
Das Hinzufügen einer Kante zu einem Baum führt zu einem eindeutigen Zyklus. Sie können jede Kante aus diesem Zyklus entfernen (anders als die, die Sie hinzugefügt haben), um einen Baum zurückzugewinnen. Dieser neue Baum enthält die Kante, die hinzugefügt wurde.
Kommentare
- Das ' ist genau das, was ich gesagt habe!
- Ja, aber Ich habe es mit weniger Worten gesagt. 🙂
- Weil meine sieben Sätze wirklich in drei zusammengefasst werden müssen. Wir haben fünf Tausend unbeantwortete Fragen auf der Website – es wäre viel besser, einige dieser Fragen zu beantworten, als doppelte Antworten auf Fragen zu veröffentlichen, die ' nicht benötigt werden.
- Dann lesen Sie bitte die vorhandene Antwort s, bevor Sie eine eigene veröffentlichen.
- Es ist wirklich nichts erforderlich – wie können wir das überhaupt durchsetzen? Es wird jedoch allgemein erwartet, dass Antworten etwas Neues beitragen, und wie können Sie wissen, dass Sie ' dies tun, wenn Sie ' nicht wissen Was ' wurde bereits gesagt? Wenn Sie mehrere Antworten haben, die alle dasselbe sagen, wird die Seite nur unübersichtlich, obwohl ' mit nur zwei keine große Sache ist. Das Posten einer kurzen, zusammenfassenden Antwort kann auf jeden Fall wertvoll sein, wenn die vorhandenen Antworten lang sind. Ich glaube nur nicht, dass ' in diesem speziellen Fall etwas hinzugefügt wird.