Låt oss säga att vi har ett diagram $ G $. Vi väljer en kant från den (vilken kant som helst). Kommer det alltid att finnas ett så omfattande träd att innehåller just den kanten?
Jag tror att svaret är ja, för oavsett vad vi gör kan vi alltid skapa ett sådant spännande träd så att själva kanten vi valde ingår. Naturligtvis ett mer formellt bevis skulle behövas?
Kommentarer
- Du ' har inte skrivit ens ett informellt bevis: i huvudsak, du ' har sagt " Jag tror att svaret är ja, eftersom svaret är ja. "
Svar
Observera att den första grafen $ G $ måste anslutas eller så har det inga spännande träd alls. (Även om samma argument som tillämpas på varje komponent skulle visa att varje graf har en spännande skog som innehåller valfri kant.)
Låt $ G = (V, E) $ vara ett anslutet diagram, låt $ T $ vara vilken som helst spännande subtree och låt $ e $ vara vilken kant som helst $ E $. Vi hävdar att det finns ett spännande träd som innehåller $ e $. Om $ e \ i T $ är vi klara. Annars innehåller $ T + e $ en cykel. Den cykeln innehåller nödvändigtvis minst en kant $ e ”\ neq e $ (faktiskt innehåller den minst två). $ T + ee” $ är ett spännande träd som innehåller $ e $.
Du bör bevisa för dig själv att $ T + ee ”$ verkligen är ett spännande träd.
Svar
Att lägga till en kant i ett träd orsakar en unik cykel. Du kan ta bort alla kanter från den här cykeln (annorlunda än den du lade till) för att få tillbaka ett träd. Det nya trädet innehåller kanten som lades till.
Kommentarer
- Att ' är exakt vad jag sa!
- Ja, men Jag sa det med färre ord. 🙂
- Eftersom mina sju meningar verkligen behöver sammanfattas i tre. Vi har fem tusen obesvarade frågor på webbplatsen – det skulle vara mycket bättre att svara på några av dem än att lägga upp dubbla svar på frågor som inte ' inte behöver dem.
- Läs sedan det befintliga svaret s innan du skickar en av dina egna.
- Ingenting krävs egentligen – hur skulle vi kunna genomdriva det i alla fall? Men det förväntas generellt att svar ska bidra med något nytt, och hur kan du veta att du ' gör det om du inte vet ' vad ' sägs redan? Att ha flera svar som alla säger samma sak förstör bara sidan, men det är uppenbart att ' inte är en stor sak med bara två. Att skicka ett kort, sammanfattande svar kan definitivt vara värdefullt när de befintliga svaren är långa; Jag tror bara inte ' att det tillför något i det här fallet.