KG1 Jiří Kalvoda: Cvičení 10

Also available as: PDF Markdown

Informace k cvičení jsou na https://kam.mff.cuni.cz/~jirikalvoda/vyuka/24z/kg1.

Vrcholová souvislost grafů

Vrcholová souvislost, značená $k_v (G)$ , je největší $k$ takové, že graf $G$ je vrcholově $k$ -souvislý. Pro neúplný graf $G$ je $k_v(G)$ rovno velikosti nejmenšího vrcholového řezu a pro $K_n$ máme $k_v (K_n) = n - 1$ .

Mengerova věta: graf je vrcholově $k$ -souvislý, právě když mezi každými dvěma různými vrcholy existuje $k$ vnitřně vrcholově disjunktních cest.

Existuje graf $G$ , pro nějž je $k_v(G) < k_e(G)$ ?
A co $k_v(G) > k_e(G)$ ?
Může být rozdíl $|k_v (G) - k_e (G)|$ libovolně velký?
Nechť $G$ je graf, jehož každý vrchol má stupeň nejvýš 3. Plyne z toho, že $k_e (G) = k_v(G)$ ?

Ušaté lemma

Připomeňme, že graf G je (vrcholově) 2-souvislý, právě když ho lze vyrobit z kružnice pomocí operací přidávání ucha.

Nechť $G$ je graf s aspoň třemi vrcholy. Dokažte, že $G$ je 2-souvislý, právě když pro každé tři různé vrcholy $x, y, z$ existuje v $G$ cesta z $x$ do $y$ obsahující $z$ .
Nechť $G$ je graf s aspoň třemi vrcholy. Dokažte, že $G$ je 2-souvislý, právě když pro každé tři různé vrcholy $x, y, z$ existuje v $G$ cesta z $x$ do $y$ neobsahující $z$ .
Dokažte, že v každém 2-souvislém grafu lze zorientovat hrany (tj. nahradit každou hranu orientovanou hranou) tak, že pro každé dva vrcholy $x, y$ bude existovat orientovaná cesta z $x$ do $y$ .