Skúška 4.6.

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?

• Skupina A:

  • Strana 1

  • Strana 2

• Skupina B

  • Strana 1

  • Strana 2

A reseni by nebylo? a probiha to jako loni? nebo spis jak to probiha

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

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ě.

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 :)