KMA/TGD1 - Teorie grafů a diskrétní optimalizace 1
- 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
[editovat] Z: http://favwiki.jenda.eu/TGD1
V souborech jsou ke stažení folie z přednášek,pracovní text i vypracovaná teorie.
[editovat] Zkoušky
Reálné příklady od zkoušky 2012:
- Převeďte posloupnost činností do grafu a určete kritickou cestu:
| Činnost | Doba trvání | Závislost |
|---|---|---|
| A | 8 | - |
| B | 10 | - |
| C | 9 | - |
| D | 2 | A |
| E | 5 | A |
| F | 3 | C |
| G | 3 | D |
| H | 10 | B, D, E |
| I | 9 | B, D, E, F |
| J | 4 | G |
| K | 6 | G, I |
- Pomocí redukce IND<SAT řešte splnitelnost formule: f(x,y,z,u) = (x∨y∨¬z∨u)∧(¬x∨¬z)∧(x∨¬y∨¬u)∧(x∨y∨z)
- Příklad na maximální tok - nic nečekaného, ale ani úplně primitivního.
Obecně lze vždy očekávat jeden příklad na SAT (dost možná na redukci IND<SAT), jeden příklad na maximální tok (bez Ford - Fulkersona se na to ani nepodívá; najdete-li maximální tok, je nutné také zdůvodnit a ukázat, *proč* je maximální) a jeden příklad kritická cesta, rozložitelnost matic nebo další (asi by tam mohl být i Floydův algoritmus).
U ústní mu stačí v podstatě pár vět, jen jde o to, aby ty věty byly správné a obsahovaly všechno potřebné. Popsat stránku textem je úplně zbytečné (označí to za kecy) a je schopen z celé té stránky zakroužkovat dvě slova a dodat, že to je to, oč mu jde a ať to teda zkusíš ještě jednou, že pořád může všechno bejt v pohodě.
