Kdy a kde:

Informace o cvicenich:

Po domluve s cvicicim muzete chodit na kterekoliv z techto cviceni; na uternim cviceni se bude procvicovat latka prednesena predchozi tyden. Zapocet je za 20 bodu, ktere lze ziskat za vyreseni zapoctovych prikladu (prvni, druha a treti serie prikladu, s napovedami), ci jinym zpusobem stanovenym cvicicimi. Pocty bodu.

Odprednesena latka:

DatumObsah prednaskyZdroje
29.9. Perfektni parovani: dukaz Tutteho vety. Tutteho veta implikuje Petersenovu vetu. Gallai-Edmondsova veta (pouze zneni a bleskovy naznak dukazu). Diestel, kapitola 2.2.
6.10. Edmondsuv algoritmus pro nalezeni nejvetsiho parovani. Nalezeni podgrafu se zadanymi stupni. Pfaffiany, pravdepodobnostni algoritmus pro nalezeni perfektniho parovani a souvislost s poctem perfektnich parovani (jen naznak hlavni myslenky). Lovasz a Plummer, kapitola 9.1.
13.10. Vrcholova a hranova barevnost grafu: Brooksova a Vizingova veta. Diestel, kapitoly 5.2 a 5.3.
20.10. Perfektni grafy: tridy perfektnich grafu, slaba a silna veta o perfektnich grafech (silna bez dukazu :-). Diestel, kapitola 5.5.
27.10. Dukaz Kuratovskeho vety (lemma o kontrahovatelne hrane, Tutteho veta of 3-souvislych grafech). Diestel, kapitoly 3.2 a 4.4.
3.11. Plochy vyssiho rodu, Eulerova a Heawoodova formule, souvislost s grafovymi minory a Hadwigerova hypoteza. Bollobas, kapitola V.3.
10.11. Burnsideovo lemma a Polyova enumerace. Bollobas, kapitola VIII.4.
17.11. statni svatek, prednaska se nekonala  
24.11. Tutteho polynom: definice, specializace (chromaticky polynom, ...), hodnoty. Bollobas, kapitoly X.1, X.2 a X.4.
1.12. Extremalni teorie: veta o slunecnici, Erdos-Ko-Radova a Turanova veta. Jukna, kapitoly 7 a 8 a Diestel, kapitola 7.1.
8.12. Ramseovska teorie: grafy, hypergrafy, nekonecna verze, princip kompaktnosti. Bollobas, kapitola VI, Diestel, kapitola 9.1.
15.12. Kanonicka Ramseyova veta, Van der Waerdenova veta. Castecna usporadani, Dilworthova veta. Bollobas, kapitola VI, Jukna, kapitola 9.
5.1. Samoopravne kody: definice, linearni kody, Singletonuv odhad, Hamminguv odhad a kod. Kaiser, kapitoly 1, 3, 4.1.
12.1. Samoopravne kody: Hadamarduv kod, Gilbertuv a Elias-Bassalyguv odhad (ktery se moc nepovedl). Kaiser, kapitola 10.1, 10.3, 12.1, 12.2 a Matouskuv text.

Priklady ze cviceni:

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

Doporucena literatura: