Zkouška Tancer 10. 1. 2025

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

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

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

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

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

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

4. Uvědtě definici a důkaz věty o sledů (se závislosti na matici sousednosti grafu G) (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.