příklad z diskrétní matematiky

bono

příklad z diskrétní matematiky

Příspěvek od bono »

Ukažte, že každý strom má nejvýše jedno úplné párování.

nevíte někdo jak to dokázat?
Návštěvník

Příspěvek od Návštěvník »

nikdo neví jak na to?:(
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

rekl bych, ze dost intuitivne, .. kazdy list musi byt parovan se svym rodicem .. kdyz kazdou takovou dvojici odstranim, zbyde strom a s tim pracuju stejne, .. vznikne li kolize (dve vetve liche delky) -> neexistuje, ale formalne se mi to tu psat nechce
Návštěvník

Příspěvek od Návštěvník »

a nemohl bys mi to prosím napsat? hodně by mi to pomohlo
Uživatelský avatar
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

Příspěvek od beaver »

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 :oops:
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"
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Příspěvek od hippies »

Anonymous píše:a nemohl bys mi to prosím napsat? hodně by mi to pomohlo
strom <=> ex. max. 1 parovani
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)
bono

Příspěvek od bono »

mohli byste mi ještě jednouvysvětlit tu indukci prosím?
chr

Re: příklad z diskrétní matematiky

Příspěvek od chr »

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...
Odpovědět

Zpět na „2006“