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
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:
Informace o terminech zkousky:
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.
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.)