| 1 |
- Dokazte Hallovu vetu pomoci Tutteho vety.
- Dokazte, ze kazdy 3-regularni graf s nanejvys dvema mosty ma perfektni parovani.
- Dokazte, ze pro kazdy 3-regularni hranove 2-souvisly graf a jeho hranu e existuje perfektni parovani, ktere e obsahuje.
- Dokazte, ze kazdy k-regularni hranove k-souvisly graf se sudym poctem vrcholu ma perfektni parovani.
- Dokazte, ze kazdy k-regularni hranove (k-1)-souvisly graf se sudym poctem vrcholu ma perfektni parovani.
- Pro kazde k naleznete k-regularni hranove (k-2)-souvisly graf se sudym poctem vrcholu, ktery nema perfektni parovani.
- Naleznete algoritmus, ktery pro graf bez perfektniho parovani nalezne mnozinu vrcholu z Tutteho vety. Predpokladejte,
ze mate k dispozici algoritmus zjistujici, zda graf ma perfektni parovani.
|
| 2 |
- Dokazte, ze determinant antisymetricke matice sousednosti grafu
je nenulovy prave tehdy, kdyz graf ma perfektni parovani.
- Jestlize G je souvisly, ma alespon 4 vrcholy, a kazda hrana lezi v nejakem perfektnim parovani, pak
G je hranove 2-souvisly.
- Urcete maximalni pocet hran grafu na 2n vrcholech bez perfektniho parovani.
- 2-souvisly graf bud nema zadne perfektni parovani, nebo ma alespon 2 perfektni parovani.
|
| 3 |
- Pro kazde n>1 existuje bipartitni graf, ktery hladovy algoritmus
(odtrhavajici pokazde vrchol nejmensiho stupne, a barvici nejmensi pouzitelnou barvou)
obarvi n barvami.
- Jestlize G je linegraph nejakeho grafu, pak G neobsahuje K_{1,3} jako indukovany podgraf.
Opacna implikace neplati.
- Hranova barevnost bipartitniho grafu je rovna jeho maximalnimu stupni.
- Hranova barevnost 3-regularniho rovinneho grafu bez mostu je 3.
- Petersenuv graf ma hranovou barevnost 4.
|
| 4 |
- Ukazte, ze line graf bipartitniho grafu je perfektni.
- Ukazte, ze comparability grafy jsou perfektni.
- Ukazte, ze split grafy jsou perfektni.
- Graf je perfektni prave tehdy, kdyz kazdy jeho indukovany podgraf H
obsahuje nezavislou mnozinu protinajici vsechny jeho kliky nejvetsi velikosti.
- Nahradime-li v perfektnim grafu vrchol v jinym perfektnim grafem H
(tj. smazeme v a pridame uplny bipartitni graf mezi sousedy v
a vrcholy H), pak vysledny graf je perfektni.
|
| 5 |
- Ukazte, ze nakresleni rovinneho 3-souvisleho grafu je (kombinatoricky) jednoznacne.
- Ukazte, ze graf je vnejskove rovinny prave tehdy, kdyz neobsahuje podrozdeleni K4
a K2,3.
- Ukazte, ze kazdy rovinny graf ma nakresleni, v nemz vsechny hrany jsou prime, tj., usecky.
- Jake podminky musi splnovat trida grafu C, aby platilo nasledujici: existuje mnozina grafu X
takova, ze graf G patri do C prave tehdy, kdyz neobsahuje podrozdeleni grafu z X?
- Naleznete zakazane minory pro rovinne grafy.
|
| 6 |
- Naleznete nakresleni K7 na torus.
- Dokazte, ze K7 nelze nakreslit na Kleinovu lahev.
- Ktere grafy Kn,n lze nakreslit do projektivni roviny? Na torus? Na Kleinovu lahev?
- Naleznete kvadrangulaci projektivni roviny a toru barevnosti 4.
- Dokazte, ze kazdy graf bez podrozdeleni K4 lze obarvit 3 barvami.
|
| 7 |
- Urcete pocet ruznych obarveni sten krychle 3 barvami. Dve obarveni povazujeme za stejna, jestlize se
lisi pouze rotaci ci zrcadlenim.
- Urcete pocet navzajem neizomorfnich grafu na 4 vrcholech. Kolik z nich ma prave 5 hran?
- Pouzitim Polyovy enumeracni formule naleznete rekurzivni vzorec pro pocet zakorenenych ternarnich stromu
(stromy lisici se pouze permutaci poradi synu v nekterych vrcholech se povazuji za stejne).
|
| 9 |
- Dokazte, ze koeficient Tutteho polynomu u x je roven c'(1), kde c je chromaticky polynom.
- Dokazte, ze pokud G je sjednocenim grafu G1 a G2 sdilejicich nanejvys
jeden vrchol, pak T(G)=T(G1)T(G2).
- Pouzitim Tutteho polynomu urcete pravdepodobnost, ze graf vznikly z G odebranim kazde hrany
s pravdepodobnosti p (nezavisle) je souvisly.
- Ukazte, ze je-li G rovinny a H jeho dual, pak TG(x,y)=TH(y,x).
|
| 10 |
- Hustota hran Turanova grafu t_k(n) se v limite blizi (k-1)/k.
- Urcete maximalni pocet podmnozin n-prvkove mnoziny takovych,
ze kazde dve z nich maji neprazdny prunik.
|
| 11 |
- Urcete hodnotu R(K3,2K3).
- Urcete hodnotu R(2K3,2K3).
- Urcete hodnotu R(aK2,bK2).
- Ukazte, ze R(T1,T2) pro dva stromy T1 a T2 je linearni v poctu jejich vrcholu.
- Ukazte, ze pro libovolne obarveni konecnych podmnozin prirozenych cisel konecne mnoha barvami existuje nekonecna
mnozina X takova, ze pro kazde n, vsechny n-prvkove podmnoziny X neobsahujici prvnich n prvku z X maji stejnou barvu.
|
| 12 |
- Zformulujte a dokazte kanonickou Ramseyovu vetu pro matice.
- Dokazte, ze kazda posloupnost nm+1 cisel obsahuje nerostouci podposloupnost
delky n+1 nebo neklesajici podposloupnost delky m+1. Dokazte, ze toto tvrzeni
neplati pro posloupnost delky nm.
- Naleznete obarveni prirozenych cisel dvema barvami, ktere neobsahuje
nekonecne dlouhou monochromatickou aritmetickou posloupnost.
- Dokazte, ze prunikove grafy grafu funkci jsou perfektni.
|
| 13 |
- Ukazte, ze Hammingova vzdalenost je metrika.
- Ukazte, ze kod, ktery jsme odvodili z Fanovy roviny, je jednim z Hammingovych kodu.
- Naleznete "prirozenou" matici Hammingova kodu.
- Jak souvisi soucin slova s dualni matici Hammingova kodu s pozici chyby?
- Ukazte, ze je-li d sude, pak A(n,d)=A(n-1,d-1).
|