KMA/TGD1 - Teorie grafů a diskrétní optimalizace 1
Z FAV wiki
- Homomorfismus a isomorfismus grafů; souvislost, stromy, kostry, minimální kostra
- Metrika grafu, minim ální cesta, distanční matice grafu
- Silná souvislost, kvazikomponenty, kondenzace, acyklické grafy, kritická cesta
- Rozložitelnost a slabá rozložitelnost matic
- Generická hodnost matice
- Síť, tok, existence toku v síti
- Maximální tok v síti, Ford - Fulkersonova věta
- Míry souvislosti grafu
- Algoritmy prohledávání a jejich použití
- Eulerovské a hamiltonovské grafy, postačující podmínky hamiltonovskosti
- Nezávislost, dominance, klikovost a jádro v neorientovaných grafech
- Jádro orientovanného grafu
- Barevnost grafu, chromatické číslo
- Třídy problémů P, NP
- Splnitelnost logických formulí, polynomialita problému 2-SAT
- NP-úplné problémy
- NP-úplnost problému splnitelnosti logických formulí
- Problém 3-splnitelnosti logických formulí a jeho NP-úplnost
- Nezávislost grafu a její NP-úplnost
- Barevnost grafu a její NP-úplnost
