DMI011 Kombinatorika a grafy I - LS 2007/08

Pondeli 14:00 v S9

Toto je stranka pondelni paralelky, stranku uterni paralelky najdete zde.


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 ke stazeni zde


Dosud probrana temata:

1. prednaska 18.2.
Opakovani pojmu z diskretni matematiky: graf, rovinny graf, rovinne nakresleni, stupen vrcholu, cesta, tah, sled, kruznice, souvislost, komponenta, 2-souvislost, strom, kostra, barevnost grafu.
Matematicka indukce: 2 priklady nespravneho dukazu matematickou indukci.
Opakovani pojmu z linearni algebry: vektorovy prostor, linearni zavislost a nezavislost, dimenze, baze.

2. prednaska 25.2.
Jeste zopakovani nekolika pojmu z linearni algebry: matice, hodnost matice, nasobeni matic.
Mocniny matice sousednosti odvozeni 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 podgrafy odpovidajici eulerovskym mnozinam hran (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)| + k, kde k je pocet komponent grafu G.

3. prednaska 3.3. (prof. Kratochvil)
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).

4. prednaska 10.3. (prof. Kratochvil)
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.

Poznamka (pro ty kdo nekdy chodi na uterni prednasku): 4. a 5. prednaska byly odpredneseny v uterni paralelce v opacnem poradi (10.3.=18.3. a 11.3.=17.3.).

5. prednaska 17.3.
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

24.3. Velikonocni pondeli - prednaska odpadla

6. prednaska 31.3. (prednasel prof. Kratochvil)
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. byla misto nasi prednasky prednaska Automaty a gramatiky.
V peti tydnech od 14.4. do 13.5. byla vzdy na programu stejna latka v obou paralelkach.
V pondeli 19.5. byly 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 byl na ni probran obsah uterni prednasky tesne po Velikonocich (aplikace vytvorujicich funkci).
V utery 20.5. byla jedna prednaska v obvykly cas (12:20 S3) a bylo na ni predneseno totez jako na prvni prednasce 19.5. (12:20 S3), tj. dukaz Kuratowskeho vety.

Informace o terminech zkousky:
Terminy jsou stejne pro obe paralelky. Posledni termin je 29.9. v 9:00, zapisujte se na nej pres SIS, zkouset budou oba prednasejici. (Omlouvam se za pomerne pozdni vypsani, k cemuz doslo vinou mych zdravotnich komplikaci.)


email: valtr-zavinac-kam.mff.cuni.cz