Kombagra II

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Kombagra II

Re: Kombagra II

od Tajpan » 10. 7. 2014 18:59

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

Kombagra II

od Oracions » 5. 2. 2014 17:37

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").

Nahoru