Kombinatorika a grafy I - Balko 2019

spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

Kombinatorika a grafy I - Balko 2019

Příspěvek od spidoosho »

Zadani
Definujte KPR a řád KPR + kolik je v KPR řádu n trojic bodov ležiacich na rovnakej priamke.

Definujte rez a elementárny rez + nájdite sieť na n vrcholoch, ktorá má n-1 elementárnych rezov, ktoré sú aj do inkluze elementární.

Definujte párovaní + nájdite súvislý bipartitný graf minimálneho stupňa 4, ktorý ma obe partity rovnakej veľkosti a nenachádza sa v ňom žiadne párovanie, ktoré obsahuje všetky vrcholy.

Uveďte a dokážte Mengerovu vetu.

Napíšte čo najviac z Ramseyovej teórie (definície, tvrdenia, vety, bez dôkazov)

Poznamky
"Skúška vyzerá presne ako vzor na stránke. Každý si vytiahne jednu A4 a pracuje na nej. Balko potom po nejakom čase začne chodiť ku študentom a pýta sa či už chcú predviesť nejakú úlohu (môžu aj všetky). Buď je správne alebo upozorní, že tam je nejaká chybička a môžeš si to ešte opraviť. Takto obíde triedu niekoľkokrát až kým si s každým neprejde všetky otázky. Prípadne dáva doplňujúce otázky.
V podstate príjemná skúška, aj keď niečo človeku vypadne snaží sa naviesť na odpoveď. Pri uvádzaní viet a definícií sa cenia maličkosti a presnosť."

-----------------------------------------

Zadani
Definujte vytvořující funkci, uveďte posloupnost jež patří k 1/(1-8x**3)

Definice kombinatorické koule.
Určete objem B((1,2,3),2)

Řekněte vše co víte o souvislosti grafů.

Dokažte kolik bodů a přímek má konečná projektivní rovina.

Definice řezu a elementárního řezu.
Uveďte graf na n vrcholech, který má n-1 vzhledem k inkluzi minimálních řezů.

Poznamky
Je to fajn, Balko si pěkně povídá.

-----------------------------------------

Zadani
1) definice VF a najit funkci pro 0,1,0,2,0,3,0...
2) definice vrcholove 2-souvisly graf a dokazat za strom a 2-souvisly graf maji jine skore
3)defince parovani a najit bipartivni graf (kazda partita stejna, stupen min 4), pro ktery existuje parovani, ktere neobsahuje vsechny vrcholy
4)Dokaz vetu o tocich a rezech
5) vse o ramseyove teorii

Reseni
2) strom ma vrcholy stupne 1 to 2-souvisly graf nema
3)vezmes 4 vrcholy (v kazde partite) a hrany z ostatnich vrcholu budou smerovat pouze do nich

Poznamky
Vsechno chtel presne zadefinovat, nejake vagni formulace mu nestaci...

-----------------------------------------

Zadani
1. Definujte systém různých reprezentantů + příklad grafů, kde vrcholy jsou reprezentovány hranami s nimiž jsou incidentní (nejsem si jit, zda si zadání příkladu pamatuji přesně ale pravděpodobně ano)
2. Definujte incindenční grafy + byla zadán množinový systém a každá množina obsahovala permutaci o 10 prvcích, kolik hran bude mít incidenční graf
3. Definujte kostry + Máte zadán úplný bipartitní graf K20,10 , kolik hran bude mít kostra grafu vzniklého odebráním jedné hrany a kolik koster bude mít doplněk tohoto grafu
4. Formulujte a dokažte Mengerovu větu
5. Průřezová otázka na řešení rekurencí.

-----------------------------------------

Zadani
1) Definovat incidenční graf a určit kolik má hran incidenční graf kde množina i obsahuje všechny permutace, kde p(i)=i.
2) definovat hranovou k-souvislost a rozhodnout jestli existuje graf s hranovou souvislostí 7 a vrcholovou 4.
3) definovat shodné kódy a určit parametry kódu s abecedou velikosti 7, délkou slov 4 a tvarem slova (x1,x1,x2,x2), určit počet shodných kódů k tomuto kódu.
4) Zformulovat a dokázat počet zakořeněných binárních stromů
5) vše o SRR

Reseni
1) 10! (10 množin, z každé vede 9! hran - i zafixujeme a zbylé permutujeme)
2) Ano (tři K4, všechny vrcholy krajních K4 jsou spojeny se všemi prostřední, ale ne mezi sebou, tedy vrcholová je 4 (prostřední K4) a hranová 7 - existuje vždy 7 disjunktních cest
3) parametry (4,2,2)7 , počet shodných = 6!/(2!2!) = počet permutací děleno permutacemi stejných prvků

Poznamky
Po tři čtvrtě hodině začne obcházet a kontrolovat co jste napsali. Rád věci nazývá pravým jménem a tedy opraví i drobné nepřesnosti, nicméně naopak i poté dokáže být shovívavý. Doporučuji se naučit ty důkazy, zbytek už se dá vymyslet a příklady nejsou těžké.
Odpovědět

Zpět na „Ostatní“