| 2.10. |
|
| 9.10. |
- Edmondsův algoritmus na nalezení největšího párování v grafu, část druhá.
- Připomenutí: hledání největšího párování v bipartitním grafu přes toky v sítích
- Připomenutí: dvě varianty Hallovy věty
- k-regulární bipartitní graf má perfektní párování
- deficitní Hallova věta: je-li pro každou podmnožinu A levé partity množina N(A) sousedů A maximálně o k menší než je velikost A, pak existuje párování pokrývající levou partitu kromě nějakých k jejích vrcholů.
|
| 16.10. |
- Jednodušší důkaz pozorování o detekci existence volné střídavé cesty pomocí Edmondsova lesa (každá volná střídavá cesta obsahuje hranu mezi sudými hladinami Edmondsova lesa).
- Strom má maximálně jedno perfektní párování.
- Strom T má perfektní párování právě tehdy, když pro každý jeho vrchol v má T-v právě jednu lichou komponentu.
- Příklad 3-regulárního grafu, co není 2-souvislý.
- Příklad 3-regulárního grafu, co nemá perfektní párování.
- Pozorování: 3-regulární hranově 2-souvislý graf je i vrcholově 2-souvislý
- Je-li graf G souvislý, má alespoň 4 vrcholy a každá jeho hrana leží v nějakém perfektním párování, pak G je vrcholově 2-souvislý.
- V 3-regulárním grafu jsou všechny mosty v každém perfektním párování.
|
| 23.10. |
- G je bipartitní graf s partitami A, B, dále S je podmnožina A a T je podmnožina B. Víme, že G má párování M pokrývající S a párování M' pokrývající T. Pak má G také párování pokrývající sjednocení S a T.
- Každý 2k-regulární graf má 2-faktor. Příklad, že nestačí, aby všechny stupně byly sudé. Příklad, že hladový algoritmus nefunguje.
- Na rozmyšlení: 2k-regulární graf se sudým počtem vrcholů má k-faktor.
- Odvození Hallovy věty z Tutteovy věty.
|
| 30.10. |
- 3-regulární 2-souvislý graf má perfektní párování. (důkaz pomocí Tutteovy věty)
- 3-regulární 2-souvislý graf bez hrany má perfektní párování.
- 3-regulární 2-souvislý graf má perfektní párování obsahující předepsanou hranu (důkaz bez rozebrání všech případů).
- Příklad 3-regulárního 2-souvislého grafu, který neobsahuje perfektní párování obsahující dvě nesousední předepsané hrany.
- Příklad 3-regulárního 2-souvislého grafu bez hrany, který neobsahuje perfektní párování obsahující předepsanou hranu.
- Tři ekvivalentní definice "H je minor G":
1) H je graf, který vznikne z G posloupností mazání vrcholů, hran a kontrakcí hran (v libovolném pořadí)
2) H je graf, který vznikne z podgrafu G kontrakcemi hran
3) v G existují disjunktní podmnožiny vrcholů V_i odpovídající vrcholům H, každá V_i indukuje souvislý podgraf a pro každou hranu (i,j) v H existuje aspoň jedna hrana mezi V_i, V_j.
- Důkaz části indukčního kroku v těžší implikaci Kuratowského věty:
Je-li G 2-souvislý graf s 2-separátorem a nemá K_{3,3} ani K_5 jako minor (resp. dělení), pak G má rovinné nakreslení.
- Příklad grafu, který má minor K_5, ale nemá dělení (topologický minor) K_5.
|
| 6.11. |
- Graf je d-degenerovaný, pravě když jeho vrcholy lze uspořádat do posloupnosti tak, že každý vrchol má nejvýše d sousedů vlevo (a libovolně mnoho vpravo).
- Mají-li všechny vrcholy H stupeň nejvýše 3, pak platí: G obsahuje minor H právě tehdy, když G obsahuje dělení H (důkaz pro definice minoru 1) a 3)).
- Každý rovinný graf s aspoň třemi vrcholy je podgrafem triangulace na stejné množině vrcholů (v případě stěn, jejichž hranice není kružnice, jen náznak důkazu).
- Každý rovinný graf je indukovaným podgrafem triangulace (náznak důkazu: např. stačí třikrát provést operaci přidání vrcholu do každé stěny připojeného na všechny její vrcholy).
- Každá triangulace na aspoň 4 vrcholech je 3-souvislá (bez důkazu, ale není těžký).
- Fáryho věta: každý rovinný graf má rovinné nakreslení, v němž všechny hrany jsou úsečky. Důkaz pro (3-souvislé) triangulace úpravou důkazu Kuratowského věty.
- Plochy, rovina jako sféra bez bodu, různé reprezentace toru, projektivní roviny, Kleinovy láhve, Möbiova pásku. Křižítko jako "záplata" Möbiovým páskem.
|
| 13.11. |
- Tři různé reprezentace Kleinovy láhve a důkaz, že jsou ekvivalentní.
- Souvislá suma ploch #, Pi_n je souvislá suma n projektivních rovin, Sigma_n je souvislá suma n torů.
- Kanonická reprezentace ploch Pi_n = aabbccdd...nn, Sigma_n=[a_1,b_1][a_2,b_2]...[a_n,b_n], kde [a,b]=aba^{-1}b^{-1}.
- Identita PP # T = PP # PP # PP ( = PP # KB), náznak důkazu obrázkem (Möbiův pásek + ucho hrníčku --> Möbiův pásek + ucho Kleinovy láhve).
- Nakreslení K_6 na projektivní rovinu (v obdélníkové reprezentaci i v reprezentaci sféry s křižítkem).
- K_7 nelze nakreslit na projektivní rovinu bez křížení.
- Kombinatorická reprezentace buňkového nakreslení grafu na ploše - buď seznam hranic stěn, nebo rotační systém (na orientovatelné ploše), resp. rotační systém + orientace hran (na neorientovatelné ploše).
- Perfektní grafy nejsou uzavřeny na mazání hran ani na kontrakce hran, speciálně tedy ani na minory.
- Liché díry (cykly délky aspoň 5) nejsou perfektní.
- Znění silné věty o perfektních grafech: graf je perfektní právě tehdy, když nemá lichou díru ani lichou antidíru jako indukovaný podgraf.
|
| 20.11. |
- Kombinatorický důkaz identity PP # T = PP # PP # PP.
- Polygonální reprezentace souvislé sumy dvou ploch S_1 # S_2 a zjednodušení pro případ, kdy S_1 je projektivní rovina.
- Šestiúhelníky s hranami slepenými podle vzoru aabbcc a [a,b]cc
reprezentují stejnou plochu (Pi_3).
- Liché antidíry (doplňky lichých děr) nejsou perfektní.
- Comparability grafy (symetrizace částečných uspořádání) jsou perfektní.
- Dilworthova věta, důkaz přes slabou větu o perfektních grafech.
- Každý chordální graf je perfektní (důkaz ze silné věty o perfektních grafech nebo použitím hladového algoritmu na PES).
- Chordální grafy jsou průnikové grafy podstromů ve stromě (bez důkazu).
|
| 27.11. |
- Průnikové grafy podstromů ve stromě jsou chordální.
- Podstrom stromu je "konvexní obal" svých vrcholů. Důsledek: průnik dvou (i více) podstromů ve stromě je zase strom.
- Nechť T_1, T_2, ..., T_k jsou podstromy stromu T. Pokud každé dva z nich
mají společný vrchol, pak všechny mají společný vrchol.
- Předchozí věta neplatí, požadujeme-li místo společného vrcholu společnou hranu.
- Příklad souvislého grafu G, jehož každý minimální řez je klika, ale G není chordální.
- Chordální graf na n vrcholech má nejvýš n maximálních klik (a jdou nalézt v polynomiálním čase), obecně graf jich může mít až exponenciálně mnoho.
- Příklad, že neplatí obdoba Vizingovy věty pro multigrafy.
- Zopakování definice Tutteova polynomu, interpretace hodnot r(F) a n(F).
|
| 4.12. |
- Tutteův polynom sjednocení dvou skoro disjunktních grafů G a H (které mají nejvýše jeden společný vrchol) je roven součinu T_G a T_H. Definice n(F) uvedena na pravou míru.
- Tutteův polynom pro cestu, cestu + izolované vrcholy, hvězdu, strom, les, n smyček, n paralelních hran, cyklus délky n.
- T_G(x,y)=x^n právě tehdy, když G je les s n hranami (a libovolným počtem vrcholů).
- T(2,2), T(2,1), T(1,2), T(1,1) počítají postupně všechny podgrafy (s množinou vrcholů V), acyklické podgrafy, souvislé podgrafy (je-li G souvislý, jinak souvislé v každé komponentě), kostry (resp. kostry v každé komponentě).
- Definice G* - duální rovinný (multi)graf rovinného (multi)grafu G. Bez důkazu: T_G(x,y)=T_{G*}(y,x).
|
| 11.12. |
- Generující (vytvořující) funkce - opakování: posloupnosti generované funkcemi tvaru 1/(1-ax), 1/(1-x)^k, základní operace (sčítání, násobení, derivace, integrál, skládání), zobecněná binomická věta.
- Třída A všech přirozených čísel, A^k - k-tice přirozených čísel, A^* - všechny konečné posloupnosti přirozených čísel. Generující funkce A^*, počet posloupností se součtem n (velikost množiny A^*_n).
- Odvození generující funkce pro celkový počet prvků v posloupnostech se součtem n, pomocí generující funkce dvou proměnných.
|
| 18.12. |
- Dopočítání celkového a průměrného počtu prvků v posloupnostech přirozených čísel se součtem n pomocí koeficientu u x^n v generující funkci spočítané minule.
- Alternativní řešení pravděpodobnostní metodou.
- Průměrný počet jedniček v poslouposloupnostech přirozených čísel se součtem n.
- Exponenciální generující funkce, "malá násobilka" (operace posloupnosti, množiny a cyklu).
- Průměrný počet cyklů v permutaci n prvků.
|
| 8.1. |
- Opakování: grupa, akce (působení) grupy G na množině X, orbita a stabilizátor prvku, pevné body akce, příklad několika akcí Z_6 na množině {1,2,3,4,5,6}. Pozorování, že velikost orbity krát velikost stabilizátoru vyšlo rovno řádu působící grupy.
- Ještě opakování: Burnsideovo lemma, základní a vážená verze.
- Počet různých "Braillových znaků" až na symetrie (zrcadlení a otočení), obecně počet obarvení obdélníku 2x3 pomocí n barev.
- Návod na odvození generující funkce 3 proměnných pro počty obarvení 3 barvami, kde každá proměnná odpovídá jedné barvě, a mocnina proměnné počtu výskytů příslušné barvy.
- Odvození generující funkce pro počty rozkladů n na součet 5 přirozených čísel uspořádaných do cyklu, kdy rozklady lišící se otočením nebo zrcadlením se považují za stejné.
- Na rozmyšlení: Počet různých obarvení stěn krychle pomocí n barev, až na Euklidovské symetrie (otáčení, zrcadlení a jejich kombinace). Hlavní je najít všech 48 symetrií a zjistit, jak permutují stěny.
|