Zkouška Tancer 10. 1. 2025

  1. Uvědtě definici kk-degenerovaného grafu. Uvědtě příklad 33-degenerového grafu, který není 22-degenerovaný. (5 bodů)

  2. Kolik existuje funkcí f:[n]→([n]2)f: [n] \to \binom{[n]}{2} takových, že ∀i∈[n]:i∉f(i)\forall i \in [n]: i \notin f(i) (6 bodů)

  3. Uvažujme ČUM P=(X,⊆)P = (X, \subseteq), kde XX je množina všech množin E⊆(V2)E \subseteq \binom{V}{2} rovinných grafu G=(V,E)G = (V,E), pro které V=[n]V = [n]. \newline Neboli X={E⊆([n]2)∣X = \{E \subseteq \binom {[n]} 2 | graf ([n], E) je rovinný}\}

    a) Najděte řetězec v PP s maximální velikostí a zdůvodnětě, že neexistuje řetězec s vetší delkou

    b) Pro n≥3n \geq 3 najděte antiřetězec s velikostí alespoň ((n2)2)\dbinom{\binom{n}{2}}{2}. (existují i delší, stačí se však omezit na ((n2)2)\dbinom{\binom{n}{2}}{2})

    Pokud se vám nedaří vyřešit jednu z možností, vyřešte pro n=5n=5. (9 bodů)

  4. Uvědtě definici a důkaz věty o sledů (se závislosti na matici sousednosti grafu GG) (10 bodů)

Za zkoušku bylo možné získat 30, bodů. Známkování bylo následující 1: 24-30b; 2: 20-23b; 3: 16-19b; 3−^-: 11-15b; 4: 0-10b. Po písemné zkoušce bylo možné si zlepšit známku 2 až 3−^- o stupeň lepší (1 až 3) na ústní zkoušce. V případě známky 3−^- byla zkouška povinná. Explicitně bylo řečeno, že není možné si na ústní zkoušce zhoršit známku.