Zápočet 10. 1. 2013

Ahoj,

tak dnes to bylo lehoučké, že už to lehčí být nemohlo. Čepek prohlásil, že seznam na webu není asi aktuální a tak zvolil něco, co tam určitě je a dělalo se to na cvičení :-)

a) Mějme množiny $S_i, i = 1..n$ po dvou disjunktní, $S$ a množinu $I=\{A \subseteq S : \forall i |A\cup S_i|\leq 1\}$. Dokažte, že (S,I) je matroid. (Takový ten středně těžký matroidový jako má na webu.
b) Najděte stok v grafu zadaném maticí sousednosti na $\mathcal{O}(n)$ přístupů do paměti.
c) Zkonstruujte optimální VP pomocí blackoboxu řešícího rozhodovací verzi.