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