# 15.1.2019 Martin🐻Mareš

<{ForumPost(poster="nogare", timestamp=2019-01-15 18:27:33)}>
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
<{/ForumPost}>

<{ForumPost(poster="KubP", timestamp=2019-01-18 18:59:34)}>
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.
<{/ForumPost}>