Kambinatorika a grafy II - 18.1. [zk]
Napsal: 19. 1. 2008 15:13
Tak jsem byl vcera na zkousce z Kombagry II. Na devatou hodinu jsem tam byl jediny :) + par lidi na diskretku. Zkousel Kráľ. Byl pomerne prijemny. Zadani (bylo v anglictine, ja napisu ceskoanglicky):
1) Zneni SRL + formulovat a dokazat "Removal lemma"
2) Dokazat, ze kazdy k-linked graf je (2k-1)-connected
3) Je dan graf na prirozenych cislech (vrcholy ~ {1,2...k}). Definujemegraf W(G), kde vrcholy odpovidaji hranam grafu G a ab~cd je hrana, pokud b=c & a<=b<=d.
Dokazte, ze W(G) neobsahuje trojuhelnik
Ukazte, ze chromaticke cislo W(Kn) jde k nekonecnu pro n jdouci k nekonecnu
...priklady celkem dobre, jen druhou cast trojky jsem nejak nedal -> dal mi hint, at pouziju Ramseyovu vetu ... ale stejne jsem se zasekl. :( Nakonec mi to skoro nadiktoval a pak se zeptal na zneni vety o vybiratelnosti rovinnych grafu.
Vysledek: za 1 , takze vzhledem k tomu, ze jsem mel na uceni 2 (slovy dva) dny a sel jsem si pro jakoukoliv znamku, tak maximalni spokojenost! :))
Jeste jsem s nim po zkousce, kdyz mi zapisoval znamku, trochu pokecal. Byl rad, ze jsem dal to removal lemma, pry je to spolu s tim hroznym Erdos-Stone nejtezsi z prednasky.
No, celkovy dojem veskrze pozitivni! ;)
1) Zneni SRL + formulovat a dokazat "Removal lemma"
2) Dokazat, ze kazdy k-linked graf je (2k-1)-connected
3) Je dan graf na prirozenych cislech (vrcholy ~ {1,2...k}). Definujemegraf W(G), kde vrcholy odpovidaji hranam grafu G a ab~cd je hrana, pokud b=c & a<=b<=d.
Dokazte, ze W(G) neobsahuje trojuhelnik
Ukazte, ze chromaticke cislo W(Kn) jde k nekonecnu pro n jdouci k nekonecnu
...priklady celkem dobre, jen druhou cast trojky jsem nejak nedal -> dal mi hint, at pouziju Ramseyovu vetu ... ale stejne jsem se zasekl. :( Nakonec mi to skoro nadiktoval a pak se zeptal na zneni vety o vybiratelnosti rovinnych grafu.
Vysledek: za 1 , takze vzhledem k tomu, ze jsem mel na uceni 2 (slovy dva) dny a sel jsem si pro jakoukoliv znamku, tak maximalni spokojenost! :))
Jeste jsem s nim po zkousce, kdyz mi zapisoval znamku, trochu pokecal. Byl rad, ze jsem dal to removal lemma, pry je to spolu s tim hroznym Erdos-Stone nejtezsi z prednasky.
No, celkovy dojem veskrze pozitivni! ;)