Hallova věta

Také můžete předpokládat, že platí aktuálně zadaný domácí úkol:

Do mateřské školky přišel Mikuláš s velkým pytlem hraček. Každé dítě ukázalo na deset hraček, které se mu líbí. Ukázalo se, že každá hračka se líbí nejvýše pěti dětem. Ukažte, že je možné každému dítěti dát jako dárek dvě hračky, které se mu líbí.

1. Nechť $G = (V, E)$ je graf. Předpokládejme, že pro každý podgraf $H$ grafu $G$ platí $|E(H)| \le |V(H)|$ Ukažte, že je možné hrany $G$ nahradit orientovanými hranami tak, že do každého vrcholu bude vstupovat nejvýš jedna hrana.
2. Nechť $G = (V, E)$ je graf. Předpokládejme, že pro každý podgraf $H$ grafu $G$ platí $|E(H)| \le 10|V(H)|$. Ukažte, že je možné hrany $G$ nahradit orientovanými hranami tak, že do každého vrcholu bude vstupovat nejvýš deset hran.
3. Mějme dvě přirozená čísla $k \leq n$. Pojmem latinský obdélník tvaru $k \times n$ označujeme matici s $k$ řádky a $n$ sloupci vyplněnou čísly $1,\dots, n$ tak, že v každém řádku se každé číslo vyskytuje právě jednou a v každém sloupci se každé číslo vyskytuje nejvýš jednou. Dokažte, že pokud $k < n$, tak ke každému latinskému obdélníku tvaru $k \times n$ lze přidat $n - k$ řádků tak, aby vznikl latinský obdélník tvaru $n \times n$, neboli latinský čtverec.

Hranová souvislost grafů

1. Čemu je rovno $k_e(K_n)$ – tj. úplný graf? Čemu je rovno $k_e(K_{m,n})$ – tj. úplný bipartitní graf?
2. Nechť $G$ je graf, jehož každý vrchol má stupeň právě $d$. Co lze říci o hodnotě $k_e(G)$?
3. Nechť $G = (V, E)$ je graf, jehož hranová souvislost je rovna $k$. Předpokládejme, že vytvoříme nový graf $G^+$ tak, že ke grafu $G$ přidáme nový vrchol z a spojíme ho hranami s nějakými $k$ různými vrcholy $y_1 , \dots , y_k$ grafu $G$. Co lze říci o hranové souvislosti grafu $G^+$?
4. Nechť $G$ je hranově $k$-souvislý graf. Zvolme v něm $k + 1$ různých vrcholů $u, v_1 , v_2 , \dots , v_k$. Dokažte, že $G$ obsahuje $k$ hranově disjunktních cest $P_1 , \dots , P_k$ , kde cesta $P_i$ spojuje vrchol $u$ s vrcholem $v_i$.

Vrcholová souvislost grafů

1. Existuje graf $G$, pro nějž je $k_v(G) < k_e(G)$?
2. A co $k_v(G) > k_e(G)$?
3. Může být rozdíl $|k_v (G) - k_e (G)|$ libovolně velký?
4. Nechť $G$ je graf, jehož každý vrchol má stupeň nejvýš 3. Plyne z toho, že $k_e (G) = k_v(G)$?
5. Nechť $G$ je vrcholově $k$-souvislý graf. Zvolme v něm $k + 1$ různých vrcholů $u, v_1 , v_2 , \dots , v_k$. Rozhodněte, jestli $G$ musí obsahovat $k$ vrcholově disjunktních cest $P_1, \dots , P_k$ , kde cesta $P_i$ spojuje vrchol $u$ s vrcholem $v_i$.