Kombinatorika a grafy

Kombinatorika a grafy Michal Vaner 2. ledna 2013

Obsah 1 Latinsk´ eˇ ctverce a koneˇ cn´ e projektivn´ı roviny

3

2 Vytvoˇ ruj´ıc´ı funkce

4

3 Hamiltonovsk´ a kruˇ znice

4

4 Ramseovy vˇ ety

5

5 Souvislost

6

6 Info k kombakra II

6

7 P´ arov´ an´ı v grafech

7

7.1

Maxim´ aln´ı p´arov´an´ı . . . . . . . . . . . . . . . . . . . . . . . 7.1.1

Algoritmy perfektn´ıho p´arov´an´ı . . . . . . . . . . . . .

8 Grafy na ploch´ ach

9 10 12

8.1

Plochy jako fundament´aln´ı mnoho´ uheln´ık . . . . . . . . . . .

13

8.2

Rovinnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

8.2.1

13

Tˇr´ısouvisl´e grafy . . . . . . . . . . . . . . . . . . . . .

9 Barevnost 9.1

16

Hranov´a barevnost . . . . . . . . . . . . . . . . . . . . . . . .

16

9.1.1

17

Klasifikace graf˚ u . . . . . . . . . . . . . . . . . . . . .

10 Polynomy v grafech

18 1

11 Burnsidova vˇ eta

21

12 Samoopravn´ e k´ ody

23

12.1 Hammingovy k´ody . . . . . . . . . . . . . . . . . . . . . . . .

23

12.2 Line´ arn´ı k´ody . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

13 Extrem´ aln´ı kombinatorika

25

14 Minory

26

15 Semeredi regularity lemma

32

16 Vyb´ıravost

36

17 Π2 -´ uplnost

38

18 Ramseioviny

42

18.1 Aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

42

  Graf je uspoˇr´ adan´ a dvojice (V, E), V nepr´ azd´a, koneˇcn´ a, E ⊆ V2 . Rovinn´ y graf je graf pro kter´ y existuje rovinn´e nakreslen´ı. Element´ arn´ı kruˇ znice vzhledem ke kostˇre (V, K) je kruˇznice v grafu (V, K ∪ {e}), kde e ∈ E − K. C(G) je vektorov´ y prostor kruˇznic nad GF (2) dimenze |E| − |V | + k, k je poˇcet komponent. Element´arn´ı kruˇznice k libovoln´e kostˇre tvoˇr´ı b´azi C(G).

D˚ ukaz: Element´arn´ı kruˇznice jsou line´ arnˇe nez´ avisl´e. Generuj´ı cel´ y prostor C(G). Laplacova matice grafu G je matice LG . Na diagon´ ale jsou stupnˇe vrchol˚ u, jin´e jsou bud’ 0, pokud tam nevede hrana a −1, pokud hrana vede. Vˇ eta: Pokud vezmu laplacovu matici, ˇskrtnu libovoln´ y ˇr´adek a odpov´ıdaj´ıc´ı sloupec a vezmu determinant, tak dostanu poˇcet koster grafu G. Matice incidence IG je matice, ˇr´adky indexovan´e vrcholy, sloupeˇcky hranami a 1 je tam, kdyˇz vrchol patˇr´ı do odpov´ıdaj´ıc´ı hrany. T , tak dost´ Kdyˇz vyn´ asob´ım IG × IG av´am matici sousednosti + matice maj´ıc´ı na diagon´ ale stupnˇe.

Laplacova matice je DegG − A – tedy stupnˇe na diagon´ ale m´ınus matice sousednosti. Matice sousednosti orientovan´ eho grafu – vˇsechny hrany zorientuji a d´am jim tud´ıˇz znam´enko jedn´ım smˇerem. Kdyˇz tuto vyn´ asob´ım, tak dostanu laplacovu matici. Lemma: ~ je libovoln´a orientace grafu G, pak DG × DT = LG . Kdyˇz E G D˚ ukaz: Kdekoliv zaˇc´ın´ a nebo konˇc´ı nebo zaˇc´ın´ a hrana, tak se na diagon´alu pˇriˇcte 1. U ostatn´ıch mus´ı vych´azet −1, protoˇze jeden konec je kladn´ y a jeden z´aporn´ y. Kdyˇz tam nen´ı hrana, tak mi vyjde 0. ∗ × (D ∗ )T . (S vyˇ L∗G = DG skrtnut´ ymi ˇr´adky). G

Determinant souˇcinu dvou neˇctvercov´ ych matic se dˇel´ a tak, ˇze se vezmou vˇsechny nejvˇetˇs´ı“ podmatice a pˇr´ısluˇsn´ ym zp˚ usobem se vydeterminant´ı, to ” vˇsechno se nakonec seˇcte. Kdyˇz si to rozmysl´ıme, jak je to s t´ım sˇc´ıt´ an´ım, vyˇskrtnut´ ym ˇr´adkem a v´ ybˇerem sloupeˇck˚ u, vˇzdy bereme n−1 hran. Determinantek je bud’ 0 (pokud to nen´ı kostra) a nebo ±1, ale protoˇze se n´asob´ı s´ am sebou, vˇzdy se pˇriˇcte jedniˇcka. Pokud nen´ı kostra, pak nen´ı souvisl´ y a je tam nulov´ y sloupek. Opaˇcnˇe

3

dok´aˇzu indukc´ı trh´an´ım vrchol˚ u – dok´aˇzu, ˇze m˚ uˇzu pˇreuspoˇr´adat na jedniˇcky na diagon´ ale a sam´e nuly nad diagon´ alou. Multigraf je trojice G = (V, E, ϕ), kde ϕ : E → V 2 .

Kontrakce hrany je slouˇcen´ı dvou vrchol˚ u dohromady na konc´ıch jedn´e hrany. Znaˇc´ı se teˇckou (v pˇr´ıpadˇe jednograf˚ u) nebo dvojteˇckou (u multigraf˚ u). Vˇ eta: Poˇcet koster grafu G je 1, pokud V = 1, pokud je nesouvisl´ y, tak nem´a ˇz´adnou kostru, smyˇcky neovlivˇ nuj´ı poˇcet koster a kdyˇz t je hrana, pak je poˇcet koster v G roven poˇctu koster v G bez t a poˇcet koster v G s t skontrahovan´ ym.

1

Latinsk´ eˇ ctverce a koneˇ cn´ e projektivn´ı roviny

Latinsk´ y ˇ ctverec je ˇctvercov´a matice je L ∈ An×n , |A| = n, v kaˇzd´em ˇr´adku a kaˇzd´em sloupci se nach´az´ı permutace prvk˚ u z A. Latinsk´e ˇctverce L a L′ jsou ortogon´ aln´ı (L ⊥ L′ ), pokud ∀a, b ∈ A∃i, j; Li,j = ′ a ∧ L i, j = b. Jako d˚ usledek plyne, ˇze je tam kaˇzd´ a dvojice pr´avˇe jednou. Vˇ eta: Necht’ L1 , L2 , . . . , Lt jsou navz´ ajem ortogon´aln´ı latinsk´e ˇctverce velikosti n, pak t ≤ n − 1. D˚ ukaz: Pˇredpokl´ adejme, ˇze A = {1, 2, . . . , n} Lemma: L, L′ ∈ An×n , π : A → A permutace. Pak π(L) je ˇctverec po pˇrejmenov´an´ı symbol˚ u. Potom L ⊥ L′ ⇔ π(L) ⊥ L′ . D˚ ukaz: Prvn´ı a druh´ y ˇctverec nemus´ı m´ıt stejnou abecedu, tedy pˇrejmenov´an´ı abecedy nehraje ˇz´adnou roli. M˚ uˇzu pˇrerovnat prvn´ı ˇr´ adky tak, aby byly stejn´e. Tedy, v prvn´ım sloupeˇcku uˇz nem˚ uˇze b´ yt dalˇs´ı jedniˇcka. A mus´ı se liˇsit v tˇechto m´ıstech, protoˇze stejn´e uˇz jsou v minul´em ˇr´ adku. Koneˇ cn´ a projektivn´ı rovina je mnoˇzinov´ y syst´em (B, P), P ⊆ P(B). Prvky mnoˇziny B se naz´ yvaj´ı body a B je koneˇcn´e. Prvky P se naz´ yvaj´ı pˇr´ımky. Mus´ı splˇ novat n´asleduj´ıc´ı podm´ınky: • Kaˇzd´e dva body jsou obsaˇzeny v nˇekter´e pˇr´ımce. 4

• ∀P 6= Q ∈ P : |P ∩ Q| = 1. • Existuj´ı takov´e 4 body takov´e, ˇze ˇz´adn´e 3 z nich neleˇz´ı na jedn´e pˇr´ımce. Lemma: ∀ koneˇcnou projektivn´ı rovinu (B, P) existuje nˇejak´e ˇc´ıslo n; ∀P ∈ P; |P | = n + 1, ∀x ∈ B; |{P |x ∈ P }| = n + 1; |B| = |P| = n2 + n + 1. D˚ ukaz: Kaˇzd´e dvˇe pˇr´ımky maj´ı stejn´ y poˇcet bod˚ u. Mˇejme dvˇe pˇr´ımky, ty se prot´ınaj´ı v nˇejak´em bodˇe, existuje nˇejak´ y dalˇs´ı bod, kter´ y nen´ı ani v jedn´e. Z nˇej vedeme pˇr´ımku bodem jedn´e pˇr´ımky a dostaneme jin´ y bod na druh´e pˇr´ımce, kter´ y tomu odpov´ıd´ a. Nyn´ı si vezmu jednu z´akladn´ı“ pˇr´ımku a z n´ı dva body, z kaˇzd´e pust´ım n ” pˇr´ımek, mus´ı se poprot´ınat na dalˇs´ıch n2 bod˚ u, dok´aˇze se, ˇze to je vˇsechno. Toto n naz´ yv´ am ˇ ra ´d. Vˇ eta: ∃ koneˇcn´ a projektivn´ı rovina ˇr´adu n, pokud ∃n − 1 navz´ ajem ortogon´aln´ıch latinsk´ ych ˇctverc˚ u. Pˇredstav´ım si ˇsachovnici“ z minul´eho d˚ ukazu, kaˇzd´ y ˇctverec popisuje jeden ” takov´ y svazek ze zbyl´eho vrcholu. T´ımto udˇel´ am vz´ ajemn´e mapov´an´ı.

2

Vytvoˇ ruj´ıc´ı funkce

Mocninn´ aˇ rada je a0 +a1 ·x+a2 ·x2 . . ., kde a0 , a1 , . . . ∈ R jsou koeficienty. Vˇ eta: Necht’ (a0 , a1 , . . .) je posloupnost re´aln´ ych ˇc´ısel.P Necht’ ∃K ∈ R+ ; |an | ≤ K n .
i Potom pro kaˇzd´e x ∈ − K1 , K1 ˇrada a(x) = ∞ i=0 ai x konverguje a a(x) m˚ uˇzeme povaˇzovat za funkci promˇenn´e x. Tato funkce se naz´ yv´ a vytvoˇ ruj´ıc´ı funkce. Potom n-t´ y koeficient t´eto ˇrady je an =

3

a(n) (0) n! .

Hamiltonovsk´ a kruˇ znice

Sled, kter´ y navˇst´ıv´ı kaˇzd´ y vrchol pr´avˇe jednou, kromˇe jednoho, kde zaˇcne a skonˇc´ı, se naz´ yv´ a hamiltonovsk´ a kruˇ znice. Graf, kter´ y obsahuje hamiltonovskou kruˇznici se naz´ yv´ a hamiltonovsk´ y. Nalezen´ı (ˇci jen ovˇeˇren´ı, ˇze existuje) hamiltonovsk´e kruˇznice je N P u ´pln´ y probl´em. 5

Vˇ eta: Jestliˇze pro kaˇzd´ y jeho vrchol plat´ı, ˇze jeho stupeˇ n ≥ n2 , pak obsahu hamiltonovskou kruˇznici. Vˇ eta: Pokud pro kaˇzd´e dva vrcholy plat´ı, ˇze souˇcet jejich stupˇ n˚ u je ≥ n, pak m´ a hamiltonovskou kruˇznici. Vˇ eta: Pokud pro kaˇzd´e dva vrcholy, kter´e nejsou spojeny hranou plat´ı, ˇze souˇcet jejich stupˇ n˚ u je alespoˇ n n, pak m´ a hamiltonovskou kruˇznici. D˚ ukaz: Pro graf G zkonstruujeme chv´atal˚ uv uz´ avˇer [G] takto: Jestli existuj´ı dva vrcholy, jejichˇz souˇcet stupˇ n˚ u je vˇetˇs´ı roven neˇz n a nejsou spojeny hranou. Pak takovou hranu pˇrid´ am. Iteruji, dokud to jde. Toto nez´ avis´ı na poˇrad´ı pˇrid´ av´an´ı. Graf G je hamiltonovsk´ y ⇔ [G] je hamiltonovsk´ y. Pˇr´ım´a implikace je zˇrejm´a. Necht’ G + {u, v} m´ a hamiltonovskou kruˇznici. Bud’ {u, v} do kruˇznice nepatˇr´ı, pak nen´ı co ˇreˇsit. Tedy tam patˇr´ı.

Protoˇze souˇcet jejich stupˇ n˚ u je alespoˇ n n, pak mus´ı existovat dva sousedn´ı vrcholy, z nichˇz jeden je dosaˇziteln´ y z u a druh´ y z v. Tedy pˇrepoj´ıme – zaˇcneme v u, dojdeme po p˚ uvodn´ı kruˇznici do druh´eho vrcholu, z nˇej do v, do prvn´ıho vrcholu a do u. Uz´avˇer tohoto grafu je u ´pln´ y graf. Takov´ y zjevnˇe m´ a hamiltonovskou kruˇznici. ´ Uloha obchodn´ıho cestuj´ıc´ıho: to je nejkratˇs´ı hamiltonovsk´ a kruˇznice.

4

Ramseovy vˇ ety

∀k∃n takov´e, ˇze graf G na n vrcholech obsahuje bud’ Kk nebo nez´avislou mnoˇzinu vrchol˚ u na k vrcholech. Ekvivalentn´ı znˇen´ı m´ a jen k, l r˚ uzn´e velikosti. D˚ ukaz: Indukc´ı, rozkl´ad´ an´ı na o jedna menˇs´ı v kaˇzd´em ˇc´ısle. Erd¨ os-Szekezerova: ∀k∃n ˇze pro n bod˚ u v obecn´e rovinˇe, pak k z nich tvoˇr´ı konvexn´ı mnoho´ uheln´ık.

6

5

Souvislost

Hranov´ yˇ rez je mnoˇzina hran, kterou kdyˇz odebereme z grafu, tak se stane nesouvisl´ y. Obdobnˇe funguje vrcholov´ yˇ rez. Hranov´ a souvislost je minimum velikost´ı vˇsech hranov´ ych ˇrez˚ u. Vrcholov´ a souvislost je minimum velikost´ı vˇsech vrcholov´ ych ˇrez˚ u, pˇr´ıpadnˇe |V | − 1 pro u ´pln´e grafy. Pozorov´ an´ı: Odebr´ an´ı hrany bud’ nech´a hranovou souvislost stejnou nebo sn´ıˇz´ı o 1. Tvrzen´ı: Odebr´ ani hrany m˚ uˇze jen sn´ıˇzit vrcholovou souvislost. Tvrzen´ı: Graf je (vrcholovˇe) dvousouvisl´ y, pokud ho lze z´ıskat postupn´ ym pˇrid´ av´an´ım uˇs´ı na kruˇznici. D˚ ukaz: Zprava doleva jasn´e. Zleva doprava, vˇse mus´ı b´ yt na nˇejak´e kruˇznici a tu lze odebrat aˇz k nejbliˇzˇs´ı spoleˇcn´e ˇc´asti. Ford-f¨ ulkersonova: Pro graf G a t ∈ N plat´ı, ˇze je hranovˇe t souvisl´ y, pr´avˇe kdyˇz pro kaˇzdou dvojici vrchol˚ u existuje t hranovˇe disjunktn´ıch cest, kter´e je spojuj´ı. D˚ ukaz: Zprava doleva: Sporem. Zleva doprava: Pomoc´ı tok˚ u. Mengerova: Pro graf G a t ∈ N plat´ı, ˇze je vrcholovˇe t souvisl´ y, pr´avˇe kdyˇz mezi kaˇzd´ ymi dvˇema r˚ uzn´ ymi vrcholy vede t vrcholovˇe disjunktn´ıch cest (s v´ yjimkou konc˚ u). D˚ ukaz: Podobnˇe, jako minul´ y.

6

Info k kombakra II

˜ http://atrey.karlin.mff.cuni.cz/kral/dm012.html Uˇc´ı Daniel Kr´al’.

7

7

P´ arov´ an´ı v grafech

Perfektn´ı p´ arov´ an´ı je mnoˇzina hran takov´a, ˇze z kaˇzd´eho vrcholu vede pr´avˇe jedna hrana t´eto mnoˇziny. P´ arov´ an´ı je mnoˇzina takov´a, ˇze z kaˇzd´eho vrcholu vede nejv´ yˇse jedna hrana. Tvrzen´ı 1 Pokud mohu naj´ıt mnoˇzinu S ⊆ V (G) takovou, ˇze kdyˇz ji odeberu, poˇcet komponent s lich´ym poˇctem vrchol˚ u (lich´e komponenty) je vˇetˇs´ı neˇz |S|, potom G nem´ a perfektn´ı p´ arov´ an´ı. D˚ ukaz: Ten zbyl´ y z kaˇzd´e lich´e komponenty mus´ı b´ yt sp´ arov´an s nˇeˇc´ım z S. Kdyˇz jich je v´ıce, nezbudou vrcholy. Vˇ eta 1 (Tutteova) Pokud takov´ a mnoˇzina S neexistuje, graf G splˇ nuje Tutteovu podm´ınku. Potom G m´ a perfektn´ı p´ arov´ an´ı. D˚ ukaz: Doplnˇeno ze skript Tom´ aˇse Vally D˚ ukaz bude sporem, tedy, G splˇ nuje Tutteovu podm´ınku, ale nem´a perfektn´ı p´arov´an´ı. Pˇrid´ av´an´ı hran nem˚ uˇze takov´e S vytvoˇrit, necht’ tedy G je ma´ xim´ aln´ı takov´ y graf (vytvoˇren´ y pˇrid´ av´an´ım hran). Upln´ y jiˇz m´ a perfektn´ı p´arov´an´ı nebo nesplˇ nuje podm´ınku. Necht’ U jsou vrcholy, jejichˇz stupeˇ n je roven n − 1 (jsou spojeny se vˇs´ım ostatn´ım). U z grafu odebereme. Rozebereme dva pˇr´ıpady. Prvn´ı je, pokud vˇsechny komponenty grafu G\U jsou u ´pln´e. V sud´ ych komponent´ach najdeme p´arov´an´ı jednoduˇse, lich´ ych je m´enˇe neˇz |V (U )| a zbyl´ y vrchol tedy m˚ uˇzeme vˇzdy spojit s libovoln´ ym z U . Celkov´ y poˇcet vrchol˚ u je sud´ y, tedy lze naj´ıt perfektn´ı p´arov´an´ı i ve zbytku U . Tedy graf m´ a perfektn´ı p´arov´an´ı – tato moˇznost nastat dle pˇredpokladu nem˚ uˇze. Necht’ tedy nastane druh´a moˇznost, ˇze nˇekter´a z komponent nen´ı u ´pln´ a. Vyberme si tu, kde je v´ıce neˇz 1 nenap´arovan´ y vrchol. Takov´a mus´ı existovat, kaˇzdou, kter´e nezbude ˇz´adn´ y neniˇc´ı p´arov´an´ı, takov´e, kter´e maj´ı jeden se spoj´ı s U a mus´ı b´ yt lich´e. Dle pˇredpokladu p´arov´an´ı neexistuje, tedy m´ ame nˇejakou takovou komponentu. Tato komponenta nen´ı u ´pln´ a, tedy mus´ı existovat dva vrcholy, a, b, kter´e nejsou spojen´e hranou. Mezi nimi vede alespoˇ n jedna cesta, vezmˇeme tedy 8

tu nejkratˇs´ı. Ta obsahuje tˇ reˇ sniˇ cku – K1,2 . (Mus´ı m´ıt alespoˇ n 2 hrany, tedy jsou tam vrcholy x, s, y, x a y nejsou spojen´e hranou, jinak by se cesta dala zkr´ atit). Neexistuj´ıc´ı hranu x, y nazveme e1 . s6∈U , proto nen´ı spojen´e s nˇejak´ ym t ∈ V (G) neexistuj´ıc´ı hranou e2 . Jak graf G ∪ e1 tak G ∪ o2 maj´ı perfektn´ı p´arov´an´ı, M1 , resp. M2 (jsou vˇetˇs´ı, tohle je nejvˇetˇs´ı, kde to nefunguje). t

s y

x

Obr´azek 1: Tˇreˇsniˇcka e1 ∈ M1 ∧ e2 ∈ M2 , jinak by uˇz G mˇelo perfektn´ı p´arov´an´ı. Nyn´ı vezmeme M := M1 ÷ M2 . V t´eto mnoˇzinˇe jsou vˇsechny komponenty bud’ samostatn´e vrcholy a nebo sud´e kruˇznice stˇr´ıdaj´ıc´ı hrany z M1 a M2 . Vezmˇeme kruˇznici obsahuj´ıc´ı e1 a nazvˇeme ji H. Pokud e2 6∈H, potom m˚ uˇzeme pouˇz´ıt na kruˇznici H p´arov´an´ı z M 2 a na zbytek z M1 . T´ım vzniklo perfektn´ı p´arov´an´ı. Pokud e2 ∈ H, potom je i t ∈ H. Vezmˇeme si oblouky, kter´e dostaneme po odebr´ an´ı e1 a e2 Na ten, kter´ y obsahuje s m˚ uˇzeme pouˇz´ıt p´arov´an´ı M2 , na ten s t M1 , t je nap´ arovan´e, jeden z x, y tak´e. Protoˇze ten druh´ y je spojen´ y s s, m˚ uˇzeme tuto hranu pˇridat do p´arov´an´ı. Na zbytek grafu lze pouˇz´ıt jak M1 , tak M2 . Sloˇzen´ım opˇet dostaneme perfektn´ı p´arov´an´ı. Deficit def (G) je maximum pˇres vˇsechny S ⊆ V z poˇcet lich´ ych komponent −|S|. def (G) ≥ 0. D˚ usledek 1 Maxim´ aln´ı p´ arov´ an´ı grafu G pokr´yv´ a n − def (G) vrchol˚ u. D˚ ukaz: Urˇcitˇe nepokryji alespoˇ n def (G) vrchol˚ u, v pˇr´ıpadˇe toho S, kter´e vytvoˇrilo ono maximum. Tedy potˇrebuji uk´azat, ˇze mi nezbude v´ yˇse neˇz tolik vrchol˚ u. Vytvoˇr´ım graf ′ G , pˇrid´ am def (G) nov´ ych vrchol˚ u a spoj´ım je se vˇsemi. G′ m´ a perfektn´ı p´arov´an´ı (deficit m´ a 0, tedy splˇ nuje Tutteovu podm´ınku). Pot´e staˇc´ı oˇr´ıznout zpˇet na G, ˇc´ımˇz ztrat´ım maxim´ alnˇe def (G) hran. 9

Kubick´ y graf je takov´ y, kter´ y m´ a kaˇzd´ y stupeˇ n 3. Vˇ eta 2 (Petersonova) Kaˇzd´y kubick´y graf bez most˚ u m´ a perfektn´ı p´ arov´ an´ı. D˚ ukaz: Dokazuji pro G souvisl´ y, kdyby nebyl, beru kaˇzdou komponentu zvl´aˇst’. M´ a sud´ y poˇcet vrchol˚ u (vˇsechny maj´ı lich´ y stupeˇ n, souˇcet stupˇ n˚ u je vˇzdy sud´ y). Necht’ je tedy S 6= ∅. Poˇcet hran vedouc´ıch z S je maxim´ alnˇe 3·|S| (deg (S)).

Pokud m´ am lichou komponentu, z n´ı urˇcitˇe vedou alespoˇ n 3 hrany. Kdyby 0, tak nen´ı lich´a. Kdyby 1, tak to byl most. Kdyby 2, tak stupeˇ n t´eto komponenty C je |C| · 3 − 2. Protoˇze |C| je lich´e, tak i toto by vyˇslo lich´e.

Vˇsechny tyto tˇri hrany mus´ı v´est do S. Tedy pro v´ıce neˇz |S| lich´ ych komponent nen´ı dostatek hran vedouc´ıch z S.

-

7.1

Maxim´ aln´ı p´ arov´ an´ı

Stˇ r´ıdav´ a cesta je cesta, kter´a zaˇc´ın´ a v nesp´arovan´em vrcholu, pot´e pˇrejde do sp´ arovan´eho vrcholu, pot´e stˇr´ıd´ am hrany z p´arov´an´ı a mimo nˇej a konˇc´ı stejnˇe, jako zaˇc´ın´ a, v nesp´arovan´em vrcholu. Pokud najdu takovou cestu, lze p´arov´an´ı zvˇetˇsit prohozen´ım p´arovac´ıch a nep´ arovac´ıch hran. Lemma 1 (Krit´ erium stˇ r´ıdav´ e cesty) P´ arov´ an´ı je maxim´ aln´ı pr´ avˇe kdyˇz neobsahuje stˇr´ıdavou cestu. D˚ ukaz: Kdyˇz obsahuje, pak je zˇrejm´e, ˇze nen´ı maxim´ aln´ı. Pˇredpokl´ adejme, ˇze M1 nen´ı maxim´ aln´ı. Tedy, ∃M2 , |M1 | < |M2 |. Vezmu symetrickou diferenci M1 ÷ M2 . Kdyˇz vezmu komponenty, tak to jsou bud’ samostatn´e vrcholy (vyml´atily se stejn´e hrany), nebo jsou kruˇznice, kter´e se stˇr´ıdaj´ı, pot´e maj´ı stejnˇe. Nebo to m˚ uˇze b´ yt cesta, kde se stˇr´ıdaj´ı hrany prvn´ıho a druh´eho p´arov´an´ı. Pokud jsou na obou stran´ ach hrany z M2 , pak je v M1 stˇr´ıdav´a cesta. Pokud maj´ı r˚ uzn´e konce, pak jich je stejnˇe, pokud je na obou hrana z M1 , pak je v´ıce hran v M1 .

10

Kde jsou M1 a M2 stejn´e, tam n´as to nezaj´ım´a, kde se liˇs´ı, tam jsou v t´eto diferenci. Protoˇze je M1 menˇs´ı, mus´ı nastat alespoˇ n jeden pˇr´ıpad stˇr´ıdav´e cesty. Svˇ edek neexistence je S, jej´ıˇz velikost je menˇs´ı neˇz poˇcet lich´ ych komponent. 7.1.1

Algoritmy perfektn´ıho p´ arov´ an´ı

Algoritmus 1 (Perfektn´ı p´ arov´ an´ı pro bipartitn´ı grafy): Pˇredpokl´ adejme, ˇze maj´ı stejnˇe velk´e partity. Zaˇcnu v nˇekter´em nepokryt´em vrcholu v partitˇe A. Pokud m´ a nepokryt´eho souseda, pak jsem naˇsel stˇr´ıdavou cestu d´elky 1. Pokud ne, pod´ıv´ am se na sousedy m´ ych soused˚ u v tomto p´arov´an´ı a zjist´ım, jestli maj´ı nepokryt´eho souseda. Pokud ano, m´ am stˇr´ıdavou cestu d´elky 3.

Obr´azek 2: Cesta d´elky 3 Pokud mi dojdou vrcholy, pak si vezmu vrcholy na lich´ ych hladin´ach (jsou v komponentˇe B, tedy nazvu je mnoˇzinou B ′ ) a ty na sud´ ych (A′ , vˇcetnˇe poˇc´ateˇcn´ıho vrcholu). |A′ | = |B ′ | + 1. M˚ uˇzu tedy prohl´asit B ′ za svˇedka ′ neexistence (A se nyn´ı skl´ ad´ a jen ze sam´ ych izolovan´ ych vrchol˚ u, kdyby ne, tak jsem jeˇstˇe pokraˇcoval). , Kruˇznice bude skorostˇ r´ıdav´ a, pokud je lich´a, m´ a jeden nepokryt´ y vrchol a jinak se stˇr´ıdaj´ı p´arovac´ı a nep´ arovac´ı hrany. Kvˇ etinka je skorostˇr´ıdav´a kurˇznice, kter´ a m´ a ale onen jeden vrchol pˇripojen´ y k stˇr´ıdav´e cestˇe, kter´a konˇc´ı nepokryt´ ym vrcholem. Z kvˇetinky lze prohozen´ım stonku“ udˇelat ” skorostˇr´ıdavou kruˇznici. Lemma 2 (O zkontrahovan´ e kruˇ znici) Necht’ C je skorostˇr´ıdav´ a kruˇznice. Potom graf G m´ a stˇr´ıdavou cestu pr´ avˇe kdyˇz G/C, kter´y vznikne kontrakc´ı C, m´ a stˇr´ıdavou cestu. 11

Obr´azek 3: Kvˇetinka

D˚ ukaz: Pˇri kontrakci byla kruˇznice C nahrazena vrcholem w. Pokud po kontrakci m´ ame stˇr´ıdavou cestu, pak je zaj´ımav´ y jen pˇr´ıpad, ˇze cesta obsahuje w. Na jedn´e stranˇe otoˇc´ım cestu jen ke kruˇznici (ta ˇc´ast, kter´a m´ a hranu obsahuj´ıc´ı w), druhou stranu m˚ uˇzu propojit aˇz k onomu nepokryt´emu vrcholu po kruˇznici a prohodit tam. Pokud ta prvn´ı ˇc´ast neexistuje, tak to nevad´ı. Algoritmus 2 (Perfektn´ı p´ arov´ an´ı pro obecn´ e grafy): Zaˇcnu v nepokryt´ ych vrcholech, postupuji stejnˇe, jako u bipartitn´ıch. Pokud nenajdu stˇr´ıdavou cestu, prohl´as´ım za S lich´e hladiny. Mohou nastat nˇekter´e probl´emy: • Hrana v sud´ e hladinˇ e – vznikne kvˇetinka nebo skoropokryt´ a kruˇznice. • P´ arovac´ı hrana na lich´ e hladinˇ e – tak´e kvˇetinka. Kvˇetinky pˇrevedu na skorostˇr´ıdav´e kruˇznice, zkontrahuji, zkus´ım v menˇs´ım. Krok˚ u, k nalezen´ı alespoˇ n jedn´e stˇr´ıdav´e cesty je maxim´ alnˇe O(n2 ), protoˇze pˇri kaˇzd´em hled´an´ı m˚ uˇzu muset kontrahovat. Celkem m˚ uˇzu naj´ıt aˇz n stˇr´ıdav´ ych 3 cest, tedy O(n ) – kaˇzd´ y pr˚ ubˇeh to zlepˇs´ı alespoˇ n o 1 hranu nebo skonˇc´ı. , Algoritmus 3 (Maxim´ aln´ı p´ arov´ an´ı): Stejn´ y algoritmus, jen na nultou hladinu mus´ım d´at vˇsechny nepokryt´e vrcholy. M˚ uˇze se mi st´at, ˇze by m´ısto kvˇetinky vznikla stˇr´ıdav´a cesta, coˇz mi nevad´ı. , 12

8

Grafy na ploch´ ach

Rovina je dvourozmˇern´ y prostor. Plochy vyˇsˇs´ıho rodu lze z´ıskat: • Vloˇzen´ım ucha – vyberu si v rovinˇe 2 kruhy, ty vyˇr´ıznu a propoj´ım v´alcem (ˇcerv´ı d´ıra). Takto z´ıskan´ a plocha se znaˇc´ı Sk pˇri vloˇzen´ı k uˇs´ı. Vˇsechny plochy z´ıskan´e vloˇzen´ım k uˇs´ı jsou homomorfn´ı (existuje spojit´e zobrazen´ı z jedn´e do druh´e a m´ a spojitou inverzi). S1 je torus, S2 je dvojit´ y torus. • Vloˇzen´ım pˇrekroucen´eho ucha – na jedn´e stranˇe d´am ten v´alec opaˇcnˇe (tedy ucho projde samo sebou, trochu jako v 4rozmˇern´em prostoru). Znaˇc´ı se N2k . • Vloˇzen´ım kˇr´ıˇz´ıtka – Vyberu si bod, kde se hrany mohou beztrestnˇe kˇr´ıˇzit, ale nesm´ı zat´aˇcet (ten bod tam prostˇe nen´ı). Znaˇc´ı se Nk . N1 je projektivn´ı rovina. Plocha, kter´ a vznikne vloˇzen´ım k1 uˇs´ı, k2 pˇrekˇr´ıˇzen´ ych uˇs´ı a k3 kˇr´ıˇz´ıtek se znaˇc´ı N2k1 +2k2 +k3 (pokud k2 + k3 > 0). Dobr´e nakreslen´ı grafu bude takov´e, ˇze kaˇzd´ a stˇena je homomorfn´ı disku. Euler˚ uv rod plochy g. g(Sk ) = 2k g(Nk ) = k Sk maj´ı vlastnost orientovatelnost“, ty Nk jsou neorientovateln´e. To ˇr´ık´ a, ” ˇze kdyˇz si vyberu smˇer hodinov´ ych ruˇciˇcek, odejdu a vr´at´ım se, tak bude stejn´ y. Neorientovateln´e to nemaj´ı. Vˇ eta 3 (Zobecnˇ en´ a Eulerova formule) Necht’ graf G je dobˇre nakreslen´y na ploˇse Eulerova rodu g. Pak n + f ≥ m + 2 − g (f je poˇcet stˇen). D˚ ukaz: Indukc´ı. Zaˇcneme s g = 0. Pro rovinu je to jiˇz dok´azan´e. Pokud to vzniklo uˇsen´ım, potom: kruˇznici m˚ uˇzu navl´eknout na ucho nebo pˇrekroucen´e ucho. V tom m´ıstˇe lze ucho rozdˇelit“ a vloˇzit tam kopii (na ” obˇe strany ˇrezu). T´ım to lze pˇrev´est na graf s jednou plochou nav´ıc ale o jedno ucho m´enˇe, lze pˇrepoˇc´ıtat poˇcty. U kˇr´ıˇz´ıtka lze vˇsechno vytahat za cenu toho, ˇze jednu vznikne stˇena s dvojn´asobnou d´elkou (vloˇz´ım kruˇznici okolo“ kˇr´ıˇz´ıtka a vnitˇrek, i s kˇr´ıˇz´ıtkem ” vynd´ am).

13

Vˇ eta 4 (Heawoodova vˇ eta) Heawoodovo ˇc´ıslo – max. barevnost grafu na rovinˇe dan´eho grafu je:   √ 7 + 1 + 24g H(g) = 2 Vezmeme graf G vnoˇren´ y na ploˇse rodu g. Potom takov´ y graf m´ a nejv´ yˇse takovou barevnost. Jednak, pˇrid´ an´ım hran, pokud chyb´ı, odhad nezhorˇs´ım – nadˇel´am rozdˇelen´ı plochy na troj´ uheln´ıky. Pot´e osek´am na Kn .

8.1

Plochy jako fundament´ aln´ı mnoho´ uheln´ık

Kdyˇz vezmu torus, pˇrestˇrihnu a rozp´aˇru, dostanu obd´eln´ık. Nˇeco podobn´eho lze udˇelat s kaˇzdou plochou. Kdyˇz m´ am plochu Sk , tak dostanu 4k-´ uheln´ık. Pro Nk je to 2k-´ uheln´ık. Lze naj´ıt v´ıce fundament´aln´ıch mnoho´ uheln´ık˚ u pro danou plochu.

8.2 8.2.1

Rovinnost Tˇ r´ısouvisl´ e grafy

Lemma 3 (O kontrahovateln´ e hranˇ e) Necht’ G je vrcholovˇe 3-souvisl´y graf takov´y, ˇze G 6= K4 , pak G obsahuje hranu e tak, ˇze G s kontrahovan´ym e je st´ ale vrcholovˇe 3-souvisl´y. D˚ ukaz: Pokud najdu takovou hranu, tak m´ am vybr´ ano. Pˇredpokl´ adejme tedy, ˇze tam nen´ı. Pak si jednu (x, y) n´ahodnˇe vyberu a zkontrahuju. Tedy je 2-souvisl´ y, tedy obsahuje 2-ˇrez. Nov´ y vrchol xy je v nˇem obsaˇzen (jinak by byl 2-ˇrez i v origin´ alu), tedy je tvoˇren {xy, z}. Tedy, pokud ˇz´adn´ a vhodn´a“ hrana neexistuje, pak pro kaˇzdou hranu (v, w) existuje vrcholu u ” tak, ˇze {u, v, w} je 3-ˇrez v p˚ uvodn´ım grafu.

Pokud G je vrcholovˇe 3-souvisl´ y a nˇejak´ a mnoˇzina {a, b, c} tvoˇr´ı vrcholov´ y 3-ˇrez, pak kaˇzd´ y z vrchol˚ u a, b, c m´ a alespoˇ n jednoho souseda v kaˇzd´e komponentˇe vznikl´e odebr´ an´ım tˇechto vrchol˚ u (jinak by zbyl´e vrcholy tvoˇrily vrcholov´ y ˇrez a tento by nebyl potˇreba). 14

Zvol´ım x, y, z tak, aby nejmenˇs´ı komponenta G\ {x, y, z} byla co nejmenˇs´ı. Vrchol z m´ a souseda v t´eto nejmenˇs´ı komponentˇe, ˇr´ıkejme mu v. Pro hranu zv existuje vrchol w takov´ y, ˇze {z, v, w} je vrcholov´ ym 3-ˇrezem.

Kde se m˚ uˇze nach´azet w:

• V nejmenˇs´ı komponentˇe: To se nem˚ uˇze st´at, spor s minimalitou nejmenˇs´ı komponenty. Kdyˇz bych totiˇz odebral {v, w, z}, tak mi vznikne podkomponenta C1 , kter´ a neobsahuje {x, y, v, w, z}. • V nˇejak´e jin´e (vˇetˇs´ı) komponentˇe. Kdyˇz odeberu v, z, pak je G st´ale jeˇstˇe souvisl´ y. Tedy C1 st´ale je v celku, mus´ı v´est cesta bud’ do x nebo do y. w je v jin´e komponentˇe neˇz C1 , v n´ı mus´ı m´ıt alespoˇ n jednoho souseda (aby po odebr´ an´ı {v, w, z} mohla vzniknout jeˇstˇe jin´ a komponenta). V t´eto komponentˇe ale mus´ı m´ıt souseda i v. Spor s t´ım, ˇze C1 je samostatn´a komponenta. C1

x v

y

C2

? w

z

Obr´azek 4: N´ ahled na dˇelen´ı

Podrozdˇ elen´ı grafu vznikne tak, ˇze nahrad´ım vˇsechny hrany cestami. Kuratovsk´ eho vˇ eta: Graf G je rovinn´ y pr´avˇe tehdy, kdyˇz neobsahuje podrozdˇelen´ı K5 ani K3,3 . D˚ ukaz: Ani K5 ani K3,3 nen´ı rovinn´ y graf, staˇc´ı pouˇz´ıt Eulerovu formuli. Ani jejich podrozdˇelen´ı nemohou b´ yt rovinn´a, proto ani G, kter´ y je obsahuje, nem˚ uˇze b´ yt rovinn´ y. Tedy, jeˇstˇe je tˇreba dok´azat, ˇze kdyˇz to neobsahuj´ı, tak mus´ı b´ yt rovinn´e. Indukc´ı dle poˇctu vrchol˚ u: • Nen´ı souvisl´ y: rozdˇel´ım. 15

• M´ a vrcholov´ y 1-ˇrez. Nakresl´ım nˇekam tento vrchol a zbytky pˇripoj´ım, kˇr´ıˇzit se zajist´e nemus´ı. U rovinn´eho grafu m˚ uˇzu prohl´asit libovolnou stˇenu jako vnˇejˇs´ı (lze prom´ıtnout na kouli, pootoˇcit a prom´ıtnout zpˇet). • M´ a vrcholov´ y 2-ˇrez. Tvoˇren vrcholy v a w. Pˇredpokl´ ad´ am, ˇze je to hrana. Kdyby ne, pˇrid´ am si tu hranu. Jedin´e, co mi m˚ uˇze nastat je, ˇze vznikne zak´ azan´ y graf. Nemohou b´ yt v r˚ uzn´ ych komponent´ach (Kaˇzd´ a ’ komponenta zvl´aˇst by mˇela 1-ˇrez). Tedy mus´ı b´ yt v jedn´e komponentˇe, ale kdyˇz bych hranu nepˇridal, pak ji mohu obej´ıt skrz jinou komponentu, tedy podrozdˇelen´ı bylo i v p˚ uvodn´ım grafu. Postup tedy obdobn´ y jako 1-ˇrezu, jen nˇekdy slepuji do vnitˇrn´ıho“ ” oka/stˇeny jin´e komponenty. • M´ a vrcholov´ y 3-ˇrez. Kdyˇz je to K4 , tak ten lze nakreslit do roviny. Pokud ne, m˚ uˇzu nˇekterou hranu zkontrahovat a aplikuji indukci (urˇcitˇe tam nˇekter´a hrana je, tedy je tam nˇekter´a, kterou sm´ım zkontrahovat). Kontrakce mi zak´ azan´ y minor nevyrob´ı. Graf bez zkontrahovan´eho vrcholu je 2-souvisl´ y, hranice kaˇzd´e stˇeny je kruˇznice (p˚ uvodnˇe byl max. 3-souvisl´ y, jinak mˇel K5 . Pak potˇrebuji dokreslit jeˇstˇe p˚ uvodn´ı (x, y). x si um´ıst´ım tam, kam patˇr´ı. Kdyˇz mi y vyjde do jedn´e nov´e stˇeny, tak je vˇsechno v poˇr´adku. Kdyˇz se mi to ale nestane, tak mohu naj´ıt nˇekter´ y zak´ azan´ y graf. • M´ a v´ıce-ˇrez. V takov´em pˇr´ıpadˇe obsahuje podrozdˇelen´ı K5 . Vˇ eta 5 (Tutteova o generov´ an´ı 3-souvisl´ ych graf˚ u) Kaˇzd´y vrcholovˇe 3souvisl´y graf lze z´ıskat z K4 nahrazov´ an´ım vrchol˚ u hranami pˇri zachov´ an´ı minim´ aln´ıho stupnˇe 3 a vˇsechny takto z´ıskan´e grafy jsou vrcholovˇe 3-souvisl´e. D˚ ukaz: To, ˇze lze kaˇzd´ y z´ıskat – p˚ ujdu opaˇcnˇe a postupnˇe kontrahuji hrany. Tedy to jde i t´ımto smˇerem. Kdybych mohl vyrobit nˇeco, co nen´ı vrcholovˇe 3-souvisl´e, pak obsahuje 2-ˇrez. Pokud ten 2-ˇrez neobsahuje ani jeden z vrchol˚ u, pak byl i v tom p˚ uvodn´ım. Kdyby obsahoval jen (v, w), pak by vw byl ˇrez p˚ uvodn´ıho grafu. Pokud tedy je v ˇrezu jeden vrchol a druh´ y ne, pak ten druh´ y mus´ı b´ yt ve sv´e komponentˇe s´ am (jinak by byl 2-ˇrez v p˚ uvodn´ım grafu) a v tom pˇr´ıpadˇe nem´a stupeˇ n alespoˇ n 3 (nem´a ve sv´e komponentˇe dostatek soused˚ u). 16

9

Barevnost

Maxim´ aln´ı barevnost je maxim´ aln´ı stupeˇ n ∆ + 1. Kaˇzd´ y vrchol m´ a max. tolik soused˚ u, jedna jeˇstˇe zbyde. Vˇ eta 6 (Brooksova) Pokud G je souvisl´y a nen´ı lich´ a kruˇznice ani kn , pak je jeho barevnost max. maxim´ aln´ı stupeˇ n. D˚ ukaz:

• G nen´ı ∆-regul´arn´ı. ∃ vrchol v stupnˇe < ∆. Vezmu kostru, zakoˇren´ım v nˇejak´em v, projdu v post-orderu a oˇc´ısluji, jak proch´az´ım. Podle tˇechto ˇc´ısel barv´ım. Pˇri barven´ı vrcholu r˚ uzn´ ych od v. Kaˇzd´ y m´ a neobarven´eho souseda – otce ve stromˇe. Proto m´ a jeˇstˇe nˇekterou barvu volnou. Nakonec obarv´ım v, protoˇze m´ a mal´ y stupeˇ n. • Je ∆-regul´arn´ı. Vezmu nˇekter´ y vrchol v a udˇel´ am to, co minule. M˚ uˇze se mi st´at, ˇze nem˚ uˇzu obarvit vrchol v. Vˇsichni soused´e v maj´ı r˚ uzn´e barvy (nazveme je v1 , . . . , vn ). Pokud nˇekter´ y nem˚ uˇzu pˇrebarvit, pak mezi nimi mus´ı existovat cesta, kde se stˇr´ıdaj´ı jejich barvy. Kaˇzd´ y vrchol na t´eto cestˇe mus´ı vidˇet vˇsech ∆ − 1 barev, jinak m˚ uˇzu pˇrebarvit.

Kdyˇz m´ am dvˇe takov´e cesty, tak se prot´ınaj´ı jen v {vi }, protoˇze kdyby se prot´ınaly ve v´ıce m´ıstech, tak je tam vrchol, kter´ y m´ a pˇr´ıliˇs mnoho stejnˇe barevn´ ych soused˚ u, tedy by nemohl vidˇet vˇsech ∆ − 1 barev.

Pokud jsou vˇsechny vrcholy vi sousedn´ı, pak m˚ uj graf byl u ´pln´ y, tedy pˇredpokl´ ad´ am, ˇze ne vˇsechny jsou sousedn´ı. Necht’ jsou to v1 a v2 . Na t´eto cestˇe prohod´ım barvy 1 a 3. Cesta c2,3 t´ım nebyla ovlivnˇen. T´ım jsem vytvoˇril dva vrcholy barvy 3 (v1 a v3 ), proto m˚ uˇzu rozˇs´ıˇrit na v. -

9.1

Hranov´ a barevnost

Hranov´ a barevnost grafu G je nejmenˇs´ı poˇcet barev χ′ (G) takov´ y, ˇze hrany G lze obarvit tak, aby ˇz´adn´e dvˇe sousedn´ı hrany (u stejn´eho vrcholu) nemˇely stejnou barvu. Vˇ eta 7 (Vizingova) Kdyˇz G je bez n´ asobn´ych hran, tak je ∆ (G) ≤ χ′ (G) ≤ ∆ (G) + 1. 17

D˚ ukaz: Uvaˇzme G nejmenˇs´ı protipˇr´ıklad. Vezmu si vrchol v. Ten m´ a sousedy v1 , v2 , . . .. Pod´ıv´ am se na graf G bez hrany (v, v1 ) a oznaˇc´ım ho za G− . Ten m´ a hranov´e obarven´ı pomoc´ı ∆(G) + 1 barev (G− je menˇs´ı, tedy na nˇem to plat´ı). Vezmu si barvu, kterou nem´a ˇz´adn´ a hrana u vrcholu v (deg(v) ≤ ∆(G) − 1) a oznaˇc´ım ji A. Kdyby se tato barva nevyskytovala ani u v1 , pak je vyhr´ ano. Necht’ se tam tedy A vyskytuje, ale nevyskytuje se tam barva C1 . Ta ovˇsem nechyb´ı u v. Tedy vede hrana do v2 a m´ a tuto barvu, tam se vyskytuje A a C1 , ale nevyskytuje se tam C2 . Obdobnˇe mus´ı v´est hrana do v3 a m´ıt barvu A, C1 , C2 , tam ale chyb´ı C3 a tak d´ale. Ale toto se mus´ı nˇekde zastavit (nem´am nekoneˇcnˇe mnoho barev). Tam tedy mus´ı chybˇet nˇejak´ a barva bud’ A (mohu pˇrebarvit tuto hranu) nebo nˇejak´e Ci pro pˇredchoz´ı i. Zaˇcnu posouvat, aby k vi vedla barva Ci , aˇz dojdu do vrcholu vi′ (ten uprostˇred, kde je stejn´ a chybˇej´ıc´ı barva jako u posledn´ıho). Kdyˇz se mi nˇekde stane, ˇze mi chyb´ı barva A, je vyhr´ ano. Necht’ tedy nechyb´ı A a m´ a ji nˇekter´a z jeho hran. Ta hrana vede do dalˇs´ıho vrcholu v nˇekde polovinˇe, kde nechyb´ı Ci = Cj . Kdyˇz se tref´ı sama do sebe, tak to nejde (Ci tu nen´ı, jinde by musela b´ yt dvakr´at). Nem˚ uˇze skonˇcit uprostˇred grafu (mohl bych to pˇrebarvit). Dojde tedy do vrcholu v. Kdyˇz posunu vˇsechno, kromˇe posledn´ıho vrcholu, m˚ uˇzu udˇelat to sam´e. A takov´a cesta nem˚ uˇze existovat v obou pˇr´ıpadech, protoˇze to mus´ı b´ yt stejn´ a cesta. Mus´ı tedy jednou skonˇcit v vi a z´aroveˇ n v vi′ +1 , to ale nem˚ uˇze nastat kv˚ uli barv´am. 9.1.1

Klasifikace graf˚ u

M´ ame vizigovu tˇr´ıdu 1 a 2, kde 1 jsou grafy, kde χ′ (G) = ∆(G), tˇr´ıda 2 jsou grafy, kde χ′ (G) = ∆(G) + 1. Napˇr. kubick´ y graf bez most˚ u, kter´ y je Vizigovy tˇr´ıdy 2 se naz´ yv´ a snark. Neexistence rovinn´eho snarku je ekvivalentn´ı s vˇetou o 4 barv´ach. Pozn´ amka 1 Pro kaˇzd´y graf G s m hranami plat´ı, ˇze: r 1 1 χ(G) ≤ + 2m + 2 4

18

D˚ ukaz: Necht’ G je graf barevnosti k s co nejm´enˇe hranami, kter´ y nesplˇ nuje tvrzen´ı. δ(G) ≥ k − 1 jinak uvaˇz vrchol stupnˇe ≤ k − 2 a χ(G\w) = k ⇒ G\w tak´e nesplˇ nuje tvrzen´ı a mˇel jsem vz´ıt G\w. m≥n·

k−1 k−1 ≥k· 2 2

Pak staˇc´ı dosadit do rovnice a zjistit, ˇze takov´ y graf m´ a alespoˇ n tolik hran, jako je pops´ ano na zaˇc´atku. -

10

Polynomy v grafech

Napˇr´ıklad, m´ am-li Kn a barv´ım mu vrcholy pomoc´ı k barev, tak na to m´ am Pkn (k) moˇznost´ı. Pn , potom poˇcet obarven´ı je k · (k − 1)n−1 , coˇz je opˇet polynom v k.

Stejnˇe tak m˚ uˇzu m´ıt strom na n vrcholech, barvit pomoc´ı odtrh´av´an´ı list˚ u. Tutteho polynom je polynom ve dvou promˇenn´ ych TG (x, y). Necht’ G je multigraf (povolen´e smyˇcky a n´asobn´e hrany). Potom je Tutteho polynom definov´an n´asledovnˇe: Vyberu si libovolnou hranu e grafu G. Pokud je hrana: • most • smyˇcka • ostatn´ı

TG (x, y) = x · TG−e (x, y) TG (x, y) = y · TG−e (x, y) TG (x, y) = TG−e (x, y) + TG|e (x, y)

(Souˇcet grafu bez hrany a s kontrahovanou hranou) Pokud graf nem´a hrany, je jeho Tutteho polynom roven 1. Vˇ eta 8 Necht’ G je graf. Pak Tutteho polynom grafu G je roven n´ asleduj´ıc´ımu v´yrazu:

19

TG (x, y) =

X

F ⊆E

(x − 1)k(F )−k(E) · (y − 1)|F |−|V |+k(F )

kde k(E) je poˇcet komponent grafu (V, E). D˚ ukaz: Indukc´ı podle poˇctu hran. Pokud nem´a ˇz´adn´e hrany, pak sˇc´ıt´ am pˇres jednu mnoˇzinu, vyjde mi 1. G m´ a most. Rozdˇel´ım sumu na ty, kter´e hranu obsahuj´ı a ty kter´e ne. X

e∈F

(x − 1)... · (y − 1)... +

X

e6∈F

(x − 1)... · (y − 1)...

Druh´a ˇc´ast bude (x−1)·TG−e (x, y) – po rozeps´ an´ı. Ta prvn´ı ˇc´ast je TG−e (x, y). Pak uˇz staˇc´ı seˇc´ıst. G m´ a smyˇcku. Rozdˇel´ım na dvˇe ˇc´asti: X

e∈F

(x − 1)... · (y − 1)... +

X

e6∈F

(x − 1)... · (y − 1)...

Pod´ıv´ am se na G − e. Prvn´ı exponent se nemˇen´ı, mˇen´ı se druh´a ˇc´ast, kter´a je o jedniˇcku menˇs´ı. Druh´a ˇc´ast grafu se zcela nemˇen´ı. Tedy, v´ ysledek je: (y − 1) · TG−e (x, y) + TG−e (x, y) Nen´ı ani smyˇcka, ani most. Opˇet rozep´ıˇsu, pod´ıv´ am se, jak vypad´ a graf se zkontrahovanou hranou a s utrˇzenou hranou. Speci´aln´ı pˇr´ıpady: • TG (1, 1) je poˇcet koster. • TG (2, 1) je poˇcet acyklick´ ych podgraf˚ u. • TG (1, 2) poˇcet podgraf˚ u se stejn´ ym poˇctem komponent. Uvaˇzme polynom 5 promˇenn´ ych U (x, y, α, σ, τ ) definov´an: 20

• x · UG−e (. . .) pokud je e most. • y · UG−e (. . .) kdyˇz je e smyˇcka. • σ · UG−e (. . .) + τ · UG|e (. . .) jinak. • α|V | pokud je bez hran. Vˇ eta 9 Tento lze z´ıskat z tutteova polynomu jako: α · x y  k n r , U (x, y, α, σ, τ ) = α · σ · τ · TG τ σ Kde: • k je poˇcet komponent • n = |E| − |V | + k • r = |V | − k D˚ ukaz: Pokud nem´a ˇz´adn´e hrany, tak je to zˇrejm´e. Pak rozebr´ an´ı pˇr´ıpad˚ u. TODO: rozepsat? Aplikace: Lze spoˇc´ıtat poˇcet obarven´ı z barvami. z−1 z y = 0

x =

σ = 1 τ

= −1

α = z Tedy, lze spoˇc´ıtat jako:

z k · (−1)r · TG (1 − z, 0)

21

11

Burnsidova vˇ eta

Napˇr´ıklad m´ ame krychli, kter´e chceme obarvit stˇeny. Zaj´ım´a n´as poˇcet obarven´ı, kter´ a na sebe nejdou pˇrev´est rotacemi krychle. Zavedeme si grupu Γ, coˇz jsou permutace odpov´ıdaj´ıc´ı rotac´ım. X je mnoˇzina obarven´ı. Potom x ∈ X je orbita definovan´ a jako: [x] = {y; ∃α ∈ Γ; α · x = y} Tedy mnoˇzina stejn´ ych“ zobrazen´ı. ” M´ ame funkci w : X → R a w je konstantn´ı na orbit´ ach. Tedy w ([x]) = w (x). P Nyn´ı si nastav´ım w(∗) = 1 a chci spoˇc´ıtat O orbita w(O). Pro vˇsechny α ∈ Γ: • F (α) = {x|α · x = x} – pevn´e body permutace α. • Γ(x) = {α ∈ Γ, α · x = x} – pevn´e permutace obarven´ı x. • Γ(x, y) = {α ∈ Γ, α · x = y} Pozorov´ an´ı: Γ(x, y) = α0 · Γ(x) pro nˇejakou α0 ∈ Γ. Kdyˇz zvol´ıme α0 ∈ Γ(x,
y). Tedy doleva je jasn´e, opaˇcn´ a je: β ∈ Γ(x, y), α0−1 β ∈ Γ(x), α0 · α0−1 · β = β.

Lemma 4 Burnsidovo

|Γ| ·

O

X

w(O) =

orbita

X X

α∈Γ x∈F (α)

D˚ usledek 2 Poˇcet orbit je: 1 X · |F (α)| |Γ| α∈Γ

D˚ ukaz: X X

w (x)

α∈Γ x∈F (α)

=

X X

x∈X γ∈Γ(x)

22

w(x)

w(x)

X

=

X X

w(x)

O orbita x∈O γ∈Γ(x)

=

X O

w(x) ·

X X

1

x∈O γ∈Γ(x)

Protoˇze |Γ(x)| = |Γ(y)| = |Γ(x, y)| = |Γ(y, x)| (viz pˇredchoz´ı lemma a prohazov´an´ı role x a y), proto se pˇredchoz´ı rovn´a: X O

w(O) · |O| · |Γ(xi )|

kde xi je libovoln´ y prvek dan´e orbity. |Γ| = |O| · |Γ(xi )| Tedy to jsou vˇsechny prvky, na kter´e m˚ uˇzu xi zobrazit. Tedy: Γ=

• [

x∈O

Γ(x, z) = |O| · |Γ(x)| -

Vˇ eta 10 (P´ olyova enumerace) Necht’ D je mnoˇzina barven´ı v objektu. R je mnoˇzina barev. Obarven´ı je potom funkce f : D → R, tedy f ∈ RD . Γ je grupa permutac´ı na D. Γ∗ je grupa permutac´ı na RD . Pokud m´ am α ∈ Γ, potom existuje nˇejak´y α∗ ∈ Γ∗ takov´y, ˇze (α∗ f )(d) = f (α(d)). Cyklick´ y index Z(Γ; a1 , a2 , . . . , ad ) je polynom: 1 X Y jk(α) · ak |Γ| α∈Γ k

jk (α) je poˇcet cykl˚ u α d´elky k. Definujeme v´ahovou funkci w : R → R. w(f ) = Πa∈D w (f (a)) Orbita O∗ v˚ uˇci Γ∗ , w je konstantn´ı na O∗ .

S = O∗

X

w(O∗ )

orbita 23

|Γ| · =

X

X

w(O∗ )

O∗

X

w(f )

α∈Γ f ∈F (α∗ )

=

XX

ξi Πm i=1 w(ri )

α∈Γ ri ∈R

=

l X XY

α∈Γ i=1

=

X

Πdk=1

α∈Γ

12

w(r)

r∈R

X

r∈R

ξi

!

w(r)k

!jk(α)

Samoopravn´ e k´ ody

M´ ame zpr´ avu v, coˇz je ˇretˇezec n bit˚ u. Pˇri pˇrenosu m˚ uˇze doj´ıt k chybˇe. Pˇredpokl´ ad´ ame, ˇze pravdˇepodobnost, ˇze vznikne v´ıce k chyb je podstatnˇe menˇs´ı, neˇz ˇze nastane nejv´ yˇse k chyb. Vezmeme v, transformujeme na w, pˇreneseme, doraz´ı w′ . Pot´e chceme z´ıskat transformac´ı opˇet v. Moˇznost duplikovat jednotliv´e bity.

12.1

Hammingovy k´ ody

Napˇr. pro ˇretˇezec bit˚ u abcd by poslal abcdef g, kde e = a + b + c f = a + b + d (mod 2), g = a + c + d (mod 2).

(mod 2),

Abeceda S je nˇejak´ a koneˇcn´ a mnoˇzina symbol˚ u (napˇr. S = {0, 1}). Slovo je libovoln´ y ˇretˇezec p´ısmen abecedy S, tedy prvek S n . K´ od d´elky n nad abecedou S je libovoln´a C ⊆ S n .

Napˇr. pro 4-bitov´e ˇretˇezce je hamming˚ uv k´od 16 7-bitov´ ych slov.

Hammingova vzd´ alenost d(u, v) = |{i ∈ 1, 2, . . . , n; ui 6= vi }|. Minim´ aln´ı vzd´ alenost k´ odu C d(C) = min {d(u, v), u, v ∈ C, u 6= v}. ˇ ım vˇetˇs´ı vzd´ C´ alenost, t´ım spolehlivˇejˇs´ı k´od, na druhou stranu, ˇc´ım v´ıce slov, t´ım v´ıce informac´ı lze poslat. K´od C opravuje t chyb, pokud pro ∀u ∈ S n ; ∃ nejv´ yˇse jedno u, d(u, w) ≤ t. Pozorov´ an´ı 1 K´ od C opravuje t chyb ⇔ d(C) ≥ 2t + 1. Tvrzen´ı 2 Hamming˚ uv k´ od opravuje 1 chybu. Napˇr. Golayovy, CD, DVD... 24

Souvis´ı s PCP vˇetou.

12.2

Line´ arn´ı k´ ody

Necht’ Si je koneˇcn´e tˇeleso (tˇreba Z2 ). C ⊆ S n je line´ arn´ı k´od, pokud C je vektorov´ y podprostor S n . Ke kaˇzd´emu k´odu existuje b´aze – generuj´ıc´ı matice k´odu – P . Jin´ y pohled ˇr´ık´ a, ˇze C je ˇreˇsen´ı soustavy line´ arn´ıch rovnic. Zobecnˇen´ y hamming˚ uv k´od, kde abeceda S = Z2 a parametr l ≥ 2 (l = 3 je hamming˚ uv k´od). Matice P m´ a l ˇr´adek a sloupce m´ a vˇsechny moˇzn´e l nenulov´e vektory z {0, 1} . Tvrzen´ı 3 Zobecnˇen´y hamming˚ uv k´ od C je d(C) ≥ 3, tedy opravuje 1 chybu. D˚ ukaz: d(u, v) = d(u+w, v+w). Tedy d(u, v) = d(u−v, 0). Tedy d(C) = min {d(w, 0); w ∈ C; w 6= 0}. Z toho to uˇz jde spoˇc´ıtat. Asymptoticky dobr´ y soubor k´ od˚ u splˇ nuje podm´ınky: • D´ a se zak´ odovat libovolnˇe velk´ y vstup. • Vzd´alenosti v nekoneˇcnu jdou k nˇeˇcemu vˇetˇs´ımu neˇz jedna. • Hustota je vˇetˇs´ı neˇz nula. Vˇ eta 11 (Gilbert,Varshamov) Existuj´ı asymptoticky dobr´e soubory k´ od˚ u. D˚ ukaz: Pomoc´ı hladov´eho algoritmu: Vstupem je abeceda, d´elka a d minim´aln´ı vzd´ alenost. Vˇzdy vybere slovo, oznaˇc´ı pˇr´ıliˇs bl´ızk´a jako nepouˇziteln´a a pokraˇcuje. Vzd´alenost je dostateˇcn´ a. -

25

13

Extrem´ aln´ı kombinatorika

Lemma 5 (o sluneˇ cnici) Mˇejme stejnˇe velk´e mnoˇziny S1 , . . . , Sk , kter´e nazvu sluneˇ cnic´ı, pokud existuje nˇejak´ a mnoˇzina Y takov´ a, ˇze ∀i, j; Si ∩ Sj = Y . Pokud m´ ame syst´em S r˚ uzn´ych s prvkov´ych mnoˇzin a |S| > s! · (k − 1)s , ′ potom existuje S ⊆ S takov´e, ˇze S ′ je sluneˇcnice a |S ′ | = k. D˚ ukaz: Indukc´ı podle s. Pokud s = 1, potom kaˇzd´ ych k jednoprvkov´ ych r˚ uzn´ ych 1 mnoˇzin tvoˇr´ı sluneˇcnici. Dle pˇredpokladu |S| > 1! · (k − 1) , |S| ≥ k.

Necht’ je s > 1. Necht’ S je syst´em v´ıce neˇz s! · (k − 1)s s-prvkov´ ych mnoˇzin. ’ Necht B1 , B2 , . . . , Bl je nejvˇetˇs´ı moˇzn´ y podsyst´em navz´ ajem r˚ uzn´ ych mnoˇzin. Pokud l ≥ k, pak je hotovo. S D´ ale tedy pˇredpokl´ ad´ ame, ˇze l < k. Potom existuje prvek x ∈ Bi , kter´ y je ve v´ıce neˇz (s − 1)! · (k − 1)s−1 mnoˇzin´ach z S.

Necht’ S = {X ∈ S, x ∈ X}. Pot´e vezmu vˇsechny mnoˇziny, ze kter´ ych tento prvek vyhod´ım. T´ım z´ısk´ am syst´em (s − 1) prvkov´ ych mnoˇzin, je jich dostatek (viz n´ıˇze), dle indukˇcn´ıho pˇredpokladu to pro tento syst´em plat´ı. Nakonec k nim opˇet tento prvek vr´at´ım a m´ am st´ale sluneˇcnici. a. Mˇejme vˇsechny Nyn´ı je tˇreba zaˇr´ıdit, aby byla mnoˇzina S dostateˇcnˇe velik´ dvojice (x, A), kde x ∈ A, A ∈ S. |{(x, A)}| > s! · (k − 1)s . Pokud by tomu nebylo, mohu nˇekterou mnoˇzinu pˇridat mezi tyto disjunktn´ı. Moˇzn´ ych s!·(k−1)s volem x je l · s. Tedy existuje nˇejak´e k, kter´e je ve v´ıce neˇz s·(k−1) = (s − 1)! · (k − 1)s−1 mnoˇzin´ach. -

Lemma 6 Erd¨ os-Ko-Rado Necht’ k a n jsou pˇrirozen´ a ˇc´ısla, 2k ≤ n. Necht’ f je syst´em k-prvkov´ych podmnoˇz in mnoˇziny {1, . . . , n} takov´y, ˇze ∀A, B ∈ n−1 f ; A ∩ B 6= ∅. Pak |f | ≤ . k−1 Pozn´ amka 2 Je to optim´ aln´ı. Vˇsechny mnoˇziny obsahuj´ı jeden pevn´y prvek. V takov´em pˇr´ıpadˇe bude velikost pˇresnˇe takov´e. Pozn´  amka  3 Kdyby  2k > n, potom lze zvolit takov´e mnoˇziny, ˇze |f | = n n−1 > (ve vˇetˇsinˇe pˇr´ıpad˚ u – aˇz na patologick´e pˇr´ıpady). k k−1

26

D˚ ukaz: Vezmu permutaci π ˇc´ısel 1, . . . , n. Mnoˇzinu X ∈ f nazvu π-konzistentn´ı, jestliˇze X = {π(i), π(i + 1), . . . , π(i + k − 1)}. π-konzistentn´ıch mnoˇzin v f je nejv´ yˇse k. Pokud tam nen´ı ˇz´adn´ a, pak je hotovo. Pokud nˇejak´ a je, tak se vˇsechny mus´ı prot´ınat se vˇsemi. Takov´ ych by bylo aˇz 2 · (k − 1) – kaˇzd´ a by mohla v nˇekter´em m´ıstˇe zaˇc´ınat nebo konˇcit. Ale v kaˇzd´e dvojici (jedna zaˇc´ınaj´ıc´ı a jedna konˇc´ıc´ı) m˚ uˇze b´ yt nejv´ yˇse jedna, protoˇze tyto dvˇe by se neprotly. Na druh´em konci se protnout nemohou, protoˇze jsou mnoˇziny jen k prvk˚ u dlouh´e.

ˇ Obr´azek 5: Cerven´ a a modr´a mnoˇzina se neprotne

Poˇc´ıt´ ame vˇsechny dvojice (π, X), X je π-konzistentn´ı. Urˇcitˇe jich nem˚ uˇze b´ yt v´ıce neˇz k · n!. (je n! permutac´ı).

D´ ale m˚ uˇzu m´ıt n · k!(n − k)! permutac´ı, se kter´ ymi je mnoˇ zina konzistentn´ı. n−1 Proto po vydˇelen´ı je celkov´ y poˇcet maxim´ alnˇe . k−1

-

14

Minory

Graf H je minorem G, pokud existuj´ı podmnoˇziny disjunktn´ı V1 , . . . , Vk ⊆ V (G), kaˇzd´ y G [V ] je souvisl´ y a plat´ı, ˇze pokud (v1 , v2 ) ∈ E(H) ⇒ ∃ hrana mezi nˇejak´ ymi vrcholy V1 a nˇejak´ y m z V2 Alternativn´ı definice je takov´a, ˇze H jde z´ıskat posloupnost´ı vynech´av´an´ım hran, izolovan´ ych vrchol˚ u a kontrakcemi hran. Vˇ eta 12 (Kuratovsk´ eho s minory) Kuratovsk´eho vˇeta plat´ı i s minory, nejen s podrozdˇelen´ımi. Hypot´ eza 1 (Hadwidgerova hypot´ eza) Pokud χ(G) ≥ k ⇒ G obsahuje Kk jako minor. Pro mal´e pˇr´ıpady to plat´ı, lze vyzkouˇset. Pro k = 4 to m˚ uˇzeme dok´azat obmˇenou implikace. 27

Lemma 7 Necht’ G je hranovˇe maxim´ aln´ı graf bez minoru K4 na alespoˇ n 3 vrcholech. Pak G lze vytvoˇrit z troj´ uheln´ık˚ u lepen´ım za hrany (eg. je to 2-strom). D˚ ukaz: Pˇredpokl´ adejme, ˇze je 3-souvisl´ y. M´ am dva vrcholy, mezi nimi mus´ı v´ezt alespoˇ n 3 vrcholovˇe disjunktn´ı cesty, alespoˇ n 2 z toho tedy maj´ı vrcholy. Ty p˚ uvodn´ı vrcholy m˚ uˇzu zahodit a st´ale to je souvisl´e. Potom ale mus´ı obsahovat minor K4 .

Kdyby nebyl souvisl´ y, tak mezi komponenty m˚ uˇzu pˇridat hranu a t´ım urˇcitˇe nem˚ uˇzu vytvoˇrit minor K4 . Kdyby nebyl 2-souvisl´ y, tak by existoval vrchol, kter´ y po utrˇzen´ı rozpadne tuto vˇec na dvˇe ˇc´asti. Ten m´ a v kaˇzd´e komponentˇe alespoˇ n jednoho souseda, m˚ uˇzu mezi nˇe pˇridat hranu. Ale to to taky nem˚ uˇze vytvoˇrit K4 . Obsahuje tedy 2-ˇrez. Kdyˇz jsou spojeny hranou, tak ho rozloˇz´ım na dva, kter´ y jsou hranovˇe maxim´ aln´ı bez minoru K4 . Hur´ a, indukce (oba jsou 2stromy, postav´ım jeden, dostav´ım k nˇemu druh´ y). Kdyˇz tedy nejsou spojeny, tak tam pˇrid´ am hranu. Vznikl mi minor (mus´ı, jsem hranovˇe maxim´ aln´ı), tak to vypad´ a takto:

V tom pˇr´ıpadˇe tam ale byla jeˇstˇe jedna komponenta, nebot’ ˇsediv´ y kus je souvisl´ y, nebyl by to 2-ˇrez. Ta dalˇs´ı komponenta mus´ı b´ yt pˇripojena na oba modr´e vrcholy, proto m´ısto zelen´e pˇridan´e hrany m˚ uˇzu proj´ıt tamtudy. Nyn´ı, pˇredpokl´ adejme, ˇze graf neobsahuje K4 jako minor ale je alespoˇ n 4 barevn´ y. Udˇel´ ame ho hranovˇe maxim´ aln´ı (pˇrid´ av´an´ı hran barevnost nesniˇzuje). 28

Protoˇze ale jde ulepit z troj´ uheln´ık˚ u, tak to jde obarvit 3 barvami (kdykoliv pˇrilep´ım nov´ y troj´ uheln´ık, tak m´ a nov´ y vrchol jen 2 sousedy, tedy m´ a volnou barvu). Pro pˇetku to plyne z vˇety o 4 barv´ach, ˇsestka uˇz je slavn´ y v´ ysledek. Graf G je chord´ aln´ı, pokud neobsahuje indukovanou kruˇznici na alespoˇ n4 vrcholech. Tvrzen´ı 4 Necht’ G je chord´ aln´ı (souvisl´y, ne u ´pln´y) a V je minim´ aln´ı (co do inkluze) ˇrez. Potom G[V ] je u ´pln´y graf. D˚ ukaz: Viz georep. Kdyby chybˇela hrana, najdu nejkratˇs´ı cesty mezi nespojen´ ymi vrcholy v r´ amci kaˇzd´e komponenty, dohromady to tvoˇr´ı kruˇznici bez chordy. Vˇ eta 13 Graf G je chord´ aln´ı ⇔ je pr˚ unikov´y graf podstrom˚ u ve stromˇe. D˚ ukaz: Viz georep. Lemma 8 (Hellyho vlastnost) Necht’ T1 , . . . , Tk jsou podstromy stromu T a kaˇzd´e dva maj´ı nepr´ azdn´y pr˚ unik. Pak vˇsechny maj´ı nepr´ azdn´y pr˚ unik. Stromov´ aˇ s´ıˇ rka tw(G) je takov´e nejmenˇs´ı k takov´e, ˇze existuje chord´ aln´ı G′ takov´ y, ˇze G ⊆ G′ a velikost kliky w(G′ ) = k + 1. Vˇ eta 14 Necht’ G je vlastn´ı tˇr´ıda graf˚ u uzavˇren´ a na minory. Pak existuje c takov´e, ˇze ∀G ∈ G, |E(G)| ≤ c · |V (G)|. Vˇ eta 15 (Cornellova) Necht’ P je probl´em popsateln´y pomoc´ı monadick´e lokigy druh´eho ˇra ´du a necht’ G je tˇr´ıda graf˚ u omezen´e stromov´e ˇs´ıˇrky. Potom existuje line´ arn´ı algoritmus, kter´y rozhoduje probl´em P na t´eto tˇr´ıdˇe. D˚ ukaz: M´ ame MSOL formuli s x1 , . . . , xk a X1 , . . . , Xl . M´ ame rovnosti, nerovnosti, provˇsechn´ıtka, exist´ıtka, inkluz´ıtka. Hrany reprezentujeme jako dvojici. Na kaˇzd´em uzlu si pamatujeme u formule: 29

• U promˇenn´e ˇze bud’ byla, ˇze teprve bude a nebo pokud je, tak jak´a. • U mnoˇziny jej´ı pr˚ unik s aktu´aln´ım uzlem. Toto je konstantnˇe omezen´e. Jde to updatovat v konstantn´ım ˇcase pˇri pˇrid´ an´ı vrcholu, pˇri odebr´ an´ı, pˇri slit´ı stromeˇck˚ u. Udˇel´ ame hezk´ y stromov´ y rozklad, vrcholy jen druhu (z algograph, drobnˇe se liˇs´ı oproti tomu pˇredn´ aˇsen´emu): • Listy jsou jednoprvkov´e. • Jeden vrchol pˇrib´ yv´ a, m´ a jednoho syna. • Jeden vrchol ub´ yv´ a, m´ a jednoho syna. • Vrcholy jsou stejn´e, m´ a pr´avˇe dva syny. Proch´az´ıme odspodu. Na kaˇzd´em m´ ame mnoˇzinu vˇsech pˇriˇrazen´ı, co jeˇstˇe pˇripadaj´ı v u ´vahu. Pˇri odebr´ an´ı vrcholu jen pˇrech´az´ı do uˇz bylo“ (nˇekter´e se t´ım mohou ” y slouˇcit), pˇri pˇrid´ an´ı se zkus´ı pˇridat do promˇenn´ ych teprve bude“ ten nov´ ” vrchol, t´ım se nageneruj´ı nov´e, zkus´ı se, jestli jeˇstˇe mohou platit, pokud ano, nechaj´ı se. U sl´ev´ an´ı mus´ıme kˇr´ıˇzit pˇriˇrazen´ı. Z dvojice pˇreˇzije, pokud max. v jednom synovi je uˇz byl“, v druh´em bude“ (nebo oba teprve budou“), ” ” ” nebo se pˇriˇrazen´ı rovn´a. V koˇreni mus´ı b´ yt nˇeco, co plat´ı a uˇz nem´a ˇz´adn´e bude“. ” Je potˇreba naj´ıt line´ arnˇe velkou dekompozici, to ale jde v line´ arn´ım ˇcase. Pozorov´ an´ı 2 Tˇr´ıda graf˚ u stromov´e ˇs´ıˇrky ≤ k je vlastn´ı tˇr´ıda uzavˇren´ a na minory. D˚ ukaz: Mazat hrany a vrcholy je v pohodˇe. Kontrakce taky jdou. Vˇ eta 16 Pro kaˇzd´e k existuje algoritmus bˇeˇz´ıc´ı v line´ arn´ım ˇcase, kter´y pro graf G bud’ vr´ at´ı, ˇze m´ a moc velkou stromovou ˇs´ıˇrku, nebo nalezne hezk´y stromov´y rozklad dan´e ˇs´ıˇrky. Vˇ eta 17 (Maderova) ∀n∃δ takov´e, ˇze kaˇzd´y graf s minim´ aln´ım stupnˇem δ obsahuje podrozdˇelen´ı grafu Kn . 30

D˚ ukaz: Udˇel´ ame silnˇejˇs´ı tvrzen´ı. Necht’ H je souvisl´ y s m hranami a G je graf s m minim´aln´ım stupnˇem 2 , pak G obsahuje podrozdˇelen´ı H. Indukc´ı. Zaˇcneme H je strom. Potom 2m ≥ n. Najdu dokonce jako podgraf, vˇzdycky m´ am jeˇstˇe dostatek soused˚ u, ze kter´ ych br´at, m˚ uˇzu prostˇe hladovˇe. D´ ale m´ ame H souvisl´ y, nen´ı strom. Tedy ∃e takov´e, ˇze H := H\E je st´ale ´ souvisl´ y. D´ ale BUNO G je souvisl´ y. Uvaˇzme nejvˇetˇs´ı mnoˇzinu vrchol˚ u W takovou, ˇze G [W ] je souvisl´ y a |E(G/W )| ≥ 2m−1 · |V (G/W )|. M˚ uˇzu si za W zvolit jeden vrchol, proto takov´e W urˇcitˇe existuje. Necht’ G′ je podgraf G indukovan´ y vrcholy w takov´ ymi, ˇze w6∈W a w m´ a sousedy v W (okol´ı mnoˇziny W ). Tvrd´ıme, ˇze minim´aln´ı stupeˇ n G′ je alespoˇ n 2m−1 .

Takov´e W ′ obsahuje dle indukce H ′ , ale chyb´ı tam jedna hrana. Tu nahrad´ım cestou skrz v W , to je podrozdˇelen´ı t´eto hrany. Nyn´ı dokazujeme, ˇze minim´aln´ı stupeˇ n v G′ je alespoˇ n 2m−1 . Sporem, vezmeme vrchol v, kter´ y m´ a m´ alo soused˚ u, tedy nejv´ yˇse 2m−1 −1. Vraz´ım takov´ y vrchol do W . Tam m´ a dostatek soused˚ u (protoˇze jich m´ a m´ alo tady). Od nˇej ztrat´ım m´ alo hran, protoˇze tady jich m´ a m´ alo. Upoˇc´ıt´ a se, ˇze W nebylo nejmenˇs´ı. D˚ usledek 3 Necht’ G je vlastn´ı tˇr´ıda graf˚ u uzavˇren´ a na minory. Potom existuje c0 takov´e, ˇze barevnost t´eto tˇr´ıdy je nejv´yˇse c0 . D˚ ukaz: Neobsahuje u ´pln´e grafy libovoln´e velikosti, existuje tedy nˇejak´e n0 takov´e, 31

ˇze Kn0 nen´ı souˇc´ast G a tedy ani podrozdˇelen´ı a minim´aln´ı stupnˇe jsou m´enˇe neˇz δ0 , obarv´ıme. D˚ usledek 4 Necht’ G je vlastn´ı tˇr´ıda graf˚ u uzavˇren´ a na minory. Pak existuje konstanta d0 takov´ a, ˇze poˇcet hran je nejv´yˇse d0 · n. Graf G je k-spojovan´ y, pokud pro kaˇzd´e vrcholy u1 , . . . , uk , v1 , . . . , vk existuje vrcholovˇe disjunktn´ı cesta mezi kaˇzdou dvojic´ı ui , vi . Vˇ eta 18 ∀k∃l takov´e, ˇze kaˇzd´y l-souvisl´y graf je k-spojovan´y. D˚ ukaz:

 

3k 2



+2k

Vezmu l := δ+2k = 2 . Odstran´ım vˇsech 2k vrchol˚ u ui , vi . Ten bytek obsahuje podrozdˇelen´ı K3k , je 2k-souvisl´ y. Z toho lze odvodit, ˇze existuje 2k disjunktn´ıch cest z kaˇzd´eho odebran´eho vrcholu do toho K3k . Vezmu takov´e, aby mimo to podrozdˇelen´ı bylo co nejm´enˇe hran. Mus´ım naj´ıt disjunktn´ı cesty ze vˇsech 2k vrchol˚ u do tohoto K3k a to tak, aby se jich moc nepotkalo na jedn´e podrozdˇelen´e hranˇe. Vezmu takov´e cesty, co maj´ı co nejm´enˇe hran mimo to podrozdˇelen´ı. TODO: Uspoˇ rit nˇ ejak to, ˇ ze nemaj´ ı nic spoleˇ cn´ eho. ˇ ıslo t(n, l) je poˇcet hran u C´ ´pln´eho balancovan´eho l-partitn´ıho grafu na n vrcholech. Vˇ eta 19 (Turanova) Pokud G je graf na n vrcholech s alespoˇ n t(n, l) + 1 hranami, pak G obsahuje Kl+1 jako podgraf. D˚ ukaz: Indukce podle n. Pokud je n ≤ l, to m´ a



(kaˇzd´ y vrchol mus´ı b´ yt samostatn´a partita).

n 2



hran, to obsahuje u ´plˇ n´ak

´ Necht’ n ≥ l + 1, G m´ a alespoˇ n t(n, l) + 1 a neobsahuje Kl+1 . BUNO pˇrid´ an´ı libovoln´e hrany vytvoˇr´ı Kl+1 , tedy obsahuje Kl . Utrhneme toto Kl , ale vyjde n´am, ˇze m´ a alespoˇ n t(n − l, l) + 1 hran. To se uindukuje. 32

15

Semeredi regularity lemma

M´ am bipartirtitn´ı graf H s partitami A, B, |A| = |B|. Potom je ǫ-regul´ arn´ı ′ ′ ′ ′ plat´ı, ˇze ∀A ⊆ A; B ⊆ B, |A | ≥ e · |A|, |B | ≥ e · |B|. Potom pokud e(A′ ,B ′ ) e(A,B) |A′ ||B ′ | − |A||B| ≤ ǫ. To e je poˇcet hran mezi dvˇema mnoˇzinami. Vˇ eta 20 (Szem´ eredi regularity lemma)

∀ǫ, m0 ∃M0 , n0 ; ∀G, |V (G)| = n ≥ n0 ∃ rozklad na V0 , V1 , . . . , Vm , m0 ≤ m ≤ M0 Takov´e, ˇze: • |V0 | ≤ ǫ · n • |V1 | = |V2 | = . . . = |Vm | • Nejv´yˇse ǫ · m2 dvojic Vi , Vj , 1 ≤ i < j ≤ m nen´ı ǫ-regul´ arn´ıch Lemma 9 (Removal lemma for triangles) ∀ǫ0 > 0∃δ0 > 0∀G plat´ı alespoˇ n jedno z n´ asleduj´ıc´ıch: • G obsahuje δ0 · n3 podgraf˚ u izomorfn´ıch s K3 . • ∃F ⊆ E(G) takov´e, ˇze G\F neobsahuje troj´ uheln´ık a |F | ≤ ǫ0 · n2 . Pozorov´ an´ı 3 Necht’ A, B je ǫ-regul´ arn´ı bipartitn´ı graf a jeho hustota je d. Potom A obsahuje alespoˇ n (1 − ǫ) · |A| vrchol˚ u stupnˇe alespoˇ n (d − e) · |B|. D˚ ukaz: Sporem, pˇredpokl´ adejme, ˇze m´ ame hodnˇe takov´ ych mal´ ych vrchol˚ u. Zvol´ım ′ ′ ′ B := B, |A | ≥ ǫ · |A| (A jsou ty mal´e vrcholy). D˚ ukaz: Nastav´ım, ˇze ǫ := ǫ0n /20 a o m0 := 20/ǫ0 a d´am to do 20. Vypadne M0 , n0 . 1 a). Pot´e nastav´ım δ0 := n3 , x . (x se spoˇc´ıt´ 0

Udˇel´ am regularity graf (kaˇzd´ a ˇc´ast m´ a vrchol, je hrana, pokud tam je alespoˇ n tolik, jako je hustota hran a je ǫ-regul´ arn´ı. Staˇc´ı dokazovat pro vrcholy s alespoˇ n n0 vrcholy (jinak bud m´ am jeden troj´ uheln´ık, nebo ne).

Udˇel´ ame H regul´ arn´ı graf pro G s rozkladem z 20 a hustotu ρ := ǫ20 . Pokud H neobsahuje troj´ uheln´ık, pak do mnoˇziny F d´ame hrany, kde jeden vrchol 33

je v V0 (odpadn´ı), hrany uvnitˇr rozkladov´ ych tˇr´ıd, hrany spojuj´ıc´ı dvojice, co nejsou ǫ-regul´ arn´ı a hrany mezi ˇr´ıdk´ ymi dvojicemi. To zajist´ı, ˇze hrany jsou jen tam, kde hrany m´ ame ted’, takˇze ted’ uˇz ˇz´adn´e troj´ uheln´ıky nem´ame. Hran ve V0 = ǫ · n2 . Uvnitˇr jedn´e je to m ·

n2 m

≤

n2 m0

=

odhad pro neregul´arn´ı dvojice. Tˇech m´ alo hust´ ych je ≤ dostateˇcnˇe m´ alo.

ǫ0 ·n2 e bude i 20 . Stejnˇ 2 ρ·n n2 ≤ 2 . To je n2 ρ m

Pokud H m´ a troj´ uheln´ık, zafixujme si ho. Kaˇzd´ a dvojice je ǫ-regul´ arn´ı a poˇcet hran mezi nimi je alepsoˇ n ρ · Vi · Vj . Vezmeme podmnoˇzinu W ⊆ Vi takovou, ˇze kaˇzd´ y vrchol m´ a alespoˇ n ρ · |Vj | soused˚ u ve Vj a takt´eˇz s Vk . |W | ≥ (1 − 2ǫ) · |Vi |. Upoˇc´ıt´ a se, ˇze ty kousky ve Vj , Vk jsou alespoˇ n ǫ · |Vj | a ǫ · |Vk |, toto jsou podmnoˇziny ǫ-regul´ arn´ı dvojice, najde se tam dostatek hran.

Vyjde ˇze m´ ame alespoˇ n (1 − 2ǫ)ǫ3 |Vi ||Vj ||Vk |. Odhadneme velikosti V a dosad´ıme do x. Vˇ eta 21 (Szemer´ ediho) ∀ǫ∃n0 ∀X ⊆ 1 . . . n0 ; |X| ≥ n0 · ǫ∃x, y, z; x + y = z Vˇ eta 22 Mˇejme danou hustotu hran d, m´ ame k barev. Kolik nejv´yˇse r˚ uzn´ych obarven´ı je moˇzn´e naj´ıt na grafu G s hustotou d? Hled´ ame tedy limitnˇe, kolik je n-t´ a odmocnina z poˇctu obarven´ı. P Toto je β(d, k) = eδ(d,k) , kde δ = αA ln |A|. D˚ ukaz: Rozdˇel´ıme na mnoˇziny indexovan´e nepr´ azdn´ ymi podmnoˇzinami barev, nacpeme u ´plˇ n´ak, pokud jsou indexy disjunktn´ı. Takˇze si m˚ uˇzu u kaˇzd´eho vrcholu vybrat libovolnou barvu z indexu. ChcemeP m´ıt relativn´ı velikosti αi mnoˇzin, coˇ z jsou nez´ aporn´e a dohromady daj´ı 1, αi · αj ≥ d. Chci maxiQ malizovat n · αi (to odpov´ıd´ a on´e n-t´e mocninˇe, kter´e se zbavujeme). T´ım m´ ame doln´ı odhad. Na druhou stranu staˇc´ı naj´ıt spr´ avn´e α, abych dok´azal, ˇze nen´ı nejlepˇs´ı. Vezmeme nekoneˇcnou posloupnost rostouc´ıch graf˚ u. Vyberu si dominantn´ı typ, vezmu si ty barvy, co se objevuj´ı ˇcasto. TODO: Hmm, tady to chyb´ ı -

34

Pˇ r´ıklad 1: M´ ame graf H. Kolik mus´ı m´ıt graf na n vrcholech, aby obsahoval H jako podgraf? Budeme pˇredpokl´ adat, ˇze H nen´ı strom (asi jen nezaj´ımav´e). Urˇcitˇe m˚ uˇzu vz´ıt χ(H) − 1 partitn´ı u ´pln´ y graf, ten ho neobsahuje, takˇze nestaˇc´ı t(n, χ(H) − 1) , Vˇ eta 23 (Erd¨ os-Stown) ∀H∀γ∃n0 ∀G; n = |V (G)| ≥ n0 , |E(G)| ≥ t(n, χ(H)− 1) + γn2 , potom G obsahuje H. D˚ ukaz: Vezmu d := γ2 . n v H. Zvol´ıme D´ ale potˇrebuji, aby (d−ǫ)∆ −∆ǫ ≥ 12 d∆ , kde ∆ je max. stupeˇ ǫ tak, aby to platilo a bylo menˇs´ı, neˇz d. Zvol´ıme m tak, aby 2γ − ǫ2 − 4ǫ − d −

1 m

> 0 a m ≥ χ(H).

Potom na to pust´ıme Semerediho Regularity Lemma a vr´at´ı M a n0,s . Potom ·|V (H)| a z´aroveˇ n n0 ≥ n0,s . d´ame n0 ≥ 2M d∆ (1−ǫ)

D´ ale m´ ame ǫ regul´ arn´ı rozdˇelen´ı na V0 , V1 , . . . , Vn tak, ˇze m ≤ n ≤ M0 , |V0 | ≤ ǫ · n, |V1 | = . . . = |Vn |. Udˇel´ ame regularity graf s hraniˇcn´ı hustotou d.

Bud’ obsahuje Kχ(H) nebo m´ a nejv´ yˇse t(m, χ(H)−1) hran (a podle Turanovy vˇety nast´ av´a alespoˇ n jedna moˇznost).

H m´ a vrcholy w1 , . . . , wk , uv´aˇz´ıme jeho obarven´ı. Jako kandid´ atskou mnoˇzinu vrcholu wi barvy c zvol´ıme Vc (kde to Kχ(H) je na prvn´ıch χ(H) V vrcholech). T´e budu ˇr´ıkat Yi . D´ ale budeme postupnˇe urˇcovat vrcholy z kandid´ atsk´ ych mnoˇzin. Budeme m´ıt invariant, ˇze Yi pro neurˇcen´ y vrchol wi bude alespoˇ n (d − ǫ)l · |Vi |, kde l je poˇcet jiˇz zafixovan´ ych soused˚ u. Druh´ y invariant je, ˇze pokud m´ am dva vrcholy urˇcen´e, tak pokud byly v H hranou, tak jsou i nyn´ı. Pokud wi je zafixovan´ y a wj nen´ı zafixovan´ y, potom Yj obsahuje jen sousedy wi . Na zaˇc´atku to trivi´ alnˇe plat´ı. Necht’ jsou w1 , . . . , wκ zafixovan´e, fixuji wκ+1 . Velikost Yκ+1 je alespoˇ n (d − ǫ)∆ · |V1 |. Nemohu pouˇz´ıt ≤ k − 1 vrchol˚ u, kter´e jsou jiˇz obsazen´e. A tak´e nem˚ uˇzu pouˇz´ıt nejv´ yˇse ∆ · ǫ · |V1 |, kter´e maj´ı m´ alo soused˚ u v kandid´ atsk´ ych mnoˇzin´ach nezafixovan´ ych soused˚ u wκ+1 . 35

Nyn´ı je potˇreba dok´azat, ˇze mi jeˇstˇe nˇeco zbylo. To je potˇreba upoˇc´ıtat z pˇredpoklad˚ u. Druh´ y pˇr´ıpad je, ˇze Kχ(H) tam nen´ı. Pˇredpokl´ adejme, ˇze |E(G) > t(m, χ(H) − 1|. Jednak m˚ uˇzeme m´ıt aˇz ǫ · n2 hran do odpadn´ı mnoˇziny. D´ ale TODO: .

Pˇ r´ıklad 2: ∀ǫ > 0∃n0 ∀A ⊆ 1 . . . n, n ≥ n0 , |ǫ · n|; A obsahuje aritmetickou posloupnost d´elky 3. Tohle se udˇel´ a pˇres removal lemma pro troj´ uheln´ıky. Udˇel´ ame si 3-partitn´ı graf, oˇc´ıslovan´e pomoc´ı 1 . . . 3n (takˇze celkem 9n vrchol˚ u). Spoj´ım hranou dva vrcholy sousedn´ıch partit, kdyˇz jejich rozd´ıl je v A, ty krajn´ı kdyˇz polovina rozd´ılu je v A. Na aritmetick´e posloupnosti vid´ım troj´ uheln´ık. Obsahuje n·|A| hranovˇe disjunktn´ıch troj´ uheln´ık˚ u. Takˇze to m´ a moc troj´ uheln´ık˚ u/hran, takˇze druh´ y pˇr´ıpad removal lemma nenastane. Tedy m´ ame troj´ uheln´ık˚ u hodnˇe. Ale troj´ uheln´ık˚ u tvaru x, x + a, x + 2a je jen 3n2 . Proto existuje ame tedy i jin´ y troj´ uheln´ık. Proto tam m´ am nˇejak´ a ˇc´ısla a, b, a+b 2 v A. M´ aritmetickou posloupnost. , D˚ ukaz regularity lemmatu: D˚ ukaz: Budeme m´ıt potenci´al rozdˇelen´ı. Jemnˇejˇs´ı rozdˇelen´ı bude vyˇsˇs´ı a je to ˇc´ıslo mezi 0 a 1. Vezmu n´ahodn´e, potom postupnˇe zlepˇsuji. Potenci´al bude: q(A, B) :=

e(E, B)2 n2 · |A| · |B|

A pro celek: q(A1 , . . . , Al ) :=

X

q(Ai , Aj )

Pro n´aˇs rozklad to bude tak, ˇze V0 rozdrobn´ım na jednotliv´e prvky, jinak je to stejn´e. Pokud rozdˇel´ım nˇeco na dva kusy, tak to z˚ ustane alespoˇ n stejn´e. e(A,B)2 |A|

≤

e(A′ ,B)2 ) |A′ |

+

e(A′′ ,B)2 |A′′ | .

36

To se vykouk´a z cauchy-swartzovy nerovnosti. To, ˇze je to do jedniˇcky, to dok´aˇzu z rozkladu na jednotliv´e vrcholy. Lemma 10 Pokud C, D nen´ı ǫ-regul´ uˇzu rozdˇelit P arn´ı dvojice, potom je 4m˚ kaˇzdou na dvˇe mnoˇziny takov´e, ˇze q(Ci , Dj ) ≥ q(C, D) + ǫ |C||D| . n2 D˚ ukaz: Hnusn´e rozeps´ an´ı a rozn´asoben´ı. Pot´e cauchy-swartz. Potom z pˇredpokladu, ˇze |C1 | ≥ |C| a obdobnˇe pro D dok´aˇzeme, ˇze to vzroste dostateˇcnˇe. ame rozdˇelen´ı Vi , velikosti jsou stejn´e. Pokud nen´ı Lemma 11 ǫ ≤ 81 , m´ ǫ-regul´ arn´ı, potom existuje rozdˇelen´ı Vi′ takov´e, ˇze: |V0′ | ≤ |V0 | + 2nm , m ≤ 5 m′ ≤ m · 4m , stejn´e velikosti, a potenci´ al vzroste alespoˇ n o ǫ4 . Toto uˇz staˇc´ı. Libovolnˇe rozdˇel´ıme na ˇc´asti V1 , . . . , Vm′0 , zbyl´e d´am do V0 , am pˇredchoz´ı lemma, dokud nen´ı ǫ-regul´ arn´ı. V m′0 ≥ m0 . Nyn´ı pouˇz´ıv´ kaˇzd´em kroku mi potenci´al vzroste o konstantu. Takˇze poˇcet krok˚ u je shora omezen, pak uˇz to urˇcitˇe nesm´ı j´ıt. D˚ ukaz: M´ am dostatek dvojic, co nejsou ǫ-regul´ arn´ı. Pro kaˇzdou dvojici pouˇziju pˇredchoz´ı lemma. Jedno Vi m˚ uˇze b´ yt v mnoha dvojic´ıch, tak ho rozdˇel´ıme v´ıcekr´ at. To vytvoˇr´ı nov´e rozdˇelen´ı. To dostateˇcnˇe zvedne potenci´al. l , kde l jsou Pot´e to nasek´ am jeˇstˇe hodnˇe tak, aby byly stejnˇe velik´e ( 4m p˚ uvodn´ı velikosti) a co zbyde, to nacpu do odpadu.

-

16

Vyb´ıravost

Definice viz barevnost. Pozorov´ an´ı 4 χ ≤ χl . Pozorov´ an´ı 5 Existuj´ı grafy, kde je to ostr´e (napˇr. K3,3 ). Tvrzen´ı 5 Existuje rovinn´y graf s vyb´ıravost´ı alespoˇ n 5. Na cviˇcen´ı. 37

Vˇ eta 24 (Thomasen) Kaˇzd´y rovinn´y graf je 5-vyb´ırav´y. D˚ ukaz: Dok´aˇzeme silnˇejˇs´ı: Necht’ G je souvisl´ y graf vnoˇren´ y do roviny. D´ale, necht’ v1 , . . . , vk jsou vrcholy vnˇejˇs´ı stˇeny takov´e, ˇze v1 a v2 jsou sousedn´ı. Pro kaˇzd´e pˇriˇrazen´ı seznam˚ u splˇ nuj´ıc´ı: • |L(V1 )| = |L(V2 )| = 1, L(V1 ) 6= L(V2 ). • |L(V3 )| . . . |L(Vk )| = 3. • ∀v ∈ V (G)\ {v1 , . . . , vk } , |L(w)| = 5. Pak existuje L-obarven´ı. Udˇel´ ame to indukc´ı podle poˇctu vrchol˚ u. Pokud nen´ı 2-souvisl´ y, tak m´ a artikulaci. Ta je bud’ venku, pak to rozˇstˇep´ım, nˇekde zbydou pˇredbarven´e, udˇel´ ame z indukce. Ve druh´e se mi pˇredbarv´ı vrchol, pˇredbarv´ım jeˇstˇe druh´ y a hotovo. Kdyˇz ˇzije uvnitˇr, potom je to podobn´e, barv´ım prvnˇe vnˇejˇsek. Nad´ale je vnˇejˇs´ı stˇena ohraniˇcena kruˇznic´ı C := v1 , . . . , vk . Kdyby mˇela chordu, tak ji m˚ uˇzu okolo t´e chordy pˇrestˇrihnout. Nyn´ı n´am tedy zbyla venku kruˇznice bez chord. Necht’ to napˇred nen´ı troj´ uheln´ık. Odtrhneme v3 (prvn´ı nepˇredbarven´ y). Tomu zb´ yvaj´ı aˇz 2 nepouˇzit´e barvy, α, β. Od vˇsech jeho soused˚ u (kromˇe v2 a v4 ) sebereme α, β. Ty se dostanou na vnˇejˇs´ı stˇenu, staˇc´ı jim tedy 3 barvy. Kdyˇz je to troj´ uheln´ık, tak to jde tak´e, obdobnˇe. v3 jeˇstˇe jedna barva nakonec zbude (v4 mohlo jednu seˇzrat). Zaˇc´atek indukce funguje kdekoliv pod 5 vrchol˚ u. Orientace grafu bude pˇriˇrazen´ı nˇejak´eho smˇeru kaˇzd´e hranˇe. Orientovan´ y graf je jadern´ y, pokud kaˇzd´ y jeho indukovan´ y podgraf m´ a j´adro. J´ adro je takov´a nez´ avisl´a mnoˇzina, do kter´e vede hrana z kaˇzd´eho jin´eho. Lemma 12 Pokud G m´ a jadernou orientaci s maxim´ aln´ım v´ystupn´ım stupnˇem nejv´yˇse k − 1, pak G je k-vyb´ırav´y. D˚ ukaz: Budeme dokazovat silnˇejˇs´ı, tedy ˇze mi budou staˇcit seznamy d´elky deg− (v)+ 1. Indukc´ı podle poˇctu vrchol˚ u. Pro jednovrcholov´ y je zˇrejm´e. 38

Necht’ γ je libovoln´a barva vyskytuj´ıc´ı se v nˇejak´em seznamu L(v). W oznaˇc´ım vˇsechny vrcholy, co maj´ı v seznamu barvu γ. Podgraf G [W ] m´ a j´adro A. Vrchol˚ um A pˇriˇrad´ım barvu γ, odeber tyto vrcholy a γ ze seznam˚ u. Vˇ eta 25 (Galvinova) Necht’ G je bipartitn´ı graf. Potom jeho hranov´ a vyb´ıravost ′ ′ χl = χ = ∆. D˚ ukaz: Nalezneme jadernou orientaci line-grafu s ∆− = ∆(G) − 1.

Obarv´ıme hrany p˚ uvodn´ıho pomoc´ı barev 1 . . . ∆. V jedn´e partitˇe zorientuji hrany v line grafu od menˇs´ı barvy ke vˇetˇs´ı, v druh´e partitˇe naopak. Je tˇreba dok´azat jadernost. Vezmeme indukc´ı podle velikosti. Vybereme kandid´ ata – v lev´e partitˇe si vybereme hranu s nejvˇetˇs´ım ˇc´ıslem. Pokud je to nez´ avisl´e, tak m´ am j´adro. Jednu ze z´avisl´ ych odeberu (tu vˇetˇs´ı), najdu j´adro zbytku. To je j´adrem i naˇs´ı mnoˇziny. Rozeberou se pˇr´ıpady. -

17

Π2 -´ uplnost

Probl´ em je nˇeco, kde m´ am vstup a oˇcek´avan´ y v´ ystup je ano/ne. Probl´em P je ve tˇr´ıdˇe P , pokud existuje polynomi´ alnˇe vyˇc´ısliteln´ y predik´ at Q takov´ y, ˇze P(x) = Q(x). Probl´em P je ve tˇr´ıdˇe N P , pokud existuje polynomi´ alnˇe vyˇc´ısliteln´ y predik´ at Q a polynom q, P(x) = ∃y, |y| ≤ q(|x|); Q(x, y). Tak´e se tomu ˇr´ık´ a Σ1 ˇ ık´ co − N P je takov´ y, ˇze doplnˇek je N P . R´ a se jim Π1 .

Probl´em P je ve tˇr´ıdˇe Πk , pokud existuje polynomi´ alnˇe vyˇc´ısliteln´ y k+1-´ arn´ı predik´ at Q a polynom q takov´ y, ˇze P(x) = ∀y1 ≤ q(|x|)∃ . . . Q(x, y1 , y2 , . . .) (prostˇe se ty ∃ a ∀ se stˇr´ıdaj´ı). Toto je vˇsechno v P − space.

Tˇr´ıda rozhodovac´ıch probl´em˚ u A, pak probl´em P ∈ A je A-´ upln´ y, pokud ′ ∗ ∀P ∈ A existuje polynomi´ alnˇe vyˇc´ısliteln´ a funkce, ˇze ∀x ∈ 2 ; x ∈ P ′ ⇔ f (x) ∈ P. Jeden z Π2 u ´pln´ ych probl´em˚ u je urˇcen´ı, jestli: ∀x1 , . . . , xn ∃xn+1 , . . . , x2n 39

m  ^

i=1

ǫi

ǫi

ǫi

xi11 ∨ xi22 ∨ xi33



To lze dok´azat zak´ odov´an´ım Turingova stroje. upln´y Vˇ eta 26 (Erd¨ os,Rabin,Taylor) 3-Vyb´ıravost bipartitn´ıch graf˚ u je Π2 -´ probl´em. D˚ ukaz: To, ˇze je ve tˇridˇe Π2 je vidˇet. Je potˇreba dok´azat i Π2 -tˇeˇzk´ y. Prozat´ım si budu diktovat, jestli vrchol dostane seznam velikosti 2 nebo 3 (pozdˇeji pˇrevedu vˇsechno na 3). Budeme dˇelat gadgety. Prvn´ı nazveme polopropag´ ator

Kaˇzd´e pˇredbarven´ı vstupu lze rozˇs´ıˇrit. Vˇzdy barva zb´ yv´ a. Pro kaˇzd´e obarven´ı v´ ystupu existuje nejv´ yˇse jedna barva, kter´a je nekompatibiln´ı (kdyby se dala na vstup, tak by neˇsla rozˇs´ıˇrit). To dok´aˇzu rozborem pˇr´ıpad˚ u a t´ım, ˇze K2,3 je 2-vyb´ırav´ y. Existuj´ı seznamy takov´e, ˇze existuje pˇredbarven´ı vstupu, kter´e je jednoznaˇcnˇe rozˇsiˇriteln´e (viz barviˇcky v obr´ azku). Propag´ ator vypad´ a tak, ˇze nalep´ı dva polopropag´atory za sebe. Kaˇzd´e pˇredbarven´ı vstupu lze rozˇs´ıˇrit. Plyne z polopropag´atoru. Existuje nejv´ yˇse jedna barva vstupu, kter´a je nekompatibiln´ı s nˇejakou barvou v´ ystupu. To se udokazuje nakreslen´ım, kter´e barvy jsou navz´ ajem nekompatibiln´ı a rozborem pˇr´ıpad˚ u. Existuj´ı seznamy takov´e, ˇze existuje pˇredbarven´ı vstupu, ˇze jej lze jednoznaˇcnˇe rozˇs´ıˇrit. Plyne z polopropag´atoru. Multipropag´ ator je toto: 40

Kaˇzd´e pˇredbarven´ı vstupu lze rozˇs´ıˇrit. Z propag´atoru. Existuje nejv´ yˇse jedna barva vstupu, ˇze je nekompatibiln´ı s nˇejak´ ym pˇredbarven´ım v´ ystup˚ u. Taky uargumentuju z propag´atoru. Existuj´ı seznamy a pˇredbarven´ı, ˇze lze jednoznaˇcnˇe rozˇs´ıˇrit. Z propag´atoru. Exist´ık je toto:

Pˇredbarven´ı z kaˇzd´e strany/vstupu (modr´ y) lze rozˇs´ıˇrit. Je vidˇet. Provˇ sechn´ık je toto:

Existuj´ı seznamy, ˇze si jednu koncovou barvu vynut´ım (zelen´a v pˇr´ıkladu nalevo). Alespoˇ n jeden z konc˚ u lze obarvit libovolnou jeho barvou. Je to oˇcividnˇe 2-vyb´ırav´e. To, ˇze jeden zbude, jak chci, je tak, ˇze kdyˇz jeden je zak´ azan´ y, urˇcitˇe m´ a druh´ y povolen´e oboje. Nyn´ı jsem dostal formuli. Udˇel´ am si exist´ıky pro existenˇcn´ı promˇenn´e, provˇsechn´ıky pro provˇsechnov´e promˇenn´e. Na kaˇzd´e v´ ystupy si povˇes´ım multipropag´ ator. Za kaˇzdou klauzuli m´ am vrchol, spoj´ım se spr´ avn´ ymi v´ ystupy multypropag´ ator˚ u.

41

Toto je bipartitn´ı. Kaˇzd´ y gadget je bipartitn´ı s´ am o sobˇe. Vˇsechny v´ ystupy z multipropag´ atoru jsou ve stejn´e (plyne z propag´atoru a u nˇej z polopropag´ atoru), exist´ık a provˇsechn´ık maj´ı konce ve stejn´e, to jde pospojovat. Vytvoˇr´ım polynomi´ alnˇe, to je vidˇet. Pˇredpokl´ adejme, ˇze je formule nesplniteln´ a. ∃x1 , . . . , xn takov´e, ˇze xn+1 , . . . , x2n nejdou doplnit, aby platilo. Vynut´ım si tedy vˇzdy jednu barvu na bud’ pozitivn´ım (kdyˇz je false) nebo negativn´ım (true) konci provˇsechn´ıka. Multipropag´ ator˚ um d´am vynucenou barvu (nad nimi). U exist´ık˚ u d´am vˇsude stejn´e seznamy A, B. Na exist´ıka nastav´ım multiplik´ atory takov´e, ˇze na jednom vynut´ı barvy kdyˇz A, na druh´em kdyˇz B (takˇze si to mus´ı vybrat, kter´ y konec vynut´ı). Klauzule dostane tu barvu, kterou m´ a na vynucen´em konci, pokud m´ a nˇeco nevynucen´e, tak cokoliv (ta uˇz nekouˇse). Kdyby se to povedlo obarvit, tak to znamen´a, ˇze kaˇzd´ a klauzule m´ a nevynucen´ y koneˇcek, potom ale m˚ uˇzu podle n´ı zvolit promˇennou. Pokud je splnˇen´ a, tak hled´am obarven´ı. Multipropag´ator m´ a nejv´ yˇse jednu ˇspatnou barvu na vstupu, tak si zvol´ım tu kter´a nen´ı ˇspatnˇe, rozˇs´ıˇr´ım to pro druhou stranu (tam moˇzn´ a nˇeco vynut´ım). T´ım jsem navolil ohodnocen´ı u provˇsechn´ıtek, dostanu ohodnocen´ı u exist´ıtek, na nich si vyberu dobrou barvu. A kaˇzd´ a klauzule je uˇz bud’ dobˇre obarven´ a, nebo mus´ı v´est do neobarven´eho (a rozˇsiˇriteln´eho) konce, a hur´a. Nyn´ı potˇrebuji nadˇelat seznamy d´elky 3. Vezmu 9 kopi´ı tˇechto graf˚ u. Potom vezmu dva nov´e vrcholy, jeden spoj´ım se vˇsemi 2 v jedn´e partitˇe, k druh´emu z druh´e partity. Tˇem d´am barvy A, B, C, kaˇzd´e kopii dopln´ım jednu disjunktn´ı dvojici barev do seznam˚ u. Pokud je obarviteln´ y ten p˚ uvodn´ı, tak ty dva nov´e dostanou libovolnou barvu. Pokud ale neˇsly obarvit, nov´ ym vyberu barvu a jednu dvojici t´ım zabiju, tedy tomu zbyly jen ty p˚ uvodn´ı 2 barvy a to neˇslo obarvit. 42

-

18

Ramseioviny

Budeme pracovat s abecedou A, |A| = t.

Ak je mnoˇzina slov d´elky k, ale tak´e k-krychle nad A. a = (a1 , a2 , . . . , ak ) ∈ Ak je k-ˇretˇezec.

Pˇrid´ ame hvˇezdiˇcku – ˇzol´ıka. Pokud bude k-ˇretˇezec nazv´ an koˇ renem, pokud obsahuje alespoˇ n jednu hvˇezdiˇcku. α(s) bude nahrazen´ı vˇsechny hvˇezdiˇcky znakem s. Kdyˇz m´ ame α koˇren, potom lα pˇ r´ımka je mnoˇzina prvk˚ u α(0), α(1), . . . , α(t). Vˇ eta 27 (Haywlet-Juwet) ∀t, r ∈ N∃N = H(t, r) ∈ N takov´e, ˇze ∀ obarven´ı χ : AN → [r] existuje monochromatick´ a kombinatorick´ a pˇr´ımka. D˚ ukaz: Indukc´ı, zafixujeme r, podle t. Pro t = 1 je jednoduch´e, jednoprvkov´a krychle m´ a jednobarevn´ y prvek. Pi−1 N +n P n j=1 j . H(t, r) := N := i = 1n Ni . Nyn´ı zvol´ıme N1 := rt , Ni := rt

Sousedi jsou takov´e prvky, kter´e jsou vˇsude stejn´e, jen jeden m´ a na jednom m´ıstˇe 0 a druh´ y 1. Tvrzen´ı 6 ∃ posloupnost koˇren˚ u τ1 , τ2 , . . . , τn nad A ∪ {∗} takov´e, ˇze |τi | = Ni a χ(τ (a)) = χ(τ (b)) pro a, b sousedi a, b ∈ An . -

18.1

Aplikace

Vˇ eta 28 (Vanclav Waerden) ∀r, t ∈ N∃N = W (r, t) takov´e, ˇze ∀ obarven´ı {1 . . . N } existuje monochromatick´ a aritmetick´ a posloupnost o t ˇclenech. D˚ ukaz:

-

43