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


Přednáška: úterý 10:40 K4 (od 5. tydne samostudium, od 14.4. doplnene moznosti ucasti na zoom prednasce)
Cvičení: po prednasce v úterý v 12:20 v K2, od 5. tydne dle pokynu cviciciho emailem

ZKOUSKA: Zkouska je ustni, je mozne si domluvit emailem distancni zkousku pres zoom. Na zkousku je potreba znat probrana temata dle seznamu nize a umet prokazat porozumeni odprednesenemu na prikladech urovne lehcich prikladu z cviceni. Za obdobi distancni vyuky je smerodatny seznam latky urcene k samostudiu; na zoom prednasce vetsinou nebylo mozno danou latku probrat v plne siri.

ZKOUSKA 2.6.: V pripade zajmu o prezencni zkousku 2.6. se behem pondeli 1.6. zapiste v SIS na cas 11:00 (Vojanovy sady) nebo na cas 14:00 (S4). Instrukce viz nize.
ZKOUSKA 2.6. 11:00: Zkouska od 11:00 bude probihat venku ve Vojanovych sadech pri zachovani dostatecnych odstupu. Pripadne pouziti rousky bude dobrovolne. Sraz je v 11:00 uvnitr Vojanovych sadu za vchodem. Vchod do Vojanovych sadu je z ulice U Luzickeho seminare, dum naproti vchodu ma adresu U Luzickeho seminare 110/40. Pokud by se nekdo zpozdil, najde nas nekde na lavickach uvnitr sadu. Vezmete si s sebou psaci potreby a blok nebo tvrde desky, abyste meli na cem psat. Take se dostatecne teple oblecte, muze tam byt dopoledne jeste pomerne chladno.
ZKOUSKA 2.6. 14:00: Zkouska bude v poslucharne S4 ve 3. patre vpravo. Poslucharna je pro 70 osob, bude nas nekolik, takze bude mozno zachovat dostatecne odstupy. Vzhledem k tomu, ze nikdo ze zajemcu o zkousku nepozaduje pouzivani rousky, povazuji za adekvatni nechat na kazdem, zda si po usednuti rousku necha nebo sunda. Po budove ji myslim musime nosit.

KONZULTACE: Vzhledem ke zkousce 2.6. nebude v tento den v dobe prednasky konzultace jako v predchozim tydnu. Misto toho je mozno domluvit emailem konzultaci pres ZOOM na dobu 10-11 hod. v pondeli 1.6.

TERMINY prezencni zkousky od cervna: utery 2.6., kolem 25.6., kolem 15.7., v zari (17.9 nebo 18.9.?)

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.
z Kapitol z diskretni matematiky v kapitole Vytvorujici funkce nastudovat toto:
Uvod kapitoly a prvni podkapitolu projdete jen velmi velmi zbezne, zacnete cist peclive az druhou podkapitolu (Rozsireni na nekonecne rady). Po prostudovani bodu A. az H. preskocte na dalsi podkapitolu (Fibonacciho cisla a zlaty rez), z ktere nastudujte necele dve strany po vetu "Je pozoruhodne, ze tento vyraz ..." pod vzoreckem F_n = ... (vyskytuje se v nem trikrat odmocnina z 5).

Přednáska a samostudium 28.4.
ze stejne kapitoly jako minule nastudovat:
1. zobecnenou binomickou vetu 12.2.5 vcetne odstavce pod ni (pripad kdy r je zaporne)
2. celou podkapitolu 12.4 Binarni stromy

Přednáska a samostudium 5.5.
1. Turinguv stroj (napr. na ceske wikipedii si projdete uvodnich nekolik sekci po sekci Neformalni popis vcetne).
2. P/NP strany 431-434 zde: http://pruvodce.ucw.cz/ (kliknete na odkaz PDF v odstavci Elektronická verze)

Přednáska a samostudium 12.5.
1. sekce 19.3 (strany 442-445) ze stejneho zdroje jako minule: http://pruvodce.ucw.cz/
2. ty casti sekce 19.2 z tehoz zdroje, ktere jeste neznate z predchoziho tydne

Přednáska a samostudium 19.5.
1. kapitola 6 skript kolegu Vally a Matouska (Hamiltonovske kruznice)
2. dukaz Cantor-Bernsteinovy vety zde (strana 7-8): http://mj.ucw.cz/papers/kg1.pdf