Cviční z KombAGry 3, podzim 2012

Cvičení probíhá každé pondělí 17:20 v S4. Sleduje přednášnku Zdeňka Dvořáka.

Zápočet

Účast na cvičení není povinná. Zápočet je za řešení dom. úkolů.

Obsah cvičení

15.10. Různé definice stromové šířky (dekompozice, k-strom, hra na policisty a zloděje, brambles), existence "hezké" a "malé" dekompozice, každá klika je celá v nějakém nodu dekompozice.

22.10. Příklady problémů v MSOL, tw(grid), modifikace formulí simulující přidání hrany a jiné, sudost |G| není v MSOL, úvahy o možnosti počítání 3-obarvení a vypsání všech řešení.

29.10. Courcellova věta, počítání řešení, maximalizace jedné množiny, Ehrenfeucht–Fraïssé hry pro MSOL a nevyjádřitelnost např. "sudost" v MSOL a "souvislost" v FOL.

5.11. Diskuze k alg. na hledání opt. stromové dekompozice, zjemňování zadané speciální dekompozice, hledání minoru mřížky když algoritmus nahlásí velkou šířku.

12.11. Souvislost a linkovanost grafů, minory a úplné podgrafy, vlastní třída uz. na minory je degenerovaná, 4-souvislý nerovinný graf je 2-linkovaný. (cvičil V. Tůma)

19.11. Arboricita a vztah k degenerovanosti a mad (maximální průměrný stupeň přes všechny podgrafy), nikde-nulové toky pro různé grafy a grupy, toky v duálu rovinného grafu odpovídají vrch. obarvením.

26.11. Vybíravost speciálních grafů v charakterizaci 2-vybíravých grafů, rovinný graf, který není 4-vybíravý, bipartitní rovinné grafy jsou 3-vybíravé (3-degenerovanost a speciální orientace pro lemma z přednášky).

3.12. Regurality lemma, znění a cvičení na regulární páry, ekvivalentní znění, trivialita pro řídké grafy, odhady počtu trojúhelníků ve třech regulárních párech.

10.12. Přednes grafově-teoretických písní (viz níže), opakování removal lemma, Erdös-Stone, Erdös-Burr pro omezený stupeň, podrobný důkaz Lemma 11 ze Zdeňkova handoutu.

Domácí úkoly

Neposílejte prosím nascanovaná či nafocená řešení. Preferuji PDF, PS, příp. TXT či ODT. Poslední termín odevzdání je konec zimního zkouškového (17.2.). Počítejte s tím, že možná nebudu vždy k zastižení.

Zápočet je za dosažení poloviny z celkového počtu bodů. Za včasné odevzdání je bodů dvojnásobek. Série budou pravděpodobně dvě až tři. Počty bodů nezveřejňuji ale eviduji a sdělím na požádání emailem či osobně před/na/po cvičení.

1. série [PDF] (29.10. — 11.11. — 17.2)

2. série [PDF] (26.11. — 10.12. — 17.2) [článek k příkladu 6]

Erdös – Kámen

Zazpívali 10.12. Ladislav Láska, Lucie Mohelníková a Jan Musílek (kytara) za 47 sekund jako řešení 2. série domácích úkolů.

Pro každý graf jménem H,
v němž je nějaká hrana,
pro každé alfa kladné,
vždy máme n nula.

Pak mějme na alespoň,
n nula uzlech graf,
má-li více než E hran,
H je jeho podgraf.

Převraťme jedna bez chí,
přičtěme jedničku,
přidejme k tomu alfa,
máme jen chviličku.

Pak celý tento výraz,
čtvercem n znásobme,
podělme celek dvěma,
a máme naše E.

Skleničku vyprázdníme,
až do dna přátelé,
vždyť to je konec znění,
Erdöse – Kamene. ❏

(pozn.: místo "v němž je nějaká hrana" je v původním znění věty chi>=2, tyto podmínky jsou ekvivalentní)

Jaj