Mondjuk, hogy van egy $ G $ grafikonunk. Kiválasztunk belőle egy élt (bármelyik él). Lesz-e mindig olyan átfogó fa, hogy tartalmazza ezt az élt?
Úgy gondolom, hogy a válasz igen, mert bármit is tegyünk, mindig létrehozhatunk egy ilyen átfogó fát, hogy a kiválasztott él is benne legyen. Természetesen egy formálisabb bizonyíték szükség lenne rá?
Megjegyzések
- Ön még ' még informális igazolást sem írt: lényegében, te ' mondtad " szerintem a válasz igen, mert a válasz igen. "
Válasz
Ne feledje, hogy a kezdeti grafikon A $ G $ -ot össze kell kapcsolni, vagy egyáltalán nincsenek átfogó fái. (Bár ugyanaz az argumentum, amelyet az egyes komponensekre alkalmazunk, azt mutatná, hogy bármelyik grafikonnak van egy átfogó erdője, amely bármelyik választott élet tartalmazza.) = (V, E) $ legyen összekapcsolt gráf, legyen $ T $ legyen bármely átívelő részfa, és $ e $ legyen bármelyik él $ E $. Állításunk szerint létezik egy átfogó fa, amely tartalmazza a $ e $ értéket. Ha $ e \ T $ -ban van, akkor készen vagyunk. Egyébként a $ T + e $ tartalmaz ciklust. Ez a ciklus szükségszerűen tartalmaz legalább egy élt $ e “\ neq e $ (valójában legalább kettőt tartalmaz). A $ T + ee” $ egy átfogó fa, amely a következőt tartalmazza: $ e $.
Bizonyítanod kell magadnak, hogy a $ T + ee “$ valóban egy átfogó fa.
Válasz
Az él hozzáadása egy fához egyedi ciklust eredményez. Ebből a ciklusból bármelyik élt eltávolíthatja (az Ön által hozzáadottaktól eltérően), hogy visszakaphasson egy fát. Ez az új fa tartalmazza a hozzáadott élt.
Megjegyzések
- Ez ' pontosan az, amit mondtam!
- Igen, de Kevesebb szóval mondtam. 🙂
- Mivel a hét mondatomat valóban háromra kell összefoglalni. Van öt ezer megválaszolatlan kérdés az oldalon – sokkal jobb lenne ezekre válaszolni, mint duplikált választ feltenni olyan kérdésekre, amelyekre nincs szükségük <
. >