Cvičení z diskrétní matematiky

PDF verze stránky
Přednášející
Martin Mareš
Petr Kolman
Ondřej Pangrác

Další cvičení
Martin Böhm
Lukáš Mach
Martin Mareš
Řešené příklady
Barvení roviny
Odhad bin. koef.

V pátek od devíti hodin na Tróji v místnosti T6 se pod vedením mým (Lukášovým, lukas@lansky.name) koná cvičení z diskrétní matematiky pro informatiky. Pokud na něj chcete chodit, budu moc rád.

Požadavky na zápočet:

Konzultace:

Samozřejmě si je mě možno odchytit po skončení cvičení (nespěchám po něm), samozřejmě se se mnou můžete domluvit mailem na nějakém individuálním termínu a místě.

Co se dělalo:

1. října: Roztomilé úvodní příklady a indukce ()

Lámání čokolády. Mravenci na vlase! Počet a barva částí roviny rozdělených přímkami. Dláždění šachovnice dominy. Dláždění šachovnice bez dvou rohů dominy. Dláždění šachovnice \( 2^n \times 2^n \) dílky tvaru L. Počet podmnožin, počet podmnožin sudé a liché velikosti.

8. října: Relace ()

Krátké povídání o barvení roviny třemi barvami. Večírky: může si každý ze sedmi lidí potřást rukou právě se třemi dalšími? (ještě potkáme jako princip sudosti); existuje mezi šesti lidmi pokaždé trojice, která se zná nebo trojice, která se nezná? (potkáme jako Ramseyovskou teorii).

Povídání o množinách: hlavně jak je potence důležitá v teorii množin.

No a potom relace: jejich základní vlastnosti, jako je symetrie, reflexivita, tranzitivita. Slabá a silná antisymetrie: ta silná vylučuje reflexivitu. Jaké z těchto vlastností mají relace =, \( \leq \), \( \lt \) na přirozených a reálných číslech? Jaké z těchto vlastností mají „lidské“ relace jako „býti otcem“, „býti předkem“, „býti pokrevným příbuzným“. Jaké množinové operace tyto vlastnosti zachovávají: když je R i S tranzitivní, bude \( R \cup S \) také?

15. října: Funkce ()

První půlhodinu jsme řešili tuto úlohu: kolik cest existuje v tabulce \( 3 \times n \) z levého horního do pravého dolního rohu, které navštíví každou buňku právě jednou.

Potom jsme zkoumali vlastnosti „prosté“ a „na“ funkce. Existují funkce \( \mathbb{N} \rightarrow \mathbb{N} \), které by byly prosté a nebyly na, či které by byly na a nebyly prosté? Jak vypadají bijekce na konečných množinách? Jak se projevuje skládání funkcí na propagaci podobných vlastností? A jak je vlastně skládání funkcí přesně definováno? :)

Na závěr jsme se vrátili k relacím. Kolik je (všech, reflexivních, symetrických) relací na n-prvkové množině? Může být relace, která není reflexivní a tranzitivní, ale je silně antisymetrická?

22. října: Kombinatorické počítání ()

Začali jsme ukázkami ekvivalencí: třeba takové té \( m, n \in \mathbb{N}; mR_pn \Leftrightarrow p|(|m-n|) \), která rozseká přirozená čísla na p tříd ekvivalence, jejichž prvky sdílejí ten samý zbytek po dělení číslem p. Ukázal jsem, jak vypadají matice ekvivalencí, které dělí n-prvkovou množinu do n nebo jedné třídy. A pak tam byl ještě jeden příklad, ve kterém relace prohazovala písmenka v řetězcích konstantní délky: některé třídy pak měly jeden prvek (to když v řetězci prohazovaná písmenka nebyla), některé dva. Na té konstantní délce vlastně nezáleží.

Chvíli jsem řečnil o tom, jak vypadají částečná a lineární uspořádání a že ta lineární jsou nudná, hlavně konečná. Snažil jsem se při té příležitosti ukázat pojem izomorfizmus, který nudu konečných lineárních uspořádání odhaluje – a rovnou jsem ho využil jako další ukázku ekvivalence.

Potom jsme pokračovali Pascalovým trojúhelníkem: jak kombinatoricky dokázat, že \( {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} \), jak identita \( \sum_{i=r}^{n}{i \choose r}={n+1 \choose r+1} \) z první sady domácích úkolů souvisí s trojúhelníkovými, tetrahedrálními a dalšími figurálními čísly.

Kolik je dvojic (A, B), že \( A \subseteq B \subseteq \{1..n\} \), popř. trojic (A, B, C), že \( A \subseteq B \subseteq C \subseteq \{1..n\} \)? Kolik je desetiznakových hesel z velkých a malých písmen anglické abecedy – že by to souviselo s počtem funkcí \( f: \{1..10\} \rightarrow \{1..52\}\)? Kolik je možností usazení n lidí kolem kulatého stolu, pokud nechceme započítat různá otočení stolu dvakrát?

29. října: Roztomilé pravděpodobnostní příklady

Účast nebyla povinná, takže jsme nedělali zásadní příklady. Úvodem se řešil počet funkcí \( f: \{1..k\}\rightarrow \{1..n\} \), které jsou neklesající, popř. rostoucí. Došlo se k tomu, že je výhodné počítat je počtem rozkladů čísla na nezáporné, resp. kladné sčítance, protože mezi rozklady a popsanými funkcemi existuje bijekce.

No a potom přišla na řadu ona hravá pravděpodobnost:

Narozeninový paradox. Máme 20 lidí. Jaká je pravděpodobnost, že nějací dva mají narozeniny ve stejný den? Vysoká – 41,14 %! Nad polovinu to vyleze pro n=23 a pro 40 lidí už je to 90 %. Jak by to vycházelo, kdybychom se ptali na trojice lidí s narozeninami ve stejný den? (To není domácí úkol. Ty tenhle týden nejsou, z minula jich je zásoba.)

Problém tří dveří.

Má sestra má dvě děti, jedno z nich je kluk. Jaká je pravděpodobnost, že to druhé je děvče? \( \frac{2}{3}\)! Jó, kdyby se řeklo: „dříve narozené je kluk“, pak by to byla očekávaná \( \frac{1}{2} \)…

Využil jsem příležitosti a vedl jsem chvilku biologické řeči o tom, proč je pravděpodobnost narození kluka větší než holky: muži umírají podstatně víc, jen to není vidět, protože stáří kosí exponenciálně. Více viz hezký článek na ScienceWorldu.

Nakonec jsem se zmiňoval o tom, jak z kostky, která hází čísla 1..n s pravděpodobností \( \frac{1}{n} \), generovat čísla 1..m s pravděpodobností \( \frac{1}{m} \). Respektive hlavně o tom, pro která m to jde, abychom měli jistotu, že někdy skončíme. Pro n=2 koukněte na jedno staré řešení KSPácké úlohy.

5. listopadu: Pravděpodobnost ()

Na úvod jsme řešili příklad na nezávislost jevů: házíme dvěma označenými kostkami, máme tři jevy:

  • na první padne liché číslo,
  • na druhé sudé a
  • součet čísel, která padla, je lichý.

Jsou po dvou nezávislé? Jsou nezávislé? Pak jsem ještě pověděl, co to znamená, že jsou dva jevy neslučitelné a v dalším průběhu cvičení jsem nadhodil svůj oblíbený matematický termín „skoro jisté“.

Dál přišla ukázka využití indikátorových náhodných veličin: nejdřív při formálním dokazování hodně jednoduché úlohy na střední počet hozených orlů, potom u jenom trochu složitějšího příkladu na počet zastřelených zajíců. Oba dva příklady byly z Kapitol.

Potom jsme řešili těžší úlohy. První byla trochu chytáková: házejme korunou, dokud nehodíme za sebou buď PPO, nebo POO. Jaká je pravděpodobnost, že skončíme na PPO? Druhá měla velmi názorné geometrické řešení: mějme Ji a Jeho. Dohodli se, že se sejdou mezi 12 a 14 hodinami v Labu a oba tam pak přišli v náhodnou chvíli v tomto intervalu. Ona je na něj ochotná čekat 30 minut, On je na ni ochoten čekat 40 minut. Jaká je pravděpodobnost, že se sejdou?

Opět házení korunou (tentokrát právě n-krát za sebou) – jaká je střední hodnota počtu úseků stejných hodů? Potom: QuickSort! Jak tento třídicí algoritmus vypadá a jak se v něm počítá chování v průměrném případě.

12. listopadu: Pravděpodobnost a úvod do grafů ()

Cvičení bylo nemastné, neslané. :-(

Nejdřív jsem objasnil, co to je, když se jen tak poví „náhodná permutace“, jako jsem to udělal v předchozích domácích úkolech a řešili jsme příklad, jsou-li jevy „\( \pi(1) = 1\)“ a „\( \pi(2) = 2\)“ nezávislé.

Potom jsem nějakou dobu ilustroval pravděpodobnostní rozdělení pomocí náhodných procházek v čtvercových sítích.

No a zbytek cvičení jsem povídal o základních grafových pojmech. Jak se graf definuje, jak vypadá graf úplný, bipartitní (kolik mají hran), co je to strom, jaké má základní vlastnosti (má dva listy, má vždy o vrchol víc než má hran), jak vypadají grafy rovinné a že v nich může být na rozdíl od grafů obyčejných jenom lineárně hodně hran.

Nakonec jsem ukazoval, jak se orientované grafy použijí na úloze topologického uspořádání.

19. listopadu: První písemka (autorské řešení)
  1. Dokažte, že platí \[ \sum_{i=0}^n{(2i+1)} = (n+1)^2 \]

  2. Kolik existuje relací \( R \subseteq (1..n)\times (1..n) \), které jsou symetrické a zároveň reflexivní?
  3. Najděte vhodnou množinu X a takovou relaci \( R_0 \subseteq X\times X \), pro kterou v posloupnosti relací definované jako \[ \forall i \in \mathbb{N} : R_{i+1} = R_i \circ R_i \]

    neexistuje žádné i, že by \( R_i = R_{i+1} \). Tj. každé další složení něco změní.

  4. Uvažte funkci \( f: (1..n) \rightarrow (1..m) \) a dokažte, že implikace „je-li tato funkce prostá, je na“ platí právě tehdy, je-li m=n.

  5. Máme mapu, na které je n měst. Každá dvě města jsou spojena cestou s pravděpodobností p. (Pojem cesta tu znamená vlastní silnici, neuvažujte žádné cestování přes jiná města, žádnou tranzitivitu.)

    Ukažte, že se pro \( n \rightarrow \infty \) pravděpodobnost jevu „existuje trojice měst, mezi kterými vedou všechny (tři) možné cesty“ blíží jistotě. (Nebodované: Platí to i pro k-tice měst?)

Bonus/Domácí úkoly:

  • [faktoriál, 3 body] Dokažte, že \[ \forall k, n \geq 1 : (k!)^n | (kn)! \]
  • [odhad, 3 body] Dokažte, že \[ {2^{2m} \over {2m+1}} \leq { 2m \choose m } \leq 2^{2m} \]

    Řešení

  • [náhodný graf, 4 body] Vezměme si mapu z úlohy na pravděpodobnost a chápejme mapu jako graf. Dokažte, že se pro \( n \rightarrow \infty \) blíží pravděpodobnost toho, že bude souvislý, k jistotě.
26. listopadu: Grafy
3. prosince: Grafy

Mluvil jsem nejdřív o uzavřených a otevřených eulerovských tazích a o tom, že je nejenom snadné charakterizovat grafy, ve kterých existují, ale je i snadné je nacházet algoritmicky. Multigrafy a hypergrafy a o praktičnosti definicí.

Pokud je úplný graf podgrafem, je i indukovaným podgrafem. Prázdný graf podgrafem bývá (stačí ověřit počet vrcholů), ale indukovaným nikoliv (cílový graf by musel obsahovat mnoho izolovaných vrcholů).

Graf na n vrcholech s c komponentami má alespoň n-c hran.

Je-li ve stromu vrchol stupně k, má strom alespoň k listů. Taky (je-li \( p_i \) počet vrcholů stupně i) platí: \( 1\cdot p_1 + 0\cdot p_2 + -1 \cdot p_3 + \ldots + (n-3)p_{n-1} = 2 \).

10. prosince: Grafy

Začal jsem mluvením o studentských nepokojích ve Velké Británii a rozvolněních rovinnosti: hlavně o crossing number a o tom, že jej neumíme určit ani pro úplné (bipartitní) grafy.

Obsahuje-li graf lichou kružnici jako podgraf, obsahuje ji též jako podgraf indukovaný? Obsahuje-li graf sled liché délky, obsahuje též nutně kružnici liché délky? A jak je to se vztahem lichých kružnic a bipartitních grafů? (Při této příležitosti jsme trochu barvili: spočítali jsme barevnost kružnice s lichým a sudým počtem vrcholů a hlavně bipartitního grafu, což se zrovna hodilo pro názornost.)

Úplný bipartitní graf \( K_{m, n} \) je rovinný právě tehdy, je-li \( min(m, n) \leq 2 \).

Jak vypadají grafy se skóre \( (2, 2, \ldots, 2) \). Našli jsme 5-regulární graf na dvanácti vrcholech. Ukázal jsem, jak se dá dobře u papíru přemýšlet nad pneumatikovými a jinými plochami, potom jsme nacházeli nakreslení \( K_7 \) a \( K_{4, 4} \) právě na pneumatice.

Je-li minimální stupeň \( \delta \), najdeme cestu délky \( \delta \).

Vánoční dárek: zajímavé úlohy! (uzávěrka: 9. ledna)
  • [k-part, 3 body] O grafu řekneme, že je k-partitní, právě když lze jeho vrcholy rozdělit do k částí tak, že neexistuje žádná hrana mezi libovolnýma dvěma vrcholy v libovolné části (tedy bipartitní graf je 2-partitní). Kolik hran může nejvýše obsahovat k-partitní graf na n vrcholech? Dokažte.
  • [nekonečný graf, 3 body] Dokažte, že v nekonečném grafu s \( \mathrm{N} \) coby nosnou množinou, kde mají vrcholy konečné, kladné a navzájem různé stupně, existuje nekonečná cesta.
  • [cr, 5 bodů] Ukažte, že v libovolném nakreslení \( K_n \) existuje alespoň \( {1 \over 5}{n \choose 4} \) křížení.
  • [nejmenší stupeň, 3 body] Je-li nejmenší stupeň rovinného grafu nejméně pět, má aspoň dvanáct vrcholů. Ano?
  • [nezavislá množina, 3 body] Nezávislá množina vrcholů grafu je takový jejich seznam, ve kterém neexistuje dvojice spojená hranou. Dokažte, maximální nezávislá množina stromu je velká aspoň \( n \over 2 \).
  • [další charakterizace, 3 body] Graf je strom právě tehdy, neobsahuje-li kružnici a |V|=|E|+1.
  • [čtyři barvy, 4 body] Dokažte větu o čtyřech barvách pro rovinné grafy bez trojúhelníků.
  • [tři barvy, 4 body] Dokažte, že vnějškově rovinné grafy jsou 3-obarvitelné. (Vnějškově rovinné jsou takové rovinné grafy, které mají stěnu, na které jsou všechny vrcholy.)
  • [doplněk rovinného grafu, 4 body] Pro která n může být doplněk rovinného grafu na n vrcholech stále rovinný?
  • [triangulace, 5 bodů] Triangulace (tj. rovinný graf, jehož všechny stěny jsou trojúhelníky) je eulerovská právě když je 3-obarvitelná (když její vrcholy můžeme obarvit třemi barvami tak, že dva stejnobarevné vrcholy nesdílí hranu).
  • [počet koster, 3 body] Kolik koster má podrozdělení \( K_4 \), tj. graf, který z \( K_4 \) vznikne tím, že „doprostřed každé hrany přistrčíme vrchol“?
17. prosince: Grafy

Začali jsme třemi úlohami, z nichž první dvě zadávám jako domácí úkoly, protože jsme je nevyřešili, ale jsou moc zajímavé na prozrazování. Třetí byla o tom najít asymetrický graf, tj. takový, který na sebe nemá žádný jiný izomorfizmus mimo identity.

Máme úplňák obarvený dvěma barvami (aniž by toto obarvení mělo nějaké zvláštní vlastnosti – je to prostě funkce \( f: E \rightarrow \{1, 2\} \)) – ukázali jsme dvěma způsoby, že v něm vždy lze nalézt jednobarevnou kostru. Jednak si lze jednu barvu představit (přeložit) jako „existence hrany“ a druhou jako „neexistence hrany“ a pak se nám tvrzení vyjadřuje o tom, že graf, nebo jeho doplněk má kostru, což platí, protože graf, nebo jeho doplněk je vždy souvislý. Druhak to jde indukcí: máme-li pro graf na n vrcholech zaručenou existenci kostry barvy 1, přidáním dalšího vrcholu se na ní buď napojíme nějakou hranou též barvy 1, nebo pokud neexistuje, tvoří vrchol napojený na všechny další vrcholy barvou 2, také kostru.

Mluvil jsem o nepořádku v terminologii: když se řekne obarvení, často se bere samo sebou, že se chce, aby bylo dobré, tj. aby dva stejně obarvené objekty nesdílely problemtickou vlastnost. V případě vrcholového barvení je jí hrana, v případě hranového vrchol, když barvíme přednášky učebnami, nechceme, aby dva předměty se stejnou učebnou sdílely čas. Často (třeba v Ramseyeově teorii, nebo našem příkladu) se ale obarvením myslí prostě jen označení objektů společnými jmenovkami. Tak bacha na to.

Ukazoval jsem, že počet koster úplného grafu je \( n^{n-2} \) pomocí POVYKOSů. Mrkněte do Kapitol na všechny důkazy, jsou legrační!

Je-li minimální stupeň \( \delta \), najdeme kružnici délky \( \delta +1 \).

Nakonec jsme trochu počítali kostry, viz poslední vánoční domácí úkol.

Domácí úkoly (do 9. ledna):

  • [nekonečně mnoho, 5 bodů] Najděte nekonečně mnoho grafů takových, že jsou izomorfní se svými doplňky. (Na cvičení jsme vyzkoumali: Jeden příklad je třeba kružnice na pěti vrcholech. Takový graf musí mít \( \frac{n(n-1)}{4} \) hran, takže to jde jen pro některé dělitelnostní třídy čtyř.)
  • [konstrukce neizomorfních grafů, 5 bodů] Pro daný počet vrcholů najděte co nejvíce navzájem neizomorfních grafů. (Na cvičení jsme vymysleli akorát, že můžeme vytvořit grafy s různými počty hran, což dává jen něco jako \( O(n^2) \).)
14. ledna: druhá písemka (autorské řešení)
  1. Mosty a artikulace (20):

    Mějme souvislý graf. O hraně řekneme, že je most, pokud graf po jejím odmazání souvislý není. O vrcholu řekneme, že je artikulace, pokud graf po odmazání tohoto vrcholu a všech incidentních hran souvislý není.

    Ověřte platnost tvrzení pro souvislé grafy na alespoň třech vrcholech:

    1. Obsahuje-li graf most, obsahuje artikulaci. (4)
    2. Obsahule-li graf artikulaci, obsahuje most. (4)
    3. Každá hrana grafu je most právě je-li graf strom. (6)
    4. Neexistuje graf, kde je každý vrchol artikulací. (6)
  2. Vysoké stupně (12)

    Dokažte, že v rovinném grafu na n vrcholech existuje alespoň n/2 vrcholů stupně nejvýše 8.

  3. Podgraf (9)

    Charakterizujte grafy, které neobsahují P3 jako podgraf. (Charakterizovat znamená výstižně alternativně popsat a dokázat platnost takového popisu.)

  4. Regularita (9)

    Může souvislý 2k-regulární graf obsahovat most?

  5. Bonusové (DÚ)

    1. V každém souvislém grafu na alespoň třech vrcholech existují dva vrcholy u, v takové, že odstraníme-li jeden z nich nebo oba najednou, graf zůstane souvislý. Dokažte. (3)
    2. Graf označíme za k-kritický, pokud má barevnost k, ale s odstraněním libovolné hrany nebo libovolného vrcholu tato barevnost klesne. Charakterizujte 2-kritické a 3-kritické grafy. (4)
    3. Dokažte, že k-kritický graf je souvislý. (3)
21. ledna: opravná písemka
  • (10) Dokažte, že pro \(n \in \mathbb{N}\) platí \[ \sum_{i=1}^{n}{i^3} = \left(\sum_{i=1}^{n}{i}\right)^2 \]
  • Dokažte pro \( n, k \in \mathbb{N}^+ \) rovnost \[ {{n-1} \choose {k-1}} + {{n-1} \choose {k}} = {n \choose k} \]
    • (10) algebraicky
    • (10) kombinatoricky
  • (10) Najděte algoritmus pro ověření bipartitnosti grafu a jeho rozdělení na partity.
  • (10) Dokažte, že jsou (n-2)-regulární grafy na n vrcholech navzájem izomorfní.

Potřebujete-li získat body z domácích úkolů, najděte si na webech Martina Mareše či Martina Böhma libovolné neřešené příklady, které jsme ještě nedělali a pošlete mi jejich řešení. Dostanete za ně přibližně po pěti bodech. Popřípadě můžete samozřejmě řešit všechny domácí úkoly, co jsem zadal a nezveřejnil řešení, za polovinu bodů.

Studenti:

... tady byla tabulka se studijními výsledky. Potřebujete-li z ní něco vědět, napište mi.

Doporučení: