Kombagra II
Napsal: 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").
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").