Diskrétní Matematika (456-533 DIM) Doc. RNDr. Petr Hliněný, Ph.D. petr.hlinenyOvsb.cz 5. května 2006 Verze 1.02. Copyright © 2004-2006 Petr Hliněný. Obsah 0.1 Předmluva.................................... iv I Základy Diskrétní Matematiky 1 1 Množiny a výběry prvků 1 1.1 Čísla, operace a množiny............................ 1 1.2 Výběry a seřazení prvků............................ 3 1.3 Výběry s opakováním ............................. 6 1.4 Cvičení: Kombinatorické výběry ....................... 8 2 Diskrétní pravděpodobnost 9 2.1 Motivační příklady............................... 10 2.2 Konečný pravděpodobnostní prostor..................... 10 2.3 Nezávislost jevů................................. 12 2.4 Střední hodnota................................. 13 2.5 Náhodné výběry ................................ 15 2.6 Cvičení: Úlohy na pravděpodobnost ..................... 16 3 Důkazy v diskrétní matematice 18 3.1 Základní logické symboly ........................... 19 3.2 Pojem matematického důkazu......................... 19 3.3 Princip matematické indukce ......................... 20 3.4 Důkazy vzorců pro výběry........................... 21 3.5 Vztahy s kombinačními čísly ......................... 22 3.6 Důkazy "počítáním".............................. 24 3.7 Cvičení: Příklady matematických důkazů .................. 25 4 Relace a zobrazení 27 4.1 Pojem relace .................................. 27 4.2 Uspořádání a ekvivalence ........................... 28 4.3 Funkce, či zobrazení.............................. 30 4.4 Skládání zobrazení; Permutace ........................ 31 4.5 Princip inkluze a exkluze ........................... 33 4.6 Cvičení: Příklady na relace a jiné....................... 34 5 Algoritmizace diskrétních struktur 36 5.1 Programová implementace struktur...................... 36 5.2 Implementace množin ............................. 37 5.3 Generování výběrů............................... 39 5.4 Generátory náhodných čísel.......................... 40 5.5 Kombinatorická "exploze"........................... 41 II Úvod do Teorie Grafů 42 6 Pojem grafu 42 6.1 Definice grafu.................................. 42 6.2 Stupně vrcholů v grafu............................. 44 6.3 Podgrafy a Isomorfizmus............................ 45 n 6.4 Orientované grafy a multigrafy........................ 48 6.5 Implementace grafů............................... 49 6.6 Cvičení: Příklady o grafech a isomorfismu.................. 49 7 Souvislost grafu 52 7.1 Spojení vrcholů, komponenty......................... 53 7.2 Prohledávání grafu............................... 54 7.3 Vyšší stupně souvislosti............................ 55 7.4 Jedním tahem: Eulerovské grafy ....................... 56 7.5 Cvičení: Příklady na souvislost grafů..................... 57 8 Vzdálenost a metrika 60 8.1 Vzdálenost v grafu............................... 61 8.2 Výpočet metriky................................ 62 8.3 Vážená (ohodnocená) vzdálenost....................... 63 8.4 Hledání nejkratší cesty............................. 64 8.5 Cvičení: Příklady o grafových vzdálenostech................. 65 9 Stromy a les 68 9.1 Základní vlastnosti stromů........................... 69 9.2 Kořenové stromy................................ 71 9.3 Isomorfizmus stromů.............................. 73 9.4 Kostry grafů .................................. 75 9.5 Cvičení: Příklady o stromech, kostrách a hladovém postupu........ 78 10 Barevnost a kreslení grafů 83 10.1 Barevnost grafu................................. 83 10.2 Rovinné kreslení grafu............................. 85 10.3 Rozpoznání rovinných grafů.......................... 88 10.4 Barvení map a rovinných grafů........................ 90 10.5 Cvičení: Příklady na barevnost a rovinnost grafů.............. 90 11 Toky v sítích 93 11.1 Definice sítě................................... 93 11.2 Hledání maximálního toku........................... 95 11.3 Zobecnění sítí a další aplikace......................... 97 11.4 Cvičení: Příklady toků v sítích ........................ 100 III 103 Klíč k řešení úloh 103 Literatura....................................... 109 ni 0.1 Předmluva Vážení čtenáři, dostává se vám do rukou výukový text Diskrétní Matematiky, který je primárně určený pro studenty informatických oborů na technických vysokých školách. Diskrétní matematika je moderní a rychle se rozvíjející oblastí matematiky, která má mnohé úzké vazby na teoretickou i aplikovanou informatiku. Kořeny diskrétní matematiky (kombinatoriky) sahají k velkým matematikům 18. a 19. století, z nichž si zaslouží jmenovat především Leonard Euler. Byl to však až nástup počítačů a rozvoj informatiky jako vědní disciplíny v druhé polovině 20. století, které přinesly nové teoretické pojmy a otázky a vtiskly tak diskrétní matematice její moderní tvář, spojenou dosti specificky s pojmem grafů. Náš text vás seznámí jak s přehlednými základy klasické kombinatoriky, tak i se hlavními pojmy a mnoha prakticky aplikovatelnými poznatky teorie grafů. Je koncipován jako soběstačný celek, který od čtenáře nevyžaduje o mnoho více než běžné středoškolské matematické znalosti a chuť do studia. (Části věnované algoritmickým aplikacím navíc předpokládají znalost a zběhlost v programování.) Svým rozsahem odpovídá jednomu semestru běžné výuky včetně cvičení. Tento výukový text vychází z vynikající moderní učebnice [■>] Kapitoly z Diskrétní Matematiky autorů J. Matouška a J. Nešetřila z MFF UK. (Tato kniha se kromě českého vydání dočkala i úspěšných vydání ve světových jazycích, jako například [ ]. Vřele ji doporučujeme zájemcům o rozšíření svých matematických obzorů.) Záběr našeho textu není zdaleka tak široký jako u zmíněné učebnice, ale zaměřujeme se především na ty oblasti a úseky, které nacházejí nejčastější použití v informatické praxi. Na druhou stranu se zde více věnujeme přímým algoritmickým aplikacím uváděné látky a zmiňujeme také některé důležité detaily programátorské implementace. Ve stručnosti se zde zmíníme o struktuře našeho textu. Přednesený materiál je dělený do jednotlivých lekcí (kapitol), které zhruba odpovídají obsahu týdenních přednášek v semestru. Lekce jsou dále děleny tematicky na oddíly. Výklad je strukturován obvyklým matematickým stylem na definice, tvrzení, případné důkazy, poznámky a neformální komentáře. Navíc je proložen řadou vzorově řešených příkladů navazujících na vykládanou látku a doplněn dalšími otázkami a úlohami. (Otázky a úlohy označené hvězdičkou patří k obtížnějším a nepředpokládáme, že by na ně všichni studující dokázali správně odpovědět bez pomoci.) Každá lekce je zakončena zvláštním oddílem určeným k dodatečnému procvičení látky. Správné odpovědi k otázkám a úlohám jsou shrnuty na konci textu. Přejeme vám mnoho úspěchů při studiu a budeme potěšeni, pokud se vám náš výukový text bude líbit. Jelikož nikdo nejsme neomylní, i v této publikaci zajisté jsou nejasnosti či chyby, a proto se za ně předem omlouváme. Pokud chyby objevíte, dejte nám prosím vědět e-mailem mailto:petr.hlineny@vsb.cz. Autor IV Pár slov o vzniku Tento učební text vznikal v průběhu let 2003 až 2004 na základě autorových přednášek a cvičení předmětu Diskrétní matematika na FEI VŠB - TUO. Jeho základní verzi utvořil soubor autorových slidů pro přednášky předmětu. Většina řešených příkladů a úloh k řešení pak vychází ze skutečných písemných zápočtů a zkoušek v předmětu. Za přípravu některých příkladů a zvláště za kontrolu celého textu patří dík také cvičícím - doktorandským studentům Martinu Kotovi, Ondřeji Kohútovi, Michalu Ko-lovratovi a Pavlu Moravcovi. v Část I Základy Diskrétní Matematiky 1 Množiny a výběry prvků Úvod Základními stavebními kameny v matematice vůbec jsou čísla a množiny, přičemž v diskrétní matematice se převážně zabýváme přirozenými čísly a konečnými množinami. (Slovo "diskrétní" je zde míněno jako opak "spojitého".) Dá se říci, že diskrétní matematika je oblastí matematiky, která je nejblíže informatice, a její poměrně nedávný prudký rozvoj byl do značné míry inspirován právě informatikou, obzvláště tou teoretickou. Pro začátek úspěšného studia je velmi důležité probrat různé kombinatorické způsoby výběrů prvků z množiny, neboť tyto znalosti jsou přímo či nepřímo používány ve většině aplikací diskrétní matematiky. Jedná se především o výběry bez pořadí či výběry uspořádané a o princip skládání nezávislých výběrů. (Čtenáři se zajisté už s některými z nich prakticky setkali dříve.) I náš učební text je na těchto znalostech založen a očekává od čtenáře jejich dobré zvládnutí. Cíle Za hlavní cíl úvodní části považujeme správné pochopení principů různých typů kombinatorických výběrů - permutací, kombinací a variací, včetně těch s opakováním prvků. Dále je potřeba si zapamatovat základní vzorce pro počty různých typů výběrů. 1.1 Čísla, operace a množiny Úvodem si připomeneme známé matematické pojmy týkající se převážně přirozených číslech a konečných množin. Zároveň si zde zavedeme (pro ujednocení) některé základní konvence a značení používané dále v našem textu. Přirozená čísla Množina přirozených čísel je tvořena prvky N = {0,1, 2, 3,4, 5, 6, 7,...}. (Pozor, všimněte si, že přirozená čísla obsahují 0.) • Značení intervalu přirozených čísel [a,b] = {a, a + 1,..., b — 1, b}. • Celá část reálného čísla x je značena následovně: dolní [x\ a horní \x]. • Posloupnost, obvykle značená (aj)™=1 = (ai,a,2, ■ ■ ■ ,an), je seřazením jakýchkoliv n prvků za sebou. (Prvky posloupnosti mohou být třeba čísla, ale taká jakékoliv jiné objekty.) Pro referenci jsou prvky posloupnosti indexovány přirozenými čísly. V posloupnosti se, na rozdíl od množiny, prvky mohou volně opakovat. • Suma posloupnosti čísel je zapsána n ^2 ai = cii + a2 + ... + an-i + an , í=i nebo také obecněji J2 a>i = cih + a«2 + • • • + a*n> kde J = {ii,Í2, ■ ■ ■ ,in} je jakákoliv íeJ množina indexů. 1 • Součin posloupnosti n čísel je analogicky zapisován jako n || (li = (1\ ■ Ü2 • ■ ■ ■ • (ln-l • dn ■ í=l Komentář: Pro ukázku připojíme několik příkladů použití značení sum a součinů: 10 ^«=1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +10 = 55 i=l 5 |J(* + 1) = 2- 3-4- 5- 6 = 720 i=l n n n í n\ / n \ í n \ /i \ 2 i=i j=i i=i \ j=i y \i=i / \j=i j v 7 Čtenář nechť si sám promyslí, co poslední uvedený zápis vlastně znamená, není v něm skryto nic složitého. Množiny a množinové operace Opět si ve stručnosti připomeneme či zavedeme některá značení používaná v teorii množin. • Obvykle značíme množiny velkými písmeny A, B,X,Y,... a jejich prvky malými písmeny a,b,x,y, — Symbol 0 značí prázdnou množinu. • M = {a, b, c, x} je množina se čtyřmi prvky a, b,c,x a píšeme a G M, b G M, ale d <£ M. Počet prvků (mohutnost) značíme \M\ = 4. N = {a, b, x} je podmnožinou M, což píšeme jako N C M. • Sjednocení množin značíme A U B, jejich průnik An B. • Rozdíl množin je definován A\B = {a G A: a <£ B}, symetrický rozdíl je AAB = (A\B)U(B\A) (jako "XOR"). n n • Rozšířené značení sjednocení (J X» a průniku f] Xi je analogické jako u sumy. Komentář: Pro názornou ukázku si zvolme například množiny A = {a,b, c,d}, B = {b,c,e,f}. Pak sjednocením těchto dvou množin je AuB = {a, b, c, d, e, /} a průnikem je AnB = {b, c}. Výsledkem rozdílu je A \ B = {a, d} a symetrického rozdílu AAB = {a, d,e, /}. V další ukázce nechť je S množinou všech sudých přirozených čísel a P je množinou všech prvočísel. Pak, jak je dobře známo, v průniku S n P je jediné číslo 2. Rozdíl P\S obsahuje všechna lichá prvočísla, kdežto obrácený rozdíl S\ P obsahuje všechna sudá přirozená čísla mimo 2. • Potenční množina (množina všech podmnožin) množiny X je 2X = {A: A = {0, {«},{&}, {«,&}} Pro počet prvků potenční množiny platí přirozený vzorec: \2X\ = 2|x| V dalším příkladě si ukažme jednoduchý kartézský součin dvou dvouprvkových množin: {a, 6} x {c, d} = {(a, c), (a, (i), (6, c), (6, (i)} Počty prvků v kartézském součinu a v kartézské mocnině splňují \AxB\ = \A\-\B\, \An\ = \A\n. Úlohy k řešení 6 (1.1.1) Sečtěte sumu J2 *2- i=l 11 (1.1.2) Vynásobte ]T 3- (1.1.3) Kolik je [3.3J? (1.1.4) Kolik je L-3.3J? (1.1.5) Kolik je [3.6]? (1.1.6) Kolik je r-3.6]? (1.1.7) Kolik prvků má potenční množina množiny {1,2, 3,4}? (1.1.8) Kolik prvků je v kartézském součinu {1,2,3,4} x {5,6,7}? *(1.1.9) Jak vyjádříte klasické zaokrouhlení pomocí |J ? 1.2 Výběry a seřazení prvků V tomto místě začneme přehledem tří základních kombinatorických způsobů výběru prvků bez opakování. Představme si množinu n prvků X, ze které hodláme vybírat. V prvé řadě můžeme vzít rovnou všechny prvky a dívat se na jejich možná seřazení. Tento pohled je formalizován následující definicí: 3 Definice 1.1. Permutace n-prvkové množiny X je uspořádání všech prvků z X do jedné posloupnosti (délky n) bez opakování prvků. Počet všech permutací n-prvkové množiny je dán vzorcem P(n) = n! = 1 • 2 • 3 • 4 • ... • (n - 1) • n (0! = 1). Jindy nás pořadí vybíraných prvků z X nemusí vůbec zajímat (případně pořadí může být již dáno, tj. nevybírá se pořadí), ale soustředíme se na to, které prvky se do výběru dostanou a které ne. To je zachyceno ve druhé definici: Definice 1.2. Kombinace na množině X je neuspořádaný výběr některých prvků z X bez opakování, tj. výběr podmnožiny X. Počet /c-prvkových kombinací na n-prvkové množině je dán vzorcem C{n,k) kl-{n-k)l A nakonec nás může zajímat obojí - jak to, které prvky jsou vybrány, tak i to, jak je jejich výběr seřazen. Definice 1.3. Variace na množině X je uspořádaný výběr některých prvků z X bez opakování, tj. podposloupnost množ. X bez opakování. Počet /c-prvkových variací na n-prvkové množině je dán vzorcem V{n,k) {n-k)\ Komentář: Pro ilustraci se podívejme na příklad - máme klub 15 (stejných) sportovců, ze kterých bychom měli poslat 3-členné družstvo na závody. — Vybíráme-li 3-členné družstvo z 15 sportovců, jedná se o kombinace, tj. počet možností je (g5) = 455. (Na jejich seřazení nám v tuto chvíli nezáleží.) — Chceme-li vybrané 3-členné družstvo seřadit na slavnostní nástup, jedná se o permutaci, tj. máme celkem 3! = 6 možností. — Představme si však, že rovnou hodláme vybrat z těchto 15 sportovců toho prvního, druhého a třetího do reprezentačního družstva. Pak se jedná o variaci, tj. máme celkem 151/12! = 2730 možností. Všimněte si dobře, že 455 • 6 = 2730; to je přirozené, neboť sportovce můžeme nejprve vybrat jako kombinaci a pak je seřadit. Poznámka o výpočtu kombinačních čísel: Definiční vztah (£) = u.t^'_k\\ se pro praktický výpočet kombinačního čísla vůbec nehodí, neboť funkce faktorial roste tak rychle, že brzy přesáhne možnosti vaší kalkulačky. Místo toho obvykle používáme zde popsaný postup. Předpokládejme, že k < t-, jinak vezměme raději číslo ( ™fc) = (k). Pak si definiční vztah upravme: n\ n{n — í)(n — 2)... (n — k + 1) Kk) k\-(n-k)\ k\ Například 100\ 100-99-98 = 50 • 33 • 98 . 3 ) 3-2 Pro výpočet variací používáme obdobnou úpravu 4 Řešení složených výběrů Při řešení praktických kombinatorických problémů však ne vždy (dokonce málokdy) jsme v situaci, kdy řešení přímo padne do jedné z uvedených tří Definic 1.1-1.3. Dalšími možnostmi jsou kombinace či permutace s opakováním, které popíšeme v příští části. Ale často se v problémech jedná o složené výběry, sestávající z několika dílčích podvýběrů. Základní (a přirozený) postup řešení takovýchto složených úloh je popsán následovně: Metoda 1.4. Princip nezávislých výběrů V situaci složeného výběru, kdy není vůbec žádná vazba každého jednoho částečného výběru (podvýběrů) k ostatním podvýběrům, stačí k získání celkového výsledku mezi sebou vynásobit počty možností jednotlivých podvýběrů. Komentář: Princip nezávislých výběrů bude nejlépe ilustrován několika praktickými ukázkami. — Vybíráme-li delegaci 2 studentů a 1 studentky ze skupiny 20 studentů a 3 studentek, pak můžeme nezávisle vybrat nejprve studenty a pak studentku (či naopak). Počet výběrů je vynásobením (2) ' (i) = ^70. — Vybíráme-li z 15 hráčů (například minifotbalu) družstvo 3 + brankář, pak ale podvýběr trojice a podvýběr brankáře nezávislé nejsou. (Striktně řečeno, jakmile zvolíme trojici hráčů do pole, žádný z nich již nemůže být brankářem.) Přesto i zde s opatrností násobit lze, pokud každý z oněch 15 hráčů může být stejně dobře brankářem - (pod)vybereme trojici a na brankáře v každém případě zbude 12 voleb. Celkem tak je (3 ) • 12 = 5460 různých možností výběru. Další možnost řešení některých složených výběrů spočívá v tom, že požadovaný výběr ještě dále "zjemníme" tak, abychom dostali jiný výběr, který již dokážeme spočítat některou z jiných metod. Počet možností původního výběru pak získáme vydělením. Metoda 1.5. Dvojího počítání Necht každý případ nějakého (složeného) výběru lze dále rozlišit (zjemnit) na stejný počet t zjemněných možností. Dále necht získaný zjemněný výběr má celkem m různých možností (které jsme schopni spočítat). Potom počet všech možností původního výběru je dán podílem m/L Komentář: Opět je nejlepší popsanou metodu dvojího počítání ilustrovat názornou ukázkou použití. (Později budou uvedeny i jiné příklady této metody, především v Lekci 3.) Vraťme se ke druhé ukázce pro Metodu 1.4 - výběru družstva 3 + brankář z 15 hráčů. — Dále si představme, že chceme ještě navíc takovéto družstvo seřadit na slavnostní nástup tak, aby brankář byl první. — Pokud je počet možných výběrů našeho družstva x, pak v každém případě musíme postavit brankáře prvního, ale zbylé tři hráče můžeme seřadit 3! = 6 způsoby za ním. Celkem tedy získáme x ■ 1 • 3! seřazení na nástup. — Na druhé straně si můžeme situaci představit tak, že rovnou vybíráme variace 4 hráčů ze všech 15 a že prvního z nich prohlásíme za brankáře. Počet možností je dle vzorce 1/(15,11) = M- — Oba pohledy jsou však ekvivalentní, takže počty musí souhlasit: x ■ 1 ■ 3! = 1/(15,11) = Hj Po vydělení: 5 (Určitě není náhodou, že výsledek vyšel stejný, že?) Úlohy k řešení (1.2.1) Upravte na jednoduchý součin (6^)- (1.2.2) Kolika způsoby seřadíme šestici studentů do řady? (1.2.3) Kolika způsoby vyberete neuspořádanou dvojici z 21 studentů? (1.2.4) Kolika způsoby vyberete uspořádanou dvojici z 21 studentů? (1.2.5) Z osudí 49 čísel táhneme jedno, vrátíme jej a táhneme druhé. Kolik různých výsledků může vyjít? * (1.2.6) Co když v předchozím výběru dvou čísel zapomeneme jejich pořadí, kolik různých výsledků získáme? * (1.2.7) Hokejový trenér má k dispozici 13 útočníků a 9 obránců. Kolika způsoby vybere pětku hráčů? (2 obránci + 3 útočníci) 1.3 Výběry s opakováním Doposud jsme se zabývali výběry prvků, které se nemohou opakovat. Nemožnost opakování prvků je přirozenou podmínkou například při výběrech skupin lidí, kdežto v jiných situacích a výběrech jsou opakování prvků žádoucí. Tak je to třeba v situaci, kdy vybíráme slova složená z daných písmen-prvků. Následující příklad uvádí tzv. permutace s opakováním. Příklad 1.6. Kolika různými způsoby můžeme seřadit do posloupnosti písmena sousloví DISKRETNIMATEMATIKA ? Pokud bychom si výskyty stejných písmen barevně rozlišili, např. DISKRETNIMATEMATIKA, pak je počet seřazení roven počtu permutací z 19 znaků, ale my neumíme různá pořadí písmene A či I atd. odlišit. Proto použijme metodu dvojího počítání (Metoda 1.5). Nechť x je neznámý počet různých seřazení našich písmen. V každém takovém seřazení si dodatečně obarvěme stejná písmena různými barvami a sestrojme 3! permutací písmen I, 2! permutací písmen K, 2! permutací písmen E, 3! permutací písmen T, 2! permutací písmen M a 3! permutací písmen A. Celkem tak získáme všech 19! permutací z rozlišených 19 znaků, a proto (3!)3-(2!)3-a;=19!, Po vydělení: 19! _ 19! X~ (3!)3 • (2!)3 ~ 3! • 3! • 3! • 2! • 2! • 2! • 1! • 1! • 1! • 1! ' D Použití metody dvojího počítání v tomto příkladě lze jednoduše zobecnit na obecné permutace s opakováním, jak dokládá následující definice. Definice 1.7. Permutace s opakováním prvků množiny X je seřazení {uspořádání) prvků z X do posloupnosti takové, ve které se každý prvek X opakuje předepsaný počet krát. (Jinými slovy, je to seřazení předepsaných počtů identických kopií prvků z X.) Počet všech permutací s opakováním z k prvků, kde i-tý prvek se opakuje mokrat pro i = 1,..., k, je (mi +m2 + ... + mk)\ m\\ ■ m£ ■ ■ -nikl 6 Komentář: V Příkladě 1.6 jsme měli 10 různých písmen, která se opakovala následující počty krát: mo = 1, mj = 3, ms = 1, rriK = 2, tur = 1, tue = 2, mx = 3, mjv = 1, tum = 2 a rriA = 3. Takže výsledek příkladu je stejný, jako bychom jej dostali dosazením do vzorce v Definici 1.7. Poznámka: Pokud uvažujeme permutace s opakováním z 2 prvků, kde se první prvek opakuje fc-krát a druhý (n — fc)-krát, dostáváme vztah pro jejich počet Jedná se tedy o tentýž počet jako fc-prvkových kombinací z n prvků. To není náhoda, protože na výběr kombinace se můžeme dívat jako na seřazení k černých a (n — k) bílých značek, kde černá značka znamená, že prvek vybereme do podmnožiny, a bílá naopak ne. Poznámka: Na permutace s opakováním se lze dívat ještě jedním pohledem. V kombinatorice se také definuje pojem "multimnožiny", která je analogická množině, ale jednotlivé prvky se v ní mohou vyskytovat v několika identických kopiích. V tomto pohledu pak permutace s opakováním je jako běžná permutace, ale nad multimnožinou místo množiny. Další zajímavý příklad uvádí tzv. kombinace s opakováním. Příklad 1.8. Kolika různými způsoby můžeme vybrat 6 kuliček ze tří barev, když počet kuliček stejné barvy není omezený? Zde hledáme neuspořádaný výběr. Představme si proto, že kuličky následně (jednoznačně) seřadíme podle barev v pořadí červená, modrá, zelená. Například •,»,•,•,•,• napíšeme jako .|..|..., kde znak | odděluje jednotlivé barvy. Nyní však vidíme, že barvy můžeme zapomenout, protože jsou už určené pozicemi oddělovačů |, a můžeme psát . | ••!•••• Takže na určení výběru kuliček stačí vybrat 2 pozice oddělovačů z 6 + 2 = 8 možností (neuspořádaně). To dává výsledek C(8,2)=(* (Uvědomme si, že skutečně vybíráme oddělovače z osmi pozic, ne ze sedmi mezer mezi kuličkami, protože v jedné mezeře mohou být oba oddělovače najednou.) D Opět můžeme uvedené řešení snadno zobecnit na všechny kombinace s opakováním, jako v následující definici: Definice 1.9. Kombinace s opakováním z množiny X je výběr neuspořádaného "seskupení" (multimnožiny) prvků z X, přičemž se prvky výběru mohou opakovat v libovolném počtu (identických kopií). Počet všech /c-prvkových kombinací s opakováním z n možností je C*(n,k) = Vzorec pro kombinace s opakováním má mnoho šikovných a zajímavých aplikací. Pro ilustraci uvedeme následující příklady. Příklad 1.10. Kolika různými způsoby můžeme zapsat přirozené číslo k jako součet n přirozených sčítanců? 7 Mějme součet k = xi + x2 + ■ ■ ■ + xn . V analogii s Příkladem 1.8 o výběrech barevných kuliček můžeme vidět číslo x\ jako počet červených kuliček, x 2 jako počet modrých, atd. Takže součet si lze představit jako fc-prvkovou kombinaci s opakováním z n prvků, kde i-tý prvek se opakuje právě Xj krát. Proto je počet takových zápisů na součty dán už známým vztahem Pro bližší vysvětlení: Přestože sčítance v součtu x\ + x2 + ... + xn jsou uspořádány svými indexy, nejedná se zde v žádném případě o uspořádaný výběr, neboť pořadí sčítanců je dáno a hraje roli jenom pro odlišení sčítanců od sebe, ale nevybírá se! D Úlohy k řešení (1.3.1) Kolika různými způsoby seřadíme do posloupnosti písmena slova ANAKONDA? (1.3.2) Automobilové rallye se účastní vozy čtyř značek, tři vozy od každé značky. Kolik různých výsledných pořadí může být, pokud nerozlišujeme vozy téže značky? (1.3.3) Kolika způsoby rozložíme číslo 7 na součet tří přirozených sčítanců? (Na jejich pořadí záleží.) * (1.3.4) Kolika různými způsoby můžeme nabarvit 6 identických bílých kuliček jednou ze čtyř barev? (Každá kulička musí být nabarvena.) * (1.3.5) Kolika různými způsoby můžeme nabarvit 6 očíslovaných kuliček jednou ze čtyř barev? (Každá kulička musí být nabarvena a čísla jsou pod barvou stále vidět - jsou vyrytá.) Rozšiřující studium Podrobnější zopakování pojmů o přirozených číslech a množinách čtenář najde v doporučované učebnici Matouška a Nešetřila [ , Oddíl 1.2], nebo v jiných učebnicích diskrétní matematiky či algebry. O kombinatorických výběrech a jejich počítání si zaujatý čtenář může přečíst více v [ , Kapitola 2]. Specifícky metodě dvojího počítání je věnována celá [5, Kapitola 6]. 1.4 Cvičení: Kombinatorické výběry Příklad 1.11. Kolik podmnožin liché velikosti lze vybrat z 33 prvků? Nechť množina X má 33 prvků a vybíráme lichou podmnožinu LCI. Podívejme se, že doplněk X \L má pak sudou velikost a naopak. To znamená, že ke každé liché podmnožině je jednoznačně přiřazena jiná sudá podmnožina, a proto je lichých podmnožin právě polovina všech podmnožin. To jest celkem ^ • 233 = 232 lichých podmnožin. □ Příklad 1.12. Mějme k dispozici 12 hráčů, mezi nimiž je 5 dobrých útočníků. Kolika způsoby můžeme sestavit A-členné družstvo, ve kterém bude alespoň jeden dobrý útočník? Na první pohled by se mohlo zdát, že nejprve vybereme jednoho dobrého útočníka a pak dobereme tři zbylé hráče. Tato úvaha má však jednu závažnou chybu - pokud vybrané družstvo má třeba dva dobré útočníky, pak jej započítáme dvakrát, za každého jednoho dobrého útočníka zvlášť. Proto budeme postupovat jinak. Všech výběrů 4-členných družstev je (142). Mezi nimi jsou i ty špatné výběry, které neobsahují žádného dobrého útočníka. Takových špatných 8 výběrů je (124 5) = (4), vybíráme totiž čtyři hráče z těch zbylých. Špatné výběry od všech jednoduše odečteme, takže výsledek je CK)' D Příklad 1.13. Kolika různými způsoby můžeme zapsat přirozené číslo k jako součet n celých kladných sčítanců? Mějme součet s kladnými sčítanci k = X\ + X2 + ... + xn . To lze ekvivalentně zapsat jako k - n = (xi - 1) + (x2 - 1) + ■ ■ ■ + (xn - 1), kde íji = Xi — 1 jsou přirozená čísla. Jinak řečeno, zapisujeme číslo k — n jako součet n přirozených sčítanců. Dále už postupujeme jako v Příkladě 1.10, tedy celkový počet způsobů je _. . , (n + k-n-í\ (k-l\ C*(»>k-»)=[ n_! J = (n-lJ- D Úlohy k řešení (1.4.1) Kolik různých součtů může padnout pokud hodíme najednou třemi kostkami s počty stěn 6, 10 a 12? (Kostky jsou číslovány od 1 do počtu stěn.) Návod: Ptáme se na hodnoty součtů, co padnou, takže třeba 2 + 3 + 7 je totéž co 1 + 2 + 9. (1.4.2) V tenisovém klubu se sešlo 5 hráčů. V kolika dvojicích si mohou zahrát dvouhru? (1.4.3) V tenisovém klubu se sešlo 9 hráčů. Kolik různých sestav na čtyřhru mohou vytvořit? Zdůvodněte svým úsudkem. (1.4.4) Kolika způsoby můžeme zamíchat 32 karet, aby byly v neklesajícím pořadí, přičemž se neohlížíme na jejich barvy? (Tj. nebude král před dámou a podobně.) * (1.4.5) Kolika způsoby můžeme nabarvit některé z 10 bílých kuliček jednou ze čtyř barev? *(1.4.6) Kolika způsoby lze psát číslo £ jako součet n sčítanců s hodnotami 1 nebo 2? Návod: Pozor, toto nelze řešit jako Příklad 1.10. Ve skutečnosti tento příklad vede na běžné kombinace bez opakování - vybíráme ty ze sčítanců, které jsou hodnoty 2. 2 Diskrétní pravděpodobnost Úvod Jedním ze základních historických motivačních zdrojů diskrétní matematiky, konkrétně klasické kombinatoriky, jsou hazardní hry. Hráči se odjakživa zamýšleli nad tím, jakou mají šanci hodit určitou kombinaci kostek nebo dostat do ruky jisté karty. Tyto otázky motivovaly jak zkoumání různých způsobů kombinatorických výběrů, tak i matematickou formalizaci důležitého filozofického pojmu pravděpodobnosti. Zabývat se zde budeme pouze (diskrétními) událostmi, ve kterých může nastat jedna z konečně mnoha izolovaných možností. Zhruba řečeno, náhodná událost je v diskrétní pravděpodobnosti modelována výběrem určitých jevů z prostoru všech možných jevů a její hodnota pravděpodobnosti je rovna relativní četnosti vybraných jevů vůči všem možným. 9 Učivo plynule navazuje na běžné středoškolské úlohy o hodech mincí, kostkou, či míchání karet, a dává jim pevné formální základy. Cíle Hlavním cílem lekce je pochopení modelu diskrétní pravděpodobnosti pomocí konečného pravděpodobnostního prostoru a relativní četnosti jevů na něm. Čtenář se naučí, jak používat model diskrétní pravděpodobnosti a jeho matematický aparát (jako sjednocení a průnik jevů, nezávislost, střední hodnotu, atd.) na řešení praktických problémů, především těch s náhodnými výběry. 2.1 Motivační příklady Před uvedením formální definice pravděpodobnostního prostoru začneme několika příklady pro osvětlení problematiky. V každém z nich se jedná o dobře známý náhodný proces s jedním z několika (předem známých) možných výsledků. • Hod mincí - má 2 možné výsledky hlava / orel, neboli 1/0. Každý padá se zhruba stejnou četností (říkáme "s pravděpodobností ^"). • Hod kostkou - má 6 možných výsledků 1,2, 3,4, 5, 6. Opět každý padá se stejnou četností (říkáme "s pravděpodobností g"). • Zamíchání karet - předpokládáme, že každé možné zamíchání karet lze asi stejně dobře očekávat. Zde je však všech možností nesrovnatelně více - 32!=2.6 • 1035, což vůbec nejsme schopni ani vypsat. Poznámka: Tento přirozený příklad zároveň přináší zajímavou filozofickou otázku: Jak můžeme tvrdit, že každé možné pořadí karet nastane stejně pravděpodobně, když se patrně za celou dobu existence lidstva a karet skutečně objeví jen nepatrný zlomek všech zamíchání? Toto lze seriózně rozřešit pouze použitím přesného formálního matematického modelu pravděpodobnosti. • Tah sportky - očekáváme, že každé příští tažené číslo bude "stejně pravděpodobné" ze všech čísel zbylých v osudí. Celý tah je však ve výsledku neuspořádaným výběrem, takže počet všech možností je (479) = 85900584. I to je příliš vysoké číslo pro snadnou představu. Často tak při našem pohledu na náhodné události přirozeně vycházíme z toho, že jisté různé možnosti si jsou "ekvivalentní" co do četnosti jejich výskytu (například proto, že fyzický postup výběru by mezi nimi neměl umět rozlišit za předpokladu poctivosti). Na tomto předpokladu pak stavíme naše "očekávání pravděpodobnosti"'. 2.2 Konečný pravděpodobnostní prostor V matematice chceme nějak modelovat chování "náhody": Náhodu přitom subjektivně vnímáme jako naše očekávání, zda nějaký jev nastane. Toto očekávání "měříme" našimi zkušenostmi s předchozí relativní četností opakování zkoumaného jevu. Proto je nasnadě se na pravděpodobnost matematicky dívat jako na číslo vyjadřující relativní četnost opakování jevu při velmi velkém množství pokusů. Seriózní formální základ tomuto pohledu poskytuje následující důležitá definice. Definice 2.1. Konečný pravděpodobnostní prostor je formálně dvojice (Q, P), kde Q je konečná množina elementárních jevů a P je funkce pravděpodobnosti, která podmnožinám Q přiřazuje reálné hodnoty z intervalu [0,1] a 10 -P(0)=O, P(íí) = l, - P(A U B) = P(A) + P (5) pro disjunktní A, B Qu. Jev je libovolná podmnožina A C fž a jeho pravděpodobnost je P (A). Čtenář nechť si dobře uvědomí významy pojmů jev a elementární jev a jejich vzájemný vztah. Elementární jev je jeden (kterýkoliv) prvek prostoru fl, neboli také příslušná jednoprvková podmnožina. Jev v obecnosti je jakákoliv podmnožina prostoru ft, tedy se skládá z několika elementárních jevů. Definice: Jevy A, B jsou disjunktní, pokud nemohou nastat zároveň, tj. pokud An B = 0. (Pravděpodobnosti disjunktních jevů se dle Definice 2.1 sčítají.) Poznámka: Pravděpodobnostní prostor je plně určený množinou SI a pravděpodobnostmi elementárních jevů - prvků íl. Pro A = {cti,... ,ak} Q íl totiž z definice platí P(A) = P(ai) + P(a2) + ... + P(ak). Nejčastější a nejpřirozenější funkcí pravděpodobnosti v praktických příkladech je následující: Definice: Uniformní pravděpodobnost je prostoru ft přiřazena funkcí p(A) = \A\/\n\, tj. každý elementární jev je stejně pravděpodobný a pravděpodobnost každého obecného jevu je dána jeho relativní velikostí vzhledem k celému prostoru ft. Komentář: Vraťme se k příkladům náhodných událostí z Oddílu 2.1 a ukažme si, jak jsou ony popsány pravděpodobnostními prostory ve smyslu Definice 2.1. - Při hodu mincí: fl = {0,1} a P(0) = P(l) = \. - Při hodu kostkou: fl = {1,2,3,4,5,6} a P(l) = ... = P(6) = \. Například jev "padlo sudé číslo" je tvořen podmnožinou {2,4,6}. — Při zamíchání karet: SI je tvořena všemi 32! permutacemi z 32 karet a každá permutace má stejnou pravděpodobnost ^. Například jev "první je eso" je tvořen podmnožinou všech těch permutací, co mají jako první kartu jedno z es. — Při tahu sportky: SI je tvořena všemi 7-prvkovými kombinacemi z 49 čísel a každá kombinace má pravděpodobnost l/(7). V jiných jednoduchých příkladech definujeme pravděpodobnostní prostor analogicky, ale jsou i složitější náhodné procesy, kde se již musíme dobře zamyslet nad tím, co jsou elementární jevy a jakou mají pravděpodobnost. Příklad 2.2. Představme si náhodný proces, kdy hodíme dvěma šestistěnnýma kostkami a zjišťujeme jejich výsledný součet. Popište jej pravděpodobnostním prostorem, ve kterém elementárními jevy jsou jednotlivé součty. Množina všech možných součtů dvou kostek je zřejmě SI = {2,3,..., 12}. Dobře se ale zamysleme nad pravděpodobnostmi těchto elementárních jevů. Je poměrně zřejmé, že součet 2, který lze získat jediným způsobem 1+1, bude padat méně často než součet 7, který lze získat šesti různými způsoby. Celkem je 6 • 6 = 36 možností hodů dvou kostek, z toho, jak jsme si všimli, součet 7 padne šesti způsoby, součet 6 pěti způsoby, atd. Užitím úvahy o poměrném počtu způsobů tak získáme funkci pravděpodobnosti P(2) = P(12) = ±, P(3) = P(11) = A = ^, 11 P(A) = P(10) = l6=± P(5) = P(9) = á = i, P(6) = P(8) = A ^(7) = é = i Ve skutečnosti je však lepší a přímočařejší použít jiný model s uniformní pravděpodobností, který je popsán v příštím příkladě. D Příklad 2.3. Popište pravděpodobnostním modelem Příklad 2.2 za použití prostoru s uniformní pravděpodobností. Jak jsme při řešení Příkladu 2.2 viděli, naše snaha prohlásit za elementární jevy při hodu dvou kostek jednotlivé součty byla dosti křečovitá a celé řešení přirozeně inklinovalo k modelu, kde elementárními jevy jsou jednotlivé dvojice hozených čísel. Takže mějme pravděpodobnostní prostor SI' = [1,6]2 (druhá kartézská mocnina množiny {1,... ,6}). Jevy jednotlivých součtů potom jsou Si=0, 52 = {(1,1)}, 53 = {(1,2),(2,1)}, 57 = {(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)}, 58 = {(2,6), (3,5), (4,4), (5,3), (6,2)}, Si2 = {(6,6)}. Jelikož pravděpodobnost jedné dvojice hozených čísel, tj. jednoho elementárního jevu v SI', je uniformní ^, snadno z tohoto popisu odvodíme stejné pravděpodobnosti jako v Příkladě 2.2. Toto řešení je přitom snazší a matematicky přesnější. D Úlohy k řešení (2.2.1) Jaká je pravděpodobnost, že na kostce padne liché číslo? (2.2.2) Hoďme dvěma kostkami. Jaká je pravděpodobnost, že padne součin 12? (2.2.3) Jaká je pravděpodobnost, že po zamíchání karet bude třetí karta shora eso? 2.3 Nezávislost jevů Nezávislost pravděpodobnostních jevů intuitivně znamená, že pravděpodobnost toho, že nastane druhý z nich, není nijak ovlivněna skutečným výsledkem prvního jevu, a naopak. Tento pojem je principiálně dosti podobný nezávislým výběrům z Lekce 1. Komentář: Začneme několika jednoduchými ukázkami. Nezávislé jevy: dva hody toutéž kostkou za sebou, hod kostkou a současné zamíchání karet, dva různé tahy sportky. Závislé jevy: vrchní a spodní číslo padlé při jednom hodu kostky, výběr první a druhé karty ze zamíchaného balíčku, dvě akumulační kurzové sázky obsahující stejné utkání. Jak však nezávislost jevů definujeme formálně? Jedná se totiž spíše o filozofický pojem, který neumíme přímo matematicky postihnout, proto pro definici nezávislosti použijeme součinové pravidlo (obdobné pravidlu pro násobení nezávislých výběrů), které je vlastně důsledkem intuitivního významu nezávislosti. Definice 2.4. Nezávislé jevy A, B jsou takové, pro které platí P (A D B) = P (A) ■ P(B). 12 Nezávislost dvou jevů A, B lze ještě vyslovit následujícím způsobem. Jev B je nezávislý na A, pokud pravděpodobnost B při nastalém jevu A je stále stejná jako pravděpodobnost jevu B obecně, tedy úměrou PjAnB) _ P{B) P(A) ~P(ň)' Jelikož P(íž) = 1, uvedený vztah je ekvivalentní definičnímu P (A n B) = P (A) ■ P (B). Poznámka: Uvedená definice nezávislosti jevů si zasluhuje bližší osvětlení, neboť je poněkud netradiční. Obvykle matematická definice pojmu obsahuje snadno ověřitelné podmínky, a pak následují tvrzení přisuzující definovanému pojmu různé užitečné vlastnosti. Zde je tomu však naopak, ona užitečná vlastnost, totiž pravidlo násobení pravděpodobností nezávislých výběrů, je přímo podmínkou v Definici 2.4. Jak jej tedy použijeme při řešení příkladů? Nejčastěji je to tak, že nezávislost dvou jevů vyplývá z kontextu situace, třeba se jedná o náhodné procesy bez jakékoliv fyzické vazby. V příkladě pak nezávislost takto zdůvodníme a součinové pravidlo využijeme při výpočtu. Poznámka: Pravděpodobnosti dané vzorcem p/^\ se také říká podmíněná pravděpodobnost jevu B za předpokladu, že nastal jev A. Značí se P(B\A). Příklad 2.5. Hodíme dvěmi stejnými kostkami najednou. Jaká je pravděpodobnost, že nám padne 4 a 5 ? Hody obou kostek jsou nezávislé, neboť v poctivé situaci mezi nimi není fyzická vazba. Pravděpodobnost, že na první kostce padne 4, je i, obdobně je i, že na druhé padne 5. Obě možnosti najednou padnou s pravděpodobností po vynásobení f • ^ = ^g • Musíme si však dát pozor na to, že kostky jsou stejné a my nemáme určeno, na které padne 4. Proto se úloha vlastně rozpadá na dva disjunktní jevy na první padne A a na druhé 5 a jev na první 5 a na druhé 4, a proto výsledná pravděpodobnost je součtem obou možností P= J- + -i- = -i- D 1 36 T 36 18 ' Úlohy k řešení (2.3.1) Ze zamíchaných karet rozdáme dvěma hráčům po pěti kartách. Jsou výběry karet, které dostanou, nezávislé? (2.3.2) Hodíme dvěma stejnými kostkami. Je jev na obou padne stejné číslo nezávislý s jevem na první padne dvojka? (2.3.3) Jaká je pravděpodobnost, že při současném hodu třemi stejnými kostkami padnou čísla 1, 3 a 5? (2.3.4) Jaká je pravděpodobnost, že při pěti hodech mincí padne vždy hlava? (2.3.5) Hráč dostává ze zamíchaných 32 karet do ruky pět karet. Jaká je pravděpodobnost, že dvakrát po sobě dostane do ruky královský pokr? 2.4 Střední hodnota Dále se podívejme na náhodné procesy, jejichž výsledkem je číslo, obvykle přirozené. (Omezíme se jen na procesy s konečně mnoha možnými výsledky.) Definice: Výsledek (předem neurčené číslo) takovéhoto náhodného procesu budeme nazývat náhodnou proměnnou. Definice: Nechť náhodná proměnná X nabývá k možných hodnot z množiny X £ {hi, ti2, ■ ■ ■, hk}, kde Xí nastává s pravděpodobností pi, a pí + p2 + • • • + Pk = 1- Střední hodnotou proměnné X je pak číslo EX = pi ■ hi + p2 ■ h2 + ... + Pk ■ hk . 13 Komentář: Zhruba řečeno, střední hodnota náhodné proměnné udává, jaký asi bude průměr získaných hodnot náhodné proměnné při mnoha opakováních náhodného procesu. Určit střední hodnotu má velký význam při statistických analýzách různých náhodných procesů, třeba známý algoritmus třídění quicksort může počítat i velmi dlouho, ale střední hodnota času jeho běhu je nejlepší ze všech běžných třídících algoritmů. Praktický výpočet středních hodnot v situacích složených výběrů lze výrazně ulehčit pomocí následujících dvou tvrzení. Věta 2.6. Pro libovolné dvě náhodné proměnné X, Y platí E(X + Y)=EX + EY. Věta 2.7. Pro libovolné dvě nezávislé náhodné proměnné X, Y platí E(X -Y) = EX • EY . Komentář: Pro příklady na střední hodnotu se podívejme na hody kostkami. Jaká je střední hodnota (průměr) čísel padlých na šestistěnné kostce? Jednoduchým výpočtem vyjde EK = ±(1 + 2 + 3 + 4 + 5 + 6) = ^ = 3.5. Jaká je střední hodnota součtu čísel padlých na dvou šestistěnných kostkách? S využitím předchozího výsledku E(K1 + K2) = EKX + EK2 = 3.5 + 3.5 = 7. Jaká je střední hodnota součinu čísel padlých na dvou šestistěnných kostkách? S využitím předchozího výsledku E(K1 ■ K2) = EKX ■ EK2 = 3.5 • 3.5 = 12.25. Vraťme se nyní k našemu intuitivnímu pojetí pravděpodobnosti jako očekávání četnosti opakování jevu. Pokud například hodíme n-krát mincí, pak pravděpodobnost \ jedné strany mince znamená, že zhruba n/2-krát padne každá ze stran mince. Pokud je naše matematická formalizace pravděpodobnosti správná, měla by nám tentýž výsledek říci střední hodnota počtu hlav při n hodech mincí. Jak tomu skutečně je, ukazuje následující příklad. Příklad 2.8. Jaký je průměrný počet hlav padlých při n hodech mincí? Pokud hlavě mince přiřadíme hodnotu 1, máme tak n náhodných proměnných Xi Y znamená "pokud X je pravda, musí Y být pravda". Ekvivalence X -<==> Y znamená "X je pravda zároveň s Y pravdivým". • Kvantifikace: - Vir : P(x) znamená, že P(x) je pravdivé pro všechny volby proměnné x (z dohodnuté či vyznačené množiny "Vir £ M"). - 3x : P (x) znamená, že P (x) je pravdivé pro aspoň jednu volbu proměnné x (z dohodnuté či vyznačené množiny u3x £ M"). Komentář: Pokusme se například vyjádřit známou "počítačovou" logickou operaci XOR pomocí výše uvedených operací matematické logiky. Jak známo, a XOR 6 je 1 (True) právě když a, b mají různé logické hodnoty, což je přesně negací ekvivalence, tj. a XOR b = -n(a^b). 3.2 Pojem matematického důkazu Než uvedeme, co je matematický důkaz, musíme si nejprve ujasnit, co bychom měli dokazovat, tj. co je matematické tvrzení. Definice: Matematické tvrzení (výrok) se skládá z přesně formulovaných předpokladů a ze závěru. Záměrně zde uvádíme jen velmi neformální opis nutných pojmů, neboť našim cílem je ukázat čtenáři základní principy a naučit jej chápat běžné jednoduché důkazy. Uvedení přesných logických definic by problematiku pro běžného čtenáře jen více zamlžilo. Definice: Slovně opsáno, matematický důkaz nějakého tvrzení P je konečná posloupnost kroků, kde každý krok obsahuje výrok, který je jedním z • axiomů - tj. obecně platných či předpokládaných faktů, • předpokladů tvrzení P, • výroků odvozených z předchozích kroků za použití některého z platných odvozovacích pravidel, a kde poslední krok obsahuje jako výrok závěr tvrzení P. Přitom volba systému axiomů závisí na matematické teorii, ve které pracujeme, a je tudíž různá v různých oblastech matematiky. Výběr použitelných odvozovacích pravidel je vlastností použité logiky a bude obvykle obsahovat jen přirozená odvození, nad kterými se v praxi ani nerozmýšlíme. Poznámka: Pamatujme, že různé matematické teorie mohou pracovat s různými množinami axiomů (dokonce i s různými odvozovacími pravidly), a tudíž dokazovat jiná tvrzení. Pro příklad můžeme zajít dokonce až do dávné historie - k axiomům Euklidovské geometrie, konkrétně k axiomu o rovnoběžkách. Po dlouhá dvě tisíciletí se matematici snažili dokázat platnost axiomu o rovnoběžkách z ostatních Euklidových axiomů, až teprve před zhruba dvěma stoletími se přišlo na to, že změnou axiomu o rovnoběžkách vzniknou úplně jiné, tzv. neeuklidovské, geometrie. 19 Pro ilustraci konceptu matematického důkazu jsme zvolili dobře známý fakt z algebry. Příklad 3.1. Dokažme v libovolném algebraickém (polo)okruhu pravidlo "agresivity nuly při násobení", tj. že x • 0 = 0 pro všechna x. Algebraický okruh je početní struktura s operacemi +, •, která splňuje několik základních a přirozených aritmetických vlastností - axiomů. Z nich zde využijeme následující axiomy: Va : a + 0 = 0 + a = a (1) Va, b,c: a + c=b + c =4> a = b (2) Va, 6, c : a • (6 + c) = a • b + a • c (3) Dobře si nyní promysleme, co je vlastně cílem našeho snažení. Někdo by se mohl ptát, proč dokazovat pravidlo x • 0 = 0, když to je přece jasné a každý to ví ze školy. Toto pravidlo však není zahrnuto mezi axiomy a důkaz potřebuje. A především, výsledkem našeho snažení bude důkaz, že fakt x • 0 = 0 platí ve všech možných početních strukturách, které splňují výše uvedené axiomy; přitom se vůbec nemusí jednak o počítání s čísly, jak je známe ze školy, ale o úplně jiné objekty, třeba geometrické. Důkaz výroku x • 0 = 0 v krocích: - Dosazením a = 0 do (1) odvodíme 0 + 0 = 0. - Vynásobením předchozího číslem x získáme x • (0 + 0) = x • 0. - Dosazením a = x, b = c = 0 do (3) odvodíme x • (0 + 0) = x • 0 + x • 0. - Spojením předchozích vztahů (tranzitivita =) vyjde x-0 = a;-0 + a;-0. - Dosazením a = x • 0 do (1) dále vyjde x-0 = 0 + a;-0 = a;-0 + a;-0. - Z (2) pro c = x • 0 nakonec dostaneme 0 = x • 0 . (Pochopitelně v praxi důkaz zapisujeme "zkratkou", ale naše zkratky musí být korektní, tj. rozepsatelné do takovýchto elementárních kroků.) D 3.3 Princip matematické indukce Princip matematické indukce je jedním z velmi důležitých axiomů přirozených čísel. Místo jeho formálního zavedení jako axiomu si jej pro lepší pochopitelnost uvedeme ve formě odvozovací metody matematických důkazů: Metoda 3.2. Matematická indukce Mějme tvrzení P (n) s celočíselným parametrem n. Nechť následující platí: • Tvrzení P(rio) je pravdivé, kde no = 0 či 1, nebo i pro obecné celé no-(Nazýváno základ indukce.) • Pro libovolné přirozené n z platnosti tvrzení P(n) plyne platnost tvrzení P(n + 1). (Tvrzení P (n) je v tomto kroku nazýváno indukční předpoklad.) Pak P(n) platí pro všechna přirozená n > no- Jak tedy můžeme princip matematické indukce použít? Typicky je použijeme v situaci, kdy máme dokázat platnost nějakého tvrzení s celočíselným parametrem, třeba n. Přitom platnost tohoto tvrzení by měla být poměrně zřejmá pro malá n a zvýšení parametru n o 1 by nemělo příliš změnit situaci. Komentář: Například, představme si, že dokazujeme korektnost nějakého algoritmu - vidíme, že po spuštění algoritmus je v konzistentním stavu, a po každém dalším kroku se konzistence stavu neporuší. Pak algoritmus zůstane v konzistentním stavu po celou dobu svého běhu podle principu matematické indukce. Nebo se podívejme na následující důležitý ilustrační příklad. 20 Věta 3.3. Každá n-prvková množina má právě 2n podmnožin (včetně prázdné). Formálně 2W. 2X Důkaz matematickou indukcí podle n: • Pro n = 0 tvrzení platí, neboť prázdná množina má jedinou podmnožinu, opět prázdnou. • Nechť nyní tvrzení platí pro n > 0. Vezmeme libovolnou množinu X o n + 1 > 0 prvcích. Zvolme prvek a G X a označme X' = X \ {a}, \X'\ = n. Potom všech podmnožin P' C X' je podle indukčního předpokladu 2n. Pro prvek a navíc máme nezávislý výběr ze dvou možností: buď a dáme do podmnožiny P', nebo nedáme. Celkem je tak 2 • 2™ = 2n+l možností volby podmnožiny PCX, cbd. Důkaz je hotov podle principu matematické indukce. □ Obdobně lze dokázat následující tvrzení: Věta 3.4. Je právě ab všech zobrazení z libovolné b-prvkové množiny do a-prvkové množiny. Formálně \A\\ß\ AB Poznámka: Zobrazení z 6-prvkové množiny do a-prvkové množiny se také jinak nazývají b-prvkové variace s opakováním z a prvků. My však dáváme přednost tomu je nazývat zobrazeními, neboli je vnímat jako posloupnost b nezávislých jednoprvkových výběrů z a-prvkové množiny. 3.4 Důkazy vzorců pro výběry Nyní si formálně dokážeme vzorce pro výběry prvků uvedené v Lekci 1. Použijeme přitom matematickou indukci a také Metodu 1.5 dvojího počítání. Věta 3.5. Počet všech permutací n-prvkové množiny je ni, pro každé n > 0. Důkaz indukcí podle n: Tvrzení platí pro n = 0, protože žádné prvky lze uspořádat jen jedním způsobem (stejně tak jeden prvek). Mějme nyní n > 0 a množinu P o n + 1 prvcích, předpokládejme pro jednoduchost P = {1, 2,..., n +1}. Zvolme první prvek p G P naší permutace jedním z n +1 způsobů. Chtělo by se přímo říct, že potom už je volba zbytku permutace P \ {p} nezávislá na volbě prvního p, ale to formálně není pravda. Aby tomu tak skutečně bylo, musíme si zbylé prvky P \ {p} nejprve "přečíslovat" na {1,2,..., n}, což počet voleb neovlivní. Pak už však zbytek plyne jasně - n-prvková množina {1,2,..., n} má podle indukčního předpokladu n! permutací, proto P má celkem (n+ 1) -n! = (n+ 1)! permutací. To je přesně to, co chceme. □ Věta 3.6. Počet všech k-prvkových variací z n-prvkové množiny je t^zwj Pro každé n>k>0. Důkaz metodou dvojího počítání: Budeme se dvěma způsoby dívat na výběr permutací n-prvkové množiny. Jak již víme, lze tyto permutace vybrat n! různými způsoby. Na druhou stranu lze vzít některou /c-prvkovou variaci, její prvky dát na začátek permutace v jejich pořadí a zbylých n — k prvků seřadit za nimi jedním z (n — k)l různých způsobů. Z různých variací tímto 21 postupem zřejmě získáme různé výsledné permutace, a přitom každou permutaci lze získat z variace vybírající jejích prvních k prvků. Označíme-li x neznámý počet všech /c-prvkových variací z n-prvkové množiny, lze výše popsaným postupem vytvořit právě x-(n — ky. všech různých permutací n-prvkové množiny. Proto platí x ■ (n — k)\ = n!, n! T = ---------------- (n-ky D Věta 3.7. Počet všech k-prvkových kombinací z n-prvkové množiny je (p, pro každé n>k>0. Důkaz metodou dvojího počítání: Nyní budeme dvojím způsobem počítat všechny /c-prvkové variace z n-prvkové množiny. Na jednu stranu už víme, že jich je t^zw> na druhou stranu můžeme z jedné k-prvkové kombinace vygenerovat celkem kl různých variací uspořádáním prvků této kombinace. Označíme-li tedy x neznámý počet všech /c-prvkových kombinací z n-prvkové množiny, dostaneme obdobně jako v předchozím důkaze n! x ■ kl {n-ky ' n! f n k\-{n-k)\ \k) D 3.5 Vztahy s kombinačními čísly Kombinační čísla splňují množství zajímavých vztahů a identit. (Zabývá se jimi dokonce celá samostatná část diskrétní matematiky.) Tři základní z nich uvádíme zde. Každá z nich má přirozenou oporu v pohledu na počty výběrů kombinací. Fakt. Pro všechna n > 0 platí Fakt. Pro všechna n > k > 0 platí UJ = \n-k)' Lema 3.8. Pro všechna n> k > 0 platí (n\ ( \k +\k + l) U + l n\ I n \ f n+ 1 + Důkaz: n\ í n \ n! n! Kk) + \k + 1J = k\-{n-k)\ + (jfe + 1)! • (n - k - l)\ = n! • (k + 1) + n! • (n - k) _ n!-(n+l) _(n+^ (jfe + l)!-(n-fc)! ~ (jfe + l)!-(n-ife)! ~ U + l D Tyto tři uvedené fakty mohou také posloužit jako definice kombinačních čísel. (Viz. Pascalův trojúhelník.) 22 1 O" Definice: Pascalův trojúhelník je naaranžováním všech kombinačních čísel do nekonečného "trojúhelníka", ve kterém krajní členy mají hodnoty 1 a každý vnitřní člen je součtem dvou členů bezprostředně nad ním. (Korektnost této definice je bezprostředním důsledkem Lematu 3.8.) Dalším důležitým vztahem dávajícím do souvislosti kombinační čísla s algebrou je následující věta. Věta 3.9. Tzv. binomická věta říká pro všechna n > 0 "-)-(:)+(j- 0 ■*+ +(„- J •*-■+(:;)-" • Důkaz: Tvrzení je možno dokazovat indukcí, ale také je možný důkaz následující jednoduchou úvahou (s využitím Věty 3.7): Jak víme, při algebraickém rozvoji součinu používáme pravidlo "násobit každý člen s každým". To znamená, že v rozvoji vztahu (1 + x)(l + x)... (1 + x) nám člen xk vyjde n tolikrát, kolik je možností (neuspořádaně) vybrat k z n činitelů-závorek. To jest právě O krát. D Důsledek 3.10. Z binomické věty plyne (pro přirozená n > 0 a druhé pro n > 0) 23 Pascalův trojúhelník 0- C)-0- Ö- GH o- o- o- e>- (:)=■ (:)=• o- O- (i o- o- a-» (;)-» o- Úlohy k řešení (3.5.1) Upravte následující výraz na jediné kombinační číslo: 2n \ í 2n n-l) \n + 2 "(3.5.2) Upravte následující výraz na jediné kombinační číslo: n\ (n + 1\ fn + 2\ f n + 3 3.6 Důkazy "počítáním" Někdy jsme při důkazech tvrzení postaveni do situace, že máme ukázat na existenci nějakého objektu nebo vlastnosti, které nejsme schopni konkrétně předvést nebo specifikovat. V takové situaci se hodí tzv. nekonstruktivní metody důkazu, které jistým způsobem "spočítají" existenci řešení, aniž řešení přímo specifikují. Nejznámějším příkladem je následující princip, který použijeme pro ilustraci: Metoda 3.11. Dirichletův princip Rozmístíme-li t + 1 (nebo více) objektů do t přihrádek, v některé přihrádce musí být aspoň dva objekty. Příklad 3.12. Mezi čtyřmi přirozenými čísly vždy najdeme dvě, jejichž rozdíl je dělitelný číslem 3. Nechť přihrádkami jsou zbytkové třídy při dělení číslem 3. Máme tedy pro naše 4 čísla tři přihrádky značené 0,1, 2. Podle Dirichletova principu do některé z přihrádek padnou dvě z čísel x,y, ale pak x — y dává zbytek 0 při dělení 3, tudíž jsme našli požadovanou dvojici. D Na závěr lekce si ukážeme na příkladech ještě jeden zajímavý postup dokazování tvrzení v diskrétní matematice počítáním možností. Zhruba řečeno, dokazujeme existenci požadované možnosti tím, že spočteme jiné možnosti a ukážeme, že je jich méně než všech možností. Komentář: Pro ilustraci: Do sledovaného objektu vešly včera tři osoby a dnes jej jen dvě osoby opustily. To znamená, že v objektu aspoň jedna osoba zůstává, přestože ji nikde nevidíme. Příklad 3.13. JVa letním táboře 29 dětí stráví celkem 16 dní a 15 nocí. Každou noc jsou dva z táborníků na hlídce. Dokažte, že některé z dětí musí jít na hlídku za celý tábor aspoň dvakrát. To je velice snadné počítání: Je-li celkem třeba 15 nočních hlídek, potřebujeme 15-2 = 30 táborníků na jejich pokrytí, pokud se žádný nemá opakovat. To však tak nejde, když je na táboře pouze 29 < 30 dětí. D Příklad 3.14. 8 kamarádů jelo na 9 dní dovolené. Každý den některá (jedna) trojice z nich šla na výlet. Dokažte, že někteří dva z nich ani jednou nebyli spolu na výletě. Rozebírání možností by asi k ničemu nevedlo... Důkaz počítáním je však opět snadný: Jedna trojice má celkem 3 dvojice, proto po 9 dnech se mohlo vystřídat nejvýše 9 • 3 dvojic ve výletních trojicích, ale 9 • 3 = 27 < (2) = 28, jedna dvojice nám zde schází. D 24 Úlohy k řešení (3.6.1) Existují na VŠB dva studenti se stejným posledním čtyřčíslím rodného čísla? (A dokážete je najít?) (3.6.2) Kdysi v dávných dobách se v MHD štípaly lístky třeba vyražením čtveřice čísel z 12. Mohli jste se spolehnout, že pokud jste si schovávali své lístky, tak nejpozději po 500 jízdách jste mohli některý lístek použít znovu? Rozšiřující studium Princip důkazu matematickou indukcí je podrobně vysvětlen v [ , Oddíl 1.3] a také v jiných učebnicích, třeba algebry. Důkazy mnoha početních kombinatorických vztahů lze najít v [5, Kapitola 2 a Kapitola 10], jedná se však o dosti obtížnou látku. 3.7 Cvičení: Příklady matematických důkazů Příklad 3.15. Dokažme indukcí podle k, že číslo (26k — 1) je dělitelné sedmi. Budeme postupovat indukcí podle parametru k > 0. • Pro k = 0 platí, že 2° — 1 = 0 je dělitelné sedmi. • Nechť nyní tvrzení platí pro nějaké k. Podívejme se, o kolik se změní hodnota výrazu (26fc — 1) při zvětšení k o jedna: /26(fc+i) _ i) _ h6k - 1\ = 26 • 26k - 26k = 26k ■ (26 - 1) = 26k ■ 63 Důležitým faktem nyní je, že číslo 63 je dělitelné sedmi. To ale znamená, že pokud (26fc — 1) bylo dělitelné sedmi podle indukčního předpokladu, bude sedmi dělitelné i 26(fe+i) _ i Formálně tento indukční krok zapíšeme následovně: Nechť dle indukčního předpokladu 26k — \ = lt, kde í je nějaké přirozené číslo. Pak í26(k+l) _1\ = 26 . 26fc _ 1 = (26 _ -g . 26fc + 26fc _ 1 = 63 . 26fc + 1(,= = 7 ■ (9 • 26k + ŕj , takže i tento výraz je dělitelný sedmi. Příklad 3.16. Dokažme následující identitu s kombinačními čísly: Představme si 2n-prvkovou množinu A = [l,2n], rozloženou na dvě disjunktní podmnožiny B = [l,n], C = [n + 1,2n], B U C = A. Budeme postupovat metodou dvojího počítání n-prvkových kombinací nad A: • Na jednu stranu je těchto kombinací ( ™). • Na druhou stranu si představme, že vybereme /c-prvkovou podmnožinu B' C B a /c-prvkovou podmnožinu C C C, pro libovolné k G [0,n]. Vytvoříme pak množinu K = B'Li (C\C). To lze podle principu nezávislých výběrů udělat právě Q) způsoby. 25 A kolik má množina K prvků? Bez ohledu na k to je k + (n — k) = n. Takže v předchozím bodě jsme vlastně jiným způsobem vybírali n-prvkovou kombinaci nad A. Jelikož dvakrát vybíráme totéž, musí platit rovnost v počtu výběrů, takže sečtením přes všechny hodnoty volného parametru k dostaneme požadované fc=0 D Příklad 3.17. Mějme 28 mincí stejné hodnoty, ze kterých je jedna falešná - lehčí než ostatní, a přesné rovnoramenné váhy bez závaží. Najděte postup, jak falešnou minci určit pouze použitím 4 vážení. Dokažte, že tři vážení na určení falešné mince nestačí. • Rozdělme mince na tři hromádky po 9-9-10 a první dvě z hromádek zvažme proti sobě. Pokud je hromádka A těžší než B, je falešná mince mezi B. Při opačném výsledku je falešná mince mezi A. A při rovnováze musí být falešná mince ve třetí hromádce C. • Totéž zopakujeme pro vybranou hromádku rozdělenou na 3-3-3 či 3-3-4 mince. • Totéž zopakujeme pro vybranou hromádku rozdělenou na 1-1-1 či 1-1-2 mince. • Případně ještě rozhodneme mezi posledními dvěma mincema. Naopak chceme ukázat, že 3 vážení nestačí. Využijeme důkaz počítáním. Každé jedno vážení má jen tři možné výsledky, proto po třech váženích jsme schopni rozlišit pouze 33 = 27 různých možností, ale celkem je 28 > 27 možných voleb falešné mince. Proto, ať děláme co děláme, při dvou různých volbách falešné mince musíme odpovědět stejně, takže jednou špatně. □ Úlohy k řešení (3.7.1) Dokažte, že pro každé přirozené n je číslo n3 — n dělitelné šesti. (3.7.2) Od jaké hodnoty n platí nerovnost (™) < (3) ? Dokažte, že pak už uvedená nerovnost je stále platná. (3.7.3) Dokažte vztah: r) + (r+1) + (r + 2)+...+ (n-1) + (n) = (n + ] r \ r I \ r I \ r I \r I \r + l "(3.7.4) Dokažte nerovnosti: n n/2 1: n ^(2* - 1) • 3i = (n - 1) • 3™+1 + 3 Návod: Nejsnadnější je důkaz matematickou indukcí. Podívejte se, jaký člen přibude vlevo, pokud se n zvýší na n + 1, a o kolik se pak zvětší pravá strana. 26 4 Relace a zobrazení Úvod Pro hlubší studium diskrétní matematiky je dále nezbytná jistá úroveň formalizace pojmů a vztahů. Dostáváme se totiž do modernějších oblastí oboru, kde již nevystačíme jen s jednoduchými kombinatorickými představami o výběrech či seřazeních prvků, ale potřebujeme přesné vyjádření různých vztahů mezi objekty. K tomu si defínujeme pojem relace a jejich speciálních případů uspořádání a ekvivalence. Dále se budeme věnovat formalizaci pojmu zobrazení a jejich skládání. Důležitým druhem zobrazení pro nás je tzv. bijekce jedné množiny na druhou - zobrazení jednoznačně přiřazující prvky první množiny na prvky druhé množiny a naopak. Speciálně si tak ukážeme jiný možný pohled na permutace jako na bijekci množiny na sebe. Závěrem ještě uvedeme princip inkluze a exkluze užívaný pro určení počtu prvků ve sjednocení množin, které nejsou disjunktní. Cíle Cílem této lekce je vysvětlit studujícímu formální pojmy relace, uspořádání a zobrazení a jejich použití k popisu různých matematických vztahů. Prezentovaný formalizmus je nezbytný pro hlubší studium diskrétní matematiky. Mimo to je zde popsán princip inkluze a exkluze mezi množinami. 4.1 Pojem relace Pro připomenutí: Kartézský součin dvou množin je množinou všech uspořádaných dvojic vybraných po složkách z těchto množin, tj. A x B = {(a,b) :ae A,be B}. Definice 4.1. Relace R na množině A je libovolná podmnožina kartézského součinu A x A = A2, tj. R IR jako z = x + y, z = 2x2y... — Funkce ze všech studentů, kde každému je přiřazen jeho nejlepší kamarád. — Funkce přiřazující jménu souboru v adresáři jeho umístění na disku (inode). Definice: Funkce / : A —> B je • prostá (injektivní) jestliže x ^ y G A implikuje f (x) j^f{y), • na (surjektivní) jestliže pro každé z G B existuje x G A, že f (x) = z, • vzájemně jednoznačná (bijektivní) jestliže je prostá a na. Bijektivní funkce budou pro nás mít zvláštní význam, jak si nyní přiblížíme. Poznámka o isomorfismu: Často se setkáváme s diskrétními strukturami, které jsou sice jinak prezentované či pojmenované, ale ve své podstatě jsou stejné - prvky jedné lze převést bijekci na prvky druhé bez změny vlastností. To vyjadřujeme slovem isomorfní. Například množina {1,..., n} má stejně mnoho podmnožin jako množina {n + 1,..., 2n}, protože mezi prvky existuje snadná bijekce předpisem b (i) = i + n. Co víc, i částečná uspořádání těchto systémů podmnožin inkluzí jsou si isomorfní přes rozšířenou bijekci b*(X) = {i + n : i £ X}. Jiným příkladem je třeba relace dělitelnosti na množině {1,2,3,4,6,9,12, 18,36} — ta je isomorfní dělitelnosti na množině {1,2,4,5,10,20,25,50,100} v bijekci p, která v prvočíselném rozkladu nahradí prvočíslo 3 prvočíslem 5, třeba p(í) = 1, p(3) = 5, p(6) = 10, p(9) = 25, ... 4.4 Skládání zobrazení; Permutace Důležitým a užitečným atributem zobrazení je možnost jejich vzájemného skládání za sebou. To je definováno zcela přirozeně (jako už znáte u složených funkcí z analýzy). Definice: Mějme zobrazení (funkce) / : A—>Bag:B—>-C. Pak jejich složením rozumíme zobrazení (g o /) : A —> C definované Í9° f){x) =g(f(x)). Poznámka: Místo výše definovaného způsobu skládání zobrazení se také často píše složení jako (fg) a skládá se "naopak" (fg)(x) = g(f(x)). Proto je třeba vždy ujasnit, který způsob skládání používáme! Pro zbytek tohoto oddílu se zaměříme na permutace coby zobrazení. Fakt: Nechť permutace ti na množině [l,n] je určena seřazením (pí,... ,pn)- Pak ti je také bijektivním zobrazením [l,n] —> [l,n] definovaným předpisem ir(i) = pi. Navíc lze permutace skládat jako zobrazení podle výše uvedené definice. 31 Fakt: Všechny permutace množiny [l,n] spolu s operací skládání tvoří grupu, zvanou symetrická grupa Sn. Poznámka: Permutační grupy (podgrupy grupy všech permutací) jsou velice důležité v algebře, neboť každá grupa je isomorfní některé permutační grupě. V kontextu pohledu na skládání zobrazení si zavedeme jiný, vhodnější, způsob zápisu permutací - pomocí jejich cyklů. Definice: Nechť it je permutace na množině A. Cyklem v it rozumíme posloupnost (ai,ü2, ■ ■ ■ ,dk) různých prvků A takovou, že 7r(aj) = uí+\ pro i = 1,2,..., k — l a7r(afc) = a\. Přitom, jak název napovídá, v zápise cyklu (a\, 02, • • •, a&) není důležité, kterým prvkem začneme, ale jen dodržení cyklického pořadí. Cyklus v permutaci může mít i jen jeden prvek (zobrazený na sebe). Komentář: Nakreslete si (vámi zvolenou) permutaci ir obrázkem, ve kterém vedete šipku vždy od prvku i k prvku ir(i). Pak uvidíte, že cykly dle naší definice jsou právě cykly tvořené šipkami ve vašem obrázku. S tímto grafickým zobrazením pro vás nebude problém pochopit následující tvrzení. Například permutaci 5, 3,4,8,6,1, 7,2 si lze obrázkem nakreslit takto: Lema 4.8. Každou permutaci na konečné množině A lze zapsat jako složení cyklů na disjunktních podmnožinách A. Důkaz: Vezmeme libovolný prvek a\ G A a iterujeme zobrazení 02 = vr(ai), atd., až se dostaneme zpět k a\. (To se musí stát, jelikož je A konečná.) Tak získáme první cyklus (ai,..., a&). Stejně pokračujeme s hledáním dalších cyklů ve zbylé množině A \ {ai,...,ak}. □ Značení permutací cykly: Nechť se permutace ti podle Lematu 4.8 skládá z cyklů (ai,..., ak), (61, • • •, h) a třeba (ci,..., cm) (nebo i libovolný jiný počet cyklů). Pak zapíšeme 7T = (ai,...,ak)(bi,... ,bi)(ci,...,cm). Komentář: Pro ilustraci. Vezměme 7-prvkovou permutaci 5,3,4,2,6,1,7. Ta se rozkládá na tři cykly (1,5,6), (2,3,4) a (7). Jiná permutace 3,4,5,6,7,1,2 má jediný cyklus (1,3,5,7,2,4,6). Nyní určíme složení těchto dvou permutací (zápisem cykly): (1,5,6)(2,3,4)(7) o (1,3,5,7,2,4,6) = (1,4)(2)(3,6, 5,7) (Nezapomínejme, že první se ve složení aplikuje pravá permutace! Postup skládání jsme použili následovný: 1 se zobrazí v permutaci vpravo na 3 a pak vlevo na 4. Dále 4 se zobrazí na 6 a pak na 1. Tím jsme uzavřeli první cyklus (1,4). Dále se 2 zobrazí na 4 a pak hned zpět na 2, tj. má samostatný cyklus. Zbylý cyklus určíme analogicky.) Úlohy k řešení (4.4.1) V zápise permutací cykly nalezněte složení těchto dvou permutací: (1,2,5,6X3,4)0 (1,3,4,5,6X2). 32 (4.4.2) Kolikrát musíme permutaci (1,2, 3)(4,5) složit samu se sebou, abychom dostali identickou permutaci? (Která zobrazí každé číslo na sebe sama.) * (4.4.3) Kolik je permutací n-prvkové množiny s jediným cyklem? 4.5 Princip inkluze a exkluze (Někdy také nazýván "princip zapojení a vypojeni1...) Následující důležitý množinový princip často využíváme v jednoduchých aplikacích, aniž si to uvědomujeme. Obrázek 4.3: Průnik dvou a tří množin - pro ilustraci inkluze a exkluze. Věta 4.9. Počet prvků ve sjednocení dvou či tří množin spočítáme: \AUB\ = \A\ + \B\-\AnB\ \A\JB\JC\ = \A\ + \B\ + \C\-\Af)B\ - \A n C\ - \B n c\ + \A n B n c\ Příklad 4.10. Podívejme se na typické použití principu inkluze a exkluze. Mezi studenty má 15 na svém počítači M$ Windows a 17 Linux. Přitom 6 z nich má oba systémy zároveň. Kolik studentů má aspoň jeden z těchto systémů? \W U L\ = \W\ + \L\ - \W n L\ = 15 + 17 - 6 = 26 Nechť ještě navíc 5 studentů má na svém počítači FreeBSD. Přitom jeden student má všechny tři systémy dohromady a další 2 mají Linux a FreeBSD najednou. Kolik studentů má aspoň jeden z těchto tří systémů? \WULUB\ = \W\-= 15 \L\ + \B\ -\wnL\ -\wnB\ - 17 + 5 - 6 - 1 - -|BnL| + |WnLnB| = 3 + 1 = 28 D Komentář: Zájemci o doplňující studium si mohou promyslet obecný princip inkluze a exkluze pro více množin, jak je symbolicky zapsaný zde: E (-d1 0^/C{l,...,n} -Tl-l (Jeho znalost nebude v předmětu vyžadována.) Úlohy k řešení (4.5.1) Mezi 30 žáky ve třídě jich 10 hraje fotbal a 20 dělá jiný sport. Z toho ale 5 žáků hraje současně fotbal a ještě dělá jiný sport. Kolik žáků celkem sportuje? (4.5.2) Ze 1000 televizí jich při první kontrole na výrobní lince má 5 vadnou obrazovku, 10 je poškrábaných a 12 má jinou závadu. Přitom 3 televize mají současně všechny tři vady a 4 jiné jsou poškrábané a mají jinou vadu. Kolik televizí je celkem vadných? 33 Rozšiřující studium Problematika relací, funkcí a uspořádání je obsáhle popsána ve většině učebnic algebry. Pro naše účely stačí zjednodušený pohled, který je prezentován třeba v [ , Oddíly 1.4,5,6,7]. Princip inkluze a exkluze (který je v kombinatorice velmi důležitý) je obsáhle popsán v [5, Oddíl 2.6]. 4.6 Cvičení: Příklady na relace a jiné Příklad 4.11. Kutil Tom má v dílně strašný nepořádek. V jedné bedýnce má pomíchané šroubky a matky všech možných průměrů. Defínujme si nyní relaci P, ve které je každý šroubek a každá matka v relaci sám se sebou (reňexivní). Navíc jsou v relaci P symetricky všechny dvojice šroubek-matka, které do sebe přesně pasují. Zdůvodněte, proč relace P nemusí být v obecnosti relací ekvivalence. Za jakých dodatečných podmínek je P relací ekvivalence? Definovaná relace je reflexivní a symetrická. Problémy jsou však s tranzitivitou. Dva různé šroubky mohou pasovat do stejné matky, takže by podle tranzitivity měly také být v relaci, ale tak tomu není. Stejný problém nastává se dvěma matkama pasujícíma na stejný šroubek. Pro druhou část se podívejme, jak výše uvedené problémy můžeme vyloučit. Stačí požadovat, aby k jednomu šroubku pasovala nejvýše jedna matka a naopak. Pak definovaná relace bude i tranzitivní a bude to ekvivalence. □ Příklad 4.12. Na množině všech přirozených čísel od 0 do 1000 defínujeme binární relaci R následovně: (a, b) G R právě když platí a) -1 b, takže R je antisymetrická. c) Tato relace je opět reflexivní. Žádnou z dalších jmenovaných vlastností nemá, jak zjistíme z toho, že (1,2), (2,1) G R, ale 1^2, dále (3,2) G R, ale (2,3), (3, ľ) <£ R. □ Příklad 4.13. 8 děvčat a 5 chlapců sedí okolo kulatého stolu rozesazeni tak, že čtyři děvčata jsou vedle sebe a jinak se pak střídají chlapec-děvče. Na povel se vymění podle následujícího schématu: Každý chlapec se přesune na místo nejbližšího chlapce po jeho pravici, každé děvče se přesune na místo nejbližšího děvčete po jeho levici. Po kolika opakováních této výměny se vrátí rozesazeni u stolu přesně do výchozího stavu? Zdůvodněte. Ze zadání se jedná o permutaci přísedících u stolu, která má právě dva cykly -jeden o 5 chlapcích a druhý o 8 děvčatech. Chlapci se dostanou na svá místa vždy po násobku 34 pěti přesunech, děvčata po počtu přesunů, který je násobkem osmi. Jelikož 5 a 8 jsou nesoudělná, nejmenší společný násobek je 5 • 8 = 40 přesunů. (Při řešení vůbec nezáleží, jak vlastně u stolu seděli, důležitá je jen existence dvou cyklů v permutaci.) □ Příklad 4.14. Kolika nulami končí desítkový zápis 33! ? Tento příklad nezapadá do žádného zatím probraného schématu, ale má své kouzlo a vztah k diskrétní matematice. Nepokoušejte se číslo 33 ! spočítat na vaší kalkulačce, její rozsah na to nestačí. Místo toho se zamysleme, jak v součinu 1 -2 •... 32 -33 vznikají nuly na konci. Jistě víte, že číslo 10 má prvočíselný rozklad 2 • 5, takže jakmile se v našem součinu objeví v rozkladu prvočísla 2 a 5, na konci za ně přibude jedna nula. Úkol tedy vlastně zní, spočítat, kolikrát se v prvočíselném rozkladu součinu 1 • 2 • ... 32 • 33 vyskytují prvočísla 2 a 5. Zřejmě se prvočíslo 2 vyskytuje mnohem častěji, takže budeme počítat pětky. Ty jsou po jedné v činitelích 5,10,15,20, dvě v 25 a opět jedna v 30. To je vše. Takže číslo 33 ! končí 4 + 2 + 1 = 7 nulami. □ Úlohy k řešení (4.6.1) JVa množině všech slov-řetězců nad běžnou abecedou definujme relaci následovně: Slovo x je v relaci se slovem y pokud je y obsaženo jako podřetězec v x. O jaký známý typ relace se jedná? Zdůvodněte. (4.6.2) JVa množině všech slov-řetězců nad běžnou abecedou defínujme relaci následovně: Slovo x je v relaci se slovem y pokud lze x získat z y jen přeházením písmen. O jaký známý typ relace se jedná? Zdůvodněte. (4.6.3) Mezi všemi studenty VŠB (obojího pohlaví) definujeme následující relaci: Dva studenti jsou v relaci, pokud mají a) stejný rok i stejný měsíc narození, b) stejný rok narození nebo různé pohlaví, c) stejný měsíc narození nebo stejné pohlaví, d) stejný rok narození a stejné pohlaví. Jaké vlastnosti má tato relace (jako reflexivní, symetrická, antisymetrická, tranzitivní) ? Jedná se třeba o částečné uspořádání nebo o ekvivalenci? * (4.6.4) Mezi všemi studenty na přednášce DIM definujeme následující binární relaci: Každý student je v relaci sám se sebou, tj. je to reflexivní relace. Každý student A je v relaci s jiným studentem B, právě když B sedí a) ve stejné řadě nalevo od A, b) ve stejné řadě jako A nebo v řadě hned za A, c) v poslední řadě (nezáleží, kde sedí A), d) v některé řadě před A. Jaké vlastnosti má tato relace (jako symetrická, antisymetrická, tranzitivní)? Jedná se třeba o částečné uspořádání nebo o ekvivalenci? Vaši odpověď dobře zdůvodněte. * (4.6.5) JVa množině všech přirozených čísel od 0 do 1000 definujeme binární relaci R ná- sledovně: (a, b) G R právě když číslo (a + 26) je dělitelné třemi. Zjistěte, jaké vlastnosti relace R má. Jedná se třeba o ekvivalenci nebo uspořádání? (4.6.6) Z kolika cyklů se skládá tato permutace? 7, 2,3, 6,4,5,1 (4.6.7) Složte dvě permutace (1,4, 6,5, 7)(2)(3) o (1,7)(2)(3)(4,6,5) v zápise cykly. (4.6.8) Složte dvě permutace (1,4, 5,6, 7)(2)(3) o (1,7)(2,3)(4,6,5) v zápise cykly. (4.6.9) Složte dvě permutace (1, 2, 3,4, 5)(6,7,8) o (2, 3,4, 5, 6,7)(1,8) v zápise cykly. (4.6.10) Mějme nějaké dvě permutace množiny [1,9], každou složenou z jediného cyklu. Kolik nejvíce cyklů může obsahovat permutace vzniklá jejich složením? (4.6.11) Kolika nulami končí desítkový zápis 66! ? (4.6.12) Jaká je poslední nenulová číslice 33! ? Návod: Obdobně Příkladu 4.14 vytkněte z rozkladu 33! prvočinitele 2 • 5 (jen v páru!) a ze zbylých činitelů stačí vynásobit poslední číslice. 35 * (4.6.13) Jaká je poslední nenulová číslice ve "složeném" kombinačním čísle (O), 5 Algoritmizace diskrétních struktur Úvod Na závěr první části našeho učebního textu zařazujeme doplňkovou lekci, která neformálně popisuje programátorskou implementaci některých dříve prezentovaných diskrétních struktur a konceptů. Ukážeme, jak lze implementovat posloupnosti, množiny, relace a zobrazení, jak je možno počítačově generovat různé typy výběrů, atd. Také se zmíníme o generátorech náhodných čísel. Ukázky programových kódů zde nejsou vyčerpávající ani jediné možné, jsou to jen jednoduché návody, jak by se s předvedenými strukturami mohlo v počítačových programech pracovat. (Samozřejmě mohou existovat jiné a třeba i lepší implementace, než jsou popsány zde.) Cíle Cílem této lekce je ukázat čtenáři praktické programové implementace některých diskrétních struktur a běžných základních algoritmů nad nimi. Jedná se skutečně jen o základní příklady, nikoliv o vyčerpávající přehled. 5.1 Programová implementace struktur Nejprve se podíváme na implementace základních struktur posloupnosti, zobrazení a obecné binární relace. (Implementaci množin pro jejich širší záběr ponecháme do samostatného oddílu.) Posloupnost (ao, ai,..., a„) implementujeme obvykle jako jednorozměrné pole a[ ], kde a [i] = a». Zobrazení / : A —> B implementujeme třeba obdobně jako posloupnost - pokud A = {ai,..., an} a B = {b\,..., bm}, použijeme pole f [ ], ve kterém f [i] =j vyjadřuje /(ßi) = bJ- Poznámka: Taková implementace se velmi hodí, pokud přímo zobrazujeme čísla, pro jiné objekty však ještě musíme "překládat" prvky z A či B na jejich indexy, což může být obtížné. Pak se lépe hodí různé pokročilé datové typy jako hašovací tabulky, atd... (Viz také implementace množin.) Binární relace R na množině A se nejpřirozeněji implementuje pro A = {a\,..., an} dvourozměrným polem (maticí) r [ ] [ ], ve kterém je r [i] [j] =0 pokud (aj, Oj) ^ R a r [i] [j]=l pokud (ai,a,j) G R. Příklad 5.1. Permutace: Pro ukázky operací se zobrazeními se soustředíme v příkladech na permutace, které lze vidět jako bijektivní zobrazení p [ ] množiny {0,1,..., n — 1} na sebe. a) Otestovat, zda zobrazení p[ ] je skutečně permutace, můžeme rychle takto (vlastně jen zjišťujeme, zda zobrazení je na): 36 for (i=0; i r\i][k] for (i=0; i=0) { if (++map[i]>=N) { i—; continue; } if (++i map[i] i—; } Podívejme se blíže na tento kód, který vlastně emuluje rekurzivní volání výběrů jednotlivých prvků (je to tak výrazně efektivnější). Jinými slovy, místo abychom volili smyčkou obraz prvního prvku map [0], pak se zanořili do rekurze a v ní volili obraz druhého prvku map[l], atd., tak se pohybujeme v jednom cyklu v proměnné "úrovni vnoření" i (od 0 do k — 1) a vybíráme vždy obraz map [i]. Pro každou volbu map [i] testujeme: • Zda už překročila rozsah N, pak se vracíme na předchozí úroveň. • Zda už byla poslední volba K-tého obrazu, jinak na další úroveň. Procházení všech variací Příklad 5.6. Všechny k-prvkové variace (bez opakování) z n prvků projdeme následovně: int i>j> select[K]; select [i = 0] = -1; while (i>=0) { if (++select[i]>=N) { i—; continue; } for (j=0; jj> select[K]; select [i = 0] = -1; while (i>=0) { if (++select[i]>=N) { i—; continue; } if (++i 3 vrcholů spojených do jednoho cyklu n hranami: 4 3 G„ 7 • • • n Cesta délky n má n + 1 vrcholů spojených za sebou n hranami: P J- n 1 2 3 4 . . . n n+1 Úplný graf na n > 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem (™) hran): 2 K„ Úplný bipartitní graf na m > 1 a n > 1 vrcholech má m + n vrcholů ve dvou skupinách (partitách), přičemž hranami jsou pospojované všechny m ■ n dvojice z různých skupin: m K„ n Úlohy k řešení (6.1.1) Zapíšeme graf výčtem vrcholů {a,b,c,d,e} a zkráceným výčtem hran {ac, ba, be, cd, de}. Nakreslete si jej! O jaký typ grafu se jedná? 43 (6.1.2) Pro jakou hodnotu n je úplný graf Kn zároveň cestou? (6.1.3) Pro jakou hodnotu n je úplný graf Kn zároveň kružnici? (6.1.4) Pro jaké hodnoty m, n > O je úplný bipartitní graf Kmn zároveň kružnici? (6.1.5) Pro jaké hodnoty m, n > O úplný bipartitní graf Kmn neobsahuje žádnou kružnici? (6.1.6) Kolik hran musíte přidat do kružnice délky 6, aby vznikl úplný graf na 6 vrcholech? (6.1.7) Má více hran úplný graf K q nebo úplný bipartitní graf K^fi? 6.2 Stupně vrcholů v grafu Máme-li graf, často nás zajímá, kolik z kterého vrcholu vychází hran-spojnic. Proto je jedním z prvních definovaným pojmů stupeň vrcholu v grafu. Definice 6.2. Stupněm vrcholu v v grafu G rozumíme počet hran vycházejících z v. Stupeň značíme dc{v). (Slovo "vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí říkat, že hrana vychází z obou svých konců zároveň.) Obrázek 6.2: Tento graf má stupně vrcholů 1,2,3,4,4,4, 6. Věta 6.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. Důkaz. Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát -jednou za každý její konec. Proto výsledek vyjde sudý. □ Vlastnosti stupňů Jelikož v obyčejném grafu zvlášť nerozlišujeme mezi jednotlivými vrcholy, nemáme dáno žádné pořadí, ve kterém bychom stupně vrcholů měli psát (pokud je nepíšeme přímo do obrázku grafu). Proto si stupně obvykle seřazujeme podle velikosti. Zajímavou otázkou je, které posloupnosti stupňů odpovídají vrcholům skutečných grafů? (Například posloupnost stupňů 1,2,3,4,5,6,7 nemůže nikdy nastat.) Věta 6.4. Nechť d\ < cfe < • • • < dn je posloupnost přirozených čísel. Pak existuje graf s n vrcholy stupňů d\, d2, ■ ■ ■, dn právě tehdy, když existuje graf s n — 1 vrcholy stupňů d\, d2, ■ ■ ■, dra_dn_i, dn_dn — 1,..., dn-2 — 1, dn-\ — 1. Komentář: K použití Věty 6.4: Mírně nepřehledný formální zápis věty znamená, že ze seřazené posloupnosti odebereme poslední (největší) stupeň dn a od tolika dn bezprostředně předchozích stupňů odečteme jedničky. Zbylé stupně na začátku posloupnosti se nezmění. (Nezapomeňme, že posloupnost je třeba znovu seřadit dle velikosti.) Příklad 6.5. Existuje graf se stupni vrcholů: 44 (1,1,1,2,3,4) ? Dle Věty 6.4 upravíme posloupnost na (1, 0,0,1, 2), uspořádáme ji (0, 0,1,1,2), pak znovu vše zopakujeme na (0,0, 0,0) a takový graf už jasně existuje. Na druhou stranu, jak takový graf sestrojíme? (Obvykle není jediný, ale nás zajímá aspoň jeden z nich.) Prostě obrátíme předchozí postup, začneme z grafu se 4 vrcholy bez hran, přidáme vrchol stupně 2 spojený se dvěma z nich a další vrchol stupně 4 takto: • • • • • • (1,1,1,1,2,3,4,6,7) ? Podobně upravíme tuto posloupnost na (1,0,0,0,1,2,3,5) a uspořádáme ji (0,0,0,1,1,2,3,5), pak znovu upravíme na (0,0,-1,0,0,1,2), ale to už přece nelze - stupně v grafu nejsou záporné. Proto takový graf neexistuje. D Úlohy k řešení (6.2.1) Kolik hran má graf se 17 vrcholy stupňů 4? (6.2.2) Existuje graf se stupni 4, 2, 3,5, 3,2, 3? Nakreslete jej. (6.2.3) Existují dva různé grafy se 6 vrcholy stupňů 2? 6.3 Podgrafy a Isomorfizmus Podgraf je, jednoduše řečeno, část grafu, ale toto musíme vyjádřit poněkud přesněji, abychom předešli situacím, kdy by nám zbyly hrany bez vrcholů. Navíc ještě definujeme indukovaný podgraf, který z původního grafu přebírá všechny hrany mezi vybranými vrcholy. Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholů V(H) C V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V(H). Píšeme H C G. Obrázek 6.3: Co je (vlevo) a co není (vpravo) podgraf. Definice: Indukovaným podgrafem je podgraf H C G takový, který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H). Pozorný čtenář si možná již při čtení předchozího textu položil otázku: Co když vezmeme jeden graf (třeba kružnici délky 5) a nakreslíme jej jednou tak, podruhé zase jinak - je to stále tentýž graf nebo ne? Přísně formálně řečeno, každé nakreslení jistého grafu, třeba té kružnice C&, je jiným grafem, ale přitom bychom rádi řekli, že různá nakreslení téhož grafu jsou "stále stejná". Už jen proto, že grafy mají modelovat vztahy mezi 45 dvojicemi objektů, ale tyto vztahy přece vůbec nezávisí na tom, jak si grafy nakreslíme. Pro tuto "stejnost" grafů se vžil pojem isomorfní grafy. Pro správné pochopení a využití teorie grafů je tedy třeba nejprve dobře chápat pojem isomorfismu grafů. Definice 6.6. Isomorfizmus grafů G a H je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —>■ V(H), pro které platí, že každá dvojice vrcholů u, v G V (G) je spojená hranou v G právě tehdy, když je dvojice f(u),f(v) spojená hranou v H. Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus. Píšeme G ~ H. Fakt: Isomorfní grafy mají stejný počet vrcholů (i hran). Komentář: Z nakreslených tří grafů jsou první dva isomorfní - jsou to jen různá nakreslení "téhož" grafu, kružnice délky 5. (Určitě snadno najdete isomorfismus mezi nimi. Pro jednoduchost isomorfismus zakreslete do obrázku tak, že vrcholy prvního očíslujete čísly 1 až 5 a vrcholy druhého stejnými čísly v pořadí odpovídajícím jeho bijekci.) Třetí graf jim isomorfní není, neboť, například, má vrcholy jiných stupňů. Fakt: Pokud je bijekce / isomorfismem, musí zobrazovat na sebe vrcholy stejných stupňů, tj. dc(v) = du{f{v)). Naopak to však nestačí! Příklad 6.7. Jsou následující dva grafy isomorfní? e Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2,2,2,2,3,3. Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého. Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické, proto si bez újmy na obecnosti můžeme vybrat, že nejlevější vrchol prvního grafu, označme jej 1, se zobrazí na nejlevější vrchol ľ v druhém grafu (taky stupně tři). Očíslujme zbylé vrcholy prvního grafu 2,... ,6 v kladném smyslu, jak je ukázáno na následujícím obrázku. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu (pravý spodní). Pak je již jasně vidět, že další sousedé 2, 6 vrcholu 1 se zobrazí na analogické sousedy 2', 6' vrcholu ľ v druhém grafu, a stejně je to i se zbylými vrcholy 3,5. Výsledný isomorfismus vypadá v odpovídajícím značení vrcholů takto: -B- Abychom mohli s isomorfismem grafů přirozeně pracovat, je potřeba vědět následující fakt: 46 m Věta 6.8. Relace "být isomorfní" ~ na třídě všech grafů je ekvivalencí. Důkaz. Relace ~ je reflexivní, protože graf je isomorfní sám sobě identickým zobrazením. Relace je také symetrická, neboť bijektivní zobrazení lze jednoznačně "obrátit". Tranzitivnost ~ se snadno dokáže skládáním zobrazení-isomorfismů. □ Důsledkem je, že všechny možné grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud mluvíme o grafu, myslíme tím obvykle jeho celou třídu isomorfismu, tj. nezáleží nám na konkrétní prezentaci grafu. Další grafové pojmy Značení: Mějme libovolný graf G. • Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice v G. • Speciálně říkáme trojúhelník kružnici délky 3. • Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta v G. • Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika v G. • Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G. • Indukovanému podgrafu H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G. Komentář: První z ukázaných grafů například neobsahuje žádný trojúhelník, ale obsahuje kružnici délky 4, dokonce indukovanou. Druhý graf trojúhelník obsahuje a kružnici délky 4 taktéž. První graf obsahuje cestu délky 4 na vrcholech 1,2,3,4,5, ale ta není indukovaná. Indukovaná cesta délky 4 v něm je třeba 2, 3,4, 5,6. Druhý graf tyto cesty také obsahuje, ale naopak žádná z nich není indukovaná. První graf má největší kliku velikosti 2 -jedinou hranu, kdežto druhý graf má větší kliku na vrcholech 3,4,5. Největší nezávislá množina u obou grafů má 3 vrcholy 2,4,6. Příklad 6.9. Jsou následující dva grafy isomorfní? Postupovat budeme jako v Příkladě 6.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2,2, 2,3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude sedět, že? Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. D 47 Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit) isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde tedy najde nějaký univerzální postup pro nalezení isomorfismu? Bohužel vás musíme zklamat, žádný rozumný univerzální postup není znám a má se za to, že jediná vždy fungující cesta pro nalezení či nenalezení isomorfismu mezi dvěma grafy je ve stylu vyzkoušejte všechny možnosti bijekcí mezi vrcholy těchto grafů. (Těch je, jak známo, ni) Úlohy k řešení (6.3.1) Jaká je velikost největší nezávislé množiny v tomto grafu? (Tj. největší podmnožiny vrcholů, mezi kterými není žádná hrana.) Vyznačte tuto množinu. (6.3.2) Jaká je délka nejkratší kružnice obsažené v grafu z Úlohy 6.3.1? (6.3.3) Jaká je délka nejdelší cesty obsažené v grafu z Úlohy 6.3.1? * (6.3.4) Jaká je délka nejdelší indukované cesty obsažené v grafu z Úlohy 6.3.1? (6.3.5) Dokážete najít ke grafu z Úlohy 6.3.1 neisomorfní graf, který má stejnou posloupnost stupňů? Proč není isomorfní? (6.3.6) Kolik existuje neisomorfních grafů s 5 vrcholy, všemi stupně 2? 6.4 Orientované grafy a multigrafy V některých případech (například u toků v sítích) potřebujeme u každé hrany vyjádřit její směr. To vede na definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.) Fakt: Orientované grafy odpovídají relacím, které nemusí být symetrické. Značení: Hrana (u, v) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v, u) je různá od (u, v)! Poznámka: Navíc někdy můžeme mluvit o tzv. multigrafech, ve kterých padají téměř všechna omezení na hrany... V multigrafu může mezi dvojicí vrcholů vést libovolný počet hran - tzv. násobné hrany, a některé z nich mohou být i orientované. Také jsou povoleny hrany, které mají oba konce totožné - tzv. smyčky. Multigrafy zmiňujeme jen okrajově pro úplnost, nebudeme se jimi dále zabývat. 48 6.5 Implementace grafů Mějme jednoduchý graf G na n vrcholech a značme vrcholy jednoduše čísly V(G) = {0,1,..., n — 1}. Pro počítačovou implementaci grafu G se nabízejí dva základní způsoby: • Maticí sousednosti, tj. dvourozměrným polem g[] [], ve kterém g [i] [j]=l znamená hranu mezi vrcholy i a j. • Výčtem sousedů, tj. použitím opět dvourozměrné pole h[] [] a navíc pole d[] stupňů vrcholů. Zde prvky h [i] [0] ,h[i] [1] , . . . ,h[i] [d[i]-l] udávají seznam sousedů vrcholu i. Poznámka: Dávejte si pozor na symetrii hran v implementaci! To znamená, že pokud uložíte hranu g [i] [j]=l, tak musíte zároveň uložit i hranu g[j] [i]=l, jinak se dočkáte nepříjemných překvapení. Totéž se týká i seznamů sousedů. Komentář: Implementace maticí sousednosti je hezká svou jednoduchostí. Druhá možnost se však mnohem lépe hodí pro grafy s malým počtem hran, což nastává ve většině praktických aplikací. (Navíc je implementace výčtem sousedů vhodná i pro multigrafy.) Ke grafům lze do zvláštních polí přidat také ohodnocení vrcholů a hran libovolnými čísly či značkami... Rozšiřující studium Rozsáhlý úvod do teorie grafů je zahrnut v [ , Kapitola 3] a navazují na něj další části této učebnice. Jiným zajímavým zdrojem, týkajícím se především implementace grafů a algoritmů na nich, mohou být výukové materiály předmětu Grafové Algoritmy na VŠB [7]. 6.6 Cvičení: Příklady o grafech a isomorfismu Příklad 6.10. Existuje graf s posloupností stupňů 1,1, 3, 3, 3,4,4,4, 6, 6, 6, 7? Daná posloupnost je již setříděná, jinak bychom ji nejprve vzestupně setřídili. Podle Věty 6.4 budeme posloupnost upravovat, přičemž vždy v řádku vypíšeme setříděnou posloupnost před odečtením a po odečtení (nesetříděnou). 1,1,3,3,3,4,4,4,6,6,6,7 -»■ 1,1,3,3,2,3,3,3,5,5,5 1,1,2,3,3,3,3,3,5,5,5 -»■ 1,1,2,3,3,2,2,2,4,4 1,1,2,2,2,2,3,3,4,4 -+ 1,1,2,2,2,1,2,2,3 1,1,1,2,2,2,2,2,3 -+ 1,1,1,2,2,1,1,1 1,1,1,1,1,1,2,2 -+ 1,1,1,1,1,0,1 0,1,1,1,1,1,1 zřejmě tento graf existuje (3 samostatné hrany). K poslední posloupnosti snadno sestrojíme graf, proto i graf s původní posloupností stupňů existuje. Zpětným přidáváním vrcholů sestrojíme i původní graf: D 49 Příklad 6.11. Najděte všechny isomorfní dvojice grafů v následujících obrázcích tří 10-vrcholových grafů. Isomorfní dvojice odpovídajícím způsobem očíslujte, u neisomorfních toto zdůvodněte. B AA i i <——•----- ----1—^^ 4v C t^----------•-------- -----•-----š* Postupujme systematicky: Všechny tři grafy mají po 10 vrcholech a všechny vrcholy stupňů 3. Takto jsme je tedy nijak nerozlíšili. Podívejme se třeba na trojúhelníky v nich - opět si nepomůžeme, neboť žádný z nich trojúhelníky neobsahuje. Co se tedy podívat na obsažené kružnice C4? Graf C jich jasně obsahuje pět, graf A po chvíli zkoumání také, ale v grafu B najdeme i při vší snaze jen tři kružnice délky 4. (Obdobného rozdílu si můžeme všimnout, pokud se zaměříme na kružnice C5, zkuste si to sami.) Takže co z dosavadního zkoumání plyne? Graf B nemůže být isomorfní žádnému z A, C. Nyní tedy zbývá najít (očekávaný) isomorfismus mezi grafy A a C. To se nám skutečně podaří poměrně snadno - stačí "prohozením" prostředních dvou vrcholů u grafu A získat lepší obrázek / 1--------- ---------1 \ 1 1 ŕ——c 1----------- ----------------c 1-------i» k --------1 1-------- / c t;--------1 1-------- ----------------c 1-----------—* a odpovídající bijekce je na pohled zřejmá. (Doplňte si ji společným očíslováním vrcholů obou grafů.) □ Příklad 6.12. Jaká je nejdelší kružnice a nejdelší indukovaná kružnice obsažená v následujícím grafu? Zdůvodněte. Co se týče nejdelší kružnice, ta nemůže být z principu delší než počet všech vrcholů, tedy 10. Přitom kružnici délky 10 v zadaném grafu snadno najdeme. Co se týče indukované kružnice, ta musí s vybranými vrcholy podgrafu obsahovat i všechny hrany mezi nimi (a přesto to musí stále být jen kružnice). To zřejmě žádnou kružnicí délky 10 splněno není. Nenajdeme dokonce ani takové kružnice délky 9 a 8, nejdelší při troše snahy najdeme indukovanou kružnici délky 7, jako třeba na následujícím obrázku: 50 Závěrem se zamysleme, proč vlastně delší indukovanou kružnici (než 7) nelze v našem grafu nalézt. Pokud bychom, pro spor, nalezli indukovanou kružnici délky 8, tak by musela použít jak ze spodního, tak z horního pětiúhelníku po čtyřech vrcholech. (Nemůže totiž být všech 5 vrcholů z jednoho pětiúhelníku, neboť to by uz byla kružnice délky jen 5.) Sami však snadným pokusem zjistíme, že v takové kružnici budou ještě hrany navíc, tudíž nebude indukovaná. □ Úlohy k řešení (6.6.1) Existuje graf s posloupností stupňů 1,1,1,3, 3,3,4,4,4? Návod: Použijte Větu 6.4. (6.6.2) Existuje graf s posloupností stupňů 1,1,1,1,1,1,1,1,6,6? (6.6.3) Kolik existuje neisomorfních grafů s 6 vrcholy, všemi stupně 3? Nakreslete je. Návod: Podívejte se místo těchto grafů na jejich doplňky - dejte hrany právě tam, kde je původní graf nemá. Tím vzniknou grafy se všemi stupni 5 — 3 = 2. (6.6.4) Kolik hran má graf s touto posloupností stupňů? A: 1,1,2,2,3,3,4,4,4,4,5,6,7 5:1,1,2,2,2,2,4,4,4,5,6,7 C: 1,1,2,2,2,3,3,4,4,4,5,6,7 (6.6.5) Najděte a vyznačte isomorfismus mezi následujícími dvěma grafy na 7 vrcholech. (6.6.6) Vyznačte isomorfismus mezi následujícími dvěma grafy na 8 vrcholech: (6.6.7) Vyznačte isomorfismus mezi následujícími dvěma grafy na 8 vrcholech: "(6.6.8) Existují dva neisomorfní grafy s posloupnostmi stupňů ii. fJ ,fJ ,fJ ,fJ ,fJ ,fJ. B: 2,2,3,3 ? U možnosti, kde dva neisomorfní grafy existují, je nakreslete. Pokud neexistují, pokuste se to správně zdůvodnit. (Pamatujte, že uvažujeme jednoduché grafy, tj. grafy bez smyček a násobných hran. Grafy nemusí být souvislé.) "(6.6.9) Najděte mezi následujícími grafy všechny isomorfní dvojice a zdůvodněte svou odpověď. (Isomorfní dvojice stejně očíslujte, u neisomorfních nejděte odlišnosti.) 51 a y______v b ,/______v c A/\ y~y j takový, že Vk = v j = Wi, a sled W pokračujeme krokem ... ,Wi = Vj = Vk,ek+i,Vk+i = Wí+\. Zbývá dokázat, že nový vrchol Wí+\ = Vk+\ se ve sledu W neopakuje. Pokud by tomu ale tak bylo wi = Wí+\} l < i, pak bychom na vrchol Wí+\ "přeskočili" už dříve z vrcholu Wi, spor. Nakonec skončíme, když Wi = v. □ Komentář: Ačkoliv uvedený důkaz vypadá složitě, je to jen jeho formálním zápisem. Ve skutečnosti se v důkaze neděje nic jiného, než že se původní sled zkracuje o opakované vrcholy, až nakonec zákonitě vznikne cesta. Závěrem se dostáváme k nejdůležitější definici souvislého grafu: Definice 7.3. Graf G je souvislý pokud je G tvořený jedinou komponentou souvislosti, tj. pokud každé dva vrcholy G jsou spojené cestou (dle Věty 7.2). 53 Poznámka: Prázdný graf je souvislý. Úlohy k řešení (7.1.1) Který z těchto dvou grafů je souvislý? (7.1.2) Kolik komponent souvislosti má tento graf? 7.2 Prohledávání grafu Když se lidé dívají na grafy, obvykle je vnímají jako obrázky a jejich pohled je jakoby globální. Pokud je však graf zpracováván v počítači (a obzvláště pokud se jedná o skutečně velký graf), tento globální pohled nemáme k dispozici a graf musíme prohledávat lokálně. Z toho důvodu se potřebujeme seznámit, jako vůbec s prvním grafovým algoritmem, s obecným postupem lokálního prohledávání grafu. Tento algoritmus není složitý a víceméně zobecňuje dobře známý postup procházení všech cest v bludišti. Pro vytvoření co nejobecnějšího schématu algoritmu pro procházení grafu vystačíme s následujícími datovými stavy a pomocnou strukturou: • Vrchol: má stavy ... - iniciační - dostane na začátku, - nalezený - poté, co jsme jej přes některou hranu nalezli, - zpracovaný - poté, co jsme už probrali všechny hrany z něj vycházející. • Hrana: má stavy ... - iniciační - dostane na začátku, - zpracovaná - poté, co už byla probrána od jednoho ze svých vrcholů. • Úschovna: je pomocná datová struktura (množina), - udržuje nalezené a ještě nezpracované vrcholy. Poznámka: Způsob, kterým se vybírají vrcholy z úschovny ke zpracování, určuje variantu algoritmu procházení grafu. V prohledávaných vrcholech a hranách se pak provádějí konkrétní programové akce pro prohledání a zpracování našeho grafu. Algoritmus 7.4. Procházení souvislých komponent grafu Algoritmus projde a zpracuje každou hranu a vrchol grafu G. Průchod se děje po jednotlivých komponentách, po projití jedné komponenty se přejde na případnou další. Konkrétní programové akce potřebné ke zpracování grafu jsou uvedeny v pomocných funkcích ZPRACUJ(). vstup < graf G; 54 sta.v(všechny vrcholy a hrany G ) = iniciační; úschovna U = {libovolný vrchol Vq grafu G}; stav (f o) = nalezený; II zpracování vybrané komponenty G while (U je neprázdná) { vybrat v G U; U = U\{v}; ZPRACUJ(v); for (e hrany vycházející zv) { if (stav(e)==iniciační) ZPRACUJ(e); w = druhý vrchol e = vw; if (stav(w)==iniciační) { stav(w) = nalezený; U = UU{w}; } stav (e) = zpracovaná; } stav (v) = zpracovaný; 1/ prípadný prechod na další komponentu G if (U je prázdná && G má další komponenty) úschovna U = {vrchol v\ další komponenty G}; } Příklady aplikací schématu Algoritmu 7.4 jsou uvedeny dále například v Důsledku 8.4 a v Algoritmu 8.9. Konkrétní postup algoritmu procházení bude ilustrován ve Cvičení 7.4. Způsoby implementace procházení grafu • Procházení "do hloubky" - úschovna U je implementovaná jako zásobník, tj. dále prohledáváme od posledních nalezených vrcholů. • Procházení "do šířky" - úschovna U je implementovaná jako fronta, tj. dále prohledáváme od prvních nalezených vrcholů. • Dijkstrův algoritmus pro nejkratší cestu - z úschovny vybíráme vždy vrchol nejbližší k počátečnímu f o- (Toto je dost podobné prohledávání do šířky, ale obecnější i pro případy, kdy hrany nejsou "stejně dlouhé".) Tento algoritmus bude v příští přednášce. 7.3 Vyšší stupně souvislosti V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním "vyšších" stupňů souvislosti grafu. Definice: Graf G je hranově k-souvislý, k > 1, pokud i po odebrání libovolných k — 1 hran z G zůstane výsledný graf souvislý. Definice: Graf G je vrcholově k-souvislý, k > 1, pokud i po odebrání libovolných k — 1 vrcholů z G zůstane výsledný graf souvislý. Speciálně úplný graf Kn je vrcholově (n — l)-souvislý. 55 Komentář: Stručně řečeno, vysoká hranová souvislost znamená vysoký stupeň odolnosti sítě proti výpadkům spojení-hran, neboli síť zůstane stále dosažitelná, i když libovolných fc — 1 spojení bude přerušeno. Vysoká vrcholová souvislost je mnohem silnějším pojmem, znamená totiž, že síť zůstane dosažitelná i po výpadku libovolných k — 1 uzlů-vrcholů (samozřejmě mimo těch vypadlých uzlů). # •©> Na ilustračním obrázku má první graf vrcholovou souvislost 4 a snadno vidíme, že po odebrání tří vrcholů či hran zůstává souvislý. Z druhého grafu bychom museli odebrat nejméně 3 hrany, aby se stal nesouvislým, a proto je jeho hranová souvislost 3. Na druhou stranu však stačí odebrat 2 vrcholy, aby mezi jeho levým a pravým krajním vrcholem žádné spojení nezůstalo. (Vidíte, které dva?) Důkaz následujícího výsledku (Mengerova věta) je příliš obtížný pro náš předmět, ale výsledek sám určitě stojí za zapamatování a pozdější použití: Věta 7.5. Graf G je hranově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k hranově-disjunktních cest (vrcholy mohou být sdílené). Graf G je vrcholově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k disjunktních cest (různých až na ty dva spojované vrcholy). Komentář: Věta nám vlastně říká, že stupeň souvislosti grafu se přirozeně rovná stupni redundance spojení vrcholů. Na výše uvedeném obrázku mezi každými dvěma vrcholy prvního grafu můžeme vést až 4 disjunktní cesty. U druhého grafu třeba mezi levým a pravým koncem lze vést jen 2 (vrcholově) disjunktní cesty, ale mezi každými dvěma vrcholy lze vést 3 hranově-disjunktní cesty. Úlohy k řešení (7.3.1) Jaký stupeň souvislosti má úplný bipartitní graf Knn? (7.3.2) Kolik nejméně vrcholů musíte vypustit z nakresleného grafu, aby v něm nezbyla žádná cesta mezi vrcholy x a y? Zdůvodněte. (7.3.3) Kolik nejméně hran musíte přidat k cestě délky 7, aby vznikl vrcholově 2-souvislý graf? 7.4 Jedním tahem: Eulerovské grafy Především z historických důvodů zařazujeme na závěr tuto poznámku o kreslení grafů jedním tahem. Definice: Tah je sled v grafu bez opakování hran. Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. 56 Nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera: (Jedná se o problém slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningradě.) Věta 7.6. Graf G lze nakreslit jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně. Důsledek 7.7. Graf G lze nakreslit jedním otevřeným tahem právě když G je souvislý a všechny vrcholy v G až na dva jsou sudého stupně. Úlohy k řešení (7.4.1) Lze tento graf nakreslit jedním otevřeným tahem? (7.4.2) Kolik hran musíte přidat ke grafu z předchozí otázky, aby se dal nakreslit jedním uzavřeným tahem? Rozšiřující studium Souvislosti grafů se blíže teoreticky věnují [ , Oddíly 3.2,8]. Algoritmy pro procházení grafu jsou podrobně popsány (včetně netriviálních aplikací) v [ } a demonstrovány i v [4]. 7.5 Cvičení: Příklady na souvislost grafů Příklad 7.8. Ukázka průchodu následujícím grafem do hloubky z vrcholu a. /*; 9 f: ------* e -A 3 \ 'if d / a *-- V této ukázce budeme obrázky znázorňovat stavy Algoritmu 7.4 v jednotlivých krocích takto: Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. 57 9 •=:: #--— -•, e í' ^'' > d h . V -\--:^» c a> d a *-- ■Ví V této ukázce budeme obrázky znázorňovat stavy Algoritmu 7.4 stejně jako v předchozím příkladě. 58 > d 9 c h d g c h Tímto zpracování zadaného grafu skončilo. Vidíte rozdíly tohoto průchodu proti předchozímu příkladu? □ Příklad 7.10. Mějme graf H3, jehož vrcholy jsou všechny podmnožiny množiny {1, 2, 3} a hrany spojují právě disjunktní dvojice podmnožin. (Tj. H3 má 8 vrcholů.) Rozhodněte, zda je H3 souvislý graf, a napište, kolik má H3 hran. Vrchol 0 odpovídající prázdné množině je spojený se všemi sedmi ostatními vrcholy, takže je graf souvislý. Nakreslete si jej! Každý vrchol i-prvkové podmnožiny je pak spojený s 23_* disjunktními podmnožinami doplňku. Celkem tedy máme součtem všech stupňů \(7 + 3 • 22 + 3 • 21 + 2°) = 13 hran. □ Úlohy k řešení (7.5.1) Kolik komponent souvislosti má tento graf? (7.5.2) Kolik nejvýše komponent může mít graf s 15 vrcholy, všemi stupně 2? "(7.5.3) Kolik nejvýše komponent může mít graf s 30 vrcholy, všemi stupně 4? (7.5.4) Kolik existuje neisomorfních grafů s 9 vrcholy, všemi stupně 2? Nakreslete je všechny a nezapomeňte na ty nesouvislé. (7.5.5) Mějme graf H5, jehož vrcholy jsou všechny dvouprvkové podmnožiny množiny {1,2,3,4,5} a hrany spojují právě disjunktní dvojice podmnožin. (Tj. H5 má 10 vrcholů.) Rozhodněte, zda je H5 souvislý graf, a napište, kolik má H5 hran. (7.5.6) Kolik nejméně hran musí mít graf na 12 vrcholech, aby stupeň jeho souvislosti byl3? (7.5.7) Kolik nejvíce hran může mít graf na 10 vrcholech, a) který se skládá ze tří komponent souvislosti, b) jehož každá komponenta souvislosti má nejvíce tři vrcholy? Tento graf také nakreslete. "(7.5.8) Existují dva neisomorfní grafy se stejnou posloupností stupňů -/i. Z. Z. Z.ó.ó. B: 2,3,3,3,3 ? U možnosti, kde dva neisomorfní grafy existují, je nakreslete. U zbylé možnosti pak správně zdůvodněte, proč dva takové neisomorfní grafy neexistují. (Pamatujte, že uvažujeme jednoduché grafy tj. grafy bez smyček a násobných hran. Grafy nemusí být souvislé.) 59 * (7.5.9) Existují dva neisomorfní grafy se stejnou posloupností stupňů B: 2,3,3,3,3 ? * (7.5.10) Existují dva neisomorfní grafy se stejnou posloupností stupňů /A.. Z. Z. Z. Z. Z. B: 1,1,3,3,3,3 ? * (7.5.11) Kolik existuje neisomorfních grafů na 6 vrcholech s posloupností stupňů 1,1,2,2,2,2? Všechny tyto grafy nakreslete a zdůvodněte i, proč jich není více. (Pamatujte, že uvažujeme jednoduché grafy tj. grafy bez smyček a násobných hran. Grafy nemusí být souvislé.) * (7.5.12) Hamiltonovská kružnice v grafů G je takový podgraf, který je isomorfní kružnici a obsahuje všechny vrcholy G. (Neboli je to kružnice procházející všemi vrcholy G právě jednou.) Najděte a nakreslete jednoduchý neorientovaný graf, který zároveň je vrcholově 3-souvislý a přitom neobsahuje Hamiltonovskou kružnici. (7.5.13) Lze tento graf nakreslit jedním tahem? A uzavřeným? (Uprostřed není vrchol, jen se tam kříží hrany.) 8 Vzdálenost a metrika Úvod V minulé lekci jsme mluvili o souvislosti grafu, tj. o možnosti procházení z jednoho vrcholu do jiného. Někdy je prostá informace o souvislosti dostačující, ale většinou bychom rádi věděli i jak je to z jednoho vrcholu do druhého "daleko". Proto se nyní podíváme, jak krátká či dlouhá taková procházka mezi dvěma vrcholy grafu je. V jednodušším případě se při zjišťování grafové vzdálenosti díváme jen na minimální počet prošlých hran z vrcholu do vrcholu. Tak například v našem ilustračním obrázku je vzdálenost mezi a, b rovna 2, vzdálenost mezi a, c je rovna oo a vzdálenost mezi c, x je rovna 3. Navíc vidíme, že vrchol d má "centrální" pozici v pravém grafu - každý další vrchol je od něj ve vzdálenosti nejvýše 2, kdežto vrchol c má "okrajovou" pozici. V obecném případě však při určování vzdálenosti bereme do úvahy délky jednotlivých hran podél cesty (tyto délky musí být nezáporné!). Jako hlavní náplň lekce si uvedeme známý Dijkstrův algoritmus pro určování nejkratší cesty v grafu. (Tento algoritmus je, mimo jiné aplikace, také základem programů vyhledávajících vlaková/autobusová spojení.) Většina tvrzení a algoritmy obsažené v této přednášce je beze změny aplikovatelná i na orientované grafy (tj. když nás zajímá i směr procházení hran). 60 Cíle Prvním cílem této lekce je definovat vzdálenost v grafech a její základní vlastnosti. Dalším úkolem je ukázat a správně pochopit Dijkstrův algoritmus pro hledání nejkratší cesty v grafu. 8.1 Vzdálenost v grafu Vzpomeňme si, že sledem délky n v grafu G rozumíme posloupnost vrcholů a hran vo,ei,vi,e2,V2,...,en,vn, ve které hrana e» má koncové vrcholy Ví-i,Ví. Definice 8.1. Vzdálenost dc{u,v) dvou vrcholů u, v v grafu G je dána délkou nejkratšího sledu mezi u a v v G. Pokud sled mezi u, v neexistuje, je vzdálenost cIg{u,v) = oo. Komentář: Neformálně řečeno, vzdálenost mezi u, v je rovna nejmenšímu počtu hran, které musíme projít, pokud se chceme dostat z u do v. Speciálně do{u,u) = 0. Uvědomme si, že nejkratší sled je vždy cestou (vrcholy se neopakují) - Věta 7.2. Grafová vzdálenost se chová dosti podobně běžné vzdálenosti, jak ji známe z geometrie, což bude vidět z následujících tvrzení. Poznámka: V neorientovaném grafu je vzdálenost symetrická do(u,v) = do{v,u). Lema 8.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: Vu,v,w £V(G) : dc{u,v) + dc{v,w) > dc{u,w). Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky cIg{u,v) mezi u,v lze navázat sled délky cIg{v,w) mezi v,w, čímž vznikne sled délky cIg{u,v) + dc{v, w) mezi u, w. Skutečná vzdálenost mezi u, w pak už může být jen menší. □ Věta 8.3. Nechťu, v, w jsou vrcholy souvislého grafu G takové, že dc{u, v) < dc{u, w). Pak při algoritmu procházení grafu G do šířky z vrcholu u je vrchol v nalezen dříve než vrchol w. Důkaz. Postupujeme indukcí podle vzdálenosti cIg{u,v): Pro dc(u,v) = 0, tj. u = v je tvrzení jasné - vrchol u jako počátek prohledávání byl nalezen první. Proto nechť cIg{u,v) = d > 0 a označme v' souseda vrcholu v bližšího k u, tedy cIg{u,v') = d — 1. Stejně tak značme w' souseda vrcholu w bližšího k u, tedy dc{u, w') > dc{u, v'). Potom byl vrchol v' nalezen v prohledávání do šířky dříve než vrchol w' podle indukčního předpokladu. To znamená, že v' se dostal do fronty úschovny dříve než w', a tudíž sousedé v' (mezi nimi v) budou při prohledávání nalezeni dříve než sousedé w'. □ Důsledek 8.4. Základní algoritmus procházení grafu do šířky lze použít pro výpočet vzdáleností z vrcholu u do ostatních vrcholů grafu: Toto je poměrně jednoduchá aplikace, kdy počátečnímu vrcholu přiřadíme vzdálenost 0, a pak vždy každému dalšímu nalezenému vrcholu přiřadíme vzdálenost o 1 větší než byla vzdálenost vrcholu, ze kterého jsme jej nalezli. Komentář: My si ale později ukážeme obecnější Dijkstrův algoritmus, který počítá nejkratší vzdálenost při libovolně kladně ohodnocených délkách hran. Úlohy k řešení (8.1.1) Jaká je největší vzdálenost dvou vrcholů v úplném grafu? (8.1.2) Jaká je největší vzdálenost dvou vrcholů v úplném bipartitním grafů K3344? 61 (8.1.3) Jaká je největší vzdálenost dvou vrcholů v kružnici Cn? (8.1.4) Jaká je největší vzdálenost mezi dvěma vrcholy v následujícím grafu? 8.2 Výpočet metriky Než se podíváme na samotný postup výpočtu vzdálenosti z jednoho vrcholu do druhého, uvedeme si ještě "globální" pohled na soubor všech vzdáleností v grafu, tedy na tzv. metriku grafu. Zajímavostí tohoto pohledu je především to, že výpočet celé metriky najednou má velice jednoduchý algoritmus, který není příliš známý a přitom je dobře použitelný i v jiných oblastech. (Jak třeba později uvidíte v teorii automatů.) Značení: Metrikou grafu myslíme soubor vzdáleností mezi všemi dvojicemi vrcholů grafu. Jinak řečeno, metrikou grafu G je matice (dvourozměrné pole) d[] [], ve kterém prvek d [i] [j] udává vzdálenost mezi vrcholy i a j. Metoda 8.5. Iterativní výpočet metriky skládáním cest • Na počátku nechť d [i] [j] udává 1 (případně délku hrany {i,j}), nebo oo pokud hrana mezi i, j není. • Po každém kroku t > 0 nechť d [i] [j] udává délku nejkratší cesty mezi i,j, která jde pouze přes vnitřní vrcholy z množiny {0,1, 2,... , t — 1}. • Při přechodu z í na následující krok t + 1 upravujeme vzdálenost pro každou dvojici vrcholů - jsou vždy pouhé dvě možnosti: (Dobře si zde všimněte, že přechodem na krok t +1 podle předchozího bodu skutečně dochází k jediné změně situace, kdy jsou teď navíc povoleny cesty přes vnitřní vrchol t.) - Buď je cesta délky d [i] [j] z předchozího kroku stále nejlepší (tj. nově povolený vrchol t nám nepomůže), — nebo cestu vylepšíme spojením přes nově povolený vrchol t, čímž získáme menší vzdálenost d [i] [t]+d[t] [j]. (Nakreslete si obrázek!) Poznámka: V praktické implementaci pro symbol oo použijeme velkou konstantu, třeba MAX-INT/2. (Nelze použít přímo MAX_INT, neboť by pak došlo k aritmetickému přetečení.) Algoritmus 8.6. Výpočet metriky grafu Tento algoritmus, pro graf s N vrcholy daný maticí sousednosti G, vypočte celou jeho metriku d. vstup: matice sousednosti G [] [] grafu na N vrcholech. kde G [i] [j ] =1 pro hranu mezi i, j a G [i] [j ] =0 jinak; for (i=0; i R. Kladně vážený graf G, w je takový, že w(e) > 0 pro všechny hrany e. Definice: Mějme (kladně) vážený graf G,w. Délkou váženého sledu S = Vo,ei,V\,-e-2, V2, ■ ■ ■, en, vn v G myslíme součet d%(S) = w(ei) + w(e2) + ■■■ + w(en). Váženou vzdáleností v G,w mezi dvěma vrcholy u,v pak myslíme dg(n, v) = min{dg(S') : S je sled s konci u, v} . Lenia 8.8. Vážená vzdálenost v kladně vážených grafech také splňuje trojúhelníkovou nerovnost. Komentář: Podívejme se na následující graf vlevo. (Čísla u hran udávají jejich váhy, hrany bez čísel mají váhu 1.) Vážená vzdálenost mezi vrcholy a, c je 3, mezi b,c také 3. Jaká je vzdálenost mezi vrcholy a, VI Ne, není to 6, ale najdeme kratší cestu délky 5. V druhém příkladě vpravo je uvedena i hrana se zápornou vahou —4. Nejkratší cesta mezi vrcholy x,y tak má délku —2, ale pokud vezmeme sled, který hranu váhy —4 vícekrát zopakuje, dostaneme se na libovolně nízkou zápornou délku. To je samozřejmě nesmyslné, a proto se takovému problému radši vyhýbáme zákazem záporných vah hran. Úlohy k řešení (8.3.1) Jaká je nejdelší vzdálenost mezi dvěma vrcholy v předchozím obrázku vlevo? (8.3.2) O kterém vrcholu v předchozím obrázku vlevo se dá říci, že má "centrální pozici", tj. že je z něj do všech ostatních vrcholů nejblíže? Jaká je z něj největší vzdálenost do ostatních vrcholů? 63 8.4 Hledání nejkratší cesty Pro nalezení nejkratší (vážené) cesty mezi dvěma vrcholy kladně váženého grafu se používá známý tzv. Dijkstrův algoritmus. Poznámka: Dijkstrův algoritmus je sice složitější než Algoritmus 8.6, ale na druhou stranu je výrazně rychlejší, pokud nás zajímá jen nejkratší vzdálenost z jednoho vrcholu místo všech dvojic vrcholů. Zrovna tento algoritmus se například používá při vyhledávání vlakových či autobusových spojení. Pravděpodobně se i vy někdy dostanete do situace, kdy budete nejkratší cestu hledat, proto si tento algoritmus zapamatujte. Dijkstrův algoritmus • Je variantou procházení grafu (skoro jako do šířky), kdy pro každý nalezený vrchol ještě máme proměnnou udávající vzdálenost - délku nejkratšího sledu (od počátku), kterým jsme se do tohoto vrcholu zatím dostali. • Z úschovny nalezených vrcholů vždy vybíráme vrchol s nejmenší vzdáleností (mezi uschovanými vrcholy) - do takového vrcholu se už lépe dostat nemůžeme, protože všechny jiné cesty by byly dle výběru delší. • Na konci zpracování tyto proměnné vzdálenosti udávají správně nejkratší vzdálenosti z počátečního vrcholu do ostatních. Algoritmus 8.9. Dijkstrův pro nejkratší cestu v grafu Tento algoritmus nalezne nejkratší cestu mezi vrcholy u a v kladně váženého grafu G, daného seznamem sousedů vrcholů. vstup: graf na N vrcholech daný seznamem sousedů sous [] [] a wh [] []. kde sous [i] [0] , . . . , sous [i] [st [i] -1] jsou sousedé vrcholu i stupně st [i] a hrana z i do sous [i] [k] má délku wh[i] [k] >0; vstup: u,v, kde hledáme cestu zu do v; // stav [i] udává zpracovanost vrcholu, vzdal [i] zatím nalezenou vzdálenost for (i=0; i<=N; i++) { vzdal [i] = MAX_INT; stav[i] = 0; } vzdal[u] = 0; while (stav[v]==0) { for (i=0, j=N; i^ \3 / ^^ \ / / 3\-^ / / \ ~^< OO i( ^5 / / \ ' 2 \ / \ / 2 x n y \ y \ u / \ / V-----------------Voo n i > oo '^l oo \ / U tohoto algoritmu se vlastně jedná a specifickou variantu procházení grafu. Proto použijeme stejné obrázkové značení jako v Příkladě 7.8 a navíc pro každý vrchol zakreslíme jeho okamžitou dočasnou vzdálenost vzdal [x]. (Tj. zpracované vrcholy budeme značit kroužkem a hrany plnou čarou.) Jednotlivé kroky následují: 66 Z průběhu algoritmu vidíme, že již ve třetím kroku jsme určili dočasnou vzdálenost z U do v na 7, ale to nebyla ta nejkratší. Nakonec po proběhnutí všech kroků algoritmu vzdálenost u,v poklesla až na optimálních 5. Nejkratší cesta je naznačená tlustými čarami. Pamatujte proto, že Dijkstruv algoritmus musíte provádět vždy tak dlouho, dokud se konečně nezpracuje cílový vrchol. □ Úlohy k řešení (8.5.1) Jaká je největší vzdálenost mezi dvěma vrcholy v každém z následujících dvou grafů? Vyznačte tyto dva nejvzdálenější vrcholy. (8.5.2) Jaká je největší vzdálenost mezi dvěma vrcholy v každém z následujících dvou grafů? Vyznačte tyto dva nejvzdálenější vrcholy. 67 (8.5.3) Kolik (neuspořádaných) dvojic vrcholů v následujícím grafů má vzdálenost právě 3? (8.5.4) Kolik nejméně hran musíme přidat do následujícího grafu, aby největší vzdálenost mezi dvěma vrcholy byla 2? Zdůvodněte. (8.5.5) Jaká je největší vzdálenost mezi dvojicí vrcholů v tomto váženém grafů? 2 2 4 4 fez (8.5.6) Kolik nejvíce vrcholů může mít graf, který má všechny vrcholy stupně 3 a největší vzdálenost mezi dvěma vrcholy je 2? "(8.5.7) Jaká největší vzdálenost může být mezi dvěma vrcholy kružnice délky 9, jejíž hrany jsou ohodnoceny vzdálenostmi 1, 2,..., 8,9 v nějakém (libovolném) pořadí? "(8.5.8) Představme si graf, jehož vrcholy jsou všechna přirozená čísla od 2 do 15 a hrany spojují právě ty dvojice vrcholů, které jsou soudělné jako čísla. Přitom délka hrany je vždy rovna největšímu společném děliteli. (Například 4,5 nejsou spojené a 8,12 jsou spojené hranou délky A.) Pomineme-li izolované vrcholy 11 a 13, jaká je největší vzdálenost mezi zbylými vrcholy tohoto grafu? 9 Stromy a les Úvod Jedním ze základních, a patrně nejjednodušším, typem grafů jsou takzvané stromy. Jedná se o souvislé grafy bez kružnic. Přes svou (zdánlivou) jednoduchost mají stromy bohatou strukturu a především množství vlastních aplikací. Patrně nejstarší motivací pojmu stromu jsou rodokmeny, jejichž původ sahá daleko před vznik teorie grafů. Proto také mnoho pojmů týkajících se stromů je motivováno rodokmeny. Co vidíme na následujících dvou obrázcích? 68 O důležitosti souvislosti grafu jsme pojednali dříve. Se stromy jako se souvislými (pod)grafy bez kružnic se pak setkáváme nejvíce v situacích, kde absence kružnic vyplývá z podstaty věci, nebo kde jsou kružnice zcela nežádoucí. To jsou různá schémata, datové struktury či již zmíněné rodokmeny. Stromy například přirozeně popisují různé hierarchické struktury. Mimo popisy struktur je ještě jedna důležitá oblast aplikací stromů, týkající se tzv. koster a problému hledání minimální kostry v grafu. Cíle Úkolem této lekce je hlavně definovat pojem stromu a ukázat základní vlastnosti stromů včetně jejich zdůvodnění. Podrobněji jsou probrány kořenové a uspořádané stromy a práce s nimi. Dále je zaveden pojem kostry grafů a důležitý problém minimální kostry, včetně jednoduchého "hladového" algoritmu pro jeho řešení. 9.1 Základní vlastnosti stromů Začneme definicemi lesa a stromů. Jelikož i smyčky a násobné hrany v multigrafech jsou považovány za kružnice délek 1 a 2, v lesích a stromech se nenacházejí. Bavíme se zde tudíž pouze o jednoduchých grafech. Definice: Les je jednoduchý graf bez kružnic. Definice 9.1. Strom je jednoduchý souvislý graf T bez kružnic. Fakt. Komponenty souvislosti lesa jsou stromy. Jeden vrchol (bez hran) je také strom. Dále si ukážeme přehled základních vlastností stromů, včetně jejich zdůvodnění, která jsou poměrně jednoduchá. Následující vlastnosti dokonce plně popisují stromy a mohou tudíž být použity místo uvedené Definice 9.1. Jedná se sice o poněkud obtížný teoretický oddíl, ale alespoň zběžné porozumění uvedeným vlastnostem je potřebné pro další práci se stromy a s jinými strukturami založenými na stromech. Lenia 9.2. Strom s více než jedním vrcholem má nějaký vrchol stupně 1. Důkaz. Souvislý graf s více než jedním vrcholem nemůže mít vrchol stupně 0. Proto vezmeme strom Tav něm libovolný vrchol v. Sestrojíme nyní co nejdelší sled S v T začínající ve v: S začne libovolnou hranou vycházející z v. V každém dalším vrchole u, do kterého se dostaneme a má stupeň větší než 1, lze pak pokračovat sled S další novou hranou. Uvědomme si, že pokud by se ve sledu S poprvé zopakoval některý vrchol, získali bychom kružnici, což ve stromu nelze. Proto sled S musí jednou skončit v nějakém vrcholu stupně 1 v T. □ Věta 9.3. Strom na n vrcholech má právě n — 1 hran pro n > 1. 69 Důkaz. Toto tvrzení dokážeme indukcí podle n. Strom s jedním vrcholem má n—1 = 0 hran. Nechť T je strom na n > 1 vrcholech. Podle Lematu 9.2 má T vrchol v stupně 1. Označme T' = T — v graf vzniklý z T odebráním vrcholu v. Pak T" je také souvislý bez kružnic, tudíž strom na n — 1 vrcholech. Dle indukčního předpokladu T' má n — 1 — 1 hran, a proto T má n — 1 — 1 + 1 = n — 1 hran. □ Věta 9.4. Mez« každými dvěma vrcholy stromu vede právě jediná cesta. Důkaz. Jelikož strom T je souvislý dle definice, mezi libovolnými dvěma vrcholy u, v vede nějaká cesta. Pokud by existovaly dvě cesty mezi u,v, tak jejich sjednocení by bylo uzavřeným tahem v T a po "zkrácení" všech opakovaných vrcholů v tomto tahu by vznikla kružnice v T, což je spor s předpokladem. Proto cesta mezi u a v existuje jen jedna. □ Důsledek 9.5. Přidáním jedné nové hrany do stromu vznikne právě jedna kružnice. Důkaz. Nechť mezi vrcholy u,v ve stromu T není hrana. Přidáním hrany e = uv vznikne právě jedna kružnice z e a jediné cesty mezi u,v v T podle Věty 9.4. □ Věta 9.6. Strom je minimální souvislý graf (na daných vrcholech). Důkaz. Strom je souvislý podle definice. Pokud by souvislý graf měl kružnici, zůstal by souvislý i po vypuštění některé hrany té kružnice. Proto minimální souvislý graf je stromem. Naopak, pokud by vypuštěním hrany e = uv ze stromu T vznikl souvislý graf, pak by mezi u,v v T existovaly dvě cesty (dohromady kružnice) - hrana e a jiná cesta v T — e. To je ve sporu s Větou 9.4. Proto je strom minimálním souvislým grafem na daných vrcholech. □ Závěrem si pro správné pochopení základních vlastností stromů vyřešíme následující (nepříliš jednoduchý) příklad. Příklad 9.7. Kolik nejvýše kružnic vznikne v grafu, který vytvoříme ze stromu přidáním dvou hran? Přidáním jedné hrany do stromu T vznikne jedna kružnice dle Důsledku 9.5. Druhá hrana vytvoří nejméně ještě jednu kružnici ze stejných důvodů, ale může vytvořit i dvě další kružnice, jako třeba v následujícím grafu, kde strom T je vyznačen plnými čarami a dvě přidané hrany čárkovaně. Každá z přidaných dvou hran vytvoří vlastní trojúhelník a navíc ještě vznikne kružnice délky 4 procházející oběma z přidaných hran. Na druhou stranu chceme ukázat, že více než 3 kružnice vzniknout nemohou po přidání dvou hran e,f do stromu T: Podle Důsledku 9.5 vznikne jen jedna kružnice procházející hranou e a neobsahující /, stejně tak jedna kružnice procházející / a neobsahující e. Nakonec stačí nahlédnout, že je nejvýše jedna možná kružnice procházející oběma hranami e, /, neboť jinak by už ve stromě T musela být kružnice. D Úlohy k řešení (9.1.1) Kolik je neisomorfních lesů na třech vrcholech? Nakreslete si je. (9.1.2) Kolik je neisomorfních stromů na čtyřech vrcholech? Nakreslete si je. *(9.1.3) Najdete graf s dvěma kružnicemi, z něhož lze odebráním jedné hrany vytvořit strom? Zdůvodněte a případně nakreslete. 70 9.2 Kořenové stromy Při mnoha použitích stromů se ke stromu jako grafu samotnému ještě váží dodatečné informace, jako třeba vyznačený jeden vrchol, tzv. kořen stromu, ze kterého celý strom "vyrůstá". Typickým příkladem jsou různé (acyklické) datové struktury, ve kterých je vyznačený vrchol - kořen, referován jako "začátek" uložených dat. Jinak třeba evoluční stromy druhů v biologii mají za kořen jejich společného (dávného) předchůdce. Kořenové stromy mají také tradiční motivaci v rodokmenech a z toho vychází jejich běžná terminologie. Definice 9.8. Kořenovým stromem je strom T spolu s vyznačeným kořenem r G V (T), zkráceně zapsaný dvojicí T,r. Komentář: Příklad kořenového stromu je na následujícím obrázku: Zajímavostí je, že v informatice stromy většinou rostou od kořene směrem dolů. (Však také nejsme v biologii...) Definice: Mějme kořenový strom T,r a v něm vrchol v. Označme u souseda v na cestě směrem ke kořeni r. Pak je u nazýván rodičem f a f je nazýván potomkem u. Komentář: Kořen nemá žádného rodiče. V přirozeně přeneseném významu se u kořenových stromů používají pojmy prarodič, předchůdce, následovník, sourozenci, atd. Zběžná ilustrace použití těchto pojmů je na následujícím schématu stromu. kořen potomci Často se také setkáte v kořenových stromech s označováním "otec-syn" místo rodič-potomek. My jsme takové označení nepoužili proto, že by (hlavně v zemích na západ od nás) mohlo být považováno za "sexistické". Definice: Vrchol stupně 1 v libovolném stromu nazýváme listem. Komentář: Pozor, i kořen stromu může být listem, pokud má stupeň 1, ale obvykle se to tak neříká. List kořenového stromu, který není kořenem, nemá potomky. Občas se můžeme dostat do situace, kdy k danému stromu potřebujeme zvolit kořen, aby jeho volba byla jednoznačná, tj. aby bylo zaručeno, že pro dva isomorfní stromy nezávisle zvolíme tentýž kořen. K tomu nám dopomůže následující názorná definice centra. Definice: Centrem stromu T rozumíme buď vrchol nebo hranu nalezenou v T následujícím postupem: 71 Pokud má strom T jeden vrchol, je to jeho centrum. Pokud má strom T dva vrcholy, je jeho centrem hrana spojující tyto dva vrcholy. Jinak vytvoříme menší strom T'CT vypuštěním všech listů T najednou. Je zřejmé, že T" je neprázdný, a vracíme se na předchozí bod. Získané (rekurzivně) centrum T" je zároveň centrem T. Příklad 9.9. Ilustrací defínice centra jsou následující dva postupy nalezení centra (zleva doprava): ® V prvním stromě získáme kořen jako jediný vrchol po třech rekurzivních krocích odebrání listů. V druhém stromě je kořenem hrana, kterou získáme po dvou rekurzivních krocích. D Fakt. Pokud chceme danému (abstraktnímu) stromu přiřadit jednoznačně kořen, je nejlepší jej přiřadit centru stromu. Speciálně, pokud je centrem hrana, bude kořenem nový vrchol "rozdělující" tuto hranu na dvě. Viz předchozí příklad: ^ Další dodatečnou informací často vázanou ke kořenovým stromům je nějaké uspořádání potomků každého vrcholu, jako třeba seřazení potomků v rodokmenech podle jejich data narození. To formalizujeme následující definicí. Definice: Kořenový strom T,r je uspořádaný, pokud je pro každý jeho vrchol jednoznačně dáno pořadí jeho potomků ("zleva doprava"). Uspořádaný kořenový strom se také nazývá pěstovaný strom. Komentář: Uspořádaný kořenový strom si jinak také můžeme představit jako strom s vyznačeným kořenem a pevně zvoleným nakreslením v rovině bez křížení hran. Nakreslení hran potomků vzhledem k hraně rodiče pak udává (ve zvolené orientaci) pořadí potomků. Tento pohled vede k názvu pěstovaný strom. Uspořádání potomků vrcholu ve stromu je přirozeně požadováno v mnoha praktických situacích. Například ve stromových datových strukturách jsou často potomci explicitně seřazeni podle daného klíče, jako třeba ve vyhledávacích binárních stromech. I v případech, kdy uspořádání potomků ve stromě není dáno, je možné jej jednoznačně definovat, jak uvidíme v následující části. Úlohy k řešení (9.2.1) Binární vyhledávací strom je uspořádaný kořenový strom, který se pro daná data obvykle tvoří následovně: První prvek dat se uloží do kořene. Každý další příchozí prvek, 72 pokud má menší klíč než kořen, uloží se rekurzivně do levého podstromu, pokud větší, tak do pravého podstromu. Vytvořte binární vyhledávací strom pro danou posloupnost dat s klíči 11,15,9,5,13,10,20,21,1,6. (9.2.2) Určete centra následujících dvou stromů: (9.2.3) Mějme libovolný strom s 33 vrcholy. Kolik jeho listů postupně odebereme, než určíme centrum? (Je to jednoznačné?) 9.3 Isomorfizmus stromů Jelikož stromy jsou speciálním případem grafů, je isomorfismus stromů totéž co isomorfismus grafů obecně. Avšak na rozdíl od grafů, kdy je určení isomorfismu algoritmicky (nakonec i ručně) těžký problém, pro isomorfismus stromů existuje efektivní postup, který si ukážeme. Nejprve si uvedeme restriktivnější (tj. vyžadující více shody) verze definice isomorfismu pro kořenové a uspořádané stromy. Definice: (Dva stromy jsou isomorfní pokud jsou isomorfní jako grafy.) Dva kořenové stromy T, r a T',r' jsou isomorfní pokud existuje isomorfismus mezi stromy T a T', který kořen r zobrazuje na kořen r'. Komentář: Například následující dva (isomorfní) stromy nejsou isomorfní coby kořenové stromy. Definice: Dva uspořádané kořenové (pěstované) stromy jsou isomorfní pokud je mezi nimi isomorfismus kořenových stromů, který navíc zachovává pořadí potomků všech vrcholů. Komentář: Například následující dva (isomorfní) kořenové stromy nejsou isomorfní coby uspořádané kořenové stromy, neboť pořadí potomků levého syna kořene se liší. 73 Kódování uspořádaných kořenových stromů Uspořádanému kořenovému stromu lze snadným postupem přiřadit řetězec vnořených závorek, který jej plně popisuje. (Možná jste se již s touto jednoduchou korespondencí závorek a kořenových stromů setkali, třeba při sémantické analýze matematických výrazů.) Definice: ( ((()()())()) (()(())) ) Kód uspořádaného kořenového stromu se spočítá rekurzivně z kódů všech podstromů kořene, seřazených v daném pořadí a uzavřených do páru závorek. Poznámka: Místo znaků '(' a ')' lze použít i jiné symboly, třeba '0' a 'ľ. Klíčovým a snadno zdůvodnitelným faktem o kódech pěstovaných stromů je toto tvrzení: Lema 9.10. Dva uspořádané kořenové (pestované) stromy jsou isomorfní pravé když jejich kódy získané podle předchozího popisu jsou shodné řetězce. Fakt. Je-li dán kód s uspořádaného kořenového stromu, příslušný strom nakreslíme následujícím postupem: - Při přečtení znaku '(' na začátku spustíme pero na papír, do kořene. - Při každém dalším přečtení znaku '(' nakreslíme hranu do následujícího potomka současného vrcholu. - Při každém přečtení znaku ')' se perem vrátíme do rodiče současného vrcholu, případně zvedneme pero, pokud už jsme v kořeni. Příklad 9.11. Nakreslete jako pěstovaný strom ten odpovídající závorkovému kódu ((()(()()()()))(()()))• D Při určování isomorfismu obecných stromů použijeme Lema 9.10 pro jejich jednoznačnou reprezentaci uspořádanými kořenovými stromy, ve které kořen volíme v centru 74 a potomky seřadíme podle jejich kódů vzestupně lexikograficky (tj. abecedně). Jinak se dá také říci, že kód přiřazený stromu T je lexikograficky nejmenší ze všech kódů uspořádaných stromů vzniklých z T s kořenem v jeho centru. Takový kód je zřejmě určující vlastností stromu T jako takového, a proto správnost následujícího algoritmu můžeme snadno nahlédnout. Algoritmus 9.12. Určení isomorfismu dvou stromů. Pro dané dva obecné stromy T a U implementujeme algoritmus zjišťující isomorfismus T ~? U následovné v symbolickém zápise: Vstup < stromy T a U; for (X=T,U) { // určení center daných stromů pro kořeny x = centrum (X); if (x je jeden vrchol ) r = x; else nový r, nahraď hranu x=uv hranami ru, rv; k [X] = minimalni_kod(X,r); } if (k[T]==k[U] jako řetězce) printf ("Jsou isomorfni."); else printf("Nejsou isomorfni."); exit; Funkce minimalni_kod (strom X, vrchol r) { if (X má jeden vrchol) return "O"; Y [1... d] = {souvislé komponenty X-r, tj. podstromy kořene r}; s[l...d] = kořeny podstromů Y[] v odpovídajícím pořadí; for (i=l,...,d) k [i] = minimalni_kod(Y[i] ,s [i]); sort lexikograficky (abecedně) podle klíče k [1] <=k [2] <=. . . <=k [d] ; return "("+k[l] + . . .+k[d]+")"; } Úlohy k řešení (9.3.1) Odvoďte správný závorkový kód pro tento pěstovaný strom: (9.3.2) Nakreslete pěstovaný strom odpovídající závorkovému kódu (((()())())((())(())))• 9.4 Kostry grafů Kromě stromů samotných se zabýváme i stromy, které jsou obsaženy jako podgrafy ve větších grafech. Definice 9.13. Kostrou souvislého grafu G je podgraf v G, který je sám stromem a obsahuje všechny vrcholy grafu G. 75 Komentář: Kostrou stromu je strom sám. Na druhou stranu kostrou kružnice Cn je každá z n cest vzniklých z Cn vypuštěním jedné hrany. Složitější grafy mají pak ještě více možných koster. Poznámka: Pojem kostry lze definovat i pro nesouvislé grafy, pak se kostrou myslí les, jehož stromy jsou kostrami jednotlivých komponent. Příklad 9.14. Kolik různých koster má tento graf? Podívejme se na kostru grafu takto - jaké hrany z grafy vymažeme, aby zbyl strom? Zajisté musíme vymazat některou hranu z první kružnice (5 možností) a některou hranu z druhé kružnice (6 možností). Na druhou stranu to v tomto jednoduchém příkladě už stačí, vždy pak zbude strom. Výběr vymazané hrany z první kružnice je nezávislý na druhé kružnici (jsou disjunktní), a proto dle principu nezávislých výběrů máme 5-6 = 30 možností vybrat dvě hrany k vymazání. Celkem tedy vyjde 30 koster. D Počet všech koster grafu lze obecně spočítat determinantem jisté matice, ale to už přesahuje rámec našeho textu. Zde si jen uvedeme následující fakt, jehož důkaz je také nad rámec textu. Fakt. Úplný graf Kn má přesně nn~2 koster. Kromě teoretických "hrátek" mají kostry grafů jedno důležité praktické použití, jež ukážeme nyní. Komentář: Dříve jsme uvažovali spojení v grafech cestami jdoucími z jednoho místa do druhého, ale nyní se podíváme na jiný způsob "propojování" všech vrcholů grafu najednou: Našim cílem je najít minimální souvislý podgraf daného grafu, tedy minimální způsob propojení (v daných podmínkách), ve kterém existují cesty mezi každou dvojicí vrcholů. Podle Věty 9.6 je tímto minimálním propojením strom - kostra našeho grafu. Tak je třeba uvažováno propojení domů elektrickým rozvodem, propojení škol interne-tem, atd. Zde nás ani tak nezajímají délky cest mezi propojenými body, ale hlavně celková délka či cena vedení/spojení, které musíme postavit. Vstupní graf nám udává všechny možné realizovatelné propojky s jejich cenami. Takto postavené zadání pak vede na následující teoretický problém. Problém 9.15. Minimální kostry (MST) Je dán souvislý vážený graf G,w s nezáporným ohodnocením hran w. Otázkou je najít kostru T v G, která má nejmenší možné celkové ohodnocení. Formálne MST = min ^ w(e) kostra TCG \eSE(T) Jak brzy uvidíme, zadaný problém má velmi jednoduché algoritmické řešení. Hladové algoritmy Asi nejjednodušším způsobem řešení různých optimalizačních úloh je uber postupně to nejlepší, dokud se dá". Tento postup se obecně v češtině nazývá hladovým, i když lepší by bylo použít správnější překlad anglického "greedy", tedy nenasytný. A ještě výstižnější české slovo by bylo postup "hamouna". 76 Metoda 9.16. Hladový postup Tato metoda řešení se používá u některých úloh, ve kterých hledáme co nejlepší řešení (optimalizujeme), skládající se z jednotlivých dílčích kroků (či elementů). Princip hladového postupu spočívá v tom, že ve vhodné pořadí bereme jednotlivé dílčí kroky úlohy a v každém se lokálně rozhodujeme pro nejlepší okamžitou možnost. Celkové řešení pak složíme z těchto dílčích nejlepších voleb. Značení: Algoritmy implementující hladový postup se všeobecně nazývají hladové algoritmy. Poznámka, pozor! Jistě jste se už setkali s tím, že postup hamouna obvykle nedává ty nejlepší výsledky (jak v teorii, tak ani v životě). Je to skutečně tak, hladový postup obvykle není matematicky korektní. Přesto však je třída optimalizačních úloh v diskrétní matematice, pro které hladový postup funguje výborně. Jedním příkladem fungování hladového postupu je právě hledání minimální kostry v grafu. Více příkladů bude uvedeno ve Cvičení 9.4. Všeobecně lze říci, že hladový algoritmus dobře funguje všude tam, kde podstatu problému lze vyjádřit tzv. matroidem. Algoritmus 9.17. Hladový pro minimální kostru. Je dán souvislý vážený grafG,w s nezáporným ohodnocením hran w. - Seřadíme hrany grafu G vzestupně podle jejich ohodnocení, tj. w(ei) < w(e2) < ... < w(em). - Začneme s prázdnou množinou hran T = 0 pro kostru. - Pro i = 1, 2,... , m vezmeme hranu e» a pokud T U {e»} nevytváří kružnici, přidáme ei do T. Jinak e» "zahodíme". - Na konci množina T obsahuje hrany minimální kostry váženého grafu G,w. Důkaz správnosti Algoritmu 9.17: Nechť T je množina hran získaná v Algoritmu 9.17 a nechť hrany jsou již seřazené w(e\) < w{e2) < ... < w(em). Vezměme množinu hran To té minimální kostry (může jich být více se stejnou hodnotou), která se s T shoduje na co nejvíce prvních hranách. Pokud To = T, algoritmus pracoval správně. Předpokládejme tedy, že Ti ^ T, a ukážeme spor, tj. že toto nemůže ve skutečnosti nastat. Označme j > 0 takový index, že se množiny To a T shodují na prvních j — 1 hranách ei,..., e.,-i, ale neshodují se na ej. To znamená, že ej G T, ale ej <£ Ti. (Jistě nemůže nastat e j <£ T, ale e j G Ti.) Podle Důsledku 9.5 obsahuje graf na hranách Ti U {ej} právě jednu kružnici C. Kružnice C však nemůže být obsažena v nalezené kostře T, a proto existuje hrana e& v C, která e& ^ T a zároveň k > j. Potom však je w(ek) > w(ej) podle našeho seřazení hran, a tudíž kostra na hranách (To \ {e&}) U {ej} (vzniklá nahrazením hrany e& hranou ej) není horší než Ti a měli jsme ji v naší úvaze zvolit místo Ti. To je hledaný spor. □ Komentář: Správný pohled na předchozí důkaz by měl být následovný: Předpokládali jsme, že nalezená kostra T se s některou optimální kostrou shoduje aspoň na prvních j — 1 hranách. Poté jsme ukázali, že některou další hranu e^ v (předpokládané) optimální kostře lze zaměnit hranou ej, a tudíž dosáhnout shodu aspoň na prvních j hranách. Dalšími iteracemi záměn ukážeme úplnou shodu naší nalezené kostry T s některou optimální kostrou. V našem důkaze jsme se vlastně zaměřili na důkaz toho, že ta poslední iterace záměn nemůže selhat. Nakreslete si tento důkaz obrázkem! Základní hladový algoritmus pro hledání minimální kostry grafu byl poprvé explicitně popsán Kruskalem, ale už dříve byly objeveny jeho podobné varianty, které zde jen stručně zmíníme. 77 Algoritmus 9.18. Jarníkův pro minimální kostru. Hrany na začátku neseřazujeme, ale začneme kostru vytvářet z jednoho vrcholu a v každém kroku přidáme nejmenší z hran, které vedou z již vytvořeného podstromu do zbytku grafu. Poznámka: Tento algoritmus je velmi vhodný pro praktické výpočty a je dodnes široce používaný. Málokdo ve světě však ví, že pochází od Vojtěcha Jarníka, známého českého matematika — ve světové literatuře se obvykle připisuje Američanu Primovi, který jej objevil až skoro 30 let po Jarníkovi. Avšak historicky vůbec první algoritmus pro problém minimální kostry (z roku 1928) byl nalezen jiným českým matematikem: Algoritmus 9.19. Borůvkův pro minimální kostru. Toto je poněkud složitější algoritmus, chová se jako Jarníkův algoritmus spuštěný zároveň ze všech vrcholů grafu najednou. Detaily lze nalézt v doplňkové literatuře [5, Oddíl 44]. Úlohy k řešení (9.4.1) Kolik koster má kružnice délky 2004? * (9.4.2) Zkuste sami vlastním počítáním odvodit, že počet koster úplného grafu K5 je 125 = 53. Návod: Zkuste něco chytřejšího, než kreslení všech koster. Co třeba se podívat na jednotlivé "typy" koster? Rozšiřující studium Stromům, jejich isomorfísmu a kódování se věnují [ , Oddíly 4.1,2]. Problém minimální kostry a jeho historie jsou výborně shrnuty v [ , Oddíly 4.3,4,5]. Hladový postup je běžně zmiňován a používán v knihách zabývajících se algoritmy a optimalizací. Pro konkrétní algoritmické implementace odkazujeme i na [3]. Zájemci o hlubší studium počítání koster v grafech si mohou přečíst (poměrně obtížnou) [ , Kapitola 7]. 9.5 Cvičení: Příklady o stromech, kostrách a hladovém postupu Příklad 9.20. Zjistěte, zda následující dva stromy jsou isomorfní. Nejprve si ověříme, že stromy mají stejný počet vrcholů (hran je pak také stejně). K daným dvěma stromům najdeme jejich centra a překreslíme si je jako kořenové stromy s kořeny v centrech. 78 Nyní přejdeme k určení minimálního závorkového kódu pro levý strom (Algoritmus 9.12): Například při rekurzivním volání ve vrcholu b určíme kódy jeho podstromů jako '()' a '(()())'. Jelikož levou závorku považujeme za slovníkově menší, tyto dva podkódy seřadíme a spojíme takto '((()())())'. Obdobně postupujeme dále... Nakonec v kořeni a získáme rekurzivními voláními kódy jeho tří podstromů '((()())())'> '()' a '((())()())'. Po seřazení a spojení nám celkový minimální kód levého stromu vyjde '(((()())())((())()())())'• Obdobně budeme postupovat při rekurzivním určování minimálního kódu pravého stromu. Zde nám podkódy jednotlivých tří podstromů kořene x vyjdou '()', '((())())' a '((()())()())'. Po seřazení a spojení nám celkový minimální kód pravého stromu vyjde '(((()())()()) ((())()) 0 )'• Napíšeme si tedy získané dva kódy pod sebe a uvidíme, kde se liší Lv . Dané dva stromy tudíž nejsou isomorfní. □ (((()())()())((())())()) J ■' Příklad 9.21. Kolik různých koster má tento graf? Jak vidíme, opět musíme vymazat dvě hrany z grafu, aby zbyla kostra. Nelze však vypouštět jednu hranu z levé kružnice a jednu z pravé, neboť by výběry nezyly nezávislé - hrana x je oběma sdílená. Podíváme se tedy na řešení jako na součet disjunktních možností, počtu koster obsahujících x a počtu koster bez hrany x. Pokud hranu x vymažeme, zbude kružnice délky 11 a ta má 11 koster. Pokud naopak hranu x zachováme, musíme z levé kružnice od x vymazat jednu ze 6 hran a z pravé kružnice jednu z 5 hran. Tyto výběry již jsou nezávislé a počet možností je 6 • 5 = 30. Celkem má náš graf 11 + 30 = 41 koster. □ Příklad 9.22. Najděme hladovým algoritmem minimální kostru v tomto váženém grafu (váhy hran. jsou zapsány čísly v obrázku). 3 4 3 3 s2 1/ l\ p-------------------------------------------------------- A 1 4 2 Hrany si nejprve seřadíme podle jejich vah 1,1,1,1, 2, 2, 2, 2, 3, 3, 3, 4, 4. (na pořadí mezi hranami stejné váhy nezáleží, proto jej zvolíme libovolně). Začneme s prázdnou množinou hran (budoucí) kostry. Pak hladovým postupem přidáme první dvě hrany váhy 1 vlevo dole, které nevytvoří kružnici. Třetí hrana váhy 1 vlevo s nimi už tvoří trojúhelník, a proto ji přidat nelze, je zahozena. Při znázornění průběhu používáme tlusté čáry pro vybrané hrany kostry a tečkované čáry pro zahozené hrany: 3 4 3 3 2 1 / 1 ''■.. i i /'■ 3 4 3 2 1 i > ^ 4 79 Poté přejdeme na hrany s vahou 2, z nichž lze tři postupně přidat bez vytvoření kružnice a čtvrtá (úplně vpravo) již kružnici vytvoří a je proto zahozena. Viz. obrázek vpravo. Nakonec ještě přidáme hranu nejmenší vyšší váhy 3 vlevo nahoře a zbylé hrany již zahodíme, protože všechny tvoří kružnice. 3 4 3 3 N ^ /\ 1 '■ i ----4 / \ M Získáme tak minimální kostru velikosti 1 + 2 + 2 + 3 + 1 + 1 + 2 = 12, která je v tomto případě (náhodou) cestou, na posledním obrázku vpravo. Poznamenáváme, že při jiném seřazení hran stejné váhy by kostra mohla vyjít jinak, ale vždy bude mít stejnou minimální velikost 12. (Například místo levé svislé hrany může obsahovat přilehlou úhlopříčku stejné váhy 1.) □ Příklad 9.23. Najděme minimální kostru grafu z Příkladu 9.22 Parníkovým algoritmem. Kostru začneme budovat v levém dolním vrcholu. (Tj. naše částečná kostra zatím dosáhla jen na levý dolní vrchol.) Vidíme, že obě hrany z něj vycházející mají váhu 1, proto je obě do kostry přidáme. Takto naše budovaná kostra již dosáhla na tři vrcholy grafu, které si v následujícím obrázku vlevo vyznačíme. (Zbylé hrany mezi dosaženými vrcholy jsou již k ničemu, proto je zahodíme.) 2 i V dalším kroku ze všech tří dosažených vrcholů vybíráme nejmenší hranu vedoucí mimo ně. Jak hned vidíme, nejmenší taková hrana má váhu 2, takže ji k naší kostře přidáme a dosáhneme čtvrtý vrchol grafu. Poté opět vybíráme nejmenší hranu z dosažených vrcholů ven, ale ty mají nyní váhu nejméně 3 (zvolíme tu nahoře vlevo). Také ji přidáme do kostry a dostaneme se do situace vyznačené na horním obrázku vpravo. Nyní již je dosažených vrcholů 5 a nejmenší z hran vedoucích z dosažených ven má váhu 2. (Všimněte si dobře tohoto rozdílu od základního hladového postupu - v tomto algoritmu se nemusí hrany probírat globálně monotónně podle svých vah!) Takto dosáhneme i pravého dolního vrcholu, na následujícím obrázku vlevo. 3 4 3 3 N< ^ / 2 1 i 1 '■ i ----4 / \ <4 Nakonec ještě dosáhneme zbylé dva vrcholy hranami po řadě vah 2 a 1. Získáme tak stejnou minimální kostru jako v Příkladě 9.22. Opět je však možnost nalézt jinou z 80 minimálních koster stejné velikosti, pokud mezi hranami stejné váhy vedoucími ven v každém kroku vybíráme jinak. □ V dalších dvou příkladech si ukážeme použití hladového postupu na řešení jiných problémů než minimální kostry. Obě aplikace postupu jsou podobné a poměrně přirozené, přesto jen první z nich je matematicky korektní - dává vždy optimální výsledek, kdežto druhá ne. Příklad 9.24. Podívejme se na tento přirozený problém z univerzitního prostředí: Kroužky studentů mají během dne pevně naplánované časy cvičení. Našim úkolem je rozmístit cvičení do co nejméně učeben, aby se samozřejmě v jedné učebně cvičení nepřekrývala. K vyřešení použijeme hladový postup: - Nejdříve začínající cvičení umístíme do učebny č. 1. - Vybereme nejdříve začínající neumístěné cvičení (libovolné, pokud jich více začíná ve stejnou dobu) a umístíme jej do první volné učebny nejmenšího čísla. - Opakujeme předchozí bod, dokud nejsou všechna cvičení rozmístěna. Jak dobrý výsledek (tj. maximální počet potřebných učeben) nám tento postup dá? Je to možná s podivem, ale tento primitivní postup nám dá zcela optimální řešení úlohy, jak si nyní stručně zdůvodníme: Předpokládejme, že učebny jsou číslovány 1,2,3,— Pokud uvedený hladový postup potřebuje celkem k učeben, znamená to, že v některém svém kroku již měl učebny 1,2,..., k — 1 obsazené probíhajícími cvičeními a pro další cvičení musel použít učebnu číslo k. (Jinak by použil učebnu menšího čísla.) To však znamená, že v onom okamžiku se najednou koná k různých cvičení, a proto použití nejméně k učeben je nutné. □ Příklad 9.25. Vrcholovým pokrytím v grafu G nazveme množinu vrcholů X C V (G) takovou, že každá hrana grafu G má aspoň jeden konec v X. Zadaným úkolem je nalézt v grafu vrcholové pokrytí nejmenší možné velikosti. Použijeme hladový postup (kdy se snažíme každým krokem pokrýt co nejvíce ze zbylých hran v grafu): - Začneme s prázdnou X = 0. - Vybereme vrchol v největšího stupně v G a přidáme jej do X. - Vrchol v odebereme z grafu G (i s jeho hranami) a jdeme zpět na předchozí bod, dokud nezbude graf G prázdný. Proč je toto řešení obecně nekorektní? Popsaný hladový postup v některých případech nenalezne nejmenší možnou množinu vrcholového pokrytí. Podívejme se na tento graf: Hladový postup nejprve vybere prostřední vrchol, ale pak ještě musí v dalších čtyřech krocích vybrat 4 vrcholy, tedy celkem vyjde množina X velikosti 5: 81 Snadno však zjistíme, že optimální vrcholové pokrytí má velikost jen 4 a je vyznačené na obrázku vpravo. □ Úlohy k řešení (9.5.1) Kolik hran je třeba vypustit z následujícího grafu na 9 vrcholech, aby zbyla jeho kostra? (9.5.2) Kolik vrcholů má strom s 2004 hranami? Je to jednoznačné? (9.5.3) Les má 2009 vrcholů a celkem 4 souvislé komponenty. Kolik má hran? (9.5.4) Kolik komponent souvislosti má les s 2004 vrcholy a 1993 hranami? (9.5.5) Mějme čísla {10,11,13,14,15,21} a spojme dvojice z nich hranami, pokud jsou soudělná. Je výsledný graf stromem? A aspoň lesem? (9.5.6) Které z následujících výrazů jsou správnými závorkovými kódy pro nakreslené uspořádané kořenové stromy? A: (((()()())())((())())) B: (((()()()())())(()())) C: (((()()())())(()(()))) (9.5.7) Kolik různých koster má tento graf? (9.5.8) Kolik koster může mít graf, který vznikne ze stromu na 8 vrcholech přidáním libovolné nové hrany (mezi dvěma nespojenými vrcholy) ? Uvědomte si, že pro různé stromy a hrany mohou vyjít různé výsledky, a vašim úkolem je najít všechny možné počty, včetně příslušných obrázků. (9.5.9) Kolik hran je třeba vypustit z úplného grafů na n vrcholech, aby vznikla jeho kostra? * (9.5.10) Kolik nejméně vrcholů musí mít graf (bez násobných hran), ve kterém lze nalézt dvě kostry nesdílející žádnou hranu? Zdůvodněte. * (9.5.11) Kolik koster má graf na následujícím obrázku? /^\ 82 10 Barevnost a kreslení grafů Úvod Již dříve jsme si připomínali jeden z historických kamenů teorie grafů - slavný problém sedmi mostů v Královci (dnešním Kaliningradě). Další neméně slavný problém pochází z poloviny 19. století a je obvykle zvaný problémem čtyř barev. Na rozdíl od sedmi mostů, problém čtyř barev zůstal nevyřešený po více než 100 let! A právě snahy o jeho vyřešení se zapříčinily o rozvoj mnoha oblastí teorie grafů. Problém čtyř barev byl původně formulován pro politické mapy států: Výrobci map chtěli státy barevně odlišit, aby každé dva sousední měli různé barvy. Přitom chtěli mapy tisknout co nejlevněji, tedy s nejmenším možným počtem barev. Není problém nakreslit čtyři státy tak, že každý s každým sousedí, a proto 4 barvy jsou někdy potřebné. Pro větší příklad se podívejme na následující obarvenou "mapu": Tiskařská praxe brzy ukázala, že 4 barvy vždy stačí, ale matematici si dlouho lámali hlavy s tím, proč tomu tak je... Zde si ukážeme, jak uvedený problém souvisí s grafy a hlavně s pojmy rovinného kreslení a barevnosti grafů. Uvedeme se (a zčásti odvodíme) základní vlastnosti rovinných grafů a grafové barevnosti. Cíle Prvním cílem této lekce je definovat barevnost grafů a naučit se s ní pracovat. Druhým cílem je definovat rovinné grafy a přehledově ukázat jejich vlastnosti, především ve vztahu k jejich barevnosti a ke geometrii. 10.1 Barevnost grafu Nejprve si formálně definujme pojem barevnosti - představme si, že hrany grafu nám říkají, že jejich koncové vrcholy musí být barevně odlišené (třeba proto, že reprezentují sousední státy, nebo proto, že jinak jsou si příliš podobné, atd). Samozřejmě bychom mohli každému vrcholu grafu dát jinou barvu, ale k čemu by pak takový problém byl? My bychom chtěli použít barev celkem co nejméně. Definice: Obarvením grafu G pomocí k barev myslíme libovolné zobrazení c:V(G)^{l,2,...,k} takové, že každé dva vrcholy spojené hranou dostanou různé barvy, tj. c(u) ^ c(v) pro všechny {u,v} G E (G). Definice 10.1. Barevnost grafu G je nejmenší přirozené číslo x(G) pro které existuje obarvení grafu G pomocí x(G) barev. Čísla 1,2,...,k z předchozí definice tak nazýváme barvami vrcholů (je to pohodlnější, než popisovat barvy běžnými jmény jako bílá, červená, atd). Poznámka: Uvědomme si, že barevnost lze definovat pouze pro graf bez smyček, protože oba konce smyčky mají vždy stejnou barvu a nic s tím nenaděláme. 83 Příklad 10.2. Určete barevnost grafu O Na první pohled je vidět, že potřebujeme aspoň 3 barvy, neboť graf má trojici navzájem spojených vrcholů (trojúhelník). Na druhý pohled pak zjistíme, že levý a pravý vrchol spojené hranou nejsou, a proto jim lze přiřadit stejnou barvu (a další dvě barvy vrchnímu a spodnímu vrcholu). Proto má graf barevnost 3. D V obecnosti lze o barevnosti grafů říci následující. Lema 10.3. Nechť G je jednoduchý graf (bez smyček) na n vrcholech. Pak x(G) 3 vrcholech má nejvýše 3v — 6 hran. Jednoduchý rovinný graf na v > 3 vrcholech a bez trojúhelníků má nejvýše 2v — 4 hran. Důkaz: Můžeme předpokládat, že graf je souvislý, jinak bychom přidali další hrany. Nechť počet vrcholů v G je v, stěn je / a hran h. Jelikož nemáme smyčky ani násobné hrany, má každá stěna v nakreslení grafu na obvodu aspoň 3 hrany, přitom každou hranu započítáme ve dvou přilehlých stěnách. Pak tedy platí e > \ ■ 3f, neboli |e > /. Dosazením do vztahu Věty 10.7 získáme 2 1 2 = v + f — e < v + -e — e = v — -e ó ó e<3(t>-2) =3t>-6. Druhá část se dokazuje obdobně, ale nyní víme, že graf nemá ani trojúhelníky, a tudíž má každá stěna v nakreslení grafu na obvodu aspoň 4 hrany. Pak tedy platí e > \ ■ 4/, neboli f e > /. Dosazením do vztahu Věty 10.7 získáme 2 1 2 = v + f — e 3• 5 — 6 hran. Podobně graf K33 má 6 vrcholů a 9 > 2-6 — 4 hran, přitom neobsahuje žádné trojúhelníky. Proto podle Důsledku 10.8 žádný z nich není rovinný. (Pokud by byl rovinný, počet jeho hran by musel být menší, než skutečně je.) D Důsledek 10.11. Grafy K$ a Ks^ nejsou rovinné. Význam grafů K$ a Ks^ uvedených v předchozím důsledku spočívá v tom, že jsou to "nejmenší" nerovinné grafy ve velmi silném významu slova nejmenší - každý další nerovinný graf jeden z nich "obsahuje". Pro uvedení takového popisu rovinných grafů ještě potřebujeme jednu definici. Definice: Podrozdělením grafu G rozumíme graf, který vznikne z G rozdělením některých hran novými vrcholy stupně 2. Důležitý abstraktní popis všech rovinných grafů nalezl K.Kuratowski: Věta 10.12. Graf G je rovinný právě když neobsahuje podrozdělem grafů K^ nebo K%ß jako podgrafy. Poznámka o rozpoznání nerovinnosti grafu: Pokud chceme ukázat, že daný graf je rovinný, prostě jej nakreslíme v rovině bez křížení hran. Předchozí věta nám naopak dává spolehlivý způsob, jak ukázat, že daný graf není rovinný - prostě v něm najdeme podrozdělení grafů K 5 nebo K33. (Ve skutečnosti tuto obtížnou větu ani nepotřebujeme ke zdůvodnění nerovinnosti, stačí nám Důsledek 10.11. Věta 10.12 nám jen říká, že příslušná podrozdělení vždy v nerovinných grafech najdeme.) Pro praktické použití věty dodáme, že až na vzácné výjimky se lépe v nerovinných grafech najde podrozdělení grafu K33 než grafu K5. Příklad 10.13. Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholů), nebo zdůvodněte nerovinnost grafu. Po chvíli zkoumání určitě přijdeme na to, že graf A se dá nakreslit rovinně takto: ' W. .A. Graf B na druhou stranu rovinný není podle Věty 10.12, protože je v něm obsaženo podrozdělení grafu K33, které je ukázáno na tomto obrázku: D Závěrem si ještě bez důkazu uvedeme, že rovinné grafy vždy mají "pěkné" nakreslení v rovině. Věta 10.14. Každý jednoduchý rovinný graf lze nakreslit v rovině (bez křížení hran) tak, že hrany jsou úsečky. Úlohy k řešení (10.3.1) Pro která n je úplný graf Kn rovinný? (10.3.2) Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholů), nebo zdůvodněte nerovinnost grafů. ,¥ (10.3.3) Kolik hran stačí přidat ke kružnici, aby vznikl nerovinný graf? 89 10.4 Barvení map a rovinných grafů Komentář: Vzpomeňme si na již zmiňovaný převod mapy na graf - jedná se vlastně o vytvoření duálního grafu k této mapě (strana 86). Aby v duálním grafu k mapě nevznikly smyčky, v mapě nesmí žádný stát sousedit sám se sebou, což je přirozený požadavek. V roce 1976 Appel a Haken, a pak v roce 1993 znovu Robertson, Seymour, Sanders a Thomas, dokázali tuto větu, která rozřešila problém čtyř barev a která je jedním z nejslavnějších výsledků diskrétní matematiky vůbec: Věta 10.15. Každý rovinný graf bez smyček lze obarvit 4 barvami. Důkaz této věty je nesmírně složitý (však byl také hledán po více než 100 let a k jeho úplnému provedení je stále třeba výkonný počítač), a proto si uvedeme slabší a mnohem jednodušší tvrzení: Tvrzení 10.16. Každý rovinný graf bez smyček lze obarvit 6 barvami. Každý rovinný graf bez smyček a bez trojúhelníků lze obarvit 4 barvami. Důkaz: Postupujeme indukcí dle počtu vrcholů grafu G. Podle Důsledku 10.9 najdeme vrchol v v G stupně nejvýše 5. Podle indukčního předpokladu lze menší graf G—v obarvit 6 barvami. Z nich jen nejvýše 5 je sousedy vrcholu v a tudíž šestou barvou můžeme v dobarvit. Druhou část dokážeme obdobně, když vezmeme vrchol stupně < 3 v G. □ Rozšiřující studium Problematika rovinného kreslení grafů a jejich barvení je pokryta v [ , Kapitola 5]. Zájemce o jednoduchý popis algoritmu na rovinné kreslení odkazujeme na [ ']. Zájemci o podrobný popis historie problému čtyř barev zase mohou mnoho zajímavých informací nalézt na Internetu. 10.5 Cvičení: Příklady na barevnost a rovinnost grafů Příklad 10.17. Uľčete a zdůvodněte barevnost tohoto grafu: Vidíme, že obvodová kružnice tohoto grafu má délku 5, což je liché číslo, a proto je potřeba na její korektní obarvení použít aspoň tři barvy 1,2,3. Pak je ale středový vrchol spojený s každou z těchto barev 1,2,3, tudíž pro něj potřebujeme čtvrtou barvu 4. 'ú: To znamená, že daný graf má barevnost 4. □ 90 Příklad 10.18. Kolik nejméně hran musíte vypustit z úplného grafu na 7 vrcholech, aby se výsledný graf dal korektně obarvit dvěma barvami? Musíme vypustit všechny hrany mezi vrcholy, kterým chceme dát stejnou barvu, aby výsledné obarvení bylo korektní. Jelikož všechny vrcholy úplného grafu jsou si ekvivalentní, stačí se rozhodnout, kolik z nich dostane barvu 1 a kolik barvu 2. Jak snadno zjistíme, optimální je barvy rozdělit napůl, tj. 3 a 4 v tomto případě. Je tedy potřeba vypustit nejméně (jj) + (g) = 3 + 6 = 9 hran. 2 1 D Příklad 10.19. Kolik nejméně hran je třeba vypustit z následujícího 8-vrcholového grafu, aby vznikl rovinný graf? Zdůvodněte. Nejprve se podíváme, zda náš graf náhodou není rovinný. To ale není, protože zde vidíme v něm obsažené podrozdělení Ks^: Tento obrázek zároveň ukazuje ještě jednu zajímavost - náš graf nebude rovinný, ani když vypustíme libovolnou z "tětiv" obvodové kružnice. Na druhou stranu není těžké objevit, že stačí vypustit třeba pravou svislou hranu a získáme rovinné nakreslení: Stačí tedy vypustit jednu hranu a získáme rovinný graf. □ Úlohy k řešení (10.5.1) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. (10.5.2) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. 91 (10.5.3) Obarvěte následující graf na 8 vrcholech třemi barvami 1,2,3 tak, aby se barva 3 použila co nejvíce krát. (10.5.4) Obarvěte následující graf na 9 vrcholech třemi barvami 1,2,3 tak, aby se barva 3 použila co nejméně krát. * (10.5.5) Jaká může být barevnost grafů, který vznikne z úplného grafu na 15 vrcholech vypuštěním tří hran? (Je to jednoznačné?) (10.5.6) Je tento graf rovinný? (10.5.7) Je ůenůo graf rovinný? (10.5.8) Kolik nejvýše hran lze přidat do následujícího grafu na 8 vrcholech, aby ještě zůstal rovinný a jednoduchý? (10.5.9) Kolik nejvýše hran lze přidat do následujícího grafu na 9 vrcholech, aby ještě zůstal rovinný a jednoduchý? (10.5.10) Nakreslete libovolný rovinný graf s 18 hranami a 10 stěnami. Kolik má takový graf vrcholů ? 92 11 Toky v sítích Úvod Závěrem se podíváme ještě na jednu oblast úloh, kde našla teorie grafů bohaté uplatnění, konkrétně orientované grafy. Jde o oblast tzv. "síťových" úloh: Pojem síť používáme jako souhrnné pojmenování pro matematické modely situací, ve kterých přepravujeme nějakou substanci (hmotnou či nehmotnou) po předem daných přepravních cestách, které navíc mají omezenou kapacitu. Jedná se třeba o potrubní sítě přepravující vodu nebo plyn, o dopravní síť silnic s přepravou zboží, nebo třeba o internet přenášející data. Obvykle nás zajímá problém přenést z daného „zdroje" do daného cíle čili „stoku" co nejvíce této substance, za omezujících podmínek kapacit jednotlivých přepravních cest (případně i jejich uzlů). Obrázkem můžeme vyjádřit síť s danými kapacitami přepravy jako: Problém maximálního toku v síti je snadno algoritmicky řešitelný, jak si také popíšeme. Jeho řešení má (kupodivu) i mnoho teoretických důsledků, třeba pro souvislost či párování v grafech. Cíle Úkolem této lekce je teoreticky popsat problém toku v síti a vysvětlit základní algoritmus nenasycených cest pro jeho řešení. Dále jsou uvedeny některé důsledky vysvětlené látky (pro rozšířené sítě, pro bipartitní párování a výběr reprezentantů množin). 11.1 Definice sítě Základní strukturou pro reprezentaci sítí je orientovaný graf. Vrcholy grafu modelují jednotlivé uzly sítě a hrany jejich spojnice. Vzpomeňme si (strana 48), že v orientovaných grafech je každá hrana tvořena uspořádanou dvojicí (u, v) vrcholů grafu, a tudíž taková hrana má směr z vrcholu u do v. Definice 11.1. Sí£ je čtveřice S = (G,z,s,w), kde - G je orientovaný graf, - vrcholy z G V (G), s G V (G) jsou zdroj a stok, - w : E(G) —>■ R+ je kladné ohodnocení hran, zvané kapacita hran. Komentář: Na obrázku je zakreslena síť s vyznačeným zdrojem z a stokem s, jejíž kapacity hran jsou zapsány čísly u hran. Šipky udávají směr hran, tedy směr proudění uvažované substance po spojnicích. (Pokud směr proudění není důležitý, vedeme mezi vrcholy dvojici opačně orientovaných hran se stejnou kapacitou.) Kapacity hran pak omezují maximální množství přenášené substance. 93 Poznámka: V praxi může být zdrojů a stoků více, ale v definici stačí pouze jeden zdroj a stok, z něhož / do nějž vedou hrany do ostatních zdrojů / stoků. (Dokonce pak různé zdroje a stoky mohou mít své kapacity.) Obvykle nás na síti nejvíce zajímá, kolik nejvíce substance můžeme (různými cestami) přenést ze zdroje do stoku. Pro to musíme definovat pojem toku, což je formální popis okamžitého stavu přenášení v síti. Značení: Pro jednoduchost píšeme ve výrazech znak e —> v pro hranu e přicházející do vrcholu v a e <— v pro hranu e vycházející z v. Definice 11.2. Tok v síti S = (G, z, s, w) je funkce / : E(G) —>■ Rj splňující - Ve G E (G) : 0 < /(e) < w{e), -VveV(G),v^z,s: E /(e)= E /(e). Velikost toku f je dána výrazem E /(e) - E /(e) Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve formátu F/C, kde F je hodnota toku na hraně a C je její kapacita. Komentář: Neformálně tok znamená, kolik substance je každou hranou zrovna přenášeno (ve směru této hrany, proto hrany musí být orientované). Tok je pochopitelně nezáporný a dosahuje nejvýše dané kapacity hrany. Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5. Poznámka: Obdobně se dá velikost toku definovat u stoku, neboť 0 = £(/(e) - /(e)) = £ £ fie) - £ £ fie) = £ (£ Ke) - £ /(e)) . e v e<—v v e—>v v=z,s \e<—v e—>v / (Dvojité sumy uprostřed předchozího vztahu nabývají stejných hodnot pro všechny vrcholy kromě zas dle definice toku.) Proto velikost toku počítaná u zdroje je rovna opačné velikosti toku počítaného u stoku Í£/(e)-£/(e)) = -(£/(e)-£/(e))- \e<—z e—>z / \e<—s e—>s / 94 11.2 Hledání maximálního toku Naším úkolem je najít co největší tok v dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy. Problém 11.3. O maximálním toku v síti Je dána stí S = (G, z, s, w) a našim úkolem je pro ni najít co největší tok ze zdroje z do stoku s vzhledem k ohodnocení w. Formálně hledáme max||/|| dle Definice 11.2. Komentář: Tok velikosti 5 uvedený v ukázce v předchozí části nebyl optimální, neboť v té síti najdeme i tok velikosti 6: Jak však poznáme, že větší tok již v dané síti neexistuje? V této konkrétní ukázce to není obtížné, vidíme totiž, že obě dvě hrany přicházející do stoku mají součet kapacit 2 + 4 + 6, takže více než 6 do stoku ani přitéct nemůže. V obecnosti lze použít obdobnou úvahu, kdy najdeme podmnožinu hran, které nelze tokem "obejít" a které v součtu kapacit dají velikost našeho toku. Existuje však taková množina hran vždy? Odpověď nám dá následující dehnice a věta. Definice 11.4. Řez v síti S = (G, z, s, w) je podmnožina hran C C E (G) taková, že v podgrafu G — C (tj. po odebrání hran C z G) nezbude žádná orientovaná cesta ze z do s. Velikostí fezu C rozumíme součet kapacit hran z C, tj. ||C|| = J2eecw(e)- Věta 11.5. Maximální velikost toku v síti je rovna minimální velikosti řezu. Komentář: Na následujícím obrázku vidíme trochu jinou síť s ukázkou netriviálního minimálního řezu velikosti 5, naznačeného svislou čárkovanou čarou. Všimněte si dobře, že dehnice řezu mluví o přerušení všech orientovaných cest ze z do s, takže do řezu stačí započítat hrany jdoucí přes svislou čáru od z do s, ale ne hranu jdoucí zpět. Proto je velikost vyznačeného řezu 1 + 4 = 5. Poznámka: Tato věta poskytuje tzv. dobrou charakterizaci problému maximálního toku: Když už nalezneme maximální tok, tak je pro nás vždy snadné dokázat, že lepší tok není, nalezením příslušného řezu o stejné velikosti. Přitom toto zdůvodnění řezem můžeme směle ukázat i někomu, kdo se vůbec nevyzná v matematice. Důkaz Věty 11.5 bude proveden následujícím algoritmem. 95 Definice: Mějme síť S1 a v ní tok /. Nenasycená cesta (v S vzhledem k /) je neorientovaná cesta v G z vrcholu u do vrcholu v (obvykle ze z do s), tj. posloupnost navazujících hran ei,e2, • • •, em, kde /(e») < w(ei) pro e» ve směru z n do f a /(e») > 0 pro e» v opačném směru. Hodnotě w(ei) — /(e») pro hrany e» ve směru z n do f a hodnotě /(e») pro hrany ei v opačném směru říkáme rezerva kapacity hran e». Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran. Komentář: Zde vidíme příklad nenasycené cesty ze zdroje do stoku s minimální rezervou kapacity +1. ^ 3/j ^ Vg r^ lJl r\ JV3 r\ 2lj r\ rezerva kapacity: +1 +1 +1 +2 +2 Všimněte si dobře, že cesta není orientovaná, takže hrany na ní jsou v obou směrech. Algoritmus 11.6. Ford-Fulkersonův pro tok v síti vstup síť S = (G, z, s, w); tok f = 0; do { prohledáváním grafu najdeme množinu U vrcholů G, do kterých se dostaneme ze z po nenasycených cestách; if ( s e U ) { P = (výše nalezená) nenasycená cesta v S ze z do s; zvětšíme tok f o minimálni rezervu kapacity hran v P; } while ( s eU ); výstup vypíšeme maximálni tok f; výstup vypíšeme min. řez jako množinu hran vedoucích z U do V (G) — U. Důkaz správnosti Algoritmu 11.6: Pro každý tok / a každý řez C v síti S platí ||/|| < ||C||. Jestliže po zastavení algoritmu s tokem / nalezneme v síti S řez o stejné velikosti ||C|| = ||/||, je jasné, že jsme našli maximálni možný tok v síti S. Zároveň tím dokážeme i platnost Věty 11.5. Takže stačí dokázat, že po zastavení algoritmu nastane rovnost ||/|| = ||C||, kde C je vypsaný řez mezi U a zbytkem grafu G. Vezměme tok f v S bez nenasycené cesty ze z do s. Pak množina U z algoritmu neobsahuje s. Schematicky vypadá situace takto: /(e) we /(e) 0 Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e <— U (odcházející z U) plný tok /(e) = w(e) a každá hrana e —> U (přicházející do U) tok /(e) = 0. Velikost toku / ze z do s se také dá psát jako = E /(e) - E /(e) = E /(e) = E w(e) = e^U e^U e^U eSC To je přesně, co jsme chtěli dokázat o výsledném toku. Z popisu Algoritmu 11.6 vyplývá ještě jeden důležitý důsledek: \C\ D 96 Důsledek 11.7. Pokud jsou kapacity hran sítě S celočíselné, optimální tok také vyjde celočíselně. Poznámka: Algoritmus pro celá čísla kapacit vždy skončí. Pro reálná čísla se ale dají najít extrémní případy, které nepovedou k řešení ani v limitě. Pro rychlý běh algoritmu je vhodné hledat nejkratší nenasycenou cestu, tj. prohledáváním sítě do šířky. V takové implementaci algoritmus dobře a rychle funguje i s reálnými kapacitami hran. Úlohy k řešení (11.2.1) Jaký je maximální tok touto sítí ze z do s? (11.2.2) Co obsahuje výsledná množina U Algoritmu 11.6 v předchozím příkladě? (11.2.3) Kde je minimální řez v této síti mezi zas? 11.3 Zobecnění sítí a další aplikace Pojmy sítě a toků v ní lze zobecnit v několika směrech. My si zde stručně uvedeme tři možnosti: 1. U sítě můžeme zadat i kapacity vrcholů. To znamená, že žádným vrcholem nemůže celkem protéct více než povolené množství substance. Takovou síť "zdvojením" vrcholů snadno převedeme na běžnou síť, ve které kapacity původních vrcholů budou uvedeny u nových hran spojujících zdvojené vrcholy. Viz neformální schéma: 2. Pro hrany sítě lze zadat také minimální kapacity, tedy dolní meze toku. (Například u potrubní sítě mohou minimální vyžadované průtoky vody garantovat, že nedojde k zanesení potrubí.) V této modifikaci úlohy již přípustný tok nemusí vůbec existovat. Takto zobecněná úloha je také snadno řešitelná, ale my se jí nebudeme zabývat. 97 3. V síti lze najednou přepravovat více substancí. To vede na problém tzv. vícekomo-ditních toků v síti. Tento problém je složitější a už není v obecnosti snadno řešitelný, a proto se jím nebudeme zabývat. Kromě uvedených (a podobných) zobecnění toků v sítích jsou velmi zajímavé i některé speciální formulace problému toků, které se vyskytují v možná i nečekaných oblastech. Více o tom napíšeme v dalších částech tohoto oddílu. Bipartitní párování V Lekci 10 jsme definovali biparitní grafy jako ty, které lze korektně obarvit dvěma barvami. Jinými slovy to jsou grafy, jejichž vrcholy lze rozdělit do dvou množin tak, že všechny hrany vedou mezi těmito množinami. Definice: Párování v (biparitním) grafu G je podmnožina hran M C E (G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol. Komentář: Pojem (bipartitního) párování má přirozenou motivaci v mezilidských vztazích. Pokud neuvažujeme bigamii ani jisté menšiny, můžeme si partnerské vztahy představit jako párování v bipartitním grafu. Jednu stranu grafu tvoří muži a druhou ženy. Hrana mezi mužem a ženou znamená vzájemné sympatie (přitom jedinec může mít vzájemné sympatie s několika jinými opačného pohlaví). Pak skutečné partnerské vztahy představují párování v popsaném grafu. Úlohu nalézt v daném bipartitním grafu co největší párování lze poměrně snadno vyřešit pomocí toků ve vhodně definované síti. Uvedená metoda použití toků v síti na řešení problému párování přitom hezky ilustruje obecný přístup, jakým toky v sítích pomohou řešit i úlohy, které na první pohled se sítěmi nemají nic společného. Metoda 11.8. Nalezení bipartitního párování Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme sít S následovně: Všechny hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. Nyní najdeme (celočíselný) maximální tok v S Algoritmem 11.6. Do párování vložíme ty hrany grafu G, které mají nenulový tok. Důkaz správnosti Metody 11.8: Podle Důsledku 11.7 bude maximální tok celočíselný, a proto každou hranou poteče buď 0 nebo 1. Jelikož však do každého vrcholu v A může ze zdroje přitéct jen tok 1, bude z každého vrcholu A vybrána do párování nejvýše jedna hrana. Stejně tak odvodíme, že z každého vrcholu B bude vybrána nejvýše jedna hrana, a proto vybraná množina skutečně bude párováním. Zároveň to bude největší možné párování, protože z každého párování lze naopak vytvořit tok příslušné velikosti a větší než nalezený tok v S neexistuje. □ Poznámka: Popsaná metoda je základem tzv. Maďarského algoritmu pro párování v bipartitních grafech. Úlohu nalezení maximálního párování lze definovat i pro obecné grafy a také ji efektivně algoritmicky vyřešit, ale příslušný algoritmus není jednoduchý. 98 Vyšší grafová souvislost Představme si, že na libovolném grafu G definujeme zobecněnou síť tak, že kapacity všech hran a všech vrcholů položíme rovny 1 v obou směrech. Pak celočíselný tok (viz Důsledek 11.7) velikosti k mezi dvěma vrcholy u,v se skládá ze soustavy k disjunktních cest (mimo společné koncové vrcholy u,v). Naopak řez odděluje n a f do různých souvislých komponent zbylého grafu. Aplikace Věty 11.5 na tuto situaci přímo poskytne následující tvrzení. Lema 11.9. Nechť u, v jsou dva vrcholy grafu G a k > 0 je přirozené číslo. Pak mezi vrcholy u a v existuje v G aspoň k disjunktních cest, právě když po odebrání libovolných k — l vrcholů různých odu,v z G zůstanou u a v ve stejné komponentě souvislosti zbylého grafu. Použitím tohoto tvrzení pro všechny dvojice vrcholů grafu snadno dokážeme dříve uvedenou důležitou Větu 7.5 (Mengerovu). Ještě jiné použití si ukážeme na problému výběru reprezentantů množin. Definice: Nechť Mi, M2,..., M& jsou neprázdné množiny. Systémem různých reprezentantů množin Mi, M2, ■ ■ ■, Mj, nazýváme takovou posloupnost různých prvků (xi,X2,--. ,Xk), že Xi e Mi pro i = 1,2,... ,k. Důležitým a dobře známým výsledkem v této oblasti je Hallova věta plně popisující, kdy lze systém různých reprezentantů daných množin nalézt. Věta 11.10. Nechť Mi, M2, ■ ■ ■, Mj~ jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí VJC {1,2,..., A;} : IU^ 'j&J >\J\, neboli pokud sjednocení libovolné skupiny z těchto množin má alespoň tolik prvků, kolik množin je sjednoceno. Důkaz: Označme Xi, X2, ■ ■ ■, xm po řadě všechny prvky ve sjednocení Mi U M2 U ... U Mfe. Definujeme si bipartitní graf G na množině vrcholů {1,2,..., k}U{xi,X2, ■ ■ ■ ,xm}U {u,v}, ve kterém jsou hrany {u,i} pro i = 1, 2,..., k, hrany {v,Xj} pro j = 1,2,... ,m a hrany {i,Xj} pro všechny dvojice i,j, pro které x j G M». Komentář: Konstrukce našeho grafu G je obdobná konstrukci sítě v Metodě 11.8: Vrcholy u a v odpovídají zdroji a stoku, ostatní hrany přicházející do vrcholu x j znázorňují všechny z daných množin, které obsahují prvek Xj. Cesta mezi u a v má tvar u,i,Xj,v, a tudíž ukazuje na reprezentanta Xj G M». Systém různých reprezentantů tak odpovídá k disjunktním cestám mezi u a v. Nechť X je nyní libovolná minimální množina vrcholů v G, neobsahující samotné u a v, po jejímž odebrání z grafu nezbude žádná cesta mezi u a v. Podle Lematu 11.9 a této úvahy mají naše množiny systém různých reprezentantů, právě když každá taková oddělující množina X má aspoň k prvků. Položme J = {1,2,... ,k}\ X. Pak každá hrana z J (mimo u) vede do vrcholů z X n {xi,..., xm} (aby nevznikla cesta mezi u,v), a proto I I Mj \xn{xí,..., xm}\ = \x\-\xn{i,..., k}\ = \x\-k + \J\. Vidíme tedy, že \X\ > k pro všechny (minimální) volby oddělující X, právě když \Ji£j Mj > \J\ pro všechny volby J, cot, je dokazovaná podmínka naší věty. □ 99 Poznámka: Předchozí důkaz nám také dává návod, jak systém různých reprezentantů pro dané množiny nalézt - stačí použít Algoritmus 11.6 na vhodně odvozenou síť. Úlohy k řešení (11.3.1) Najděte největší párování v tomto bipartitním grafu: (11.3.2) Najděte největší párování v tomto bipartitním grafu: (11.3.3) Mají všechny tříprvkové podmnožiny množiny {1,2,3,4} systém různých reprezentantů? (11.3.4) Mají všechny tříprvkové podmnožiny množiny {1,2,3,4, 5} systém různých reprezentantů? Rozšiřující studium Problematika toků v sítích je běžnou součástí teorie grafů (i když není pokryta v [5]) a je možno najít její obsáhlejší popis třeba v [ ] nebo v [7]. IIA Cvičení: Příklady toků v sítích Příklad 11.11. Jaký je maximální tok touto sítí ze z do s? Na tomto příkladě si ukážeme průběh Algoritmu 11.6. Začneme s nulovým tokem a najdeme nejkratší z nenasycených cest mezi zas (vedoucí spodem grafu a vyznačenou na prvním obrázku). Minimální rezerva kapacity na této cestě je 2, takže tok nasytíme o 2 podél této cesty (viz obrázek vpravo). 100 V dalším kroku najdeme nenasycenou cestu délky 3 vedoucí vrchem grafu. Její minimální rezerva kapacity je opět 2, takže ji o tolik nasytíme (viz další obrázek vlevo). Nyní již nenasycená cesta délky 3 neexistuje, takže najdeme nenasycenou cestu délky 4 s rezervou kapacity 1, kterou hned nasytíme (viz obrázek vpravo). Obdobně ještě najdeme nenasycenou cestu délky 5, kterou také nasytíme o 1. Závěrečný obrázek nám ukazuje všechny nenasycené hrany, mezi kterými již nevede žádná nenasycená cesta ze z do s, takže máme maximální tok velikosti 6 v naší síti. Zároveň je na posledním obrázku vyznačen i příslušný minimální řez velikosti 6. □ Úlohy k řešení (11.4.1) Najděte maximální tok v následující síti. (Kapacity hran jsou vyznačeny u svých šipek.) Tok do obrázku zapište, vyznačte hrany příslušného minimálního řezu a napište velikost toku. o (11.4.2) Najděte maximální tok v následující síti. 101 (11.4.3) Najděte maximální tok v následující síti. (11.4.4) Najděte maximální tok v následující síti. (11.4.5) Má tento seznam množin systém různých reprezentantů? Pokud ano, vyznačte je v množinách, jinak správně zdůvodněte, proč systém různých reprezentantů nemají. {1,2,3,4}, {6,7,8,9}, {3,5,7}, {3,4,5,6}, {1,2,8,9}, {3,6,7}, {4,5,6,7}, {4,5,6}, {4,6,7}. (11.4.6) Má tento seznam množin systém různých reprezentantů? Pokud ano, vyznačte je v množinách, jinak správně zdůvodněte, proč systém různých reprezentantů nemají. {1,2,3,4}, {6,7,8,9}, {1,3,9}, {3,4,5,6}, {1,2,3,9}, {2,4,9}, {4,5,6,7}, {2,3,4}, {3,4,9}. 102 Část III Klíč k řešení úloh (1.1.1) 91 (1.1.2) 990 (1.1.3) 3 (1.1.4) -4 (1.1.5) 4 (1.1.6) -3 (1.1.7) 16 (1.1.8) 12 (1.1.9)* [x + 0.5\ (1.2.1) n(6n-l)(6n-2) (1.2.2) 720, permutace (1.2.3) 210, kombinace (1.2.4) 420, variace (1.2.5) Nezávislé dva výběry, takže 49 • 49. (1.2.6)* Nyní místo původních dvou dvojic x, y a y, x máme jen jednu bez pořadí. Výsledek však není prostě polovinou 49 • 49/2, neboť dvojici stejných čísel x,x dělit nemůžeme. Správně je C(49, 2) + 49 = 1225 za neuspořádané dvojice různých čísel plus 49 dvojic stejných čísel. (1.2.7)* Nezávislými výběry kombinací (3) • (2). (1.3.1) Permutace s opakováním 3x A, 2x N, výsledek 3360. (1.3.2) p (1.3.3) Kombinace s opakováním C*(3,7) = 36. (1.3.4)* Kombinace s opakováním C*(4,6) = 84. (1.3.5)* To už je jiná úloha než předchozí, neboť i ve výsledku stále rozeznáme první, druhou, atd. Pro první kuličku máme 4 možnosti, pro druhou nezávisle zase 4, pro třetí také ..., celkem 46 = 4096. (1.4.1) Možné součty jsou 3,4, ....,28, tedy 26 možností. (1.4.2) 10 (1.4.3) (4) • 3 - nejprve vybereme čtyři, co budou hrát, a pak je rozdělíme třemi způsoby na dvě dvojice proti sobě. (1.4.4) Nezávislé výběry pro uspořádání čtveřice králů, pak čtveřice dam, atd., celkem 4!8. (1.4.5)* C*(4 + 1,10), k 4 barvám je nutno přičíst 1 za zbylé bílé kuličky. (1.4.6)* C(£-n,n) (2.2.1) i (2-2-2) é = \ (2.2.3) 32 = g (2.3.1) Nejsou, například pokud jeden dostane pikové eso, druhý ho už dostat nemůže. (2.3.2) Ano, je. Ať na první padne cokoliv, druhá má stejnou šanci se trefit do stejného čísla. (2.3.3) 3. • gš = 3g (2.3.4) Tři nezávislé hody, (±)5 = ±. (2.3.5) Královský pokr může dostat 28 způsoby z (3g2) (neuspořádaných) rozdání, takže 28/ (3g2) pro jedno rozdání a [28/ (5 )] pro obě. (2.4.1) f (2.4.2) 7, pro součet nepotřebujeme nezávislost. Navíc kostky obvykle mají součet protějších stěn po 7. 103 ;2.4.3) \ -2+ \ -3 = 2.5 ;2.4.4)* i-l + i-2+|-3+^-4 + ... = 2 2.5.1) y^q, kombinace! ;2.5.2) £ ;2.5.3) £ ;2.5.4) i ;2.6.i) ^ '2 6 21 -^- = -2- z,.u.z,; 32 31 248 '2 6 31 ___-___ A.v.o) 32.31.30-29 2.6.4) (^)/26 - vybereme všechny posloupnosti výsledků se 3 hlavami a 3 orly, každá z nich má pravděpodobnost 1/26. ;2.6.5) Výsledky: a) ^, b) ^, c) §§, d) fjjL ;2.6.6)a)(C27) + Q)/(224), b)(l7.7)/(224). Í2.6.7) (258)/(352) = ü '9 R «1 I 1 + 1. 1 + 1. I = JĽ 2.6.9)* f + § + |L = ^=4.18 ;2.6.10)*S = 2.A + 3.(l-A-if.A)+4.i|.A 2.6.11)* Pokud na první kostce padne 1, nenastane součet s > 8, naopak pokud padne 6, nenastane součet s < 6. Proto jedině jev součtu B-j může být nezávislý na jevu Ak- Dosazením do definice nezávislosti ověříme, že skutečně Ak a B-j jsou nezávislé pro všechna k = 1,..., 6. 2.6.12)* ((15°)/210) , stačí, že v každé barvě budou póly přesně napůl. Í3.5.1) K1) 3.5.2)* (n+4) (Uvědomte si nejprve, že (™) = ("+1).) 3.6.1) Ano, posledních čtyřčíslí je 10000 a studentů kolem 17000. 3.6.2) Ano, (^ < 500. 3.7.1) Indukcí, nebo rozkladem n3 — n = (n — í)n(n + 1). 3.7.2) Pro n > 6, důkaz třeba indukcí podle n, nebo úpravou. 3.7.3) Indukcí podle n. 3.7.4)* Rozepsáním faktoriálu na součin a úpravou členů. ;3.7.5)* (n - 1)3™+1 + 3 + (2(n + 1) - 1)3™+1 = (n - 1)3™+* + (2n + 1)3™+* + 3 = n3™+2 + 3 4.1.1) 5 4.1.2) 10 4.1.3) 14 4.1.4)* Reflexivní a symetrická, ale není tranzitivní. 4.2.1) a) délky 4 b) nejmenší 1, největší není c) 6 4.2.2) 8 tříd (s minimy 1, ...,8), nejvíce je s minimem 1 - celkem (141). ;4.4.1) (1,4,6,2,5)(3) 4.4.2) 6-krát. 4.4.3)* (n-1)! 4.5.1) 25 4.5.2) 17 4.6.1) Reflexivní, antisymetrická, tranzitivní, tedy částečné uspořádání. Lineární není, protože dvě slova nemusí být porovnatelná. 4.6.2) Reflexivní, symetrická, tranzitivní, tedy ekvivalence. 4.6.3) a) je to ekvivalence, b) je reflexivní, symetrická, ale ne tranzitivní, c) je reflexivní, symetrická, ale ne tranzitivní, d) je to ekvivalence 4.6.4)* a) je to částečné uspořádání, b) není symetrická, antisymetrická ani tranzitivní, c) je tranzitivní, ale ne symetrická ani antisymetrická, d) je to částečné uspořádání 4.6.5)* Je to ekvivalence - přesně podle zbytkových tříd modulo 3. 104 4.6.6) čtyř: (1, 7)(2)(3)(4, 6,5) 4.6.7) (1)(2)(3)(4,5,6,7) 4.6.8) (1)(2,3)(4,7)(5)(6) 4.6.9) (1,6,8,2,4X3,5,7) 4.6.10) Až 9, když složením vznikne identická permutace. 4.6.11) 15 4.6.12) 8 4.6.13)* 5, musíte ručně pokrátit jmenovatele zlomku. 6.1.1) Kružnice délky 5. 6.1.2) Pro n = 1 a 2, cesty délky 0 a 1. 6.1.3) Pro n = 3, trojúhelník. 6.1.4) Pro m = n = 2, délky čtyři. 6.1.5) Pro m = 1 nebo n = 1 a druhé libovolné. 6.1.6) 9 6.1.7) Oba stejně 36 hran. 6.2.1) 34 6.2.2) Ano: 6.2.3) Ano, kružnice délky 6 a dvě kružnice délky 3 vedle sebe. 6.3.1) 3, více nelze, neboť na obvodě kružnice by se musely ob-jeden střídat. 6.3.2) 3 6.3.3) 7 6.3.4)* 5, dokážete ji vůbec najít? 6.3.5) Ano, na.příkla.d y \ y 1 ■ Tento graf obsahuje 4 trojúhelníky, kdežto původní graf jen 3. Mohli jste však sestrojit úplně jiný graf... 6.3.6) Jeden, jen kružnice délky 5. 6.6.1) Ano. 6.6.2) Ne. 6.6.3) Dva. 6.6.4) A: 23, B: 20, C: 22. 6.6.5) Snadno... 6.6.6) Isom. z pravého do levého grafu: spodní dva nahoru vpravo, pravé dva dolů vpravo, atd. 6.6.7) ... 6.6.8)* A ano, K33 a graf trojbokého hranolu. B ne, protože dva vrcholy stupně 3 musí být spojené s ostatníma a tím již získáme celý graf jednoznačně. 6.6.9)* B ~ C, A ~ D, u neisomorfních dvojic vždy jedna obsahuje kružnice délky 5 a druhá ne. 6.6.10) Nejdelší Cg v obou, nejdelší indukovaná Cq v A a jen C5 v B. 6.6.11)* ( 4 ) -3, neboť ( 4 ) způsoby vybereme čtveřici vrcholů pro ten podgraf a každé 4 vrcholy lze třemi způsoby propojit do kružnice. 6.6.12)* Je jich 10, 6 z nich vznikne různým přidáváním vrcholů stupně 2 na hrany úplného grafu K4 a 4 další jsou jiné. 6.6.13) ... 6.6.14) Vlevo 4, vpravo 3. 7.1.1) B 7.1.2) 4 7.3.1) Vrcholově n-souvislý. 105 (7.3.2) Najdeme 3 disjunktní cesty mezi x,y. Proto musíme vypustit 3 vrcholy. (7.3.3) 1 do kružnice. (7.4.1) Ne, má čtyři vrcholy lichého stupně. (7.4.2) Tři, dvě by teoreticky stačily na změnu všech stupňů na sudé, ale v tomto grafu jen dvě hrany prostě přidat nejdou. (7.5.1) Jednu. (7.5.2) 5, samé trojúhelníky. (7.5.3)* 6, samé úplné grafy K5. (7.5.4) Celkem 4. (7.5.5) Souvislý s 15 hranami (ke každému vrcholu 3 sousedé). (7.5.6) 18, stupně > 3, třeba jako šestiboký hranol. (7.5.7) a)28: K8+ K1+K1, b) 9: K3 + K3 + K3 + K1 (7.5.8)* Jen v A: graf K33 a graf C5 s jednou diagonálou. Pro B uvažte doplněk toho grafu - má stupně 2,1,1,1,1, což dá jednoznačný graf. (7.5.9)* Jen v A: cesta délky 4 a trojúhelník s hranou vedle. (7.5.10)* Jen B: úplný K4 s hranou vedle a dále K4 s "rozpojenou" hranou. Pro A jde sestrojit jen kružnice C5, protože na nesouvislý nemá dost hran. (7.5.11)* 3 (7.5.12)* Třeba úplný bipartitní K34. (7.5.13) Ano, ale jen otevřeným. (8.1.1) 1, ale jen 0 pro graf na jednom vrcholu. (8.1.2) 2 (8.1.3) 5 (8.1.4) 3, najdete příslušnou dvojici vrcholů? /O 1 2 1\ (8.2.1) Vyjde * J J \ . Vi 2 1 0/ (8.3.1) 5 (8.3.2) Jsou to vrcholy ve zbylých dvou cípech hvězdy, do každého dalšího vrcholu je z nich vzdálenost nejvýše 4. Lépe to nejde. (8.5.1) Vlevo 3 a vpravo 2. (8.5.2) Vlevo 3 a vpravo 5. (8.5.3) 3. Ten prostřední vrchol má vzdálenost < 2 do každého dalšího. Zbytek grafu je grafem krychle, kde největší vzdálenost 3 mají protilehlé dvojice vrcholů (ve smyslu geometrické krychle). Z těchto 4 dvojic má kratší spojení přes prostřední vrchol, takže zbývají 3 dvojice. (8.5.4) 2 - jedná se o graf krychle, tak přidáme dvě úhlopříčky na jednu stěnu-čtverec. Pak budou vzdálenosti < 2. Naopak jedna hrana nestačí, protože po přidání libovolné hrany e stále najdeme dva protilehlé vrcholy krychle, které hraně e nepatří, a tyto dva vrcholy zůstanou ve vzdálenosti 3. (8.5.5) 2 + 3 + 2 = 7 (8.5.6) 10. Vezmeme jeden vrchol v, ten má 3 sousedy a každý ze sousedů v má 2 další sousedy mimo v. To je dohromady 10 vrcholů a více jich už nemůže být, protože vzdálenosti jsou < 2 od v. Nakreslete si takový graf! (8.5.7)* 22, což je [45/2J, ohodnocení hran v pořadí 1,2,3,4,5, 7, 6,8, 9. (8.5.8)* Vzdálenost 14 mezi 7 a 5. (9.1.1) 3, jeden bez hran, jeden s jednou hranou a poslední strom s dvěma hranami. (9.1.2) 2, cesta P3 a "hvězda" K1>3. (9.1.3)* Nenajdete, to by bylo v rozporu s Důsledkem 9.5. 106 (9.2.1) (9.2.2) Centra jsou vyznačená: (9.2.3) Pokud centrum vyjde jeden vrchol, odebereme celkem 32 listů - za každou hranu jeden. Jinak odebereme jen 31 listů a jedna hrana zbude jako centrum. (9.3.1) ((()(()()()))((()())(()))) (9.3.2) (9.4.1) 2004 (9.4.2)* Je celkem 5!/2 = 60 koster, co jsou cestou P4, dále jen 5 koster, co jsou "hvězdou" K\^ a nakonec 5 • 4 • 3 = 60 koster, které mají vrchol stupně 3. (9.5.1) 3 (9.5.2) Ano, 2005 vrcholů podle Věty 9.3. (9.5.3) 2009 - 1 - 1 - 1 - 1 = 2005 (9.5.4) 11, počítejte hrany v každé komponentě - stromu. (9.5.5) Graf není souvislý, 13 není spojeno s ničím. Není ani lesem, neboť 10,14,21,15 tvoří kružnici. (9.5.6) Vlevo B, vpravo A. (9.5.7) 5 (9.5.8) 3 až 8 koster. Nejméně koster, 3, vznikne pokud nová hrana vytvoří trojúhelník. Nejvíce, 8, pokud strom byl cestou délky 7 a nová hrana ji uzavře do kružnice délky 8. (9.5.9) (™)-n+l (9.5.10)* 4. Pro 3 vrcholy by každá kostra musela mít 2 hrany, ale 2 + 2 = 4 hrany mezi třemi vrcholy nelze mít. Na druhou stranu úplný graf K4 má takové dvě kostry. (9.5.11)* 56. Obvodová kružnice má 8 koster, dalších 3 • 5 = 15 koster obsahuje vrchní příčku a 15 spodní příčku, nakonec 3 • 3 • 2 = 18 koster obsahuje obě příčky. (10.1.1) 3 (10.1.2) Méně než 4 barvy nestačí, protože najdeme úplný podgraf na 4 vrcholech. Obarvení 4 barvami je snadné. (10.1.3) 1 pokud má jeden vrchol a jinak 2 podle Věty 10.5 - stromy totiž nemají žádné kružnice. (10.1.4) 3 (10.1.5)* 102 barvami, postup je následovný: Odebereme jeden vrchol v, zbytek grafu rekurzivně obarvíme 102 barvami a v nejhorším případě dostanou sousedé vrcholu v 101 různých barev. Proto i v můžeme korektně dobarvit. (10.2.1) Je to graf krychle. (10.2.2) v = 12, / = 20, v + / - e = 2, tedy e = 12 + 20 - 2 = 30. (10.2.3) Graf pravidelného osmistěnu. 107 (10.2.4) 3 (10.3.1) Pro n= 1,2,3,4. (10.3.2) Rovinný jen B. (10.3.3) 3 - takto z kružnice délky 6 vytvoříme graf K33, nakreslete si to. (10.5.1) 3 (10.5.2) 4, všimněte si, že graf obsahuje K4. (10.5.3) 3 (10.5.4) 1 (10.5.5)* Buď 13, pokud vypustíme tři hrany jednoho trojúhelníku, nebo 12, pokud vypustíme tři disjunktní hrany. (10.5.6) Ano, stačí dolní levé dva vrcholy překreslit nahoru. (10.5.7) Ne, obsahuje podrozdělení K33, najdete jej? (10.5.8) 8 (10.5.9) 11 (10.5.10) Má 10 vrcholů podle Eulerova vztahu. (11.2.1) Tok 5. (11.2.2) Jen zdroj z. (11.2.3) Rez velikosti 4 zde: ti 5: I I.V. L (11.3.1) Velikosti i /:. 11. (11.3.2) Velikosti 4: (11.3.3) Ano, reprezentanti jsou zapsaní první: (1,2,3), (2,1,4), (3,1,4), (4,2,3). (11.3.4) Ne, všech podmnožin je (jj) = 10, ale prvků k reprezentaci jen 5. (11.4.1) 12 (11.4.2) 13 (11.4.3) 11 (11.4.4) 9 (11.4.5) Nemá - 6 z množin má sjednocení {3,4,5,6,7}, kde se najde jen 5 různých prvků pro reprezentanty. (11.4.6) Nemá - 6 z množin má sjednocení {1,2,3,4,9}, kde se najde jen 5 různých prvků pro reprezentanty. 108 Reference [1] P. Hliněný, Web stránky předmětu DIM (2004), http://www.es.vsb.cz/hlineny/vyuka/DIM.html. [2] D. Knuth, The Art of Computer Programming, Volumes 1-3, Addison-Wesley Pub Co, 2nd edition 1998. [3] L. Kučera, Kombinatorické Algoritmy, SNTL, Praha, 1983. [4] L. Kučera, Algovize, http://kam.mff.cuni.cz/~ludek/Algovision/Algovision.html. [5] J. Matoušek a J. Nešetřil, Kapitoly z Diskrétní Matematiky, Karolinum, UK Praha, 2000. [6] J. Matoušek and J. Nešetřil, Invitation to Discrete Mathematics, Oxford University Press, 1998. [7] E. Ochodková, Grafové Algoritmy, http://www.es.vsb.cz/ochodkova/courses/gra/. 109