Kdy a kde:

Informace o cvicenich:

Zapocet je za 15 bodu, ktere lze ziskat za vyreseni zapoctovych prikladu (celkem max. 30 bodu) nebo jinym zpusobem stanovenym cvicicim. Aktualni pocty bodu. Zadani prikladu budou zverejnovana zde (ve trech seriich v prubehu semestru).

Odprednesena latka:

DatumObsah prednaskyZdroje
5.10. Perfektni parovani (Tutteho veta pomoci Edmonds-Gallaiovy dekompozice), Petersenova veta (existence perfektniho parovani v 3-regularnim grafu bez mostu), hledani podgrafu s predepsanymi stupni. Diestel, kapitola 2.2.
12.10. Edmondsuv algoritmus pro nalezeni nejvetsiho parovani. Pocet parovani v bipartitnim kubickem grafu. Lovasz a Plummer, kapitola 9.1.
19.10. Plochy vyssiho rodu, Eulerova formule. Barevnost grafu na plochach, Heawoodova formule. Prezentace. Bollobas, kapitola V.3.
26.10. Grafove minory. Dukaz Kuratovskeho vety (a Tutteho veta o 3-souvislych grafech). Diestel, kapitoly 3.2 a 4.4.
2.11. Vrcholova a hranova barevnost grafu: Brooksova a Vizingova veta. Prezentace. Diestel, kapitoly 5.2 a 5.3.
9.11. Perfektni grafy: tridy perfektnich grafu, slaba a silna veta o perfektnich grafech. Diestel, kapitola 5.5.
16.11. Tutteho polynom: definice, specializace (chromaticky polynom, ...), hodnoty. Bollobas, kapitoly X.1, X.2 a X.4.
23.11. Hamiltonovske kruznice (Diracova a Oreho veta, Chvataluv uzaver, protipriklad na hamiltonovskost rovinnych 3-souvislych 3-regularnich grafu a souvislost s vetou o 4 barvach). Diestel, kapitola 10.
30.11. Enumerace (zopakovani a prohloubeni vysledku o generujicich funkcich). Wilf, kapitoly 1.1, 2.1, 2.2, 3.15, 3.16 a 3.17.
7.12. Burnsideovo lemma a Polyova enumerace. Bollobas, kapitola VIII.4.
14.12. Extremalni teorie: Turanova veta, zakazane minory vynucuji degenerovanost, Erdos-Ko-Radova a Erdos-Szekeresova veta. Jukna, kapitoly 7 a 8 a Diestel, kapitoly 7.1. a 7.2
21.12. Ramseovska teorie (hypergrafy, nekonecna verze, kanonicka Ramseyova veta, Erdos-Hajnalova hypoteza). Bollobas, kapitola VI, Diestel, kapitola 9.1., Jukna, kapitola 9; veta 1.1 v Ramsey-type theorems with forbidden subgraphs.
4.1. Samoopravne kody: definice, linearni kody, Singletonuv odhad, Hamminguv odhad a kod, Golayuv kod. Kaiser, kapitoly 1, 3, 4.1.
11.1. Samoopravne kody: Hadamarduv kod, Plotkinuv odhad, Gilbert-Varshamova konstrukce. Elias-Basallyguv odhad. Kaiser, kapitoly 10.1, 10.3, 12.1, 12.2.

Priklady ke cviceni

Na strankach prednasky z predchozich let (2010, 2009) muzete nalezt pomerne obsahly seznam prikladu, ktere by vam mohly pomoci pri priprave na zkousku.

Doporucena literatura: