příklad z diskrétní matematiky
příklad z diskrétní matematiky
Ukažte, že každý strom má nejvýše jedno úplné párování.
nevíte někdo jak to dokázat?
nevíte někdo jak to dokázat?
- beaver
- Matfyz(ák|ačka) level III
- Příspěvky: 189
- Registrován: 2. 2. 2007 09:33
- Typ studia: Nestuduji ale učím na MFF
- Bydliště: Praha
Ja bych to resil indukci (predpokladam souvisly strom - jinak bychom to resili po komponentach):
Jeden vrchol - nema parovani (=> ma nejvyse jedno parovani).
Dva vrcholy - urcite maji jen jedno uplne parovani
I.P. strom o N-1 vrcholech ma nejvyse 1 uplne parovani. Dostanu strom o N vrcholech. Takovy strom ma urcite alespon 1 list. Vezmu tento list. Pokud vubec existuje uplne parovani, pak musi byt tento list sparovan s rodicem. Tak je sparuju a oba utrhnu z grafu. Tim se mi strom rozpadl na les (nekolik komponent, kde kazda je strom), kde jsou vsechny stromy mensi, nez N-2. A z I.P. vim, ze vsechny tyhle stromy maji nejvyse jedno uplne parovani => cely les ma nejvyse jedno uplne parovani.
Spolubydlici navrhl dokazovat to sporem. Vezmete si strom, ktery ma dve ruzna parovani, obe parovani si slozte na sebe (do jednoho grafu) a pak by se vam melo podarit dokazat, ze ten slozeny graf obsahuje kruznici => neni strom => spor.
Vyse uvedene dukazy berte bez zaruky. Mohli jsme se zmylit
Jeden vrchol - nema parovani (=> ma nejvyse jedno parovani).
Dva vrcholy - urcite maji jen jedno uplne parovani
I.P. strom o N-1 vrcholech ma nejvyse 1 uplne parovani. Dostanu strom o N vrcholech. Takovy strom ma urcite alespon 1 list. Vezmu tento list. Pokud vubec existuje uplne parovani, pak musi byt tento list sparovan s rodicem. Tak je sparuju a oba utrhnu z grafu. Tim se mi strom rozpadl na les (nekolik komponent, kde kazda je strom), kde jsou vsechny stromy mensi, nez N-2. A z I.P. vim, ze vsechny tyhle stromy maji nejvyse jedno uplne parovani => cely les ma nejvyse jedno uplne parovani.
Spolubydlici navrhl dokazovat to sporem. Vezmete si strom, ktery ma dve ruzna parovani, obe parovani si slozte na sebe (do jednoho grafu) a pak by se vam melo podarit dokazat, ze ten slozeny graf obsahuje kruznici => neni strom => spor.
Vyse uvedene dukazy berte bez zaruky. Mohli jsme se zmylit
Cožpak většina z nás svým způsobem nehledá svou kravičku?
T. Pratchett, z knihy "Kdepak je má kravička"
T. Pratchett, z knihy "Kdepak je má kravička"
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
strom <=> ex. max. 1 parovaniAnonymous píše:a nemohl bys mi to prosím napsat? hodně by mi to pomohlo
list ma stupen 1 ~> jeho dvojice je jednoznacne definovana
odstranim ji, cimz vznikne les (ne nutne nesouvisli strom)
a pokracuji takto dal, dokud nic nezbyde .. to je pokud existuje, tak jsem ho ukázal
pokud tohle nevyjde, znamena to nekolik moznosti, bud mi v nejake komponente na konci zbyl vrchol, nebo jsem tam mel vidlicku a paroval jsem jednoho rodice se dvema listy. Ale protoze vsechny pary co jsem vytvoril byly jednoznacne urceny (pokud parovani existuje, tak to musi byt takto), tak to znamena, ze to nejde vubec.
.. slo by to i s pismenkama, ale prijde mi to zbytecny..
PS: regni/prihlas se .. kdyz ty si nedas praci s tim, proc ja si mam dat praci odpovidat (kdyz ani nevim komu)
Re: příklad z diskrétní matematiky
zdarvim,
mohl bych vas poprosit o pomoc jak dokazat, ze strom s uplnym parovanim ma vzdy jen jednu lichou komponentu?
dalo by se rici, ze po vylouceni vrcholu (korene) stromu, ze ktereho se zkoumaji komponenty a vrcholu jedne liche komponenty mi zustane mnozina sudeho poctu vrcholu, ze ktere lze vytvorit tedy uz jen sudy pocet paru, ktere pripadaji na zbyle komponenty?
dal bych mozna mel nejak sikovne dokazat, ze ten koren, ze ktereho se ty komponenty posuzuji, je vzdy soucasti paru na te liche komponente...
mohl bych vas poprosit o pomoc jak dokazat, ze strom s uplnym parovanim ma vzdy jen jednu lichou komponentu?
dalo by se rici, ze po vylouceni vrcholu (korene) stromu, ze ktereho se zkoumaji komponenty a vrcholu jedne liche komponenty mi zustane mnozina sudeho poctu vrcholu, ze ktere lze vytvorit tedy uz jen sudy pocet paru, ktere pripadaji na zbyle komponenty?
dal bych mozna mel nejak sikovne dokazat, ze ten koren, ze ktereho se ty komponenty posuzuji, je vzdy soucasti paru na te liche komponente...