15.1.2019 Martin🐻Mareš

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}_{n}K(k,n)\cdot 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

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\cdot 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.