Informace k prednasce "Kombinatorika a grafy I" (zimni semestr 2002/2003; Martin Loebl, Jiri Matousek, KAM)

Zkouska: 22. zari od 2 hodin, prihlasovani zde

Typograficke konvence

• x_1 znaci x s dolnim indexem 1. a_{ij} znamena a s dolnimi indexy i a j. x^2 je x na druhou (tedy s exponentem 2).
• x \in X znamena "x nalezi do X", tedy "\in" nahrazuje znak pro nalezeni do mnoziny (stylizovane epsilon).
• V prednasce a v literature se mnozina vsech realnych cisel znaci pismenem R specialniho typu (na prednasce s dvojitou svislou nozkou). Na teto strance bude pouze obycejne R. Podobne nektera recka pismenka zde budou nahrazena latinskymi.

Prednaska 14/X/2002: Prostor kruznic a prostor rezu nad Z_2.

• POZNAMKA. Dosud kruznice byla definovana jako posloupnost vrcholu a hran s jistymi vlastnostmi. Nyni budeme mnozinu hran kruznice tez nazyvat kruznici. Nasledujici lemma ma tudiz smysl.
• LEMMA. Kazda neprazdna eulerovska mnozina je disjunktnim sjednocenim kruznic.
• DUKAZ. Kazda neprazdna eulerovska mnozina E' obsahuje kruznici, a vynechame-li ji z E', dostaneme opet eulerovskou mnozinu.

Uvedomte si, ze charakteristicky vector je mozno tez chapat jako funkci z E do {0,1}.

Oznacme K mnozinu vsech charakteristickych vektoru eulerovskych mnozin. Budeme potrebovat jeste jeden pojem: kostra grafu G (ne nutne souvisleho) je maximalni acyklicka mnozina hran. Je-li T kostra a e hrana mimo T, potom vime ze 'T sjednoceno s {e}' obsahuje jedinou kruznici: rikejme ji elementarni kruznice a oznacme ji C_e.

• VETA (O prostoru kruznic). K je vektorovy prostor nad Z_2 dimenze |E|-|V| +k, kde k je pocet komponent G. Nazyva se prostor kruznic. Necht T je libovolna kostra. Mnozina charakteristickych vektoru elementarnich kruznic tvori bazi K.
• DUKAZ. Necht A,B patri do K a C je symetricka diference A,B. Potom C tez patri do K. To znamena ze K je uzavrena na scitani v Z_2 a trivialne je tez uzavrena na nasobeni prvkem ze Z_2. K je tudiz vektorovy prostor. Vektory v_{C_e} jsou linearne nezavisle, protoze v_{C_f}(e)=0 prave kdyz f=e. Zbyva dokazat, ze generuji celou K. i Necht A je eulerovska a necht B je symetricka diference vsech C_e takovych, ze e lezi v A-T. Samozrejme B patri do K a B je podmnozina 'A sjednoceno s T' a B obsahuje A-T. Necht D je symetricka diference A,B. Potom D je tez z K ale D je podmnozina T, coz znamena ze D je prazdna mnozina a A=B.

• VETA. K je jadro D (nad Z_2), tj. K={v; Dv=0 mod 2}.

• VETA. R je mnozina vsech charakteristickych vektoru rezu.
• DUKAZ. Radek matice D indexovany vrcholem v je charakteristickym vektorem rezu urceneho mnozinou V'={v}. Navic symetricka diference rezu je tez rez, urceny symetrickou diferenci urcujicich mnozin vrcholu. Tato dve pozorovani jednoduse dokazuji vetu.

• Doporucene priklady na cviceni: pojem ortogonalniho doplnku, otazky za 11.4 v knize Matousek, Nesetril; rovinna dualita a kruznice, rezy.

Prednaska 21/X/2002: Prostor kruznic a prostor rezu nad R.

• DUSLEDEK. Graf G ma 2^{|E|-|V|+k} eulerovskych podmnozin.
• POZOROVANI. Necht G je 2-souvisly rovinny graf. Uvazme libovolne rovinne nakresleni G. Jak vime, kazda stena je ohranicena kruznici. Necht F je mnozina vsech kruznic ohranicujicich steny, a necht S je libovolny prvek z F. Potom charakteristicke vektory prvku F-{S} tvori bazi prostoru kruznic.
• DUKAZ. Z Eulerovy formule plyne, ze mame spravny pocet vektoru, a zbyva dokazat jejich nezavislost. Bez ujmy na obecnosti muzeme predpokladat, ze S je vnejsi stena (predstavime si zvolene nakresleni na kouli). Uvedomime si, ze prvky F-{S} lze ocislovat S_1,...,S_f tak ze pro kazde i, S_i neni podmnozina sjednoceni S_j, j mensi nez i. Z toho ihned plyne linearni nezavislost.

• PRIKLAD. Necht C je kruznice grafu G. Prochazejme C libovolnym smerem. Jsme-li prave na hrane e a prochazime ji proti orietaci v O, definujme f(e)=1; prochazime-li e po smeru v O, necht f(e)=-1. Nakonec necht f(w)=0 pro kazdou hranu w nelezici na C. Takto definovana funkce je cirkulace.

• VETA. K_r tvori jadro matice D(O).
• DUKAZ. Primo z definic.

• VETA. R_R je presne mnozina potencialovych rozdilu.
• DUKAZ. Divejme se na dp jako na vektor a vsimneme si ze dp=-sum_{v vrchol} p(v)r_v, kde r_v je radek D(O) indexovany vrcholem v. Toto pozorovani ihned dokazuje vetu.
• PRIKLAD. Necht V' je podmnozina vrcholu. Definujme p(v)=1 pro v \in A, a p(v)=0 jinak. Necht E' je rez urceny V'. Potom dp(e)=0 pro e mimo E', dp((x,y))=1 pro x \in A, y \in V-A a dp((x,y))=-1 pro y \in A, x \in V-A.
• VETA. dim(R_R) = |V|-k, kde k je pocet komponent G.
• DUKAZ. dim(R_R) je hodnost matice D(O), coz je maximalni pocet linearne nezavislych sloupcu D(O). Staci ukazat ze mnozina sloupcu je linearne nezavisla, prave kdyz jeji indexova mnoxina je acyklicka v G. Mnozina obsahujici kruznici v G indexuje zavislou mnozinu sloupcu dle prikladu cirkulace. Necht E' je acyklicka podmnozina hran G ktera indexuje zavislou mnozinu sloupcu D(O), t.j. sum_{e \in E'} a_e s_e=0, kde s_e znaci sloupec D(O) indexovany e a navic vsechna a_e jsou nenulova. Je-li ale E' neprazdna, indukuje stupen 1 u alespon jednoho vrcholu v, a tudiz sum_{e \in E'} a_e s_e(v)=a_w, kde w je jedina hrana E' incidencni s v. Tudiz nutne takova E' je prazdna mnozina, coz dokazuje zbyvajici tvrzeni.

Prednaska 4/XI/2002: Toky v sitich

• DUSLEDEK. K_R(O) je vektorovy prostor dimenze |E|-|V|+k a R_R(O) je vektorovy prostor dimenze |V|-k. Necht T je libovolna kostra G. Potom cirkulace dane elementarnimi kruznicemi vzhledem k T tvori bazi K_R(O). Necht O' je libovolna jina orientace G. Potom K_R(O) a K_R(O') jsou izomorfni, a prirozeny izomorfismus je urceny elementarnimi kruznicemi vzhledem k T. Tudiz i R_R(O) a R_R(O') jsou izomorfni. Tyto prostory tedy nezavisi na zvolene orientaci, a nazyvame je prostor kruznic a prostor rezu grafu G nad realnymi cisly.

Toky v sitich

• DEFINICE. Sit je (G=(V,E),r,s,c) kde G je orientovany graf, r,s dva ruzne vrcholy grafu G a c je funkce z E do nezapornych realnych cisel.
• DEFINICE. Tok v siti je kazda funkce z E do nezapornych realnych cisel, splnujici f(e)<=c(e) pro kazdou hranu e\in E a f^v=0 pro kazdy vrchol v ruzny od r,s. Velikost toku f je f^s.
• Rekneme ze R\subset V je oddelujici, jestlize r\in R,s\notin R. Oznacme d(R) mnozinu vsech orientovanych hran, ktere zacinaji ve vrcholu z R a konci mimo R.
• POZOROVANI. Necht R je oddelujici. Potom f(d(R))-f(d(V-R))=f^s.
• DUKAZ. f(d(R))-f(d(V-R))=\sum_{v\in V-R}f^v = f^s.
• Uloha, kterou chceme zkoumat, je nalezt tok maximalni velikosti. Uvedomme si nejprve, ze tuto ulohu lze zapsat pomoci linearnich nerovnosti (takovemu zapisu se rika linearni program): Definujme novy orientovany graf G'=(V,E'), E' vznikne z E pridanim hrany (s,r): byla-li uz v E, neprida se nic. Definujme tez c((s,r)) jako 'dostatecne velke cislo'. Potom uloha maximalniho toku je ekvivalentni uloze
• max x_{(s,r)}; D(G')x=0, x<=c, x>=0.
• VETA (o maximalnim toku a minimalnim rezu; hlavni veta o tocich). Necht (G=(V,E),r,s,c) je sit. Potom
  max {f^s; f tok} = min {c(d(R)); R oddelujici}.
  Slovy, velikost maximalniho toku z r do s se rovna velikosti minimalniho rezu oddelujiciho r od s.
• DUKAZ.
  • Uvedomme si nejprve, ze max <= min, protoze pro libovolny tok f a oddelujici mnozinu R mame f^s= f(d(R))-f(d(V-R))<=f(d(R))<=c(d(R)).
  • Abychom ukazali rovnost, staci najit tok f a oddelujici R ze f^s=c(d(R)). Necht f je tok. Definujme pomocny graf G(f)=(V,E(f)) a def(e), e\in E(f), predpisem: (v,w)\in E(f), jestlize (v,w)\in E a f((v,w))< c((v,w)), nebo jestlize (w,v)\in E a f((w,v))>0. V prvnim pripade definujeme def((v,w))=c((v,w))-f((v,w)), a ve druhem pripade def((v,w))=f((w,v)).
  • POZOROVANI. f neni maximalni prave tehdy, kdyz G(f) ma orientovanou cestu z r do s.
  • DUKAZ POZOROVANI. Existuje-li takova cesta P, necht D je min {def(e);e\in P}. Zmenme f na f' takto: je-li hrana e\in P orientovana stejne v E jako v E(f), polozme f'(e)=f(e)+D, a je-li hrana e\in P orientovana v E a v E(f) opacne, polozme f'(e)=f(e)-D. Potom f' je tez tok a f'^s=f^s+D. Naopak, necht takova cesta neexistuje. Necht R je mnozina vsech vrcholu, do nichz vede z r orientovana cesta v G(f). Potom R je oddelujici a nutne c(d(R))=f(d(R)) a f(d(V-R))=0, a tedy c(d(R))=f^s. Tim je pozorovani dokazano. Navic aplikujeme-li pozorovani na maximalni tok a vyuzijeme-li konstrukce R v druhe casti dukazu pozorovani, dokoncime dukaz vety.
• POZNAMKY
  • Je-li c celociselna, potom existuje tok maximalni velikosti, ktery je tez celociselny. Toto nahledneme, uvedomime-li si, ze dukaz Pozorovani poskytuje algoritmus na nalezeni maximalniho toku: Vyjdeme z toku rovnemu 0 na kazde hrane, a budeme ho postupne zlepsovat pomoci zlepsujicich cest z Pozorovani. Je-li c celociselna, muzeme vzdy mit D cele cislo, a tudiz kazdy z toku, ke kterym se dostaneme, bude celociselny. Jedine si zbyva uvedomit dulezitou vec: nas algoritmus najde maximalni tok po konecne mnoha krocich.
  • V pripade ze c je racionalni, nas algoritmus take skonci po konecne mnoha krocich a najde maximalni tok. Napriklad je mozne vynasobit vsechna c(e) jejich spolecnym jmenovatelem a pouzit pozorovani pro celociselne c.
  • Je-li c racionalni, nemusi existovat maximalni tok, ktery je navic celociselny.
  • Prirozenou otazkou je, jak dobry je nas algoritmus (c racionalni). Jednoduchy priklad (K_4 bez hrany, vrcholy stupne 2 jsou r,s, hrany incidentni s r orientovany od r a jejich kapacita je M, hrany incidentni s s orientovany do s a jejich kapacita je M, zbyla hrana orientovana libovolne a s kapacitou 1, M je velke cislo, uvazme vzdy zlepsujici cestu delky 3) ukazuje, ze nas algoritmus prilis zavisi na c.
  • Tvrzeni bez dukazu: modifikujeme-li nas algoritmus tak, ze uvazime v G(f) vzdy nejkratsi cestu z r do s, pak najdeme maximalni tok po nejvyse |V|.|E| krocich.
  • Co kdyz pripustime i iracionalni kapacity hran? Existence maximalniho toku plyne z kompaktnosti (spojita funkce na kompaktni mnozina nabyva sveho minima; nase mnozina = podmnozina R^E odpovidajici vsem tokum, nase spojita funkce = velikost toku). Platnost vety o maximalnim toku a minimalnim rezu se odvodi limitnim argumentem (kdyby veta neplatila pro nejake realne kapacity, nebude platit ani pro dostatecne blizke racionalni kapacity - cviceni).
• MENGEROVA VETA 1. Necht D je orientovany graf a x\neq y vrcholy D. Potom maximalni pocet hranove disjunktnich orientovanych cest z x do y je roveni
  min {|d(R)|; x\in R, y\notin R}.
• DUKAZ. Uvazime sit (D,x,y,c), kde c=1, a pouzijeme vetu o maximalnim toku.
• MENGEROVA VETA 2. Necht G je (neorientovany) graf a x\neq y vrcholy G. Potom maximalni pocet hranove disjunktnich cest mezi x, y je roven
  min {|W(R)|; R podmnozina vrcholu, x\in R, y\notin R},
  kde W(R) je mnozina hran s presne jednim koncem v R.
• DUKAZ. Definujeme orientovany graf D z G tak, ze se zdvoji kazda hrana a dve kopie kazde hrany se orientuji opacne. Potom pouzijeme predeslou vetu.

Prednaska 11/XI/2002: Souvislost grafu. Ramseyovy vety.

• MENGEROVA VETA 3 (orientovana, vrcholova): Necht G je orientovany graf, a necht x a y jsou jeho vrcholy, kde (x,y) neni hrana. Pak maximalni pocet vrcholove disjunktnich orientovanych cest z x do y (disjunktnich az na x,y) je roven minimalnimu poctu vrcholu, po jejichz vynechani nezbude zadna orientovana cesta z x do y.
• Dukaz: kazdy vrchol z ruzny od x,y nahradit dvema vrcholy v_1,v_2, hrana (v_1,v_2) s jednotkovou kapacitou, a dale hrany, ktere vchazely do v, budou nyni vchazet do v_1, a hrany, ktere vychazely z v, budou nyni vychazet z v_2, kapacita = velke cislo. Pak pouzit vetu o maximalnim toku a minimalnim rezu.
• MENGEROVA VETA 4 (neorientovana, vrcholova): Necht G je neorientovany graf, a necht x a y jsou jeho vrcholy, kde {x,y} neni hrana. Pak maximalni pocet vrcholove disjunktnich cest z x do y (disjunktnich az na x,y) je roven minimalnimu poctu vrcholu, jejichz vynechani oddeli x od y.
• Dukaz: prejit k orientovane verzi nahrazenim kazde hrany dvojici opacne orientovanych hran.
• DEFINICE. Graf G je k-souvisly, ma-li aspon k+1 vrcholu a po odebrani libovolnych k-1 vrcholu zustane souvisly. Graf G je hranove k-souvisly, jestlize po odebrani libovolnych nejvys k-1 hran zustane souvisly.
• VETA (Mengerova veta bez cisla). Graf G je k-souvisly, prave kdyz ma aspon 2 vrcholy, a mezi libovolnymi dvema vrcholy existuje k disjunktnich (az na konce) cest.
• Dukaz: snadne z Mengerovy vety 4, ale je treba trochu rozmyslet. Specialne, uvazit pripad, kdy chceme k cest z x do y a {x,y} je hrana (muzeme tu hranu vymazat, najit k-1 cest,a pridat ji zpatky).
• Podobna veta plati pro hranovou souvislost (cviceni).
• Pripomente si z 1. rocniku (nebo nastudujte ve skriptech) vytvareni 2-souvislych grafu (lemma o usich)

Uvod do Ramseyovy teorie

• Na kazdem vecirku s aspon 6 lidmi jsou 3, kteri se navzajem znaji, nebo 3, kteri se navzajem neznaji (kde relaci "znat se" povazujeme za symetrickou).
• Ramseyova veta pro grafy: Pro kazde n existuje N takove, ze libovolny graf na N vrcholech obsahuje uplny graf velikosti n nebo nezavislou mnozinu velikosti n. Trochu obecneji: jsou-li hrany K_N obarveny r barvami, existuje jednobarevny podgraf K_n (kde N=N(n,r)).
• Dukaz (pro r=2 barvy, cervenou a modrou): Oznacme R(k,l) minimalni N takove, ze kazdy K_N, jehoz hrany jsou libovolne obarveny cervene a modre, obsahuje cerveny K_k nebo modry K_l. Plati R(k,l)<= R(k-1,l)+R(k,l-1) (uvazme jeden vrchol, bud je aspon R(k-1,l) vrcholu s nim spojeno cervenymi hranami, nebo je aspon R(k,l-1) vrcholu s nim spojeno modrymi hranami), odtud R(k,l)<= (k+l-2 nad k-1).
• Doporucene cviceni: jak odvodit pripady r=3,4,... z pripadu r=2.
• Ramseyova veta pro systemy p-tic: Pro kazde n,r,p existuje N takove, ze je-li X N-prvkova mnozina, a kazda p-prvkova podmnozina X je obarvena nekterou z barev 1,2,...,r, potom existuje n-prvkova podmnozina Y mnoziny X takova, ze vsechny p-prvkove podmnoziny Y jsou obarveny stejnou barvou. Zapis (sipkova notace): N -> (n)_r^p.
• Dukaz (tezsi): pro r=2 barvy, indukci podle p. Necht X je obrovske, jeho p-tice jsou libovolne obarveny, veta plati pro p-1. Poloz X_0:=X a udelej nasledujici krok pro i=1,2,...,2n-1.
  • Zvol x_i\in X_{i-1} libovolne, obarvi vsechny (p-1)-prvkove podmnoziny mnoziny X_{i-1}\{x_i}, kde (p-1)-tice S dostane barvu p-tice S+{x_i}.Podle indukce existuje dosti velka podmnozina X_{i} mnoziny X_{i-1}\{x_i}, v niz vsechny (p-1)-tice maji stejnou barvu b_i.
  Nektera z barev se objevi jako b_i aspon n-krat, treba cervena; pak {x_i: b_i=cervena} je hledana n-prvkova Y.
• Poznamka: Ramseyova cisla (minimalni N v takovychto vetach, napriklad R(k,l)) jsou pomerne velka, a je znamo pouze nekolik malo presnych hodnot a neprilis dobre odhady.
• Priklad aplikace, doporucene cviceni: Kazda dostatecne velka mnozina bodu v rovine v obecne poloze (zadne 3 body na primce) obsahuje mnozinu vrcholu konvexniho k-uhelnika (pro k=4 staci 5 bodu, a pro vetsi k lze pouzit Ramseyovy vety pro ctverice).
• Poznamka, vety Ramseyova typu: Mame-li dostatecne velkou strukturu daneho typu, najdeme v ni "pravidelnou" podstrukturu dane velikosti ("totalni chaos neni mozny").

Prednaska 25/XI/2002: Teorie parovani.

• Parovani je mnozina disjunktnich hran. Necht M je parovani grafu G. Cesta P se nazyva M-stridava, obsahuje-li stridave hrany z M a mimo M, a nazyva se M-zlepsujici, jestlize je M-stridava a zacina a konci ve vrcholu nepatricim do zadne hrany M. Parovani je maximalni, ma-li maximalni pocet hran. Parovani je perfektni, jestlize pokryva vsechny vrcholy G. Defekt parovani je pocet nepokrytych vrcholu.
• Uvedomte si dve jednoducha pozorovani:
  • Symetricka diference dvou parovani sestava ze stridavych cest a (nebo) stridavych cyklu vzhledem k obema parovanim.
  • Parovani M je maximalni, prave kdyz neexistuje M-zlepsujici cesta.
• Konigova veta: Maximalni velikost parovani v bipartitnim grafu G=(V,V',E) je rovna minimalni mohutnosti vrcholoveho pokryti. Vrcholove pokryti je podmnozina W vrcholu takova, ze kazda hrana ma aspon jeden vrchol ve W.
• Dukaz: Z vety o tocich. Z G udelejme sit tak, ze pridame ke G dva nove vrcholy r,s (zdroj a stok); z vrcholu r pridame nove orientovane hrany do vsech vrcholu V, z V orientujeme vsechny hrany grafu G do V' a z V' pridame nove orientovane hrany do s. Kapacita hran grafu G necht je 'dostatecne velke cislo', a kapacita novych hran je '1'. Velikost maximalniho toku v teto siti je rovna maximalni velikosti parovani (existuje bijekce mezi toky a parovanimi) a minimalni velikost rezu je rovna minimalni velikosti W s pozadovanou vlastnosti: zde se vyuzije toho, ze zadna stara hrana nemuze byt v minimalnim rezu, protoze ma velikou kapacitu.
• Preformulovani: Maximalni velikost nenulove transverzaly matice je rovna minimalnimu poctu linii (linie je radek nebo sloupec) nutnych k pokryti vsech nenulovych prvku matice.
• Hallova veta: Necht G=(V,V',E) je bipartitni graf. G ma parovani velikosti |V| prave, tehdy kdyz pro kazdou podmnozinu W mnoziny V, |N(V)| neni mensi nez |V|; N(V) oznacuje mnozinu vsech vrcholu spojenych hranou s aspon jednim vrcholem z W.
• Dukaz: Z toku v sitich stejne jako Konigova veta.
• Preformulovani: Mnozinovy system (A_i;i\in I) ma system ruznych representantu (SRR), prave kdyz pro kazdou podmnozinu J mnoziny I, |J| neni mensi nez pocet prvku sjednoceni A_i, i\in J. SRR je prosta funkce f z I do sjednoceni vsech A_i splnujici pro kazde i ze f(i)\in A_i.
• Tuttova-Bergeova veta: Necht G=(V,E) je graf a m(G) znaci velikost maximalniho parovani grafu G. Je-li A podmnozina vrcholu, necht G-A oznacuje graf vznikly z G vynechanim vsech vrcholu z A a necht oc(G-A) znaci pocet komponent souvislosti G-A s lichym poctem vrcholu. Veta rika, ze m(G)=min 1/2(|V|-oc(G-A)+ |A|); min je pres vsechny podmnoziny vrcholu A.
• Dukaz: Nejprve si uvedomte, ze m(G) je nejvyse rovno prave strane. Tudiz staci najit parovani M a mnozinu A, pro nez se ve formuli nabyva rovnost (stejne jako pri dukazu vety o tocich a rezech). Postujeme takto: Necht C je kruznice liche delky (dale licha kruznice) grafu G. Potom G+C bude znacit graf vznikly stazenim C do jednoho vrcholu (ktery budeme tez znacit C).
• Pozorovani 1: Pro kazde parovani M' grafu G+C=G' existuje parovani M grafu G s vlastnostmi: M je podmnozina M' sjednoceno s C a defekt M (v G) je roven defektu M' (v G'): M sestrojime jednoduse tak, ze k M' pridame vhodne maximalni parovani v C.
• Dusledek: m(G) neni mensi nez m(G+C) + (|V(C)|-1)/2 (uvedomte si: (|V(C)|-1)/2=m(C)).
• Licha kruznice C se nazyva padnouci, jestlize se v predchozim dusledku nabyva rovnost. Vrchol v se nazyva nedulezity, jestlize m(G)=m(G-v).
• Pozorovani 2: Jestlize se pro mnozinu vrcholu A nabyva rovnosti ve formuli Tuttovy-Bergeovy vety, tak kazdy vrchol A je dulezity.
• Dukaz Pozorovani 2: Necht v\in A a G'=G-v. Potom G'-(A-v) ma presne stejne liche komponenty jako G-A, a tudiz m(G') je nutne mensi nez m(G) z jednoduche dokazane nerovnosti v nasi formuli, aplikovane na G'.
• Pozorovani 3. Necht (vw) je hrana G. Jsou-li oba vrcholy v,w nedulezite tak existuje padnouci licha kruznice C, ktera obsahuje hranu (vw). Navic C je nedulezity vrchol grafu G+C.
• Dukaz Pozorovani 3: Necht M_v je maximalni parovani G, ktere zije v G-v, a necht M_w je maximalni parovani G, ktere zije v G-w. Nutne M_v pokryva w a M_w pokryva v, jinak bychom k nim mohli pridat hranu (vw). Uvazme komponentu K symetricke diference M_v a M_w, ktera obsahuje v. K je nutne cesta a v je jeji koncovy vrchol. Jednoduchym rozborem moznych pripadu zjistime, ze druhym koncovym vrcholem je w. Tudiz C=K+(vw) je licha kruznice, ktera je dokonce padnouci, protoze existuje maximalni parovani v G (dokonce dve, M_v a M_w)i, jehoz ze kazda hrana je bud disjunktni s C nebo podmnozina C. Z dusledku pozorovani 1 plyne, ze C je nedulezity vrchol G+C.
• Nyni ukazeme, ze existuji M a A, pro nez se ve formuli vety nabyva rovnost, tj. defekt M =2(oc(G-A)-|A|). Tim bude veta dokazana. Postupujme indukci dle poctu hran. Jestlize G nema zadnou hranu, veta plati pro A=V. V indukcnim kroku necht (vw) je hrana G. Rozlisime dva pripady:
• 1. m(G-v)=m(G)-1. Potom G'=G-v ma A' a M' dle indukcniho predpokladu a muzeme vzit A=A'+v (+ znaci sjednoceni) a libovolne maximalni parovani v G.
• 2. Tudiz predpokladejme ze oba v,w jsou nedulezite. Pro G'=G+C, kde C je kruznice z Pozorovani 3, existuje dle indukcniho predpokladu A',M'. Navic C neni v A' podle Pozorovani 2,3. Uvedomte si, ze proto dostavame oc(G-A')=oc(G'-A'). Zvolme A=A' a necht M vznikne z M' aplikaci Pozorovani 1, t.j. defekt M = defekt M'. Tim je dokazan indukcni krok a cela veta.
• Dusledek(puvodni Tuttova veta): Graf G ma perfektni parovani, prave kdyz oc(G-A) je nejvys rovno A pro kazdou podmnozinu A.

Prednaska 26/XI/2002: Vytvorujici funkce.

• Pocet umisteni m ruznych micu do k ruznych kosu je k^m, stejne jako pocet funkci z mnoziny micu do mnoziny kosu. Zopakujte si, kolik je prostych funkci a funkci na.
• Pocet umisteni m stejnych micu do k ruznych kosu je roven poctu nezapornych celociselnych reseni rovnice x_1+x_2+...+x_k=m. Je to 'm+k-1 nad m', a dukaz je obrazkovy: predstavte si, ze mate m+k-1 objektu v rade, z nich je m micu a k-1 svislych car: cary 'ohranicuji' kose.

• kniha Matousek, Nesetril: 10.2.1, 10.2.2, 10.2.5, 10.2.6.

Prednaska 2/XII/2002: Vytvorujici funkce a pocet koster.

• kniha Matousek, Nesetril: str. 287-290, 7.1, 7.2

Prednaska 3/XII/2002: Pocet koster.

• kniha Matousek, Nesetril: 7.4

Prednaska 9/XII/2002: Konecne projektivni roviny

Prednaska 16/XII/2002 (posledni)

Strucne par veci, na ktere se letos nedostalo

• Latinsky ctverec radu n je tabulka velikosti n x n s cisly 1,2,...,n, v kazdem radku i sloupci je permutace cisel 1,2,...,n. Ortogonalni latinske ctverce: kdyz se daji pres sebe, vznikne v n^2 policcich vsech n^2 moznych dvojic (i,j), i,j=1,2....,n. Veta: Projektivni rovina radu n existuje prave tehdy, kdyz existuje n-1 latinskych ctvercu radu n, z nichz kazde dva jsou ortogonalni. (Viz kniha Matousek, Nesetril, 8.3.)
• Kuratowskeho veta (pripomenuti z 1. rocniku?): Graf G je rovinny, prave kdyz neobsahuje jako podgraf deleni K_{3,3} ani deleni K_5. Pritom deleni grafu vznikne nahrazenim kazde hrany cestou (delky aspon 1).
• Pojem barevnosti grafu, opet opakovani z 1. rocniku.

Hamiltonovske kruznice v grafech

• Hamiltonovska kruznice v grafu je kruznice prochazejici vsemi jeho vrcholy (tedy kazdym vrcholem prave jednou).
• Rozhodnout, zda dany graf ma hamiltonovskou kruznici, je algoritmicky tezky problem (NP-uplny; neni na nej znam polynomialni algoritmus).
• Postacujici podminky pro existenci hamiltonovske kruznice:
  • Veta I: Ma-li kazdy vrchol stupen alespon n/2 , existuje hamiltonovska kruznice.
  • Veta II: Je-li deg u + deg v >= n pro kazde dva ruzne vrcholy u,v netvorici hranu, pak existuje hamiltonovska kruznice.
• Chvatalovsky uzaver grafu G je graf [G], ktery z grafu G vytvorime postupnym pridavanim hran uv takovych, ze deg u + deg v >= n (dynamicky). Takovy uzaver je urcen jednoznacne, to jest, nezavisi na poradi pridavani hran.
• Veta III: G je hamiltonovsky prave tehdy, kdyz [G] je hamiltonovsky.
• Povsimnete si, ze Veta III => Veta II => Veta I.
• Dukaz vety III: Dokazeme lemma - Pokud deg u + deg v >= n a G+{u,v} ma hamiltonovskou kruznici, pak existuje hamiltonovska kruznice i v G.
  • pokud hamiltonovska kruznice v G+{u,v} nepouziva hranu uv, pak je to hamiltonovska kruznice i v G;
  • necht u=u_1,u_2,...,u_n=v je hamiltonovska kruznice v G+{u,v}. Polozme A={i:{u,u_i}\in E(G)} a B={i:{v,u_{i-1}}\in E(G)}. Pak |A|=deg u, |B|=deg v a A i B jsou obsazeny v mnozine {2,3,...,n}, tedy |A sjednoceno B|<= n-1 a |A prunik B| = |A| + |B| - |A sjednoceno B| >= 1. Tedy existuje index i patrici do A i do B. Pak ale u_1,u_2,...,u_{i-1},u_n,u_{n-1},...,u_{i+1},u_i je hamiltonovska kruznice v G.

Uloha obchodniho cestujiciho - TSP

• Vstupem je uplny graf K_n s ohodnocenymi hranami. Otazkou najit okruzni jizdu (tj. hamiltonovskou kruznici) nejmensi mozne celkove vahy. (na prednasce byla uloha formulovana pro libovolny graf, coz pak vedlo ke zmatkum - drzme se tedy uplneho grafu).
• TSP je tezky problem, nebot cerna skrinka pro jeho reseni by davala reseni ulohy hamiltonovske kruznice (je-li dan graf G, dejte vsem hranam vahu 0 a nehranam vahu 1, pak G ma hamiltonovskou kruznici prave kdyz odpoved na TSP noveho grafu je 0).
• Priblizny algoritmus na TSP, pro ohodnoceni splunjici trojuhelnikovou nerovnost (w(x,y) <= w(x,z)+w(z,y)):
  • 1. Najdete minimalni kostru T ohodnoceneho grafu na vstupu.
  • 2. Sestrojte uzavreny orientovany tah S, ktery je nakreslenim jednim tahem symetricke orientace T.
  • 3. Pokud existuje vrchol u, kterym S projde vice nez jedenkrat, zkratte tah S (necht vuw je druhy pruchod vrcholem u, nahradte hrany vu,uw hranou vw).
  • Opakujte krok 3 dokud takovy vrchol u existuje, pak odevzdejte S.
• Tento algoritmus pracuje v polynomialnim case (pokud pouzijete polynomialni algoritmus na hledani minimalni kostry v kroku 1, ale takove znate jiz z prvniho rocniku). Vysledny tah je hamiltonovska kruznice a jeho vaha je w(S) <= 2OPT, kde OPT je velikost optimalniho reseni TSP (to proto, ze reseni TSP bez jedne hrany je specialni kostra, a tedy w(T) <= OPT, v kroku 2 prochazi S kazdou hranu T dvakrat, a tedy w(S) <= 2OPT, a diky predpokladu platnosti trojuhelnikove nerovnosti se v zadnem pruchodu krokem 3 vaha S nezvetsi).