| 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.
- Dokazte, ze graf G ma parovani pokryvajici alespon |V(G)|-k jeho vrcholu prave tehdy, jestlize
neexistuje mnozina S vrcholu takova, ze G - S ma vice nez |S|+k lichych komponent.
|
| 2 |
- 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; toto tvrzeni je ekvivalentni vete o 4 barvach.
- Petersenuv graf ma hranovou barevnost 4.
|
| 4 |
- 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).
|
| 5 |
- 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.
|
| 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.
|
| 6 |
- 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?
|
| 7 |
- Ukazte, ze 3-ti mocnina kazdeho souvisleho grafu je hamiltonovska.
- Ukazte, ze ma-li graf vsechny stupne liche, pak kazdou jeho hranou prochazi sudy pocet hamiltonovskych kruznic.
- Naleznete souvisly graf G bez hamiltonovske kruznice takovy, ze pro kazdou neprazdnou podmnozinu jeho vrcholu S
je pocet komponent G-S nanejvys |S|.
|
| 8 |
- Naleznete vytvorujici funkci pro retezce z pismen A, B a C bez podretezce ABC.
- Naleznete vytvorujici funkci pro zakorenene stromy (kde zalezi na poradi synu).
- Naleznete vytvorujici funkce pro
- pocet zpusobu, jak vyjadrit n jako soucet lichych prirozenych cisel (bez ohledu na poradi)
- pocet zpusobu, jak vyjadrit n jako soucet navzajem ruznych prirozenych cisel (bez ohledu na poradi)
a ukazte, ze tyto pocty jsou stejne.
|
| 9 |
- 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?
- Urcete pocet obarveni cyklu delky n tremi barvami, kde obarveni lisici se pouze rotaci cyklu
povazujeme za stejna, a kde sousedni vrcholy musi mit ruznou barvu.
- 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).
|
| 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.
- Dokazte, ze kazdych n>=5 bodu v rovine obsahuje 4 body, ohranicujici konvexni 4-uhelnik, jehoz vnitrek
neobsahuje zadny ze zbylych bodu.
|
| 11 |
- 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.
|
| 12 |
- 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 paritni matici Hammingova kodu s pozici chyby?
|