5 tvrzení o stromu a důkaz ekvivalence dvou z nich
Dlouhý a široký + důkaz
spočítat/zjednodušit
hint: binomická větauká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
15.1.2019 Martin🐻Mareš
Přidávám zadání z 14. 1.
Zformulujte a dokažte větu: linearita střední hodnoty
Zformulujte a dokažte větu: eulerova formule
Upravte/zjednodušte:
k=0∑nk×(kn)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í:
Jak bylo ukázáno na přednášce: vyjdeme z definice střední hodnoty, pak je to jen úprava vzorců.
Jak bylo ukázáno na přednášce: určíme v pevné, dokážeme indukcí podle e.
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⋅2n−1
Najdeme kostru grafu a trháme z ní listy, tím pádem nikdy neporušíme souvislost v původním grafu.