Matfyz Wiki

15.1.2019 Martin🐻Mareš

nogare at 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
    ∑nk=0K(k,n)⋅3k\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

KubP at 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:
    ∑k=0nk×(nk)\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⋅2n−1n\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.