Zkouška 27.6.

Zdravím, před chvílí jsem slezl ze zkoušky do labu, tak Vám tu nechám čerstvé informace o tom, jak to vypadalo (pokud náhodou nejsem poslední, kdo tu zkoušku skládá :) )

1. Najděte vytvořující funkci pro (1,1,3,2,5,4,7,8,9,16,11,32,...)

2. Určete dimenzi prostoru cyklů "šachovnice" nxm a popište nějakou bázi.

3. Dokažte, že každý 4-regulární graf obsahuje 2-faktor. (Nápověda: 4 je sudé číslo. Ještě jedna nápověda: Dokonce 4/2 je sudé číslo. Poslední nápověda: Není radno zapomínat, co jsme se naučil v prvním ročníku.)

4. Nechť G je rovinná triangulace s alespoň 4 vrcholy (to je rovinné nakreslení, jehož všechny stěny jsou trojúhelníky). Označme Dg množinu všech stěn. Pokud G obsahuje Hamiltonovskou kružnici, potom existuje množina stěn D' (podmnožina Dg) taková, že bipartitní graf incidence

      Bg,d' = (V(G) U D', {uS : u (element) S (element) D'})  
   

též obsahuje Hamiltonovskou kružnici. Dokažt. (Nápověda, tady vám stačí, co jsme se učili v DMI011).

Takto doslova opsáno zadání, snad Vám to bude užitečné :wink:

A reseni by nebylo? :)

No něco bych věděl:

1. (x^2+1)/(1-x^2)^2 + x/(1-2x^2)

2. Má-li šachovnice n x m vrcholů, má prostor cyklů dimenzi (m-1)*(n-1). Buď se na to přišlo základními větami o prostoru cyklů (v přednášce nebo v Matouškovi a Nešetřilovi), nebo se také dalo vzpomenout si, že stěny rovinného grafu tvoří bázi prostoru cyklů, to je takové elegantní, nicméně na to přišel jediný člověk (a já to nebyl).

3. To si moc nepamatuju, jak to vysvětloval. Našel tam kružnici přes všechny hrany (viz věty o eulerovských tazích), pak nějak na každém vrcholu barvil hrany vždy dvě červeně a dvě zeleně a pak už nevím.

4. Přes Hallovu větu, myslím, že se procházela ta hamiltonovská kružnice grafu G (řekněme C), z každého vrcholu u kružnice C se v C místo po hraně uv skočilo do jedné ze dvou stěn, které s uv sousedí, pak do vrcholu v a takhle se postupně postavila HK v Dg. A právě na volbu stěny, do které se má z u skočit, se použila Hallova věta, jen bylo potřeba si to rozmyslet a ověřit předpoklady, dají se tam vysledovat stupně vrcholů na každé partitě Dg (zde se použije, že je to triangulace) a prostě tak nějak.