slama.dev

Kombinatorika a Grafy II

1. 3. 2021; lecture notes

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Kouteckého z akademického roku 2020/2021. Pokud by byla někde chyba/nejasnost, nebo byste rádi někam přidali obrázek/text, 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 MEM \subseteq E t. ž. vV1\forall v \in V \exists \le 1 hrana eM:vee \in M: v \in e

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

Definice (střídavá cesta): (vzhledem k MM) – 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ž ME(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í MM', 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í MM' 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)).

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): SV:odd(GS)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ť SV\exists S \subseteq V t. ž. odd(GS)>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={vV  deg(v)=n1}={vv 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: e1M1,e2M2,H=(V,M1M2)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 SVS \subseteq V.

  1. každá komponenta GSG - 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 GSG - S je s SS spojena lichým počtem hran:
    • nechť LL je lichá komponenta GSG - S; pak: xV(L)degG(x)=3reg.3V(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é}}

Sodd(GS)|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. ž. GeG \setminus e je 3-souvislý.

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

Lemma (pomocné): e={x,y}zeV{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 GeG \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 Gz,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 uC,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ý zfVz_f \in V t. ž. {ze,zf,u}\left\{z_e, z_f, u\right\} je vrcholový řez GG. Chceme dokázat, že Gze,zf,uG - z_e, z_f, u má menší komponentu než CC.

Nechť DD je komponenta Gze,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 DC{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 DC{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 K4G0,G1,,GnGK_4 \cong G_0, G_1, \ldots, G_n \cong G t. ž. i[n],Gi1\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 GnGG_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 GiRG_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 Gi1G_{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 HGH \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.