Trošku pevu opravím, 3 příklady po 6 bodech, dva po 8. Stupnice šla dolů po 5 ti bodech.
Jinak řešení:
1)
A: vezmu 1,2,3,... a odečtu od ní 0,2,0,2,... (jsem v tom prostě neviděl a dělal to hrozně složitě )
B: Trivka, dvakrát 1,2,3,... obě proložím nulami a jednu posunu.
2)
A: Metodou kouknu a vidím nebo F-F, maximální párování protože zaplním celou jednu paritu.
B: Max párování velikosti 5, chtělo to ukázat proč.
3)
A: Vzoreček na dimenzi |E| - |V| + 1. Bázi popíšu pomocí nějaké konkrétní kostry a přidávám hrany do kružnic. Také to šlo dělat tak, že pro rovinné grafy tvoří jejich bázi vnitřní stěny, ale to jste museli i naznačit důkaz.
B: Stejný vzoreček, chtělo to šikovně vybrat kostru.
4)
A i B: 4 tvrzení, odpovědi v pořadí ano, ne, ne, ano u obou. Ze znalosti odpovědí už na to přijdete, u ne se dali nalézt protipříklady.
5)
doplňující otázka neplatila u obou, stačí najít protipříklad (u B je už na 4 vrcholech)
A: že Kv(G) <= Ke(G) víme z přednášky, chtělo to tu druhou inkluzi. Rozborem případů vrcholové souvislosti, jak pak vypadá hranová - nezapoměňte, jako já, že je i 0-souvislost.
B: Pozor na indukci, musí se dělat podle počtu uší! Také když začnete od 4 vrcholů, neřekne vám to nic o C5. Takže kdo prý začal od C3 měl sice popsaného víc prostoru, ale nemusel se zabývat speciálními případy.
Druhá možnost je dokazovat sporem přes výběr maximální komponenty ke kontrahované hraně.
Věda je jako sex. Jistěže má nějaké praktické výsledky, ale proto ji přece neděláme. - R.P.Feynman
I krátký algoritmus může mít chování tak komplikované, že mu nerozumí ani jeho autor.
