# Zápočet 10. 1. 2013

<{ForumPost(poster="Krakonoš", timestamp=2013-01-10 21:33:29)}>
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.
<{/ForumPost}>