DMI011 Kombinatorika a teorie grafu I - 2006/07 (Valtr, Kratochvil)

Streda 9:00 v S5

ZKOUSKA: Hlaste se pres SIS (ke kteremukoliv prednasejicimu). Pred zkouskou musite mit udelen a zapsan zapocet. Pozadovany jsou znalosti odprednesene latky a schopnost reseni lehcich a stredne tezkych prikladu. Hlavni casti zkousky je 90minutova pisemka, po opraveni a vyhlaseni vysledku dostanete znamku nebo budete jeste ustne dozkouseni.

stranka uterni paralelky

Literatura:
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, Karolinum, Praha 2002 - ISBN 80-246-0084-6
T. Valla, J. Matousek: Kombinatorika a grafy I. ITI series 2005-260 ke stazeni zde

Dosud probrana temata:

1. prednaska 21.2.
Opakovani pojmu z diskretni matematiky a linearni algebry z prvniho rocniku: grafy, stupen vrcholu, cesty, kruznice, uplny graf, souvislost, komponenta, podgraf, indukovany podgraf, 2-souvislost, stromy, kostry;
vektorove prostory, linearni zavislost a nezavislost, dimenze, matice, hodnost matic, nasobeni matic, determinanty;
barevnost grafu, rovinny graf, rovinny graf nema steny (maji je jeho nakresleni).
Dukazy matematickou indukci: Spravny dukaz vety o 6 barvach (kazdy rovinny graf lze obarvit 6 barvami). Obdobne, o neco sloziteji, lze dokazat vetu o 5 barvach (delalo se v Diskretni matematice v 1. rocniku). Nespravny dukaz vety o 5 barvach (priklad nespravneho uziti matematicke indukce).
Ulohy na rozmyslenou:
1) Pro jake dvojice teles T1,T2 \in {C,R,Q,GF(2),GF(3),GF(5)} plati pro kazdou matici A\in {0,1}^{nxn}, ze det_{T1}A = 0 implikuje det_{T2}A = 0? (Predpokladame n >= 2.)
2) Rovinna triangulace je rovinny graf, ktery ma rovinne nakresleni, v nemz hranici kazde steny tvori trojuhelnik (= trojcyklus). Ukazte, ze rovinne triangulace jsou prave maximalni rovinne grafy (co do inkluze na mnozine hran pri pevne mnozine vrcholu).

2. prednaska 28.2. (J.K.)
Souvislosti s linearni algebrou
Maticovy popis grafu: matice sousednosti, incidence, Laplaceova.
Prvni vety:
Mocniny matice sousednosti a pocet sledu dane delky (Tvrzeni 3.2.5 z Kapitol).
Pocet koster grafu pomoci determinantu Laplaceovy matice (Veta 7.5.1 z Kapitol).

3. prednaska 7.3. (J.K.)
Dva rekurzivni vzorecky
Pocet koster t(G)=t(G-e)+t(G:e) (pokud e neni smycka, G je multigraf - vyjimecne pripoustime jak nasobne hrany tak smycky, a kontrakce G:e je multigrafova).
Chromaticky polynom P_G(x) udava pocet obarveni grafu G pomoci x barev. Je to polynom stupne n a rekurzivne se pocita podle vzorecku P_G(x) = P_{G-e}(x) - P_{G.e}(x), pricemz P_G(x) = x^n pro graf sestavajici z n izolovanych vrcholu.

Prostor cyklu grafu (Veta 11.4.3 z Kapitol) - podgrafy daneho grafu G tvori vektorovy prostor nad dvouprvkovym telesem GF(2), a jeho specialni podprostor tvori eulerovske podgrafy (grafy jejichz vsechny vrcholy maji sudy stupen). Ukazali jsme si konstrukci baze tohoto podprostoru (elementarni kruznice vuci nejake kostre), z cehoz plyne, ze dimenze tohoto prostoru je |E(G)| - |V(G)| + 1 (za predpokladu souvisleho grafu G).

4. prednaska 14.3.
Vytvorujici funkce
Tri priklady s bankomatem a jejich reseni pomoci roznasobeni soucinu vhodnych polynomu.
Dve ekvivalentni formulace binomicke vety a dukaz jedne z nich pomoci roznasobeni vyrazu (1+x)^n.
Mocninna rada, vytvorujici funkce, (jednoznacny) vztah mezi posloupnosti a jeji vytvorujici funkci.
Operace s posloupnostmi: soucet dvou posloupnosti, vynasobeni posloupnosti realnym cislem, vynasobeni posloupnosti polynomem x^r, dosazeni alfa.x za x, dosazeni x^k za x, derivovani a integrovani, vynasobeni dvou posloupnosti

5. prednaska 21.3.
Dve aplikace vytvorujicich funkci
odvozeni vzorecku pro n-te Fibonacciho cislo
zobecnena binomicka veta, odvozeni vzorecku pro pocet binarnich stromu na n vrcholech

6. prednaska 28.3.
Ramseyovy vety
priklad ukazujici r(3)=6
4 verze Ramseyovy vety (zakladni, nesymetricka, dvoubarevna, vicebarevna)
r(k,l) je mensi nebo rovno (k+l-2 nad k-1)

7. prednaska 4.4. (J.K.)
Dokonceni Ramseyovych vet
Odhad n_r(3) <= 1 + [er!]
Schurovo lemma o existenci jednobarevneho reseni rovnice x+y=z.
Erdos-Szekeresova veta o n bodech v konvexni poloze.

Latinske ctverce a konecne projektivni roviny
Definice Latinskych ctvercu, ortogonalita. NOLC(n) <= n-1.
Konecne projektivni roviny, definice, rad roviny.

8. prednaska 11.4. (J.K.)
Dokonceni Latinskych ctvercu a konecnych projektivnich rovin.
Veta: Konecna rovina radu n existuje prave tehdy, kdyz existuje n-1 Latinskych ctvercu radu n.
Veta: Je-li n mocnina prvocisla, pak existuje konecna rovina radu n.

Zaciname grafy.
Hamiltonovske kruznice
Kruznice prochazejici vsemi vrcholy grafu. Postacujici podminky existence (Diracova veta, Oreho veta, Chvataluv uzaver, Lovaszuv dukaz tvrzeni, ze G je Hamiltonovsky prave kdyz jeho uzaver [G] je Hamiltonovsky).

9. prednaska 18.4.
TOKY V SITICH
sit, tok, velikost toku, existence max. toku (bez dukazu), rez, veta o tocich, elementarni rezy, kazdy rez obsahuje elementarni rez, kazdy v inkluzi min. rez je elementarni, dukaz jednodussi nerovnosti ve vete o tocich, nasycena cesta, je-li tok maximalni pak je kazda cesta ze z do s nasycena

10. prednaska 25.4.
POKRACOVANI TOKU V SITICH, HALLOVA VETA
je-li kazda cesta ze z do s nasycena pak je tok maximalni, poskladani dukazu (hlavni) vety o tocich z uvedenych tvrzeni, Ford-Fulkersonuv algoritmus, veta o celocis. toku, Hallova veta (dukaz pomoci toku v sitich)

11. prednaska 2.5. (J.K.)
APLIKACE TOKU V SITICH
doplnovani latinskych obdelniku na ctverce.
vrcholova a hranovou souvislost, Ford-Fulkersonova veta, Mengerova veta

email: valtr-zavinac-kam.mff.cuni.cz