zkouška Ondřej Pangrác 24.6. 2010

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
blejzz

zkouška Ondřej Pangrác 24.6. 2010

Příspěvek od blejzz »

Dnešní zkouška byla strašně super.

Příklady společné pro všechny:

1) napište generující funkci k posloupnosti (2,1,4,3,6,5,8,7,...)

řešení:
prvně víme, že poslopnost ze samých jedniček je určena generující funkcí 1/(1-x) po zderivování dosteneme poslounost (1, 2, 3, 4,...) však to známe... tomu tedy odpovídá funkce 1/(1 -x)^2 teď stačí funkci vynásobit dvěma a provést substituci x^2 za x to dostaneme posloupnost (2, 0, 4, 0, 6, 0, 8,...) a funkci 2/(1 - x^2)^2 to máme půlku hotovou... teď si stačí všimnout, že před substitucí vypadala posloupnost takto: (2, 4, 6, 8, ...) a od ní, když odečteme původní poslopnost ze samých jedniček a dostaneme tedy posloupnost (1, 3, 5, 7, ...) vytvořující funkce k této posloupnosti bude vypadat 2/(1 - x)^2 - 1/(1 - x) = (1 + x)/(1 - x)^2 a po substituci x za x^2 dostaneme (1, 0, 3, 0, 5, 0, 7, 0, ...) posuneme vpravo vynásobením x a dostaneme poslounost (0, 1, 0, 3, 0, 5, 0, 7, 0, ...) generovanou funkcí x * (1 + x^2)/(1 - x^2)^2 = (x + x^3)/(1 - x^2)^2 teď už jen stačí sečíst posloupnosti (2, 0, 4, 0, 6, 0, 8,...) a (0, 1, 0, 3, 0, 5, 0, 7, 0, ...) a dostaneme výslednou (2,1,4,3,6,5,8,7,...) pro kterou je generující funkce součet funkcí 2/(1 - x^2)^2 a (x + x^3)/(1 - x^2)^2 což je hledaná generující funkce (2 + x + x^3)/(1 - x^2)^2

2) druhý příklad byl netriviální:
Dokažte, že pro každý (2k)-regulární graf G(V,E) existuje 2-faktor . 2-faktorem grafu rozumíme takový podgraf H(V, F) grafu G(V,E), že V(G) = V(H) a F je podmnožinou E tak, že pro každý vrchol v z V(H) platí, že deg(v) = 2.

řešení:
neznám. nevím. nenapadá mě. Jinak poznámka pod čarou pro ty co nevědí :) (2k)-regulární graf G(V,E) je graf pro který platí, že pro každý vrchol v z V(G) platí, že deg(v) = 2k (tzn. nějaké číslo dělitelné dvěmi) Byl bych rád, kdyby zde někdo své řešení zveřejnil. :)

potom samozřejmě každý dostal úlohu xtra přímo pro něj :) většinou něco jako: napište definici... (latinských čtverců, KPR, Toku v síti...) a zformulujte a dokažte větu.... bla bla bla :) Jinak nejpříjemnější zkouška na které jsem zatím byl. doufám, že jsem někomu aspoň ulehčil život, když už jsem se tu s tím psal :) PEACE
Návštěvník

Re: zkouška Ondřej Pangrác 24.6. 2010

Příspěvek od Návštěvník »

2) Graf orientujeme ve směru Eulerovského tahu, každý vrchol rozpůlíme na vstupní (v+) a výstupní (v-), hrany se nechají tak, že když byla (u, v), vezmeme (u-, v+). Z Hallovy věty existuje mezi vstupními a výstupními vrcholy perfektní párování, vezmeme ho a slepením vrcholů dostaneme 2-faktorizaci.
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“