DMI011 Kombinatorika a teorie grafu I - 2004/05

Pondeli 9:00 v M1

Literatura:
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, Karolinum, Praha 2002 - ISBN 80-246-0084-6
Komentovane zapisky z prednasek v minulych letech obetave pripavil pan Valla. Pokryvaji vpodstate celou latku semestru a lze je nalezt zde.

4.10.2004

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.

11.10.2004

Souvislosti s linearni algebrou
Maticovy popis grafu: matice sousednosti, incidence, Laplaceova.
Prvni dve 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).

18.10.2004

Pokracovani v interakcich linearni algebry a teorie grafu
Pocet koster rekurzivne t(G)=t(G-e)+t(G:e).
Prostor kruznic (tj. eulerovskych podgrafu) (Veta 11.4.3 z Kapitol).


POZOR! 25.10.2004 Maraton prednasime 2 dvouhodiny za sebou, tj. 9:00 - 12:10, pote 1. a 8.11.2004 se prednaska nekona (bude prednaset D. Bednarek svuj predmet Objektove orientovane programovani). My se opet sejdeme ke grafovemu maratonu 15.11.2004.


25.10.2004

Toky v sitich Definice toku a rezu, elementarni rezy, nasycene a nenasycene cesty a toky.
Existence toku maximalni velikosti (pres linearni programovani), algoritmus na jeho nalezeni (v pripade celociselnych kapacit).
Veta o toku maximalni velikosti a rezu minimalni kapacity.
Veta o existenci celociselneho maximalniho toku (v pripade celociselnych kapacit).

Systemy ruznych reprezentantu a parovani v grafech Mnozinove systemy. Systemy ruznych reprezentantu (SRR). Hallova veta udavajici nutne a postacujici podminky pro existenci SRR s dukazem pres toky v sitich.

Mira souvislosti grafu Vrcholova a hranova souvislost grafu, definice, porovnani (nektera lemmata budou dokazana na cvicenich).
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 (bude dokazana na cvicenich).

15.11.2004

Latinske ctverce a konecne projektivni roviny Definice Latinskych ctvercu, ortogonalni ctverce, veta o tom, ze NOLC(n) je nejvyse n-1. (NOLC(n)=Navzajem Ortogonalni Latinske Ctverce radu n.)
Doplnovani Latinskych obdelniku na Latinske ctverce (jako dusledek Hallovy vety).
Konecne projektivni roviny - definice, rad roviny, dualni rovina, maticovy popis. Konstrukce projektivnich rovin z konecnych teles.
Veta davajici do souvislosti konecne projektivni roviny a ortogonalni Latinske ctverce - projektivni rovina radu n existuje, prave kdyz existuje n-1 NOLC(n).

Parovani v obecnych grafech. Tutteova veta o existenci perfektniho parovani.

22.11.2004

Edmondsuv algoritmus na nalezeni nejvetsiho parovani v obecnem grafu
Lemma o volnych stridavych cestach a kontrakci liche kruznice. Dekompozice grafu na Edmondsuv les a Palouk (Kompost). Rekurzivni algoritmus. Odhad casove slozitosti bude proveden na cvicenich.

29.11.2004

Rovinne grafy - dukaz Kuratowskeho vety Nejprve Lemma o vytvareni 3-souvislych grafu: Je-li G vrcholove-3-souvisly graf s alespon 5 vrcholy, pak existuje hrana, jejiz kontrkaci se 3-souvislost nepokazi. Pote dukaz Kuratowskeho vety (Graf je rovinny prave tehdy, kdyz neobsahuje deleni grafu K_5 and K_3,3 jako podgraf.) indukci podle poctu vrcholu. V indukcnim kroku rozlisujeme pripady k_v(G)=0, 1, 2 a k_v(G)=>3.


6.12.2004 se prednaska nekonala

13.12.2004

Hamiltonovske kruznice Kruznice prochazejici vsemi vrcholy grafu. Postacujici podminky existence (Diracova, Oreho, Chvataluv uzaver, Lovaszuv dukaz tvrzeni, ze G je Hamiltonovsky prave kdyz jeho uzaver [G] je Hamiltonovsky). Uloha obchodniho cestujiciho a aproximacni algoritmus zalozeny na minimalni kostre (funguje pouze pro vahy splnujici trojuhelnikvoou nerovnost), apr. faktor 2.

Ramseoyva veta "Uplny chaos je nemozny" Barveni hran uplneho grafu dvema barvami, nesymetricka verze a konecnost Ramseyova cisla R_2(n). Odhad pomoci kombinacniho cisla. Barveni k barvami a barveni p-tic (bez dukazu).
Schurovo lemma o existenci jednobarevneho reseni rovnice x+y=z.
Erdos-Szekeresova veta o n bodech v konvexni poloze.

20.12.2004

Vytvorujici funkce podle Kapitol z DM (Kapitoly 10.1 - 10.4)


Predtermin 21.12.2004 v 9:00, zapisujte se pomoci SISu. A doucte se vytvorujici funkce z Kapitol z DM!

3.1.2005

Mengerova veta dukaz.

10.1.2005

Kombinatoricke pocitani Multinomicke koeficienty a pocet stromu s predepsanym skore (a pote pocet stromu na n-prvkove mnozine). Burnsidovo lemma (akce permutacni grupy na mnozine, pocet orbit - pocitani nahrdelniku).


Zkousky 17., 24., 31. ledna vzdy zacatek v 9:00 hod.
honza@kam.ms.mff.cuni.cz