Zkouška Kantor 29. 1. 2025

  1. [10 bodů] Dokažte následující vztah (výpočtem nebo kombinatorickou úvahou nebo nějak jinak), pro n \geq 1: \sum_{k=0}^{n}k \cdot \binom{n}{k} = n \cdot 2^{n-1}

  2. (a) [2 body] Doplňte definici symetrické relace:
    Řekneme, že relace R na množině X je symetrická, pokud…

    (b) [3 body] Nechť R je relace \{(1, 1), (2, 2), (2, 3), (3, 2)\} na množině X = \{1, 2, 3\}.
    Je R reflexivní relace? Je R symetrická relace? Odpovědi dostatečně zdůvodněte.

    (c) Nyní nechť Y = \{1, 2, 3, 4\}

    • i. [4 body] Kolik je všech ekvivalencí na množině Y? (Nápověda: Ekvivalence nám dělí nosnou množinu na třídy ekvivalence.)

    • ii. [2 body] Kolik je všech relací na množině Y?

    • iii. [3 body] Kolik je reflexivních relací na množině Y? (Nápověda: Jak vypadá matice, která odpovídá reflexivní relaci?)

  3. [10 bodů] Dokažte dolní a horní mez tohoto odhadu: n^{n/2} \leq n! \leq \left( \frac{n+1}{2} \right)^n

  4. (a) [4 body] Formulujte Kuratowského větu.* Stačí formulace, větu nedokazujte.

    (b) [4 body] Je graf na obrázku rovinný? Buďto ho nakreslete rovinně, nebo nějakým přesvědčivým (!) způsobem argumentujte, proč rovinné nakreslení neexistuje.

    (c) [4 body] Průměrný stupeň grafu G je průměr jeho stupňů, neboli číslo \frac{1}{n} \left( \sum_{v \in V(G)}\text{deg}(v) \right) (kde $n je počet vrcholů grafu G$). Je pravdivé následující tvrzení? Buďto ho dokažte (třeba s použitím nějaké věty z přednášky), nebo najděte nějaký konkrétní protipříklad.

    Tvrzení: *Kdykoliv G je graf, který má průměrný stupeň nejvýše 2,3, pak je G rovinný.

  5. (a) [4 body] Doplňte definice grafu a souvislého grafu:

    • Graf je…

    • Řekneme, že graf G je souvislý, pokud…

    (b) Pokud t je přirozené číslo a t \geq 2, tak definujeme graf G_t takto: vrcholy jsou všechny dvouprvkové množiny čísel z množiny \{1, \ldots, t\} (neboli V(G_t) = \binom{\{1, \ldots, t\}}{2}) a dvě takové množiny tvoří hranu právě tehdy, když jsou disjunktní. Zde je například obrázek G_5:

    (Mimochodem, tyto grafy jsou celkem důležité a mají název: Kneserovy grafy.)
    [4 body] Pro každé t \geq 2 rozhodněte, zda je G_t souvislý graf. Odpověď dostatečně zdůvodněte.

    (c) [3 body] Graf G_t definovaný výše má všechny vrcholy stejného stupně. Jakého? (Bude to pochopitelně nějaké číslo, které závisí na t.) Odpověď dostatečně zdůvodněte.

    (d) [3 body] Nyní předpokládejme, že t = 4k+3 pro nějaké přirozené číslo k. Je graf G_t (definovaný výše) eulerovský? Odpověď dostatečně zdůvodněte.