Složitost I Čepek 23. 1. 2014

Písemná
Poly algoritmus na záporný cyklus ohodnoceného digrafu - viz 13. zadání zkouškových příkladů do tramvaje (na studnici)
[Bellman-Ford s 1 iterací navíc]
NP-úplnost záporné cesty ohodnoceného digrafu - viz 14. zadání zkouškových příkladů do tramvaje
[např. z Hamilt. kruž.:

1. graf (na $n$ vrcholech) -> digraf (s obousměrnými původními hrany)

2. nějaký vrchol $s$ si zduplikuju na $s$ a $s'$

3. ohodnotím hrany na $-1$

4. přidám nový vrchol $t$ a orient. hranu $s' \rightarrow t$ o váze $n-1$]

Ústní
Dneska neslyšel alg. na 2-souvislost, takže ten jsem dostal (možná strategie na učení, vylučovací metodou zjistit, jaká témata si těsně před tím zopakovat :D ). Pak ještě definice silné NP-úplnosti

Nestihl jsem přečíst všechny příklady do tramvaje, takže písemná docela chuťovka - 2. úlohu jsem vymyslel až 5 min před koncem :shock: Doporučuju si je aspoň 1 přečíst :wink: