DMI011 Kombinatorika a teorie grafu I - 2006/07

Utery 14:00 v M1 Od 20.6. do 2.7. budu mimo CR. Znamky za zkousky tem, kteri v dobe skladani zkousky nemeli zapocet, zapise Doc. Valtr v dobe svych zkousek (20.6., 25.6., 29.6.). Podminkou je zapocet zapsany jak v indexu tak v SISu od cviciciho (nebo sefcviciciho - Jelinek nebo Pangrac).

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 zde.

20.2.2007

Opakovani pojmu z diskretni matematiky a linearni algebry z prvniho rocniku: grafy, cesty, tahy, sledy, kruznice, souvislost, 2-souvislost, stromy, kostry; vektorove prostory, linearni zavislost a nezavislost, dimenze, matice, hodnost matic, nasobeni matic, determinanty.
Filipika o dukazu matematickou indukci - indukcni krok n <-- n-1. Dva priklady chybneho dukazu indukci (skore stromu a barevnost rovinnych grafu).
DCV:
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).

27.2.2007

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

6.3.2007

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 13.3.2007 (PV)
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 20.3.2007 (PV)
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 27.3.2007 (PV)
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 3.4.2007
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.

10.4.2007
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. Hamiltonovkse 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).


honza@kam.ms.mff.cuni.cz