15.1.2019 Martin🐻Mareš

Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).
nogare

15.1.2019 Martin🐻Mareš

Příspěvek od nogare »

1) 5 tvrzení o stromu a důkaz ekvivalence dvou z nich
2) Dlouhý a široký + důkaz
3) spočítat/zjednodušit
sum(k=0 to n)(K(k,n)*3^k)
hint: binomická věta
4) ukázat, že graf se všemi vrcholí sudého stupně, lze převést na orientovaný graf, kde každý vrchol má stejný počet vstupních a výstupních hran
KubP
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 18. 1. 2019 18:38
Typ studia: Informatika Bc.

Re: 15.1.2019 Martin🐻Mareš

Příspěvek od KubP »

Přidávám zadání z 14. 1.

1) Zformulujte a dokažte větu: linearita střední hodnoty
2) Zformulujte a dokažte větu: eulerova formule
3) Upravte/zjednodušte:
$$\sum_{k=0}^{n} k \times {n\choose k}$$
4) Najděte postup, jak ze souvislého grafu postupně odstranit všechny vrcholy v takovém pořadí, aby byl po každém odstranění stále souvislý.

Nástin řešení:
1) Jak bylo ukázáno na přednášce: vyjdeme z definice střední hodnoty, pak je to jen úprava vzorců.
2) Jak bylo ukázáno na přednášce: určíme v pevné, dokážeme indukcí podle e.
3) Všimneme si, že vzorec sčítá velikosti každé možné podmnožiny n-prvkové množiny (počet prvků k krát počet podmnožin o k prvcích). Každý z n prvků se nachází právě v polovině všech možných podmnožin, a celkem máme 2^n podmnožin, výsledný vzorec lze tedy zjednodušit na n*2^(n-1)
4) Najdeme kostru grafu a trháme z ní listy, tím pádem nikdy neporušíme souvislost v původním grafu.
Odpovědět

Zpět na „DMI002 Diskrétní matematika“