3.10.2000
Opakovani a doplneni diskretni matematiky z prvniho rocniku:
Latinske ctverce, ortogonalni ctverce, veta o tom, ze NOLC(n) je nejvyse n-1.
Konecne projektivni roviny - definice, dualni rovina, maticovy popis.
10.10.2000
Opakovani a doplneni diskretni matematiky z prvniho rocniku:
Konstrukce projektivnich rovin z konecnych teles.
Dukaz vety o existenci
projektivni roviny radu n prave kdyz existuje n-1 NOLC(n).
Pocet koster grafu rozvojem t(G)=t(G-e)+t(G:e).
Maticovy popis grafu - matice sousednosti, incidence a Laplacova.
Mocniny matice sousednosti a pocet sledu dane delky.
Pocet koster grafu pomoci determinantu Laplacovy matice - zacatek dukazu.
17.10.2000
Jeste trochu linearni algebry:
Dokonceni dukazu poctu koster pomoci determinantu.
Grafy jako vektory - prostor eulerovskych podgrafu, jeho
dimenze a baze.
24.10.2000
Toky v sitich:
Definice toku a rezu, existence toku maximalni velikosti,
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).
31.10.2000
Mira souvislosti grafu:
Vrcholova a hranova souvislost grafu,
definice, porovnani.
Ford-Fulkersonova veta a Mengerova veta o existenci
souboru k disjunktnich cest v k-souvislych grafech s dukazy pres toky v sitich.
7.11.2000
Jeste k mire souvislosti grafu:
Gohringuv dukaz Mengerovy vety bez pouziti toku v sitich.
Hallova veta a systemy ruznych reprezentantu:
Ekvivalence
pohledu na mnozinovy system jako matici incidence nebo bipartitni graf
incidence, system ruznych reprezentantu (SRR) mnozinoveho systemu jako
nezavislou mnozinu v matici resp. parovani v bipartitnim grafu.
Hallova
veta udavajici nutne a postacujici podminky pro existenci SRR s dukazem
pres toky v sitich.
14.11.2000
Prednaska se nekonala, bude nahrazena na Mikulase od 15:40.
21.11.2000
Parovani v bipartitinich a obecnych grafech:
Dusledky Hallovy vety o SRR.
Tuttova veta o existenci perfektniho parovani v obecnem grafu s dukazem.
28.11.2000
Parovani v obecnych grafech
Stridave cesty, volne vrcholy, Lemma o maximalite parovani iff neexistuje
volna stridava cesta. Lemma o kontrakci lichych kruznic (kvetinek).
Edmondsuv algoritmus pro nalezeni maximalniho parovani v obecnem grafu.
5.12.2000
Maraton od 15:40. Hamiltonovske kruznice. Definice, poznamka, ze existence je tezka (NP-uplna). Postacujici podminky pro existenci HK, veta o Chvatalovskem uzaveru grafu. Problem obchodniho cestujiciho (resp. obchodni cestujici), slozitost, aproximacni algoritmus zalozeny na minimalni kostre. Pocet Hamiltonovskych kruznic v grafu, jehoz vsechny stupne jsou liche.
12.12.2000
Barevnost grafu. Definice (vrcholove) barevnosti, par zakladnich nerovnosti (vztahy ke klikovosti, nezavislosti, maximalnimu stupni). Barveni metodou First Fit. Rozhodnout, zda dany graf lze obarvit 3 barvami, je tezky (NP-uplny) problem. Veta o acyklickych orientacich.
19.12.2000
Jeste barevnost. Definice k-degenerovanych grafu, priklady (1-degenerovane = lesy, 3-degenerovane obsahuji rovinne bez trojuhelniku, 5-degenerovane obsahuji vsechny rovinne grafy). Metoda First Fit pro vhodne usporadani obarvi k-degenerovany graf pomoci nejvyse k+1 barev. Chordalni grafy (kazda kruznice delky vetsi nez 3 ma uhlopricku), lemma o minimalnich vrcholovych rezech (indukuji uplny podgraf) a existenci simplicialnich vrcholu (to je vrchol, jehoz sousede indukuji uplny podgraf). Vhodnemu usporadani (ziskanemu ze simplicialnich vrcholu) staci pri barveni metodou First Fit tolik barev, kolik je velikost nejvetsiho uplneho podgrafu. Proto pro chordalni grafy je barevnost rovna klikovosti (a jsou tzv. perfektni).
2.1.2001
Ramseyova veta
9.1.2001
Vytvorujici funkce
Zkousky
Ve zkouskovem obdobi (zacatek 9:00 - pisemka)
18.1. ctvrtek S4,
24.1. streda S3,
31.1. streda S3,
7.2. streda S3