slama.dev

poznamky Icon Kombinatorika a Grafy II

poznámky · 1. 3. 2021 · 🇨🇿 · dostupné v PDF · [upravit]

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Kouteckého z akademického roku 2020/2021 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

1. přednáška

Největší párování

Definice: Párování v G=(V,E)G = \left(V, E\right) je M⊆EM \subseteq E t. ž. ∀v∈V∃≤1\forall v \in V \exists \le 1 hrana e∈M:v∈ee \in M: v \in e

Definice (volný vrchol) (vzhledem k MM) je vrchol, kterého se nedotýká žádná hrana párování.

Definice (střídavá cesta) (vzhledem k MM) je cesta, na které se střídají hrany v párování a hrany mimo párování: u0,…,uku_0, \ldots, u_k, kde každá sudá/lichá hrana je v MM, lichá/sudá není v MM

Tvrzení: Nechť G=(V,E)G = \left(V, E\right) je graf, MM párování v GG. Pak GG obsahuje VSC (vzhledem k MM), právě když MM není největší párování v GG.

Definice (květ): lichá „střídavá“ kružnice s vrcholem v1v_1, ke kterému přiléhají dvě hrany ∉M\not\in M Definice (stonek): střídavá cesta z v1v_1 (i nulové) délky končící volným vrcholem (dál od květu)

Definice (kytka): květ + stonek

Definice (kontrakce hrany): Nechť G=(V,E)G = \left(V, E\right) je neorientovaný graf a e={u,v}e = \left\{u, v\right\} jeho hrana. Zápis G.eG . e označuje graf vzniklý z GG kontrakcí („smrštěním“) hrany ee do jednoho vrcholu:

Tvrzení: Nechť CC je květ v grafu GG. Potom párování MM v GG je maximální, právě když M∖E(C)M \setminus E(C) je maximální párování v grafu G.CG . C, tj. s květem CC zkontrahovaným do jediného vrcholu. Navíc pokud znám VSC pro M.CM . C, tak v poly. čase najdu VSC pro MM v GG.

Důkaz: Tady je sketchy důkaz, tady je míň sketchy důkaz.

Algoritmus (Edmondsův „zahradní/blossom“): vstupem je graf GG a jeho libovolné párování MM, třeba prázdné. Výstupem je párování M′M', které je alespoň o 11 větší, než MM, případně MM pokud bylo maximální.

Tvrzení: Edmondsův algoritmus spuštěný na GG a MM doběhne v čase O(n⋅(n+m))\mathcal{O}(n \cdot (n + m)) a najde párování M′M' alespoň o 11 hranu větší než MM, případně oznámí, že MM je největší ⇒\Rightarrow nejlepší párování lze nalézt v čase O(n2(n+m))\mathcal{O}(n^2 (n + m)).

Důkaz: nejvýše nn-krát se vždy zrekurzíme s tím, že při každém rekurzení prohledáme celý graf (O(n+m)\mathcal{O}(n + m)). Tohle celé opakujeme nejvýše dokud nejsou všechny vrcholy zpárované, tedy nn-krát.

2. přednáška

Definice (perfektní párování): Párování MM je perfektní, pokud neexistuje v GG žádný volný vrchol.

Tutteova věta

Definice (Tutteova podmínka): ∀S⊆V:odd(G−S)≤∣S∣\forall S \subseteq V: \mathrm{odd}(G - S) \le |S|

Věta (Tutteova věta): GG má perfektní párování   ⟺  \iff platí Tutteova podmínka.

Důkaz: ⇒\Rightarrow obměna: neplatí TP ⇒\Rightarrow není PP. Nechť ∃S⊆V\exists S \subseteq V t. ž. odd(G−S)>∣S∣\mathrm{odd(G - S)} > |S|. V perfektním párování se alespoň 11 vrchol z každé liché komponenty musí spárovat s nějakým z SS, ale těch není dostatek.

⇐\Leftarrow nechť GG splňuje Tutteovu podmínku. ∣V∣|V| je sudá (nastavíme SS prázdnou). Dokážeme, že GG má PP indukcí podle počtu nehran.

Nechť S={v∈V ∣ deg⁡(v)=n−1}={v∣v je spojenyˊ se vsˇemi vrcholy}S = \left\{v \in V\ |\ \deg(v) = n - 1\right\} = \left\{v \mid \text{$v$ je spojený se všemi vrcholy} \right\}

Indukujeme dvakrát: G1=G+e1G_1 = G + e_1 a G2=G+e2G_2 = G + e_2 díky předchozímu pozorování splňují TP a spolu s IP ⇒∃\Rightarrow \exists PP M1,M2M_1, M_2 v G1,G2G_1, G_2

Těžší případ: e1∈M1,e2∈M2,H=(V,M1∪M2)e_1 \in M_1, e_2 \in M_2, H = (V, M_1 \cup M_2)

Věta (Petersen): každý 33-regulární 22-souvislý (vrcholově i hranově, pro 3-regulární grafy je to to samé; alternativně můžeme říct graf bez mostů a artikulací) graf má PP.

Důkaz: Nechť G=(V,E)G = (V, E) je 33-regulární a 22-souvislý. Chci ukázat, že GG splňuje TP. Předpokládejme danou S⊆VS \subseteq V.

  1. každá komponenta G−SG - S je v GG spojena aspoň dvěma hranami s SS
    • je 22-souvislý, nemáme mosty
  2. dokážeme, že každá lichá komponenta G−SG - S je s SS spojena lichým počtem hran:
    • nechť LL je lichá komponenta G−SG - S; pak: ∑x∈V(L)deg⁡G(x)=3−reg.3∣V(L)∣⏟licheˊ cˇıˊslo=2(# hran vedoucıˊch uvnitrˇ L)⏟sudeˊ cˇıˊslo+1(# hran vedoucıˊch uvnitrˇ L)⏟musıˊ byˊt licheˊ\sum_{x \in V(L)}\deg_G(x) \overset{3-\text{reg.}}{=} \underbrace{3|V(L)|}_{\text{liché číslo}} = \underbrace{2 (\text{\# hran vedoucích uvnitř $L$})}_{\text{sudé číslo}} + \underbrace{1 (\text{\# hran vedoucích uvnitř $L$})}_{\text{musí být liché}}

∣S∣≥odd(G−S)|S| \ge \mathrm{odd}(G - S), tedy TP platí a graf má perfektní párování.

3. přednáška

Tutte v2.0

Lemma (o kontrahovatelné hraně = LoKH): Nechť GG je vrcholově 33-souvislý různý od K4K_4. Potom GG obsahuje hranu t. ž. G∖eG \setminus e je 3-souvislý.

Důkaz: Sporem – nechť GG je 3-souvislý ale neexistuje žádná hrana, která jde zkontrahovat. Tedy ∀e∈E:G∖e\forall e \in E: G \setminus e není 33-souvislý.

Lemma (pomocné): ∀e={x,y}∃ze∈V∖{x,y}\forall e = \left\{x, y\right\} \exists z_e \in V \setminus \left\{x, y\right\} t. ž. {x,y,ze}\left\{x, y, z_e\right\} tvoří vrcholový řez v G, navíc každý z {x,y,ze}\left\{x, y, z_e\right\} má alespoň jednoho souseda v každé komponentě G∖{x,y,ze}G \setminus \left\{x, y, z_e\right\}.

Důkaz (způsob z přednášky): Vím, že G∖eG \setminus e není 33-souvislý, tedy má vrcholový řez velikosti 22. Nechť vev_e je vrchol vzniklý kontrakcí e={x,y}e = \left\{x, y\right\}. Řez velikosti 22 obsahuje vev_e, jinak by to byl řez už pro GG (obsahoval by vrcholy z původního grafu, které nekontrahujeme).

Označme řez ve,zev_e, z_e. Po rozkontrahování vidíme, že ∀{x,y,ze}\forall \left\{x, y, z_e\right\} musí mít souseda v každé komponentě (jinak spor s 3-souvislostí). Tedy zez_e je hledaný vrchol.

Důkaz (moje intuice): Pokud by neplatilo (existovala by taková hrana), tak máme hranu, přes kterou kontrahujeme. Jelikož pro tu hranu platí, že neexistuje zz, které spolu s jejími vrcholy tvoří řez, tak bude graf i po kontrakci 33-souvislý.

Pro důkaz původního lemmatu si zvolím e={x,y}∈Ee = \left\{x, y \right\} \in E a zez_e z pomocného tvrzení tak, aby nejmenší komponenta G−z,y,zeG - z, y, z_e byla co nejmenší (co do počtu vrcholů).

Protože zez_e má souseda ve všech komponentách, má nějakého souseda u∈C,f={ze,u}u \in C, f = \left\{z_e, u\right\} (kde CC je naše nejmenší komponenta). Pomocné tvrzení pro ff dá nějaký zf∈Vz_f \in V t. ž. {ze,zf,u}\left\{z_e, z_f, u\right\} je vrcholový řez GG. Chceme dokázat, že G−ze,zf,uG - z_e, z_f, u má menší komponentu než CC.

Nechť DD je komponenta G−ze,zf,uG - z_e, z_f, u neobsahující x,yx, y. Existuje, protože x,yx, y jsou spojené a graf se rozpadne alespoň na 22 komponenty. Tvrdím, že D⊆C∖{u}D \subseteq C \setminus \left\{u\right\}, protože DD nemůže obsahovat ze,zf,uz_e, z_f, u (vrcholy řezu), x,yx, y (z definice DD), ale uu má nějakého souseda v DD (podle pomocného tvrzení, uu má sousedy ve všech komponentách řezu), takže v DD ještě něco zbyde. Navíc ho tam mělo uu i předtím, takže opravdu D⊆C∖{u}D \subseteq C \setminus \left\{u\right\}. Tedy ∣D∣<∣C∣|D| < |C|, což je spor s minimalitou.

Věta (Tutteova charakterizace 3-souvislých grafů): Graf GG je 3-souvislý   ⟺  \iff existuje posloupnost K4≅G0,G1,…,Gn≅GK_4 \cong G_0, G_1, \ldots, G_n \cong G t. ž. ∀i∈[n],Gi−1\forall i \in [n], G_{i - 1} vznikne z GiG_i kontrakcí hrany, navíc GiG_i má všechny vrcholy stupně ≥3\ge 3.

Důkaz: ⇒\Rightarrow Induktivní aplikace lemmatu o kontrahovatelné hraně.

⇐\Leftarrow Mějme G0,…,GnG_0, \ldots, G_n dle předpokladu. Chceme, že Gn≅GG_n \cong G je 3-souvislý. Indukcí:

Obměnou nechť GiG_i má vrcholový řez velikosti 2, označme ho R={x,y}R = \left\{x,y\right\}. Pak každá komponenta Gi−RG_i - R má alespoň 2 vrcholy (osamocený vrchol zz mohl sousedit jen s řezem, ale ten je velikosti 2, což je spor se stupněm vrcholů ≥3\ge 3 pro vv).

Pak ale Gi−1G_{i - 1} nebyl 3-souvislý, rozborem toho, kde vznikla hrana:

Minory

Definice (minor): Nechť H,GH, G jsou grafy. Pak HH je minor GG (nebo že GG obsahuje HH jako minor), značíme H⪯GH \preceq G, pokud HH lze získat z GG posloupností mazání vrcholů, mazání hran nebo kontrakcí hran.

Věta (Kuratowského): GG rovinný   ⟺  \iff neobsahuje dělení K5K_5 ani K3,3K_{3, 3}

Věta (Kuratowski 1930, Warner 1937): Následující jsou ekvivalentní:

  1. GG je rovinný
  2. GG neobsahuje dělení K5K_5 ani K3,3K_{3, 3} jako podgraf
  3. GG neobsahuje K5K_5 ani K3,3K_{3, 3} jako minor.

Důkaz:

Pokračování v další přednášce…

4. přednáška

Označme CC kružnici ohraničující stěnu G′′\mathcal{G}'', v níž ležel (v G′\mathcal{G}' vrchol vev_e) – musí to být kružnice, protože v rovinném nakreslení každého 22-souvislého grafu je každá stěna kružnice.

3 případy: