# Skúška 4.6.

<{ForumPost(poster="Caparzzo", timestamp=2007-06-04 10:44:04)}>
1. vytv. funkcia (1,0,3,2,5,4,7,6,...)  
2. nájsť maximálne párovanie v bipartitnom grafe  
3. Dimenzia priestoru cyklov šachovnice s n*m vrcholmi, popísať bázu  
4. Pár otázok na Hallovu vetu :)  
5. dokázať, že v 3-regulárnom grafe je vrcholová súvislosť rovná hranovej.Platí to aj v 4-regulárnom grafe?
<{/ForumPost}>

<{ForumPost(poster="Zdeněk Vilušínský", timestamp=2007-06-04 11:02:48)}>
* Skupina A:

    * [Strana 1](http://www.ms.mff.cuni.cz/~gurss5am/A1.png)
    * [Strana 2](http://www.ms.mff.cuni.cz/~gurss5am/A2.png)
* Skupina B

    * [Strana 1](http://www.ms.mff.cuni.cz/~gurss5am/B1.png)
    * [Strana 2](http://www.ms.mff.cuni.cz/~gurss5am/B2.png)

<{/ForumPost}>

<{ForumPost(poster="luckless", timestamp=2007-06-04 13:48:55)}>
A reseni by nebylo? a probiha to jako loni? nebo spis jak to probiha
<{/ForumPost}>

<{ForumPost(poster="peva", timestamp=2007-06-04 15:06:52)}>
Probiha to tak, ze dostanes papier, mas hodinu a pol na vyriesenie, odovzdas papier, po 2h sa dozvies vzorove riesenia spolu s bodmi (fikane v tomto poradi), na trojku musis mat priblizne nieco cez 2 a pol prikladu. Konkretne stupnica bola nejak taka, ze max. pocet bodov bol myslim 32, do 29 1 ,do 24 2, do 19 3,zvysok neuspel( mozno trosku nepresne, ale nepamatam si to presne), body boli cca 6,6,4,8,8 . Takze na trojku musis mat minimalne nejake 3 priklady, potazne 2 a nejaku vazciu polku z tazkeho tretieho
<{/ForumPost}>

<{ForumPost(poster="Zdeněk Vilušínský", timestamp=2007-06-04 15:24:02)}>
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ě ) :oops:   
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ě.
<{/ForumPost}>

<{ForumPost(poster="vlk^0R", timestamp=2007-06-04 16:26:23)}>
Povedal by som ze velmi jednoduche otazky, jedina spinavost bola v priklade 2, kde si kazdy vsimol zadanie: "Najdite najvacsie parovanie v nasledujucom grafe", ale zabudol si precitat ten dovetok napisany 'bielym atramentom':  "... a dokazte, ze je najvacsie". To pripravilo vela ludi o lepsiu znamku, vratane mna :)
<{/ForumPost}>