Diskrétní matematika (NDMI002), ZS 2015/2016

Doporučená literatura:

• Jiří Matoušek, Jaroslav Nešetřil; Kapitoly z diskrétní matematiky (kterékoliv vydání). Omezený počet výtisků je k dispozici v informatickém oddělení knihovny MFF UK.
• Online sbírka příkladů z diskrétní matematiky

Na případných konzultacích se můžeme domluvit osobně nebo e-mailem (kyncl zavináč kam.mff.cuni.cz).

Odkazy na cvičení a paralelní přednášky:

Vzor zadání zkoušky

Vybavení ke zkoušce:

• povinné: studentská průkazka nebo jiný doklad totožnosti
• doporučené / povolené: psací potřeby, papíry, občerstvení, znalosti z diskrétní matematiky
• není nutný společenský oděv
• nejsou povolené externí poznámky, knihy, elektronická a komunikační zařízení (kromě ne příliš chytrých hodinek, případně zdravotních pomůcek)

Témata přednášek:

6.10.

• Opakování středoškolských pojmů a značení (číselné obory, operace, funkce, suma, součin, kvantifikátory, logické spojky, množinové operace)
• Důkazy: sporem, indukcí, pomocí nejmenšího protipříkladu
• Kartézský součin, binární relace, reprezentace relací (výčtem, orientovaným grafem, maticí, bipartitním grafem)
• Vlastnosti relací (reflexivní, symetrická, antisymetrická, tranzitivní), složení relací
• Zobrazení a funkce (prosté, na, bijekce). Doporučené cvičení: funkce na konečné množině je prostá pravě tehdy, když je na. Platí to i pro nekonečnou množinu?

13.10.

• Složené zobrazení. Doporučené cvičení: jaké zobrazení vznikne složením dvou zobrazení prostých, na, bijekcí, či jejich kombinací?
• Relace ekvivalence, třída ekvivalence, tvrzení o třídách ekvivalence
• Částečné uspořádání, částečně uspořádaná množina, ostré částečné uspořádání, lineární uspořádání, Hasseův diagram
• Věta o reprezentaci uspořádání inkluzí
• Nejmenší a minimální prvek, každá konečná částečně uspořádaná množina má aspoň jeden minimální prvek (důkaz indukcí).

20.10.

• Každé konečné částečné uspořádání lze rozšířit na lineární uspořádání
• Řetězec, antiřetězec, věta o dlouhém a širokém
• Kombinatorické počítání: počet zobrazení z [n] do [m], počet podmnožin n-prvkové množiny, počet prostých zobrazení z [n] do [m], počet permutací na [n]
• Doporučené cvičení: n-prvková množina má 2^{n-1} podmnožin sudé velikosti
• Různé reprezentace permutací (slovem, orientovaným grafem, cyklickým zápisem, permutační maticí)
• Binomický koeficient (kombinační číslo) n nad k

27.10. (přednáší doc. Jiří Fiala)

• Počet k-prvkových podmnožin n-prvkové množiny
• Základní vlastnosti kombinačních čísel, Pascalův trojúhelník
• Binomická věta
• Multinomická věta (jen znění), multinomický koeficient
• Princip inkluze a exkluze
• Problém šatnářky

3.11.

• Řešení problému šatnářky, značení S_n pro množinu všech permutací na [n]
• Eulerova funkce phi(n). Úloha: dokažte vzorec pro výpočet phi(n) pomocí principu inkluze a exkluze. Dále rozhodněte, pro která n je phi(n) liché.
• Základy teorie pravděpodobnosti: konečný pravděpodobnostní prostor, elementární jev, jev, pravděpodobnost jevu, příklady
• K dopočítání: pravděpodobnost, že z 80 lidí má některá dvojice narozeniny ve stejný den
• Podmíněná pravděpodobnost, Bayesova věta
• Nezávislé jevy. Úloha: najděte jevy A,B,C takové, že každé dva jsou nezávislé, ale všechny tři nezávislé nejsou.

10.11.

• Příklad jevů A,B,C takových, že každé dva jsou nezávislé, ale všechny tři nezávislé nejsou
• Příklad jevů A,B,C takových, že p(A průnik B průnik C)=P(A)*P(B)*P(C), a přitom A,B,C jsou závislé
• Náhodná veličina, střední hodnota náhodné veličiny, indikátor jevu
• Věta o linearitě střední hodnoty a její použití
• Nezávislé náhodné veličiny, pro nezávislé náhodné veličiny X,Y je střední hodnota součinu XY rovna součinu středních hodnot X a Y
  • Úloha: na příkladu ukažte, že to neplatí obecně pro závislé náhodné veličiny

24.11.

• Rozdělení (diskrétní) náhodné veličiny, distribuční funkce náhodné veličiny
• Bernoulliho rozdělení, rovnoměrné rozdělení, binomické rozdělení, Poissonovo rozdělení
• Úvod do teorie grafů: graf, vrcholy, hrany, značení, kreslení grafů
• Bijekce mezi grafy a symetrickými antireflexivními relacemi
• Úplný graf K_n, kružnice C_n, cesta P_n, úplný bipartitní graf K_{m,n}, bipartitní graf
• Izomorfismus grafů, podgraf, indukovaný podgraf

1.12.

• Doplněk grafu
• Relace "býti izomorfní" je ekvivalence na množině grafů na [n] (důkaz je cvičení)
• Počet všech grafů na [n] a dolní odhad počtu tříd izomorfismu grafů na [n].
  • Cvičení: pro nějaké n>=2 najděte graf na [n], jehož třída izomorfismu grafů na [n] má n! prvků.
• Cesta, tah, sled, kružnice a klika v grafu
• Souvislý graf, relace "být spojený cestou" je ekvivalence na množině vrcholů grafu, komponenty (souvislosti) grafu
• Vzdálenost d_G(u,v), nejkratší cesta z u do v je indukovaná a nemusí být jediná, vzdálenost d_G je metrika
• Každý souvislý graf G s aspoň jedním vrcholem má vrchol v takový, že G-v je souvislý
• Graf je bipartitní právě tehdy, když neobsahuje lichou kružnici (důkaz indukcí)

8.12.

• Graf je bipartitní právě tehdy, když neobsahuje indukovanou lichou kružnici (důkaz prohledáváním do šířky).
  • Cvičení: bez použití tvrzení o charakterizaci bipartitních grafů dokažte, že pokud G obsahuje lichou kružnici, pak obsahuje i indukovanou lichou kružnici.
• Stupeň vrcholu, izolovaný vrchol, k-regulární graf, skóre grafu
• Princip sudosti, každý graf má sudý počet vrcholů lichého stupně
• Izomorfní grafy mají stejné skóre, ale existují i neizomorfní grafy se stejným skóre
• Věta o skóre
• Eulerovský (uzavřený) tah, eulerovský graf
• Eulerovský graf je souvislý a má všechny stupně sudé

15.12.

• Souvislý graf, který má všechny stupně sudé, je eulerovský
• Poznámka o eulerovských orientovaných uzavřených tazích v orientovaných multigrafech, aplikace na existenci cyklické posloupnosti 0 a 1 délky 2^k, kde žádné dvě k-tice po sobě jdoucích číslic nejsou stejné
• Strom, les, list, každý strom s aspoň dvěma vrcholy má aspoň dva listy
• Přilepením nebo utržením listu získáme ze stromu strom

22.12.

• Informace o zkouškách
• Ekvivalentní charakterizace stromů
• Křivka, prostá křivka, oblouk, uzavřená křivka, prostá uzavřená křivka, topologická kružnice
• Jordanova věta o kružnici (bez důkazu)
• Rovinné nakreslení grafu, rovinný graf

5.1.

• Příklady rovinných grafů
• Každý rovinný graf s n vrcholy má rovinné nakreslení, kde hrany jsou nakreslené jako úsečky, a dokonce vrcholy jsou mřížové body v mřížce 2n x 2n (bez důkazu)
• Stěna rovinného nakreslení (vnitřní a vnější)
• Eulerův vzorec pro souvislé rovinné grafy; úloha: zobecněte pro nesouvislé rovinné grafy
• Horní odhad na počet hran rovinného grafu a rovinného grafu bez trojúhelníků
• Každý rovinný graf má vrchol stupně nejvýše 5, každý rovinný graf bez trojúhelníků má vrchol stupně nejvýše 3
• K_5 ani K_3,3 není rovinný
• Dělení grafu, Kuratowského věta (dokázána pouze implikace "Je-li G je rovinný, pak neobsahuje dělení K_5 ani dělení K_3,3")
• Duál rovinného nakreslení; úloha: najděte graf a dvě jeho rovinná nakreslení R_1 a R_2 taková, že duál R_1 není izomorfní duálu R_2
• Kreslení grafů na plochy

12.1.

• Kreslení grafů na plochy
• Obarvení grafu (k barvami), barevnost grafu, příklady
• Klikovost a nezávislost grafu, odhady na barevnost
• Věta o 4 barvách (bez důkazu)
• Každý rovinný graf má barevnost nejvýše 6
• Každý rovinný graf má barevnost nejvýše 5 (dva důkazy)
• Erdősovo–Szekeresovo lemma o monotónní podposloupnosti