# Složitost I Čepek 23. 1. 2014

<{ForumPost(poster="mathemage", timestamp=2014-01-23 17:39:17)}>
*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:
<{/ForumPost}>