Sanotaan, että meillä on kaavio $ G $. Valitsemme siitä yhden reunan (minkä tahansa reunan). Onko siellä aina sellainen ulottuva puu, että sisältää tuon reunan?
Luulen, että vastaus on kyllä, koska riippumatta siitä, mitä teemme, voimme aina luoda niin kattavan puun, että valitsemamme reuna on mukana. Tietenkin muodollisempi todiste tarvittaisitko?
Kommentit
- Et ' et ole kirjoittanut edes epävirallista todistetta: olet ' sanonut " Mielestäni vastaus on kyllä, koska vastaus on kyllä. "
vastaus
Huomaa, että alkuperäinen kaavio $ G $ on liitettävä tai siinä ei ole lainkaan kattavia puita. (Vaikka sama argumentti, jota sovelletaan kuhunkin komponenttiin, osoittaisi, että missä tahansa kuvaajassa on ulottuva metsä, joka sisältää minkä tahansa valitun reunan.)
Anna $ G = (V, E) $ on kytketty kaavio, olkoon $ T $ on mikä tahansa kattava alipuu ja olkoon $ e $ mikä tahansa reunan $ E $. Väitämme, että on olemassa kattava puu, joka sisältää $ e $. Jos $ e \ sisällä T $, olemme valmiit. Muussa tapauksessa $ T + e $ sisältää jakson. Tämä sykli sisältää väistämättä vähintään yhden reunan $ e ”\ neq e $ (itse asiassa se sisältää vähintään kaksi). $ T + ee” $ on kattava puu, joka sisältää $ e $.
Sinun tulee todistaa itsellesi, että $ T + ee ”$ on todella kattava puu.
Vastaa
Reunan lisääminen puuhun aiheuttaa ainutlaatuisen syklin. Voit poistaa minkä tahansa reunan tästä syklistä (eri kuin lisäämäsi) saadaksesi puun takaisin. Tämä uusi puu sisältää lisätyn reunan.
Kommentit
- Se, että ' on juuri se, mitä sanoin!
- Kyllä, mutta Sanoin sen vähemmän sanoilla. 🙂
- Koska seitsemän lauseeni todella täytyy tiivistää kolmeen. Meillä on viisi tuhat vastaamatonta kysymystä sivustolla – olisi paljon parempi vastata joihinkin niistä kuin lähettää kaksoisvastauksia kysymyksiin, jotka eivät ' sitä tarvitse.
- Lue sitten olemassa oleva vastaus s ennen oman julkaisemista.
- Mitään ei oikeastaan vaadita – miten voimme sen kuitenkin panna täytäntöön? Mutta yleensä odotetaan, että vastausten pitäisi antaa jotain uutta, ja kuinka voit tietää, että ' teet sen uudelleen, jos et tiedä ' et tiedä mitä ' jo sanottiin? Jos sinulla on useita vastauksia, jotka kaikki sanovat saman, vain sekoitetaan sivua, vaikka ' ei tietenkään ole iso juttu vain kahdella. Lyhyen, yhteenvetotyyppisen vastauksen lähettäminen voi olla varmasti arvokasta, kun nykyiset vastaukset ovat pitkiä; En vain ' usko, että se lisää mitään tässä tapauksessa.