Kombinatorika a grafy II - Vít Jelínek - 7.1.2013

Každý neuvedený předmět
pizet
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 25. 4. 2011 11:24
Typ studia: Informatika Bc.

Kombinatorika a grafy II - Vít Jelínek - 7.1.2013

Příspěvek od pizet »

Na skuske si clovek taha dve otazky. Jedna je dokaz nejakej vety z prednasky a druha je uloha.

Ja som mal:

1. Dokazat Brooksovu vetu z prednasky, teda dokazat, ze pre kazdy suvisly graf $G$, ktory nie je uplny alebo neparna (licha) kruznica plati, ze $\chi(G) \leq \Delta(G)$.

2. Nech $G$ je circle-arc graf (na papierku s ulohou bola uvedena definicia circle-arc grafu). Bolo treba dokazat, ze $\chi(G) \leq 2\omega(G)$. Najprv som nevedel, ze co s tym ale potom nahintoval, ze si mam uvedomit, ze intervalovy graf je specialny pripad circle-arc grafu, s tym to uz slo.

Skuska prebiehala v pohode, pan Jelinek mi dal dostatok casu na premyslanie.
Naposledy upravil(a) pizet dne 8. 1. 2013 12:57, celkem upraveno 1 x.
I love ginger candy.
Abby
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 4. 9. 2011 12:57
Typ studia: Informatika Mgr.

Re: Kombinatorika a grafy II - Vít Jelínek - 7.1.2013

Příspěvek od Abby »

Tak pridam moje skusenosti:

1. Sformulovat a dokazat extremalnu vetu pre grafy so zakazanymi minormi.
2. Buď K_{n,n} úplný bipartitný graf s partitou na vrcholoch \{v_1, \dots, v_n\}, úlohou je dokázať, že existuje n \choose 2 hranovo disjunktných ciest P_{1,2}, P_{1,3}P_{n-1, n}, kde cesta P_{i,j} vedie medzi vrcholmi v_i, v_j. Hint: Graf K_n má dobré hranové obarvení pomocí n barev.
3. Keďže sa mi ten príklad príliš nepodaril (a šla som na jednotku), tak som dostala moznost vytiahnut si dalsi - pocet roznych hranovych obarevni zakorenenych binarnych stromov na 7 vrcholoch (2 hladiny) k farbami, ak dva stromy povazujeme za rovnake, pokial sa lisia iba poradim synov. [Burnsideovo lemma]
Odpovědět

Zpět na „Ostatní“