Title: Státnice / Obecná informatika / Pokročilá diskrétní matematika

Barvení grafů: definice a základní vlastnosti

Q: Barvení grafů: hranová barevnost (definice, formulace Vizingovy věty, souvislost s párováními v grafech)
A: Tomášovo Slámičovo video: https://www.youtube.com/watch?v=OZWZpQmGp0g
Souvislost s párováním: žádné dvě sousední hrany nesmí mít stejnou barvu -> každá barva definuje nějaké párování -> obarvení rozkládá graf na disjunktní sjednocení párování -> chromatický index reprezentuje minimální počet disjunktních párování

Q: Barvení grafů: Brooksova věta (formulace)
A: To je actually docela hustá věta.

Q: Barvení grafů: základní metody z důkazů Vizingovy a Brooksovy věty (Kempeho řetězce, hladový algoritmus)
A: Vizing tady: https://youtu.be/OZWZpQmGp0g

Q: Barvení grafů: silná a slabá věta o perfektních grafech (formulace), chordální grafy a další příklady tříd perfektních grafů
A: V teorii grafů udává silná věta o perfektních grafech charakterizaci perfektních grafů pomocí zakázaných podgrafů. Podle věty je graf perfektní právě tehdy, když neobsahuje lichou díru (tj. lichou kružnici délky alespoň 5) ani lichou antidíru (tj. doplněk liché díry) jako indukovaný podgraf.
Bipartitní grafy a linegrafy jsou taky perfektní

Párování v grafech: definice párování a perfektního párování

Q: Párování v grafech: párování v obecných grafech (formulace Tutteovy věty včetně důkazu jednodušší implikace, Petersenova
věta a její důkaz použitím Tutteovy věty)
A: Mučeníčko, mučeníčko...

Q: Párování v grafech: Edmondsův algoritmus (pouze vědět o jeho existenci)
A: vězte

Kreslení grafů na plochách: základní topologické pojmy (homeomorfismus, křivka, plocha)

Kreslení grafů na plochách: konstrukce ploch pomocí přidávání uší a křížítek (formulace), orientovatelné a neorientovatelné plochy, Eulerova charakteristika

Kreslení grafů na plochách: pojem buňkového (2-cell) nakreslení

Kreslení grafů na plochách: zobecněná Eulerova formule, její použití pro horní odhad počtu hran a minimálního stupně v grafu nakresleném na dané ploše

Grafové minory: definice a základní vlastnosti

Q: Grafové minory: zachovávání nakreslení při minorových operacích
A: pro podgraf očividné, je potřeba si rozmyslet kontrakci

Q: Množiny a zobrazení: přehled o používané terminologii (třídy a vlastní třídy, kartézský součin, relace, zobrazení, suma, potenční množina, …)
A: zbytek je asi jasný

Subvalence a ekvivalence množin: definice

Subvalence a ekvivalence množin: Cantorova-Bernsteinova věta (bez důkazu)

Subvalence a ekvivalence množin: spočetné množiny: definice

Subvalence a ekvivalence množin: spočetné množiny: zachovávání spočetnosti při množinových operacích

Subvalence a ekvivalence množin: mohutnost množin racionálních a reálných čísel, důkaz neekvivalence diagonální metodou

Dobré uspořádání: definice

Q: Dobré uspořádání: ordinální a kardinální čísla (definice)
A: Ordinální číslo nazveme kardinálním číslem, pokud každé menší ordinální číslo má i menší mohutnost.