Kombinatorika a grafy II (NDMI012)

Jan Hubička, hubicka@kam.mff.cuni.cz

Konzultace po dohodě emailem (nejlépe ve středu nebo pátek na MS, 3. patro). Do subjektu emailů pište "KG2".

Odpřednesená látka

3. října
Edmondsův algoritmus [VM]

Cvičení: dokončení důkazu Edmonsova algoritmu (kontrakce květu).

10. října
Halova věta (opakování), Tutteova věta o existenci perfektního párování, Petersenova věta o perfektním párování v 2-souvislém a 3-regulráním grafu [VM]

Cvičení: každý k-regulrání (k-1)-souvislý graf má perfektní párování. Hallova veta z Tutteovy.

17. října
Lemma o kontrahovatelné hraně pro 3-souvislé grafy [VM,D], Tutteova charakterizace 3-souvislých grafů [D]. Definice minoru. Kuratowského-Wagnerova věta (důkaz bude dokončen částečně na cvičení, částečně na příští přednášce) [VM, D].

Cvičení: každý 3-regulrání graf s max. dvěma mosty má perfektí párování. Minor K3,3 implikuje dělení K3,3. Minor K5 implikuje dělení K5 nebo dělení K3,3.

24. října
Poslední část důkazu Kuratowského a Wagnerovy věty. Základní pojmy týkající se ploch: homeomorfismus, přidání ucha a křížítka, klasifikace ploch, rod plochy [Dv1].

Cvičení: Graf je vnějškově rovinný pokud neobsahuje minor K4 nebo K2,3. Kombinatorická jednoznačnost nakreslení.

31. října
Nakrelsení grafů na plochy, zobecněná Eulerova formule, její důsledky pro degenerovanost a barevnost grafů nakreslitelných na danou plochu [Dv1].

Cvičení: Každý 3. souvsilý rovinný graf ma kombinatoricky jednoznačné nakreslení, klasifikace ploch, dokončení důkazu Eulerovy formule pro mosty.

7. listopadu
Haywoodova formule, degenerované grafy, Brooksova věta [Dv2].

Cvičení: Výuka kreslení na projektivní roviny (K5, K6), torus (K7) a Kleinovu láhev (zde nakreslit K7 nejde). Duály grafů. Hladový algoritmus na bipartitním grafu může použít libovoně mnoho barev.

14. listopadu
Vizingova věta o vztahu hranové barevnosti a největšího stupně [Dv2]. Pojem perfektního grafu, slabá věta o perfektních grafech [D].

Cvičení: Hladový algoritmus na bipartitním grafu.

21. listopadu
Přednáší Vít Jelínek. Chordální grafy, existence perfektních eliminačních schémat pro ně, jejich perfektnost, jejich rozpoznávání v polynomiálním čase [Ba, D, HR]. Bondyho-Chvátalova věta o hamiltonovskosti [BCh].

Cvíčení v týdnu 19-23. listopadu odpadá.

28. listopadu
Počítání koster, chromatický polynom, spolehlivost grafu. Tutteův polynom - Nullity-rank expanze a multiplikativita pro disjunkntní sjednocení. [Bo]

Cvičení: Příklady a vlastnosti perfektních grafů, chordální grafy

Domácí úkoly

Literatura

Záznamy přednášek Víta Jelínka
[Ba] P. Bartlett: Chordal graphs (pdf zápisky z přednášky)
[BCh] The Bondy and Chvátal theorem
[Bo] B. Bollobás: Modern Graph Theory
[D] R. Diestel: Graph Theory
[Dv1] Z. Dvořák: Prezentace o kreslení grafů na plochy (pozor, používá se tam jiná definice rodu plochy než na přednášce)
[Dv2] Z. Dvořák: Prezentace o Brooksově a Vizingově větě
[EKR] The Erdős-Ko-Rado theorem
[HR] Y. Haimovitch, A. Raviv: Chordal graphs (ppt prezentace)
[T] R. Tarjan: Sketchy notes on [...] blossom algorithm for general matching
[VM] T. Valla, J. Matoušek: Kombinatorika a grafy I
[W] H. Wilf: Generatingfunctionology