Laten we zeggen dat we een grafiek $ G $ hebben. We kiezen er een rand uit (een willekeurige rand). Zal er altijd zon spanning tree zijn dat bevat die rand?
Ik denk dat het antwoord ja is, want wat we ook doen, we kunnen altijd zon opspannende boom maken, zodat de rand die we hebben gekozen, wordt meegenomen. Natuurlijk een formeler bewijs zou nodig zijn?
Reacties
- Je ' hebt zelfs geen informeel bewijs geschreven: in wezen je ' hebt gezegd " Ik denk dat het antwoord ja is, omdat het antwoord ja is. "
Answer
Merk op dat de initiële grafiek $ G $ moet verbonden zijn of het heeft helemaal geen opspannende bomen. (Hoewel hetzelfde argument toegepast op elke component zou aantonen dat elke grafiek een overspannend forest heeft met een gekozen rand.)
Laat $ G = (V, E) $ een verbonden grafiek zijn, laat $ T $ is een willekeurige overspannende substructuur en laat $ e $ elke rand zijn in $ E $. We beweren dat er een spanning tree is die $ e $ bevat. Als $ e \ in T $, zijn we klaar. Anders bevat $ T + e $ een cyclus. Die cyclus bevat noodzakelijkerwijs minstens één rand $ e “\ neq e $ (eigenlijk bevat hij minstens twee). $ T + ee” $ is een spanning tree die $ bevat e $.
Je moet voor jezelf bewijzen dat $ T + ee “$ echt een spanning tree is.
Antwoord
Het toevoegen van een rand aan een boom veroorzaakt een unieke cyclus. Je kunt elke rand uit deze cyclus verwijderen (anders dan degene die je hebt toegevoegd) om een boom terug te krijgen. Deze nieuwe boom bevat de rand die is toegevoegd.
Reacties
- Dat ' is precies wat ik zei!
- Ja, maar Ik zei het met minder woorden. 🙂
- Omdat mijn zeven zinnen echt in drie moeten worden samengevat. We hebben vijf duizend onbeantwoorde vragen op de site – het zou veel beter zijn om enkele daarvan te beantwoorden dan dubbele antwoorden te posten op vragen die ' niet nodig hebben.
- Lees dan het bestaande antwoord s voordat u er zelf een plaatst.
- Niets is echt vereist – hoe kunnen we dit eigenlijk afdwingen? Maar over het algemeen wordt verwacht dat antwoorden iets nieuws moeten bijdragen, en hoe kun je weten of je ' dat doet als je ' niet weet wat is ' er al gezegd? Meerdere antwoorden hebben die allemaal hetzelfde zeggen, maakt de pagina onoverzichtelijk, hoewel het duidelijk is dat ' met slechts twee geen probleem is. Het plaatsen van een kort antwoord in samenvattende stijl kan zeker waardevol zijn als de bestaande antwoorden lang zijn; Ik denk gewoon niet dat ' niet iets toevoegt in dit specifieke geval.