Kombagra II

Vše co není uvedeno jinde
Oracions
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 30. 1. 2014 16:18
Typ studia: Informatika Mgr.

Kombagra II

Příspěvek od Oracions »

Dokažte Turánovu větu.
Dokažte Tutteovu větu.
Dokažte Kuratowského větu.
Napište uzavřenou formu exponenciální vytvořující řady, kde an = počet involucí na 1..n
Nechť H je graf. Dokažte, že existuje takové číslo c, že každý graf G, který neobsahuje H jako minor, tak má barevnost menší nebo rovnu tomu číslu c.

Věty nebyly zadány všechny jménem, ale svým popisem ("co víte o tom, jak Tutte charakterizuje grafy s perfektním párováním").
Tajpan

Re: Kombagra II

Příspěvek od Tajpan »

dneska jsem u Jelínka měl
a) počet (ne nutně dobrých) hranových obarvení K4 k barvami neizomorfních vůči permutaci vrcholů. -> aplikace Burnsideova lemmatu
b) postačující podmínky existence Hamiltonovské kružnice v grafu. to jsem nevěděl, vyměněno za Vizingovu větu. nějaké doplňující otázky

mezi doplňujícími otázkami bylo, jak jsou na tom s hranovou barevností úplné grafy - pro lichá n \chi\prime(K_n) = \Delta(K_n)+1, pro sudá \chi\prime(K_n) = \Delta(K_n). důkazy jsem k tomu nevěděl, po zapsání známky (trojky, vzhledem k předvedenému výkonu jsem byl spokojený) mi Jelínek navrhl, že mi je ukáže. liché n bylo hned (každý vrchol by musel mít hrany všech barev, ale vrcholů je licho, takže se nedají spárovat), ale u postupu, jak obecně obarvit sudé n, jsme se zadrhli a asi po půlhodině Jelínek naznal, že na to nemůže přijít a že můžu jít, jestli chci.

jako přednášející i zkoušející moc fajn
Odpovědět

Zpět na „Ostatní“