Utery 12:20 v S3
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.
19.2.2008
Opakovani pojmu z diskretni matematiky z prvniho rocniku:
grafy, cesty, tahy, sledy, kruznice, souvislost, stromy, kostry, rovinne grafy, triangulace, barevnost grafu.
Filipika o dukazu matematickou indukci - indukcni krok n+1 <-- n. Dva priklady
chybneho dukazu indukci (skore stromu a barevnost rovinnych grafu).
Pred pristi prednaskou si zopakujte take pojmy z linearni algebry - vektorove prostory,
linearni zavislost a nezavislost, dimenze, matice, hodnost matic, nasobeni matic,
determinanty.
26.2.2008 (prednasel doc. Valtr)
Souvislosti s linearni algebrou
Maticovy popis grafu: matice sousednosti.
Prvni vety:
Mocniny matice sousednosti a pocet sledu dane delky (Tvrzeni 3.2.5 z Kapitol).
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.3.2008
Pocet koster grafu pomoci determinantu Laplaceovy matice (Veta 7.5.1 z Kapitol).
Pocet koster rekurzivne: 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).
11.3.2008 (prednasel doc. Valtr)
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
18.3.2008
Latinske ctverce a konecne projektivni roviny
Definice Latinskych ctvercu, ortogonalita. Veta: NOLC(n) <= n-1.
Konecne projektivni roviny, definice, rad roviny.
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.
(Konstrukce: Rovina ma nevlastni primku $A_0, A_1, A_2, ..., A_n$, bodem
$A_0$ prochazeji "vodorovne primky" $p_1, ..., p_n$, bodem $A_n$ "svisle" primky $q_1, ... , q_n$. Prusecik $p_i \cap
q_j$ oznacime $X_{ij}$.
Sikme primky prochazejici bodem $A_{\alpha}$ jsou $p_{\alpha\beta}, \beta = 1,2,...,n$, pricemz $$p_{\alpha\beta} =
\{A_{\alpha}\}\cup\{X_{\alpha j+\beta,j}|j=1,2,...,n\}$$. Scitani v indexu je v GF(n).
) Dukaz, ze toto je konecna projektivni rovina, bude proveden na cviceni.
25.3.2008 (prednasel doc. Valtr)
Aplikace vytvorujicich funkci Zobecnena binomicka veta, Fibonacciho cisla, pocet pestovanych binarnich stromu na n vrcholech. Vse viz Kapitoly.
1.4.2008 (plati i pro 31.3.2008 )
Hamiltonovske grafy Definice Hamiltonovske kruznice, postacujici podminky (Oreho, Dirakova a Lovaszova veta, Chvataluv uzaver).
Problem Obchodniho cestujiciho TSP Aproximacni algoritmus
zalozeny na minimalni kostre (funguje pouze pro vahy splnujici
trojuhelnikvoou nerovnost), apr. faktor 2.
Lizatkove grafy Smithova a Thomasonova veta - v grafu, jehoz vsechny vrcholy maji lichy stupen, prochazi kazdou hranou sudy pocet Ham. kruznic. Otevreny problem Mame-li takovy graf dan s jednou Ham. kruznici, existence dalsi Ham. kruznice je zarucena vetou. Avsak neni jasne, zda se dalsi HK da nalezt v polynomialnim case.
Informace o prednaskach v obou paralelkach (pondeli, utery)
ve zbytku semestru:
7.4. a 8.4. bude misto nasi prednasky prednaska Automaty a gramatiky
(v obou techto dnech tedy budou vzdy dve devadesatiminutovky prednasky
Automaty a gramatika).
Od 14.4. do 13.5. se bude vzdy ucti totez v obou paralelkach.
V pondeli 19.5. budou dve prednasky Kombinatorika a grafy I,
prvni od 12:20 v S3 (nahradou za Automaty a gramatiky).
Druha bude v obvykly cas (14:00 S9) a probere se na ni obsah
uterni prednasky tesne po Velikonocich (aplikace vytvorujicich funkci).
V utery 20.5. bude jedna prednaska v obvykly cas (12:20 S3)
a prednese se na ni totez jako na prvni prednasce 19.5. (12:20 S3).
14. a 15.4.2008 (prednasel doc. Valtr)
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).
Erdos-Szekeresova veta o n bodech v konvexni poloze.
21. a 22. 4. 2008
Toky v sitich
Definice toku a rezu, elementarni rezy, nasycene a nenasycene
cesty a toky.
Algoritmus pro nalezenitoku nejvetsi velikosti
(v pripade celociselnych kapacit).
Veta
o toku maximalni velikosti a rezu minimalni kapacity.
Veta o existenci
celociselneho maximalniho toku (v pripade celociselnych kapacit).
Aplikace na vztah mezi minimalni velikosti secny a maximalni velikosti parovani v bipartitnim grafu.
28. a 29. 4. 2008 (prednasel doc. Valtr)
Mira souvislosti grafu
Vrcholova a hranova souvislost grafu,
definice, porovnani.
Usate lemma o vytvareni 2-souvislych grafu.
5. a 6. 5. 2008 (prednasel dr. Pangrac)
Ford-Fulkersonova veta o existenci
souboru k hranove disjunktnich cest v hranove-k-souvislych grafech
s dukazem pres toky v sitich.
Mengerova veta
o existenci
souboru k vrcholove disjunktnich cest ve vrcholove-k-souvislych grafech.
12. a 13. 5. 2008
Hallova veta o existenci systemu ruznych reprezentantu pro mnozinovy system.
Aplikace na
parovani v bipartitnich grafech a na doplnovani Latinskych obdelniku na Latinske ctverce.
Jeden domaci ukol: Ukazte, ze pro kazde k a kazdy graf G plati, ze G ma orientaci, v niz
kazdy vrchol ma vystupni stupen nejvyse k, prave kdyz kazdy podgraf grafu G ma kejvyse k-krat
vice hran nez vrcholu.