NMIN331 Základy kombinatoriky a teorie grafů
(P. Valtr)
LS 2019/20


Přednáška: úterý 10:40 K4
Cvičení: po prednasce v úterý v 12:20 v K2

Literatura:
J. Matoušek, J. Nešetřil: Kapitoly z diskretní matematiky
T. Valla, J. Matoušek: Kombinatorika a grafy I. ITI series 2005-260 ke stažení zde

Email: valtr zavinac kam.mff....

Probraná témata:

Prednaska 18.2.
Opakovani pojmu z DM: graf, vrchol, hrana, stupen vrcholu, podgraf, indukovany podgraf, tvrzeni: pocet indukovanych podgrafu je 2^|V|, uplny graf, kruznice, cesta (delka kruznice, cesty), cesta v grafu, tah, sled, izomorfismus grafu, priklad: K_4 obsahuje 7 ruznych kruznic, souvisly graf, nesouvisly graf, komponenta, strom, kostra
Toky v sitich: sit, tok, velikost toku, maximalni tok, tvrzeni: existuje tok max. velikosti (zatim bez dukazu).

Prednasky 25.2., 3.3., 10.3.
Tyto tri prednasky spolu s casti prvni prednasky a se zbytkem Mengerovy vety (k samostudiu 17.3.) odpovidaly kapitolam 2 a 3 ve skriptech (T. Valla, J. Matoušek: Kombinatorika a grafy I, odkaz vyse), pricemz:
a) existence maximalniho toku (podkapitola 2.5) byla probrana na cviceni a na zkousku se ji prosim take naucte,
b) latka podkapitoly 2.4 (Toky v sítích a lineární programování) je sice zajimava, ale nebyla probirana a nemusite se ji na zkousku ucit.

Souhrnne se jedna o tuto latku: (Hlavni) Veta o tocich. Ford-Fulkersonuv algoritmus na nalezeni max. toku. Veta o celociselnosti. Souvislost grafu: Vrcholovy a hranovy rez, vrcholova a hranova souvislost. Po odebranim hrany nebo vrcholu hranova i vrcholova souvislost zustane zachovana nebo klesne o 1. Vrcholova souvislost je mensi nebo rovna hranove souvislosti (pro libovolny graf). Ford-Fulkersonova veta. Mengerova veta.

Samostudium 17.3.
zbytek důkazu Mengerovy věty, který se na přednášce 10.3. nestihl, kapitola 4 (bez 4.1) o Hallově větě

Samostudium 24.3.
OPAKOVÁNÍ (patrne jiz znate z Diskretni matematiky): 1) Definice: oblouk, rovinny graf, rovinne nakresleni grafu, jeho steny, topologicka kruznice. Jordanova veta o topologicke kruznici (bez dukazu). Tvrzeni: K_5 neni rovinny graf. Tvrzeni: K_3,3 neni rovinny graf. [ K_5 = uplny graf na 5 vrcholech, K_3,3 = uplny bipartitni graf na 3+3 vrcholech. ] Euleruv vztah (= Eulerova formule) pro souvisle rovinne grafy
NOVÁ LÁTKA (neco uz mozna znate): 2) Barveni politickych map a barveni rovinnych grafu, vztah mezi nimi. Veta o 4 barvach (pouze zneni, dukaz je velmi slozity). 3) Dukaz Syntezy 2-souvislych grafu 4) Pozorovani: G rovinny <==> kazde jeho deleni je rovinne Kuratowskeho veta: G rovinny <==> G neobsahuje deleni K_5 ani deleni K_3,3 (implikace zleva doprava vyplyva z predchoziho pozorovani a z toho, ze K_5 a K_3,3 nejsou rovinne, implikaci zprava doleva se nebudeme ucit)
------------------------------------------
K jednotlivym castem: Cast 1): Tuto latku lze nalezt v Kapitolach z DM. Naznak dukazu tvrzeni o K_5 a K_3,3 lze take nalezt ve skriptech v 1. odstavci dukazu Kuratowskeho vety (uprostred strany 42) Cast 2): Take tuto latku lze nalezt v Kapitolach z DM. Nemusite se ucit kresleni na jine plochy nez do roviny. Cast 3): Veta (Synteza 2-souvislych grafu): Graf je 2-souvisly prave kdyz ho lze dostat z K_3 posloupnosti deleni hran a pridavani hran. [Trochu jinak formulovano: Graf je 2-souvisly prave kdyz ho lze dostat z K_3 opakovanim operaci typu pridani hrany nebo deleni hrany. Napr. K_4 lze dostat z K_3 delenim jedne jeho hrany (cimz dostaneme kruznici na 4 vrcholech) a pote postupnym pridanim dvou hran.] Dukaz Syntezy 2-souvislych grafu lze nalezt v Kapitolach z DM. Cast 4): Prectete si prvni pulstranu 7. kapitoly skript (na strane 40). Proc plati Pozorovani a lehci implikace Kuratowskeho vety je na Vas si rozmyslet.

Samostudium 31.3.
1. Vybiravost kazdeho rovinneho grafu je nejvyse 5.
2. Ramseyova veta pro grafy
K jednotlivym tematum:
1. K prvnimu tematu je vhodny online zdroj v anglictine zde: https://www.sciencedirect.com/science/article/pii/S0095895684710628 (kliknete na Dowload PDF nad cernou listou a potom na Dowload this article) Nastudujte si Vetu (Theorem) v tomto clanku i s dukazem. Ignorujte ve zneni Vety text "which has no loops or multiple edges" (to my automaticky predpokladame). Jak nazev clanku napovida, v clanku se dokazuje, ze kazdy rovinny graf je 5-vybiratelny (5-choosable). K tomuto zaveru je ale je potreba krome Vety jeste nasledujici pozorovani: Pozorovani: Kazdy rovinny graf je podgrafem nejake "near-triangulation". Dukaz (naznak): K kazdemu rovinnemu grafu muzeme pridavat hrany az dostaneme "near-triangulation".
2. Zdrojem k druhemu tematu jsou Kapitoly z DM (pozor: ve vydani z 2000 jeste toto tema neni, ve vydani z 2007 a novejsich uz je). Ve vydani z roku 2009 nastudujte posledni dva radky na strane 331 a pote vse do 9. radku na strane 335 (konec dukazu Vety 11.2.1). Pokud mate jen vydani z roku 2007, nastudujte uvod Kapitoly 11 (Rad z nepravidelnosti: Ramseyova veta) a podkapitolu 11.1 do konce dukazu Vety 11.2.1. (Ramseyova veta pro grafy), tj. do 9. radku na strane 319. V uvodu muzete vynechat prvni tri odstavce, tedy skoro celou prvni stranu.

Samostudium 7.4.
1. Zbytek Kapitoly 11 o Ramseyove vete. Koncili jsme minule na konci dukazu Ramseyovy vety pro grafy, takze zacnete cist text hned za dukazem. Pote nasleduje kapitola 11.3, tu si prectete celou. Pote je dobre si jeste promyslet Cviceni 1. na konci kapitoly. Dolni odhad je jen preformulovani, ale pro horni odhad si musite uvedomit jisty odhad pro kombinatoricka cisla (=binomicke koeficienty).
2. ze stranky http://math.mit.edu/~fox/MAT307.html toto:
A. Lecture 5, Veta 2 na strane 2 vcetne dukazu. Rozmyslete si zaroven, ze pro k=2 je tato veta ekvivalentni Ramseyove vete pro grafy.
B. Lecture 6, sekce 2 na stranach 2-3 (sekci 3 uz ne)

Přednáska a samostudium 14.4.
Opakování dosud probrané látky, zejména z předchozích dvou týdnů (Ramseyovy věty).

Přednáska a samostudium 21.4.
bude brzy doplneno

Přednáska a samostudium 28.4.
bude brzy doplneno

Přednáska a samostudium 5.5.
bude brzy doplneno

Přednáska a samostudium 12.5.
bude brzy doplneno

Přednáska a samostudium 19.5.
bude brzy doplneno