KMA/TGD1 - Teorie grafů a diskrétní optimalizace 1

1. Homomorfismus a isomorfismus grafů; souvislost, stromy, kostry, minimální kostra
2. Metrika grafu, minim ální cesta, distanční matice grafu
3. Silná souvislost, kvazikomponenty, kondenzace, acyklické grafy, kritická cesta
4. Rozložitelnost a slabá rozložitelnost matic
5. Generická hodnost matice
6. Síť, tok, existence toku v síti
7. Maximální tok v síti, Ford - Fulkersonova věta
8. Míry souvislosti grafu
9. Algoritmy prohledávání a jejich použití
10. Eulerovské ́a hamiltonovské ́grafy, postačující podmínky hamiltonovskosti

Nez ́vislost, dominance, klikovost a j ́dro v neorientovan ́ch grafech a a y J ́dro orientovan ́ho grafu a e Barevnost grafu, chromatick ́ ˇ ́ grafu e cıslo Tˇ ́ probl ́m ̊ P, NP rıdy e u Splnitelnost logick ́ch formul ́ polynomialita probl ́mu 2-SAT y ı, e NP- ́pln ́ probl ́my u e e NP- ́plnost probl ́mu splnitelnosti logick ́ch formul ́ u e y ı Probl ́m 3-splnitelnosti logick ́ch formul ́ a jeho NP- ́plnost e y ı u Nez ́vislost grafu a jej ́ NP- ́plnost a ı u Barevnost grafu a jej ́ NP- ́plnost