Na začátku cvičení jsme si zopakovali pojmy kolem grafů a začali jsme s izomorfismy. Vyřešili jsme první úlohu (řešení je kombinace této a této úlohy) a ukázali si pár invariantů, které izomorfismy zachovávají. Dále jsme se podívali na druhou úlohu, kde můžeme pro neizomorfismus pohodlně využít právě jeden z invariantů, konkrétně počet hran.

Pokračovali jsme s doplňky ve třetí úloze (řešení zde) a nakonec jsme si uvědomili, že doplňky bipartitních grafů o aspoň pěti vrcholech nemůžou být bipartitní (zde).

Po krátkém opakování jsme se vrhli na první úlohu, kdy jsme zkoumali, co se děje s metrikami, když máme nějak ohodnocené hrany. Vysvětlili jsme si, kde selhává přístup definování délky pomocí nejkratších ohodnocených sledů když máme záporné hrany, ale pak jsme zjistili, že ani u nejkratších cest si se zápornými ohodnoceními moc nepomůžeme.

Pak jsme se rozhodli omezit se na nezáporné hodnoty, protože se zápornými byly takové problémy. Ale ukázalo se, že ani nula není tak milá, jak bychom chtěli, a rozbíjí nám první podmínku v definici metriky, tedy jsme měli dva různé vrcholy ve vzdálenosti 0. Když jsme se nakonec omezili na kladné hodnoty, všechno už klaplo a mohli jsme si oddechnout - je ovšem nutné podotknout, že je důležité, že vzdálenost sousedních vrcholů nemusí dle definice nutně odpovídat ohodnocení jejich hrany.

Pokračovali jsme s počítáním čtyřcyklů v grafu pomocí matice sousednosti, k tomu jsme si prvně zopakovali, jak počítat trojúhelníky. Potom jsme si rozmysleli, že už nemůžeme být tak přímočaří, protože ne všechny uzavřené sledy délky čtyři jsou kružnice. Když jsme však všechny tyto potíže překonali odečtením těchto problémových sledů, už bylo vše snadné, stačilo si jen uvědomit, kolikrát počítáme každý čtyřcyklus.

Nakonec jsme si vyzkoušeli rozpoznávání eulerovských grafů, řekli jsme si, že to je hodně odlišný problém od Hamiltonovské kružnice, a nakonec jsme si dokázali, že grafy se všemi stupni sudými (což není totéž jako eulerovské grafy!) nemají most (zde).

Začali jsme s připomenutím věty o skóre a jejím použitím. Tím jsme si vyřešili první úlohu (skóre jsou jenom případy a,f). V druhé úloze jsme si pak uvědomili, že stejné skóre nutně neznamená izomorfismus grafů. Je celkem snadné najít příklad nějakých dvou neizomorfních grafů, ale dokonce existují i neizomorfní souvislé grafy se stejným skóre. Na rozmyšlení jsem je možné toto rozšířit ještě silněji: existují i neizomorfní stromy se stejným skóre.

Zbytek cvičení jsme věnovali biologii grafů - hráli jsme si se stromy, lesy, listy a kostrami. Ve cvičení 3 (řešení těžší implikace zde) jsme zpozorovali, že kostru můžeme chtít po jakémkoliv souvislém grafu. V úloze 4 jsme potom zjistili, že stromy můžeme vytvořit přidáváním listů a že díky tomu můžeme snadno ukázat, že stromy jsou bipartitní. Nakonec jsem rychle naznačil, jak dokázat, že eulerovský graf nemá žádné mosty.

Na cvičení jsme se věnovali dvěma tématům: rovinnosti a barevnosti grafů. Po připomenutí definic jsme si řekli nějaké obecné odhady na počty hran rovinného grafu, které se mohou celkam často hodit jako způsob rozpoznání, že graf není rovinný. (Na druhou stranu, existují nerovinné grafy, které tímto testem mohou projít.) To jsme si poté vyzkoušeli na přikladech konkrétních grafů: 1a), který je rovinný a teserakt (4-rozměrná hyperkrychle), který rovinný není. Též přidávám slíbený link na stackexchange, kde se ukazuje, jak je v hyperkrychli možné najít podrozdělení K_{3,3} nebo minor K_5.

Pak jsme pokračovali s dalšími úlohami ohledně rovinných nakreslení, konkrétně jsme si spočítali maximální počty stěn rovinných grafů (řešení zde) a pokračovali jsme s barvením grafů bez trojúhelníků, kde jsme zvládli dokázat slabší verzi věty o čtyřech barvách (zde). Jen bych poznamenal, že pro rovinné grafy bez trojúhelníků to dokonce umíme ještě vylepšit, Grötzschova věta dokonce říká, že všechny rovinné grafy bez trojúhelníků jsou 3-obarvitelné.

Nakonec jsme si z Eulerovy formule spočítali, že graf na alespoň jedenácti vrcholech nemůže zároveň být rovinný a přitom mít rovinný doplněk.

Na začátku jsme si prošli pojmy, tvrzení a věty z přednášky (i té budoucí, tam jsme ovšem neřekli vše, vynechali jsme mj. Markovovu a Čebyševovu nerovnost). Potom jsem ukázal ukázkový příklad na výpočet střední hodnoty pomocí rozdrobení náhodné veličiny na indikátory.

Po zbytek cvičení jsme potom počítali různé příklady.