Kombinatorika a Grafy II

1. 3. 2021 · Poznámky · 47 min čtení · 🇨🇿 · dostupné v PDF · [upravit]

• • 1. přednáška
    • Největší párování
  • 2. přednáška
    • Tutteova věta
  • 3. přednáška
    • Tutte v2.0
    • Minory
  • 4. přednáška
    • Kreslení grafů na plochy
  • 5. přednáška
  • 6. přednáška
    • Vrcholové barvení
    • Pár poznámek
    • Hranové obarvení
  • 7. přednáška
    • Perfektní grafy
  • 8. přednáška
    • Chordální grafy
  • 9. přednáška
    • Tutteův polynom
  • 10. přednáška
    • Formální mocninné řady
    • Obyčejné vytvořující funkce
  • 11. přednáška
    • Exponenciální vytvořující funkce
    • Grupy a Burnside
  • 12. přednáška
  • 13. přednáška
    • Extremální teorie
      • Pro minory
    • Pronikající systémy množin
  • Zdroje/materiály
  • Poděkování

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Kouteckého z akademického roku 2020/2021 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

1. přednáška

Největší párování

• TLDR celé této části jsem zpracoval do YouTube videa

Definice: Párování v je t. ž. hrana

• maximální (do inkluze) – přidání další hrany pro dané párování už není možné; v přednášce nás nezajímá
• největší –

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

Definice (střídavá cesta) (vzhledem k ) je cesta, na které se střídají hrany v párování a hrany mimo párování: , kde každá sudá/lichá hrana je v , lichá/sudá není v

• volná střídavá cesta (VSC) – krajní vrcholy jsou volné (vůči párování)
• obsahuje lichý počet hran, sudý počet vrcholů

Tvrzení: Nechť je graf, párování v . Pak obsahuje VSC (vzhledem k ), právě když není největší párování v .

• pokud má VSC, mohu zvětšit prohozením hran

• pro spor nechť je párování v t. ž.

  • uvažme ; pak má každý vrchol stupeň nebo komponenty souvislosti jsou kružnice sudé délky a cesty (navíc jsou střídavé)

  • (👀): musí existovat komponenta, která má více hran z (je větší)

    • není to kružnice (musela by být lichá a měli bychom kolizi ve vrcholu)
    • je to volná (z definice, vzhledem k ) střídavá (jinak by měly stejný počet hran) cesta

Definice (květ): lichá „střídavá“ kružnice s vrcholem , ke kterému přiléhají dvě hrany

Definice (stonek): střídavá cesta z (i nulové) délky končící volným vrcholem (dál od květu)

• může (a nemusí) být volný vrchol – stačí, aby byl volný vzhledem ke květu

Definice (kytka): květ + stonek

Definice (kontrakce hrany): Nechť je neorientovaný graf a jeho hrana. Zápis označuje graf vzniklý z kontrakcí („smrštěním“) hrany do jednoho vrcholu:

Tvrzení: Nechť je květ v grafu . Potom párování v je maximální, právě když je maximální párování v grafu , tj. s květem zkontrahovaným do jediného vrcholu. Navíc pokud znám VSC pro , tak v poly. čase najdu VSC pro v .

Důkaz: Tady je sketchy důkaz, tady je míň sketchy důkaz.

Algoritmus (Edmondsův „zahradní/blossom“): vstupem je graf a jeho libovolné párování , třeba prázdné. Výstupem je párování , které je alespoň o větší, než , případně pokud bylo maximální.

• zkonstruujeme maximální možný Edmondsův les vzhledem k aktuálnímu tím, že z volných vrcholů pustíme BFS a střídavě přidáváme vrcholy
  • hranám, které se v lese neobjeví, se říká kompost a nebudou pro nás důležité

• pokud existuje hrana mezi (potenciálně různými) sudými hladinami různých stromů, pak máme volnou střídavou cestu, kterou zalterujeme a jsme hotovi (párování je o větší)
• pokud existuje hrana mezi (potenciálně různými) sudými hladinami jednoho stromu, máme květ – ten zkontrahujeme a rekurzivně se zavoláme
  • vrátí-li , pak nic dalšího neděláme
  • vrátí-li nějaké větší párování, tak z něho zkonstruujeme párování v
• neexistuje-li hrana mezi sudými hladinami, pak

Tvrzení: Edmondsův algoritmus spuštěný na a doběhne v čase a najde párování alespoň o hranu větší než , případně oznámí, že je největší nejlepší párování lze nalézt v čase .

Důkaz: nejvýše -krát se vždy zrekurzíme s tím, že při každém rekurzení prohledáme celý graf ( ). Tohle celé opakujeme nejvýše dokud nejsou všechny vrcholy zpárované, tedy -krát.

2. přednáška

Definice (perfektní párování): Párování je perfektní, pokud neexistuje v žádný volný vrchol.

Tutteova věta

Definice (Tutteova podmínka):

• je počet lichých komponent grafu

.

Věta (Tutteova věta): má perfektní párování platí Tutteova podmínka.

Důkaz: obměna: neplatí TP není PP. Nechť t. ž. . V perfektním párování se alespoň vrchol z každé liché komponenty musí spárovat s nějakým z , ale těch není dostatek.

nechť splňuje Tutteovu podmínku. je sudá (nastavíme prázdnou). Dokážeme, že má PP indukcí podle počtu nehran.

• základ: , ten PP má
• indukční předpoklad: má nehranu a každý graf na s počtem hran alespoň o 1 větší než a platí TP, pak má perfektní párování

Nechť

• lehký případ: každá komponenta je klika
  • sudé kliky spárujeme triviálně
  • v rámci liché kliky vypáruji vše až na jeden vrchol, ten spáruji v rámci ( vidí všechny) a zbytek v spáruji spolu (sudé komponenty do parity nepřispívají, liché + z také ne a v tedy zbyde sudý počet vrcholů)

• alespoň komponenta není klika, tedy nesousední
  • ti mají společného souseda (tvrzení o třešničce), který není v
  • pro existuje vrchol , se kterým není spojený (jinak by byl v , což ale víme, že není)

• (👀): přidáním hrany do grafu se neporuší TP ( počet lichých komponent buď klesne o nebo zůstane stejný).

Indukujeme dvakrát: a díky předchozímu pozorování splňují TP a spolu s IP PP v

• jednoduchý případ: je PP pro , analogicky pro a

Těžší případ:

• obsahuje „dvoubarevné hrany“ nebo střídavé sudé cykly
• neobsahuje izolované vrcholy a střídavé cesty, protože byly perfektní

• jednodušší případ těžšího případu: leží v jiné komponentě než – stačí přealternovat hrany tak, aby ani ani v neležely.

• složitější případ těžšího případu: a leží ve stejné komponentě – vybereme podle obrázku

Věta (Petersen): každý -regulární -souvislý (vrcholově i hranově, pro 3-regulární grafy je to to samé; alternativně můžeme říct graf bez mostů a artikulací) graf má PP.

Důkaz: Nechť je -regulární a -souvislý. Chci ukázat, že splňuje TP. Předpokládejme danou .

1. každá komponenta je v spojena aspoň dvěma hranami s

   • je -souvislý, nemáme mosty

2. dokážeme, že každá lichá komponenta je s spojena lichým počtem hran:

   • nechť je lichá komponenta ; pak:

• kombinace (1) a (2) říká, že každá lichá komponenta je s spojena hranami:
  • počet hran mezi a lichými komponentami
    • (ukázali jsme výše)
    • (každý vrchol vysílá ven hrany (z -regularity))

, tedy TP platí a graf má perfektní párování.

3. přednáška

Tutte v2.0

Lemma (o kontrahovatelné hraně = LoKH): Nechť je vrcholově -souvislý různý od . Potom obsahuje hranu t. ž. je 3-souvislý.

Důkaz: Sporem – nechť je 3-souvislý ale neexistuje žádná hrana, která jde zkontrahovat. Tedy není -souvislý.

Lemma (pomocné): t. ž. tvoří vrcholový řez v G, navíc každý z má alespoň jednoho souseda v každé komponentě .

- přesně popisuje situaci, že kontrakce libovolné hrany nám dá řez velikosti \(2\) - ve skutečnosti **neplatí** (ale dovětek ano) a dokazujeme ho pouze v rámci sporu! -

(👀) (které platí): minimální vrcholový řez , pak každý vrchol má souseda v každé komponentě – když to pro nějaký neplatí, tak je pořád řez

Důkaz (způsob z přednášky): Vím, že není -souvislý, tedy má vrcholový řez velikosti . Nechť je vrchol vzniklý kontrakcí . Řez velikosti obsahuje , jinak by to byl řez už pro (obsahoval by vrcholy z původního grafu, které nekontrahujeme).

Označme řez . Po rozkontrahování vidíme, že musí mít souseda v každé komponentě (jinak spor s 3-souvislostí). Tedy je hledaný vrchol.

Důkaz (moje intuice): Pokud by neplatilo (existovala by taková hrana), tak máme hranu, přes kterou kontrahujeme. Jelikož pro tu hranu platí, že neexistuje , které spolu s jejími vrcholy tvoří řez, tak bude graf i po kontrakci -souvislý.

Pro důkaz původního lemmatu si zvolím a z pomocného tvrzení tak, aby nejmenší komponenta byla co nejmenší (co do počtu vrcholů).

Protože má souseda ve všech komponentách, má nějakého souseda (kde je naše nejmenší komponenta). Pomocné tvrzení pro dá nějaký t. ž. je vrcholový řez . Chceme dokázat, že má menší komponentu než .

Nechť je komponenta neobsahující . Existuje, protože jsou spojené a graf se rozpadne alespoň na komponenty. Tvrdím, že , protože nemůže obsahovat (vrcholy řezu), (z definice ), ale má nějakého souseda v (podle pomocného tvrzení, má sousedy ve všech komponentách řezu), takže v ještě něco zbyde. Navíc ho tam mělo i předtím, takže opravdu . Tedy , což je spor s minimalitou.

• netvrdím, že je nejmenší!

Věta (Tutteova charakterizace 3-souvislých grafů): Graf je 3-souvislý existuje posloupnost t. ž. vznikne z kontrakcí hrany, navíc má všechny vrcholy stupně .

Důkaz: Induktivní aplikace lemmatu o kontrahovatelné hraně.

Mějme dle předpokladu. Chceme, že je 3-souvislý. Indukcí:

• je 3-souvislý
• je 3-souvislý je 3-souvislý

Obměnou nechť má vrcholový řez velikosti 2, označme ho . Pak každá komponenta má alespoň 2 vrcholy (osamocený vrchol mohl sousedit jen s řezem, ale ten je velikosti 2, což je spor se stupněm vrcholů pro ).

Pak ale nebyl 3-souvislý, rozborem toho, kde vznikla hrana:

• má řez velikosti 1.
• celá obsažená v komponentě je stále řez v
• pro z nějaké komponenty je řez v
  • využíváme předchozí pozorování, že každá komponenta má alespoň vrcholy – kdyby ne, tak nemusí nic odříznout, pokud tam byla jednovrcholová komponenta

Minory

Definice (minor): Nechť jsou grafy. Pak je minor (nebo že obsahuje jako minor), značíme , pokud lze získat z posloupností mazání vrcholů, mazání hran nebo kontrakcí hran.

• (👀): je tranzitivní (prostě spojím posloupnosti operací)

• (👀): podgraf minor

  • podgraf vzniká přesně mazáním vrcholů a mazáním hran

• (👀) (spíš fakt): rovinný jeho minory jsou také rovinné

  • pro podgraf očividné, je jen potřeba si rozmyslet kontrakci (že nic topologicky nerozbije)

Věta (Kuratowského): rovinný neobsahuje dělení ani

Věta (Kuratowski 1930, Wagner 1937): Následující jsou ekvivalentní:

1. je rovinný
2. neobsahuje dělení ani jako podgraf
3. neobsahuje ani jako minor.

Důkaz:

• * : z prváku, protože ani nejsou rovinné
• : obměna: „obsahuje dělení jako podgraf“ „obsahuje dělení jako minor“
• : je-li rovinný, tak i minor bude rovinný (fakt výše)
• * : na přednášce nebyl, k přečtení tady[^1]
• * : indukcí podle
  • pro vše funguje
  • předpokládám má alespoň 5 vrcholů a neobsahuje ani jako minor. Rozeberu případy podle (vrcholová souvislost )
    • nesouvislý graf, použijeme indukci
    • artikulačním vrcholem rozpojíme, podle IP nakreslíme
      • musí být na vnější stěně, což umíme přes trik s projekcí z koule na rovinu
    • , rozložení podél dvou vrcholů tvořících řez, ale opatrně – musíme si rozmyslet, že můžeme obě části zkontrahovat do hrany mezi vrcholy, aby poté v nakreslení šly spojit

Pokračování v další přednášce…

4. přednáška

• použijeme lemma o kontrahovatelné hraně: t. ž. je -souvislý

  • (👀): nemůže obsahovat ani jako minor (kontrakcí něčeho, co je nemělo, je nevytvoříme)

  • rovinné nakreslení (existuje z IP)
  • (vrchol vzniklý kontrakcí )

    • (👀): bude -souvislý (protože je -souvislý a vznikne odebráním vrcholu)

    • (👀): taky rovinný (odebráním mi žádný minor nevznikne)

    • nakreslení vzniklé z odebráním

Označme kružnici ohraničující stěnu , v níž ležel (v ) vrchol – musí to být kružnice, protože v rovinném nakreslení každého -souvislého grafu je každá stěna kružnice.

• – sousedi
• – sousedi
• (každý soused kromě je i sousedem v , stejně pro )

3 případy:

• – nenastane, protože kontrakcí dostanu , což je spor s předpokladem

• , na jsou v pořadí – nenastane, protože kontrakcí dostanu

• zbytek – nenastane ani (1), ani (2)
  • označme v pořadí, jak se objevují na
  • můžu nakreslit všechny hrany
  • rozdělují na vnitřně disjunktní cesty ( protože je -souvislý… sousedí s a s dalšími vrcholy)
    • chceme: patří do jediné (pro nějaké ), jinak by nastaly předchozí případy
  • nakreslím do té správné stěny, spojím s a mám hotovo

Kreslení grafů na plochy

Definice: Nechť . Potom homeomorfismus z na je funkce , která je spojitá, bijekce a je spojitá. jsou homeomorfní ( ) pokud mezi nimi existuje homeomorfismus.

• něco jako isomorfismus u grafů ( znamená, že se chovají stejně)

Definice (plocha): kompaktní (uzavřená, omezená), souvislá (např. oblouková – každé dva body můžu propojit obloukem), -rozměrná varieta bez hranice (dostatečně malé okolí každého bodu je homeomorfní otevřenému okolí v ).

• např. sféra v nebo torus v
• není to např.
  • , jelikož není kompaktní (omezená)
  • čtverec s hranicí, jelikož pro každý krajní bod není homeomorfní

Operace s plochami, přes které umíme všechny zkonstruovat:

• přidání ucha (od hrnku)
  • vyříznu dva kruhy
  • vezmu plášť válce bez dna a vrchu
  • ohnu a přilepím jej na díry po kruzích

  • (👀): teleport, do kterého když vejdeme, tak na druhé straně vyjdeme opačně („otočeně“)

• přidání křížítka (cross-capu):

  • (👀): teleport, do kterého když vejdeme, tak nás to přesune naproti

Pro nechť značí plochu vzniklou ze sféry přidáním uší, tak říkáme, že je orientovatelná plocha rodu .

Pro nechť značí plochu vzniklou ze sféry přidáním křížítek, tak říkáme, že je neorientovatelná plocha rodu .

Fakt: Každá plocha je homeomorfní právě jedné ploše z posloupnosti

• máme tu skryté tvrzení, že žádné dvě z této posloupnosti nejsou homeomorfní.

Fakt: Přidám-li ke sféře ( ) uší a křížítek, vznikne neorientovatelná plocha homeomorfní ( „přidání dvou křížítek je jako přidání ucha,“ pokud už tam bylo křížítko)

• sféra
• projektivní rovina
• torus
• Kleinova láhev

5. přednáška

Definice (nakreslení grafu): na plochu je zobrazení t. ž.:

• každému vrcholu přiřadí bod
• každé hraně přiřadí prostou (neprotínající se) křivku spojující konce
• vrcholy se nepřekrývají:
• hrany se překrývají nejvýše ve sdílených vrcholech:
• vrcholy, které neleží na hraně, se s ní neprotínají:

Definice (stěna nakreslení): souvislá komponenta

• prostě souvislé komponenty toho, když odeberu všechna nakreslení hran a vrcholů

Definice (buňkové nakreslení): každá stěna je homeomorfní otevřenému kruhu v .

Připomenutí: souvislý v každém rovinném nakreslení platí

• využíváme faktu, že rovinné nakreslení je buňkové je souvislé
• je speciální pro rovinu

Definice (Eulerova charakteristika plochy): charakteristika plochy je

Věta (zobecněná Eulerova formule): Nechť máme nakreslení grafu na ploše , které má stěn. Pak . Pokud je buňkové, tak dokonce .

Důkaz (rovnosti): idea je indukce podle rodu

• platí

Mějme buňkové nakreslení na

• pro se dělá analogicky, jen trháme obě ucha a vyjde to
• značíme počet vrcholů, hran a stěn

Nechť je křížítko na , jsou body (ne nutně vrcholy grafu), kde hrany kříží

• (👀): , jinak by stěna obsahující nebyla buňka

• rovněž předpokládám, že vrchol neleží přesně na křížítku, jinak bych ho mohl BUNO posunout

Vytvoříme přidáním dvou dělících vrcholů na každou hranu křížící těsně vedle („před a za křížítkem“). Děláme to proto, že jedna hrana by mohla procházet křížítkem na více místech a bylo by to pak dost rozbitý.

• tedy: (kde je levá strana)

Vytvoříme přidáním cest délky k sousedním vrcholům z předchozího kroku. Vznikne tím kružnice obcházející .

• (každou z stěn dělím na kusy)
• tedy:

Vytvoříme odebráním všeho uvnitř .

• ( křížících-se hran uvnitř )
• („spojím“ stěn do jedné)
• tedy:

Tedy

Důsledek: Každý graf nakreslitelný na plochu splní , pokud

• důkaz přes to, že předpokládáme, že každá stěna je trojúhelník a dosadíme , jelikož každá stěna je tvořena třemi hranami a zároveň je každá hrana ve dvou stěnách
• každý takový graf má průměrný stupeň
  • na žádnou zafixovanou plochu nelze nakreslit libovolně velký -regulární graf
  • pro libovolně velký úplňák dokážeme vytvořit plochu, na kterou ho nakreslíme

Tvrzení: Nechť je plocha, , nechť je graf nakreslený na , potom obsahuje vrchol stupně

Důkaz: Mějme podle předpokladu. Opět značíme jako počet vrcholů a hran. Rozlišíme případy:

• (t.j. ), dosazením do předchozího důsledku dostáváme průměrný stupeň , tedy existuje vrchol stupně , což jsme chtěli
• (t.j. nebo ), průměrný stupeň vrchol stupně
• min. stupeň ; víme:
  • (žádný vrchol nemá víc než sousedů)
  • chceme zjistit max. hodnotu , což je řešení dvou rovnic výše; dosazením a vyřešením kvadratické rovnice vyjde přesně výraz, který dokazujeme

Důsledek (Heawoodova formule, 1890): Pokud , tak každý graf nakreslitelný na je nejvýš -obarvitelný

• vyplývá z předchozího důsledku – pokud má graf stupeň nejvýše , tak je -obarvitelný
• platí i pro sféru: věta o -barvách
• tento odhad je těsný pro všechny plochy kromě
• na každou plochu lze kreslit kliku velikosti
  • (každý graf nakreslitelný na je dokonce -obarvitelný)

6. přednáška

Vrcholové barvení

• barevnost nejmenší počet barev, kterými lze (dobře) obarvit vrcholy
• max. stupeň , min. stupeň

Definice: je -degenerovaný každý podgraf grafu má

• každý podgraf má vrchol stupně nejvýše

Definice (eliminační pořadí): Alternativní definice -degenerovanosti: graf je -degenerovaný pořadí vrcholů (eliminační) t. ž. a má sousedů v

• trháme vrcholy – každý další odebraný má nejvýše sousedů a graf je stále -degenerovaný

• (👀): je -degenerovaný

  (barvím indukcí v pořadí \(v_n, \ldots, v_1\))

• z minule: pokud je nakreslitelný na má vrchol stupně nejvýše a je stále nakreslitelný na je -degenerovaný je -obarvitelný

(👀): je -degenerovaný (triviálně) (z pozorování výše)

• s rovností platí např. pro úplné grafy a liché cykly

Lemma: souvislý graf a , pak

• když nás zajímá předchozí otázka, tak se stačí zaměřit na nějaký regulární graf

Důkaz: Tvrdím, že je ( )-degenerovaný. Volme neprázdný podgraf a dokazujeme, že v existuje stupně

• pokud obsahuje všechny vrcholy předpoklad
• jinak t. ž. a

Věta (Brooks, 1941): Nechť je souvislý graf, který není úplný a není lichá kružnice. Pak

Důkaz: nechť a navíc předpokládám, že je -regulární (jinak viz předchozí lemma).

• • : zakázané
• • :
  • : zakázané
• ; označme vrcholová souvislost a opět rozebereme případy

1. • máme artikulaci, vrchol artikulace měl souseda v obou částech grafu, proto
   • podle lemmatu ( a nejsou regulární) lze i -obarvit a stačí přepermutovat barvy, aby měl v obou obarveních stejnou

2. • dobré případy (lze slepit)
     • a
     • a
   • těžší případ – na jedné straně stejné, na druhé různé
     • a
       • pokud nebo , tak po přidání hrany půjde použít lemma a vrcholy budou mít různou barvu a máme dobrý případ
         • nemůže se stát, že by např. druhý měl , protože musí vidět i do druhé komponenty
       • nebo
         • pak musí (stupeň je celkově )
         • z předpokladu máme k použití alespoň barvy, přebarvím jimi a a máme dobrý případ

3. – použiji lemma o třešničce (souvislý graf, který není klika, obsahuje třešničku)
   • seřadím vrcholy jako tak, aby měl alespoň jednoho souseda napravo a barvím (hladově):
     • umíme získat jako BFS vrstvy od , kromě a
     • -souvislost využívám k tomu, že i po odstranění a graf bude stále nějakou kostru mít a bude tedy stále souvislý
     • má neobarveného souseda je nějaká nepoužitá z barev
     • všichni sousedé už obarvení, ale dva sousedé ( ) mají stejnou barvu, tedy vidí barev a jedna je volná

Pár poznámek

Hadwigerova domněnka: (není minor)

• relativně jednoduché
• zobecnění věty o barvách
• pomocí věty o barvách + hodně práce
• neví se

Tvrzení: nakreslitelný na Kleinovu láhev je -obarvitelný.

Důkaz: Z Eulerovy formule plyne, že platí jedno z následujících:

• • obarvím z indukce, přidám a mám volnou barvu
• je -regulární:
  • – nesmí, protože nejde nakreslit (je potřeba si rozmyslet)
  • – přímo Brooksova věta

Hranové obarvení

Definice: (barvy) t. ž. . Hranová barevnost (“chromatic index”) je min. počet barev pro hranové barvení .

7. přednáška

Věta (Vizing, 1964): Pro každý graf platí, že

• grafy Vizingovy třídy jsou grafy , třídy jsou
• je NP-úplné rozhodnout, zda daný graf má Vizingovu třídu (i pro grafy s )
• důkaz jsem zpracoval do YouTube videa

Perfektní grafy

Věta (Slabá věta o perfektních grafech, 1972): je perfektní je perfektní.

• důkaz jsem zpracoval do YouTube videa

8. přednáška

Chordální grafy

Definice (chordální graf): Graf je chordální, pokud neobsahuje jako in. podgraf.

• alternativní pohled vycházející ze jména: každá kružnice má chordu (tětivu)

Definice: Nechť dva nesousední vrcholy . je -řez, pokud je to řez takový, že patří do různých komponent .

Tvrzení: je chordální pro každé dva nesousední vrcholy existuje -řez, který je klika.

Důkaz: nechť není chordální, tedy obsahuje indukovanou kružnici délky alespoň . Uvážíme-li dva její nesousední vrcholy, tak jakýkoliv řez musí obsahovat vrcholy z horní a dolní cesty mezi a . Ty nesousedí, tedy řez nebude klika.

nechť je chordální, nesousední. Nechť je -řez s co nejméně vrcholy. Tvrdím, že tvoří kliku.

Pro spor: není klika obsahuje nesousedy. Protože je nejmenší, má i sousedy na obou stranách. Jelikož jsou to komponenty souvislosti, tak tam bude existovat cesta. Vezmu nejkratší cesty v komponentách , . Vrcholy nesousedí (jinak by nebyl řez), tvoří indukovaný cyklus.

Definice: Vrchol je v grafu simpliciální, pokud jeho sousedství tvoří kliku .

Věta: Každý chordální graf (kromě prázdného) obsahuje simpliciální vrchol.

• dokážeme pomocí silnějšího tvrzení

Věta: Každý chordální graf je buď úplný, nebo obsahuje dva nesousední simpliciální vrcholy.

Důkaz: indukcí podle

• základ: platí
• pro více vrcholů
  • je úplný, platí
  • nebo nechť nesousedi v a je -řez tvořící kliku
    • , obdobně

    • (👀): pokud byl chordální, pak je také chordální

    • použijeme IP na
      • pokud klika, vezmi jako libovolný vrchol (např. )
      • pokud není klika, má dva simpliciální vrcholy; nejvýše jeden může ležet v , jelikož je to klika a za zvolím ten druhý; analogicky pro

      • (👀): jelikož je řez, tak se sousedství nezmění: (proto vlastně děláme indukci přes , ne jen přes )

Definice (PES): Perfektní eliminační schéma (PES) grafu je pořadí vrcholů t. ž. platí, že leví sousedé ( ) tvoří kliku.

Věta: G je chordální G má PES.

Důkaz: obměnou nechť není chordální a má tedy indukovanou kružnici velikosti alespoň . Pro spor nechť máme PES. Nejpravější vrchol špatné kružnice má na této kružnici dva levé sousedy, kteří spolu nesousedí, což je spor, což je spor s definicí PES.

nechť je chordální. Má tedy simpliciální vrchol . Jeho sousedé tvoří kliku a je opět chordální (indukovaný graf chordálního je opět chordální) a opakujeme, čímž vznikne PES pro .

Důsledek: pro daný graf lze v polynomiálním čase rozhodnout, zda je chordální.

Důkaz: Trháme simpliciální vrcholy, které chordální graf musí vždy mít – ty umíme v polynomiálním čase najít otestováním všech sousedů. Pokud simpliciální vrchol v nějakém bodě nenajdeme, tak graf chordální být nemohl.

Důsledek: chordální grafy jsou perfektní.

Důkaz: Je-li graf chordální, pak má PES, pomocí kterého ho umíme obarvit tak, aby měl nejvýše barev. Jelikož je navíc každý indukovaný podgraf chordálního grafu také chordální, tak platí i pro indukované podgrafy, což potřebujeme pro perfektnost.

Definice: je hamiltonovský, pokud má kružnici na vrcholech (jako podgraf).

Věta (Bondyho-Chvátalova): Nechť je graf na vrcholech. Nechť jsou nesousedé t. ž. . Nechť . Pak je hamiltonovský je hamiltonovský.

Důkaz: jasné

nechť je hamiltonovská kružnice a vrcholy splňující podmínku.

• pokud neobsahuje , pak je hamiltonovská kružnice
• jinak očíslujeme vrcholy a navíc
  • chceme je ham. kružnice v
  • (vrcholy dobré pro )
    • povoluji vrcholy , viz indexování
  • (vrcholy dobré pro )
    • povoluji vrcholy , viz indexování
  • (pozor, indexování je posunuté!)
  • (nesmím použít )
  • (nesmím použít )
  • (z předpokladu)
  • ale znamená, že se překrývají

Věta (Dirac): graf na vrcholech s min. stupněm je hamiltonovský.

Důkaz: Z Bondy-Chvátalovy věty doplníme na , který je hamiltonovský.

9. přednáška

Tutteův polynom

Definice (multigraf) kde jsou vrcholy a multimnožina prvků z

• odstranění a kontrakce fungují intuitivně – kontrakce nezahazuje hrany, protože máme multigraf

Definice (most): hrana je most, v multigrafu , pokud má více komponent než

• počet komponent

Definice (hodnost/rank) je

• intuice: velikost největší „neredundantní“ podmnožiny (t. ž. )

Důkaz: Chceme dokázat, že neobsahuje cykly a že . Víme, že .

Postupné přidávání hran z (právě tohle zaručuje, že nemáme cykly):

• snižuje počet komponent, vždy o , tedy
• zvyšuje rank vždy o (nastává druhý případ z tabulky dole), tedy

Spojením dostáváme .

Důkaz (alternativní): Pokud je rank , tak je graf souvislý a přesně to odpovídá počtu hran jeho kostry. Pokud má komponenty souvislosti, tak bude mít hran, protože jednu hranu z kostry odebereme a graf tím roztrhneme. Pro více komponent souvislosti opakujeme a tedy

Definice (nulita) je

• intuice: velikost největší „redundantní“ podmnožiny (t. ž. počet komponent se nezmění po jejím odebrání) – to dává smysl, jelikož je to a jelikož rank udává počet těch užitečných, tak nulita těch neužitečných

Příklad:

změna
přidání hrany bez změny počtu komponent
přidání hrany se změnou počtu komponent

• odpovídá intuici – hrana, která se přidala, ale nezměnila souvislost (byla tedy zbytečná), zvýší nulitu, kdežto užitečná hrana zvýší rank

Definice (Tutteův polynom) multigrafu je polynom proměnných definovaný jako

Tvrzení: pro souvislý je počet koster

Důkaz: Dosadím do polynomu a získám . Vím, že , tedy výraz bude počet takových, že a .

• z předpokladu souvislosti je počet komponent
  • musí mít také pouze , protože
• znamená, že , tedy
• kombinace počtu hran a souvislosti dává, že je to strom a tedy kostra

Tvrzení: Nechť jsou multigrafy, t. ž. , (protínají se nejvýše v jednom vrcholu a v žádné hraně). Definujeme , kde a . Potom

Důkaz: V definici kvantifikuji přes podmnožiny hran. Ty ale můžu vždy rozdělit na disjunktní sjednocení podle a . Navíc:

• (z pohledu jako největší neredundantní množina hran)
• (analogicky, opět z intuice)

Pak rozepíšu:

Důsledek: dva grafy se stejným Tutteovým polynomem nemusí být stejné.

• vyplývá přímo z předpokladu – že se mohou protínat v nejvýše vrcholu
• neobsahuje tedy informaci o počtu komponent či počtu vrcholů

Věta: Nechť je multigraf. Potom je jednoznačně určen rekurencemi:

most
	poslední rovnost: z důsledku výše
smyčka
	poslední rovnost: odstranění smyčky je to stejné jako její kontrakce
jindy

Důkaz: Pro jasné, jinak rozdělíme:

Stačí dokázat následující (a dosazení do výrazu výše):

1. pokud není most, tak
   • není most, jeho odebráním se rank nezmění, tedy
2. pokud je most, tak
   • je most, jeho odebráním se rank zmenší o , tedy
3. pokud není smyčka, tak
   • není smyčka, kontrakce však zachová zbylé hrany (jsme v multigrafu) jako smyčky a nulita se tedy nezmění (jelikož, pokud to chápu správně, se spojením vlastně zmenší jak počet hran, tak vrcholů)
4. pokud je smyčka, tak
   • je smyčka, kontrakcí se nulita zmenší o , tedy

Poté pro větu stačí následující:

• je most: (2) + (3)
• je smyčka: (1) + (4)
• není most ani smyčka: (1) + (3)

Definice (chromatický polynom) multigrafu je funkce , kde pro je počet dobrých obarvení (posunutí udělá nové obarvení) pomocí barev .

• pokud má smyčku, pak

Věta: Pro každý multigraf platí

10. přednáška

Formální mocninné řady

Definice: Pro posloupnost reálných čísel je formální mocninná řada (FMŘ) zápis tvaru

• všechny FMŘ nad
• pro je
• pro FMŘ je
  • , kde (konvoluce)

Fakt: tvoří (komutativní) okruh (máme )

• s nulovými koeficienty
• s a zbytek nulové koeficienty

Fakt: tvoří vektorový prostor (násobení konstantou je FMŘ pro )

Definice (převrácená hodnota): Převrácená hodnota FMŘ je taková FMŘ , že

• není (muselo by být něco jako )
• • , kde bude nulové pro (požere se to), proto

Tvrzení: Nechť je FMŘ. Potom existuje, právě když (a pak je jednoznačně určena).

Důkaz: Hledejme inverz. Rozepsání nám dává soustavu takovýchto rovnic, které mají jednoznačné řešení:

Definice (složení): jsou FMŘ. Složení je

. Obecně je problém to zadefinovat, potřeboval bych znát hodnotu součtu, ale jde to, když:

1. je polynom ( t. ž. )
2. • chci ukázat, že součet je konečný
     • pro FMŘ
     • , koeficient u je nulový, tedy všechny koeficienty pro jsou nulové

Definice (derivace) FMŘ značená

Příklad: Můžu mít také FMŘ více proměnných, např.

Obyčejné vytvořující funkce

Definice (OVF): Nechť je množina, jejíž každý prvek má definovanou velikost , předpokládáme, že je v konečně mnoho prvků velikosti .

Potom obyčejná vytvořující funkce pro je FMŘ

Příklad: Jídla ( ):

• Polévky ( )

  • gulášová:
  • knedlíčková:

• Hlavní jídla ( )

  • guláš:
  • řízek:
  • smažák:

• (👀):

• (👀):

  - \(P(x) \cdot H(x) = \) kartézský součin dvojic (polívka, hlavní jídlo) - \([x^{130}](J(x) \cdot J(x)) = \) počet uspořádaných dvojic jídel, které se sečtou na \(130\)

11. přednáška

Exponenciální vytvořující funkce

Chci dojít k , což bude vytvořující funkce pro počet lesů na vrcholech, pomocí vytvořující funkce pro počet stromů na vrcholech.

Nechť je počet stromů na vrcholech

Nechť je počet kružnic na vrcholech

Definujeme a tak, aby

Potom platí, že , tedy počet grafů na vrcholech majících dvě komponenty souvislosti, z nichž jedna je strom a druhá kružnice:

Definujeme a tak, aby

• počet způsobů, jak rozdělit vrcholy na červené a modré a vytvořit strom na každé barvě

Dále definujeme hromadu dalších věcí:

• jako , abychom měli počet lesů se dvěma komponentami, tedy .
• , tedy je počet uspořádaných -tic stromů tvořících rozklad vrcholů
• , tedy je počet lesů s komponentami

Konečně vyjádříme

---

V následujících definicích a pozorováních je takovýhle text odkaz na to, co si pod tím představovat v rámci minulého příkladu.

Definice (EVF): Mějme množinu (všechny konečné stromy s očíslovanými vrcholy), předpokládejme:

1. každý prvek (nějaký strom) má množinu vrcholů (vrcholů) konečná
2. pro každou konečnou existuje konečně mnoho t. ž.
   • (existuje konečné množství stromů)
3. pro dvě konečné množiny t. ž. platí, že počet t. ž. je stejný jako počet t. ž. (co do počtu, záleží jen na velikosti množiny vrcholů)
   • (dvě stejně velké množiny vrcholů mají stejný počet stromů)

Potom exponenciální vytvořující funkce pro je

kde

(👀): Nechť je , potom:

1. pokud jsou disjunktní (příklad výše), pak je
   • stejné jako u , protože
2. , kde je počet uspořádaných dvojic t.ž. (tvoří rozklad)
3. , kde je počet uspořádaných -tic , kde
4. pokud , pak kde je počet -prvkových množin splňujících
5. pokud , pak kde je počet množin , kde

Grupy a Burnside

Definice (akce grupy): nechť je množina, nechť je grupa, její neutrální prvek. Potom akce grupy na množině je binární operace t.ž.

2. • pozor, a jsou jiné operace

(👀): Pokud je inverzní prvek k , potom

Důsledek: zobrazení je bijekce

12. přednáška

Definice (množina pevných bodů) , značená

Definice (stabilizátor) prvku je

(👀):

(👀): je podgrupa

• , protože
• z pozorování
• , dosazením dostávám

Prvky jsou ekvivalentní (značím ), pokud t.ž.

• (👀): je to ekvivalence:

  • reflexivní –
  • symetrická –
  • transitivní –

Definice (orbita) obsahující prvek je množina

množinu orbit značíme .

Příklad: Koláčky (mák, tvaroh, povidla).

• akce odpovídají otočením koláčku.

Lemma (o orbitě a stabilizátoru): Nechť je konečná grupa s akcí na množině . Potom

Důkaz: Nechť množina je množina akcí , pro které . Pro akce pomocí lze definovat bijekci mezi a . Poté

Věta (Burnsideovo lemma): Nechť je konečná grupa s akcí na

1. (jednoduchá) pokud je konečná, pak počet orbit je roven „průměrnému počtu pevných bodů“
2. Nechť každá orbita má přiřazenou váhu . Potom

Důkaz: , když jsou váhy .

– dvojím počítáním

Poté první a druhý způsob dám do rovnosti