Vysoká Škola Báňská - Technická Univerzita Ostrava Fakulta Elektrotechniky a Informatiky Diskrétní Matematika Doc. RNDr. Petr Hliněný, Ph.D. Text pro distanční a kombinované studium Diskrétní Matematika (456-533 DIM) Doc. RNDr. Petr Hliněný, Ph.D. petr.hlinenyOvsb.cz 23. února 2005 Verze 1.01. Copyright © 2004-2005 Petr Hliněný. Obsah 0.1 Předmluva................................. vi 0.2 Pokyny k distančnímu studiu ...................... viii I Základy Diskrétní Matematiky 1 1 Množiny a výběry prvků 2 1.1 Čísla, operace a množiny......................... 2 1.2 Výběry a seřazení prvků......................... 5 1.3 Výběry s opakováním........................... 8 1.4 Kombinatorické výběry........................ 12 2 Diskrétní pravděpodobnost 14 2.1 Motivační příklady............................ 14 2.2 Konečný pravděpodobnostní prostor................... 15 2.3 Nezávislost jevů.............................. 17 2.4 Střední hodnota.............................. 19 2.5 Náhodné výběry.............................. 21 2.6 Úlohy na pravděpodobnost ..................... 23 3 Důkazy v diskrétní matematice 26 3.1 Základní logické symboly......................... 27 3.2 Pojem matematického důkazu...................... 27 3.3 Princip matematické indukce....................... 29 3.4 Důkazy vzorců pro výběry........................ 30 3.5 Vztahy s kombinačními čísly....................... 31 3.6 Důkazy "počítáním" ........................... 33 3.7 Příklady matematických důkazů.................. 36 4 Relace a zobrazení 39 4.1 Pojem relace................................ 39 4.2 Uspořádání a ekvivalence......................... 41 4.3 Funkce, či zobrazení ........................... 44 4.4 Skládání zobrazení; Permutace...................... 45 4.5 Princip inkluze a exkluze......................... 47 4.6 Příklady na relace a jiné....................... 49 5 Algoritmizace diskrétních struktur 52 5.1 Programová implementace struktur................... 52 5.2 Implementace množin........................... 54 5.3 Generování výběrů............................ 55 5.4 Generátory náhodných čísel....................... 57 5.5 Kombinatorická "exploze" ........................ 58 ni II Úvod do Teorie Grafů 60 6 Pojem grafu 61 6.1 Definice grafu............................... 62 6.2 Stupně vrcholů v grafu.......................... 64 6.3 Podgrafy a Isomorfizmus......................... 65 6.4 Orientované grafy a multigrafy...................... 69 6.5 Implementace grafů............................ 70 6.6 Příklady o grafech a isomorfismu.................. 71 7 Souvislost grafu 75 7.1 Spojení vrcholů, komponenty ...................... 76 7.2 Prohledávání grafu............................ 77 7.3 Vyšší stupně souvislosti ......................... 79 7.4 Jedním tahem: Eulerovské grafy..................... 80 7.5 Příklady na souvislost grafů..................... 82 8 Vzdálenost a metrika 86 8.1 Vzdálenost v grafu............................ 87 8.2 Výpočet metriky............................. 88 8.3 Vážená (ohodnocená) vzdálenost..................... 89 8.4 Hledání nejkratší cesty.......................... 90 8.5 Příklady o grafových vzdálenostech................ 94 9 Stromy a les 98 9.1 Základní vlastnosti stromů........................ 99 9.2 Kořenové stromy............................. 101 9.3 Isomorfizmus stromů........................... 104 9.4 Kostry grafů................................ 106 9.5 Příklady o stromech, kostrách a hladovém postupu...... 111 10 Barevnost a kreslení grafů 117 10.1 Barevnost grafu.............................. 118 10.2 Rovinné kreslení grafu.......................... 121 10.3 Rozpoznání rovinných grafů....................... 124 10.4 Barvení map a rovinných grafů ..................... 126 10.5 Příklady na barevnost a rovinnost grafů............. 128 11 Toky v sítích 132 11.1 Definice sítě................................ 133 11.2 Hledání maximálního toku........................ 134 11.3 Zobecnění sítí a další aplikace...................... 137 11.4 Příklady toků v sítích......................... 142 III 145 IV Klíč k řešení úloh 146 Literatura....................................156 v 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 [6]. 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 VI 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 Kolovratovi a Pavlu Moravcovi. vn 0.2 Pokyny k distančnímu studiu Úvodem si shrneme několik užitečných rad a pokynů pro distanční studium předmětu. Jak již bylo zmíněno v předmluvě, 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. Každá lekce je uvedena následujícími pomocnými informacemi, které studujícímu poslouží ke snadné zběžné orientaci v obsahu i náročnosti studia. Čas ke studiu: xx h. Uveden je orientační čas potřebný k prostudování a pochopení látky. Přestože jsou lekce zhruba stejně rozsáhlé, jejich obsah je nestejně náročný na pochopení, což je (velmi hrubě) vyjádřeno právě tímto údajem. Průvodce studiem Uvádí neformální zběžný popis obsahu lekce i její motivace. Studující by se měl nejprve seznámit s jednotlivými průvodci studia, aby věděl a očekával, co jej v předmětu čeká (a nemine). Předpoklady ke studiu Zde jsou stručně shrnuty předpoklady, které by měl studující již ovládat pro úspěšné zvládnutí následující látky. Není zcela nutné studovat lekce po řadě, stačí, když jsou splněny vypsané předpoklady. Cíle Nakonec jsou popsány obecné cíle a předpokládané výsledky následujícího učiva. (Viz také shrnutí učiva na konci lekce.) Poté následuje samotný výklad látky, rozdělený tematicky na jednotlivé oddíly. Výklad je členěn obvyklým matematickým stylem na definice, tvrzení, případné důkazy, poznámky a neformální komentáře. Důležité body jsou číslovány v rámci lekcí a těmito čísly jsou pak dále v textu odkazovány. (Poznamenáváme, že v PDF verzi publikace fungují hypertextové odkazy.) Pro ukázku zde přinášíme: Definice 0.1. Pojem a jeho definice / popis... Věta 0.2. Významné matematické tvrzení... Leraa 0.3. Pomocné matematické tvrzení... Poznámka (formální) k vykládané látce. .. Komentář: Neformální komentování vykládané látky a příklady z praxe... Algoritmus 0.4. pro řešení problému X funguje následovně... Navíc je výklad proložen řadou vzorově řešených příkladů navazujících na vykládanou látku. Pro odlišení jsou vzorové příklady uváděny v textu takto: vin :ŕ\> Příklad 0.5. Zadání príkladu ------ a jeho řešení... □ Za každým oddílem jsou připojeny doplňkové otázky a úlohy určené pro ověření, jak studující zvládl přednesenou látku. (Otázky a úlohy označené hvězdičkou patří k obtížnějším a nevyžadujeme, že by na ně všichni studující bez pomoci dokázali odpovědět.) Správné odpovědi k otázkám a úlohám jsou sepsány na konci textu. ? Doplňkové otázky Otázky se zaměřují především na (možné) problematické body přednesené látky a svými odpověďmi na ně si studující ověřuje, zda skutečně látku (a především pojmy a definice) správně pochopil. Úlohy k řešení Zadané úlohy přímo navazují na předchozí text a vzorové příklady. Studující si jejich správným řešením především potvrzuje, že umí právě nabyté vědomosti skutečně používat. Celá lekce je zakončena shrnutím nejdůležitějších pojmů a konceptů, které by si studující měl dobře zapamatovat. Shrnutí Z uvedené látky si především vezměme: Pak následuje poslední oddíl každé lekce - cvičení, určený k dodatečnému procvičení látky. Obvykle jsou tam uvedeny příklady a úlohy, které předvádějí podanou látku v širším kontextu celé lekce. Pro snazší orientaci studujícího mají i cvičení uvedenou svou časovou náročnost, cíle a shrnutí (jako je popsáno výše). Jak studovat Na začátek čtenáři doporučujeme se zběžně seznámit s průvodci a časovou náročností jednotlivých lekcí tohoto textu a dobře si rozvrhnout studium na celý semestr podle svých schopností, současných znalostí a časových možností. (Mimo jiné by měl studující počítat s tím, že přinejmenším část látky bude potřebovat již při vypracovávání semestrálních referátů a písemné práce.) Není bezpodmínečně nutné dodržet pořadí jednotlivých lekcí, pokud studující splní vyznačené předpoklady studia. Některé obtížnější partie lekcí si tak třeba může ponechat na pozdější dobu a pokračovat zatím plynule ve studiu. Po prostudování látky každého oddílu a pochopení uvedených řešených příkladů by se čtenář měl zaměřit na doplňkové otázky a úlohy k řešení, které jsou jeho hlavní zpětnou vazbou při učení (a nahrazují tak běžná cvičení u denního studia). Studující by si měl u každé otázky či úlohy promyslet, ke které části výkladu se vztahuje a jak nabytých vědomostí využije při jejím řešení. Po vyřešení a své odpovědi si může její správnost zkontrolovat v seznamu správných odpovědí na konci výukového IX textu. V žádném případě nedoporučujeme se na správné odpovědi dívat dříve, než si studující promyslí vlastní řešení! Až čtenář zvládne látku celé lekce, čeká jej poslední oddíl - cvičení, který znovu přináší další vzorově řešené příklady na probíranou látku a nové úlohy k řešení. Jeho náplň by měla zhruba odpovídat normálnímu cvičení u denního studia. Nakonec by si studující měl přečíst shrnutí učiva každé lekce a cvičení a sám si odpovědět, zda vypsaná témata skutečně ovládá. Pokud ano, může se (po zaslouženém odpočinku) s uspokojením pustit do další lekce. Případné nejasnosti a dotazy, ke kterým čtenář přijde během studia našeho výukového textu, může buď posílat e-mailem svému tútorovi, nebo si je připravit na příští studijní setkání. Studující by však měli věnovat velkou pozornost formulaci svých dotazů, aby odpověď vůbec mohla být užitečná. Například na dotaz ve stylu "nerozumím oblasti XX, vysvětlete mi to" lze stěží odpovědět něco jiného, než "přečtěte si příslušný oddíl v textu". Správně formulovaný dotaz by měl mít formu "přečetl jsem si oddíly YY, pochopil jsem Z a T, ale u W mi není jasné toto" nebo "... řešení příkladu P mi vyšlo takto -jinak než v textu". Dobře formulované dotazy zároveň pomůžou tútorovi lépe připravit obsah příštího setkání i pro ostatní. Závěrem bychom rádi studujícím připomněli, že by se uvedenou látku v žádném případě neměli učit mechanicky nazpaměť. Byla by to jen zbytečná ztráta času, neboť takto nabyté "vědomosti" by jim vůbec nepomohly ani při skládání zkoušky, ani v dalším studiu a praxi. Spíše než přesná recitace zde uvedeného slovosledu je důležité pochopení principů přednášených definic, tvrzení a metod a jejich aplikací pro řešení úloh. Mnoho zdaru! x Část I Základy Diskrétní Matematiky Petr Hliněný: Diskrétní Matematika 2 Lekce 1 Množiny a výběry prvků ^ :/: Čas ke studiu lekce: 3 h. Průvodce studiem 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í. Předpoklady ke studiu JVa úvod kurzu předpokládáme pouze znalost základního středoškolského učiva o přirozených číslech a konečných množinách. Pojmy a symbolika jsou zopakovány v prvním oddíle. Cíle lekce 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álneho čísla a; je značena následovně: dolní [x\ a horní \x\. • Posloupnost, obvykle značená («»)£=! = («i, a2, • • •, 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 J2aí = al+a2 + ■■■ + a>n-l + (ín , i=\ nebo také obecněji J2 ca = «ň +öj2 + . • • + «»„, kde J = {i\, 12, ■ ■ ■, in} je jakákoliv íeJ množina indexů. • Součin posloupnosti n čísel je analogicky zapisován jako n || Cli = Ol ' Q>2 ' • • • ' Q>n-l ' an ■ í=l Komentář: Pro ukázku připojíme několik příkladů použití značení sum a součinů: 10 ^i = l + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9+10 = 55 í=i 5 [J(i + 1) =2-3-4-5-6 = 720 i=lj = l i=l v J=1 / ^=i / \J = 1 / Č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& píšeme a G M, b G M, ale d G" M. Počet prvků (mohutnosť) značíme \M\ =4. N = {a, b, x} je podmnožinou M, což píšeme jako N C M. 3 • Sjednocení množin značíme A U B, jejich průnik A D 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 Xi a průniku f] Xi je analogické jako u sumy. í=i í=i 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 A U B = {a, b, c, d, e, f} a průnikem je A n B = {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:ACX}. • Množinový systém nad X (což je vhodněji znějící název místo "množina množin") je jakákoliv podmnožina potenční množiny TC2X. • 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. Ax B = {(a,b) :aeA,beB}. • Kartézská mocnina je definována rekurzivně An = A x A x ... x A, n kde A1 = A a A° = {0}. Komentář: Podívejme se například na potenční množinu dvouprvkové množiny {a, b}. Ta obsahuje prázdnou množinu, dvě jednoprvkové množiny s těmito prvky a celou dvouprvkovou množinu: 2W>} = {0, {a}, {&}>,&}} 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,b} x {c, d} = {(a,c), (a,d), (b,c), (b, d)} 4 Počty prvků v kartézském součinu a v kartézské mocnině splňují \AxB\ = \A\-\B\, \An\ = \A\n. J Doplňkové otázky (1.1.1) Můžeme z prvků nějaké pětiprvkové množiny sestavit posloupnost délky 11 ľ (1.1.2) Která množina je podmnožinou každé množiny? (1.1.3) Připomeňte si známá pravidla pro počítání s množinami: a) A n (B U C) = ? b) AU {B n C) = _? c) AnB = ? (X značí doplněk množiny X) a) (A D B) U (A D C), b) {A U B) n {A U C), c) ÄU B. (1.1.4) Obsahuje potenční množina prázdné množiny nějaký prvek? (1.1.5) Proč je kartézský součin libovolné množiny s prázdnou množinou A x 0 roven prázdné množině 0 ? (1.1.6) Může pro některé dvě množiny zároveň platit A C B i A £ B? Úlohy k řešení 6 (1.1.7) Sečtěte sumu J2 i2- í=\ n (1.1.8) Vynásobte ]\ j. (1.1.9) Kolik je L3.3J? (1.1.10) Kolik je L-3.3J? (1.1.11) Kolik je [3.6] ? (1.1.12) Kolik je [-3.6] ? (1.1.13) Kolik prvků má potenční množina množiny {1, 2, 3,4}ľ (1.1.14) Kolik prvků je v kartézském součinu {1, 2, 3,4} x {5, 6, 7}? *(1.1.15) Jak vyjádříte klasické zaokrouhlení pomocí [\ ? 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í: 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). 5 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 A;-prvkových kombinací na n-prvkové množině je dán vzorcem C(n, k) k\-(n-k)\ ' 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 A;-prvkových variací na n-prvkové množině je dán vzorcem Ti' 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 Q) = klj™'_k)\ se Pro praktický výpočet kombinačního čísla vůbec nehodí, neboť funkce faktoriál 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 < f, jinak vezměme raději číslo (ra™fc) = (%)■ Pak si definiční vztah upravme: ín\ n\ n(n — 1)(n — 2)... (n — k + 1) Například k) k\-{n-k)\ k\ /l00\ 100 -99-98 \3 J 3-2 Pro výpočet variací používáme obdobnou úpravu 50 • 33 • 98 . 6 Ř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ýberu, 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) = 570. - Vybíráme-li z 15 hráčů (například minifotbalu) družstvo 3 + brankář, pak ale pod-vý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 (g) • 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í Nechť každý případ nějakého (složeného) výběru lze dále rozlišit (zjemnit) na stejný počet i zjemněných možností. Dále nechť 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. 7 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 V(15,11) = ±f|. Oba pohledy jsou však ekvivalentní, takže počty musí souhlasit: z-1.3! = V(15,ll) = ^! Po vydělení: 15! x = TITS! =5460 (Určitě není náhodou, že výsledek vyšel stejný, žel ? Doplňkové otázky (1.2.1) Proč 0! = 1 (a ne třeba 0)? (1.2.2) Proč je k-prvkových kombinací z n prvků stejně jako těch (n — k)-prvkových ? (1.2.3) Proč totéž jako v předchozí otázce nelze říci o variacích? (1.2.4) Představme si, ze táhneme za sebou náhodná čísla z osudí. Po každém jednotlivém tahu jsou dvě možnosti - tažené číslo buď odložit pryč, nebo jej vrátit do osudí. Pro kterou z těchto možností jsou dva po sobě jdoucí tahy nezávislé? Úlohy k řešení (1.2.5) Upravte na jednoduchý součin (6™). (1.2.6) Kolika způsoby seřadíme šestici studentů do řady? (1.2.7) Kolika způsoby vyberete neuspořádanou dvojici z 21 studentů? (1.2.8) Kolika způsoby vyberete uspořádanou dvojici z 21 studentů? (1.2.9) 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.10) 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.11) 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. 8 :ŕ\> Příklad 1.6. Kolika různými způsoby můžeme seřadit do posloupnosti písmena ''" I 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 Po vydělení: (3!)3 -(2!)3 -a; = 19!, 19! 19! (3!)3-(2!)3 3!-3!-3!-2!-2!-2!-l!-l!-l!-l! ■ 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 m^-krát pro i = 1,..., k, je (m-i + m2 + ■ ■ ■ + mk)\ m\\ ■ m = 1, mi = 3, ras = 1, tuk = 2, m# = 1, mg = 2, tut = 3, m« = 1, rriM = 2 a m a = 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 /c-krát a druhý (n — /c)-krát, dostáváme vztah pro jejich počet Jedná se tedy o tentýž počet jako /c-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. 9 Další zajímavý příklad uvádí tzv. kombinace s opakováním. :r\, Příklad 1.8. Kolika různými způsoby můžeme vybrat 6 kuliček ze tří barev, když '"' I 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 (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.) □ 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 A;-prvkových kombinací s opakováním z n možností je ^-("I-r1)- Vzorec pro kombinace s opakováním má mnoho šikovných a zajímavých aplikací. Pro ilustraci uvedeme následující příklady. O 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ů? Mějme součet k = X\ + 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, X2 jako počet modrých, atd. Takže součet si lze představit jako /c-prvkovou kombinaci s opakováním z n prvků, kde i-tý prvek se opakuje právě Xi krát. Proto je počet takových zápisů na součty dán už známým vztahem C*(n,k) = 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! □ 10 ^ Doplňkové otázky (1.3.1) Ptáme se, kolik různých pořadí může mít automobilová rallye, pokud nerozlišujeme mezi vozy téže značky. O jaký typ výběru se zde jedná? (1.3.2) Představme si, že máme bílé kuličky (od sebe nerozeznatelné) a chceme každou z nich nabarvit libovolnou z barev červená, modrá, zelená. O jaký typ výběru se zde jedná? * (1.3.3) Dovedete si představit ještě jiný typ kombinatorického výběru prvků s opakováním, který zde ještě nebyl uveden? Úlohy k řešení (1.3.4) Kolika různými způsoby seřadíme do posloupnosti písmena slova ANAKONDA? (1.3.5) 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.6) Kolika způsoby rozložíme číslo 7 na součet tří přirozených sčítanců? (Na jejich pořadí záleží.) *(1.3.7) 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.8) 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á.) y1 Shrnutí lekce Z uvedené látky si především vezměme: • Základní značení čísel a množin. • Deňnice a vzorce pro permutace, kombinace a variace, včetně těch s opakováním. • Princip nezávislých výběrů pro složené výběry. #f~\ 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ám 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á [ , Kapitola 6]. 11 Cvičení 1.4 Kombinatorické výběry Čas ke studiu cvičení: 1.5 h. Cíle cvičení Úkolem tohoto cvičení je čtenáři ukázat některé další úlohy kombinatorických výběrů, které nezapadnou přímo do schémat prezentovaných v Lekci 1, ale vyžadují i jiné úvahy. :ry«i 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 L C X. 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. □ -f_\» 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 í 4 j. Mezi nimi jsou i ty špatné výběry, které neobsahují žádného dobrého útočníka. Takových špatných výběrů je (1275) = (4), vybíráme totiž čtyři hráče z těch zbylých. Špatné 4 j V4, výběry od všech jednoduše odečteme, takže výsledek je D O 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 = xi + x2 + ■ ■ ■ + xn . To lze ekvivalentně zapsat jako k - n = (x i - 1) + (x2 - 1) + • • • + (xn - 1), 12 kde yi = Xi — 1 jsou přirozená čísla. Jinak řečeno, zapisujeme číslo A; —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 ™, i ^ fn+k-n-l\ (k-l\ c(n-*-»>=( „-i J = U-iJ- 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. Shrnutí cvičení Z uvedené látky si především vezměme: • Různé drobné triky používané při řešení úloh kombinatorických výběrů. 13 Petr Hliněný: Diskrétní Matematika 14 Lekce 2 Diskrétní pravděpodobnost ^ :/: Čas ke studiu lekce: 2.5 h. Průvodce studiem 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 fílozofícké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. 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. Předpoklady ke studiu V této lekci očekáváme dobrou znalost předchozí látky o kombinatorických výběrech prvků (tj. permutace, kombinace a variace). Také předpokládáme, že se čtenář již setkal s pojmem náhody, ale vůbec nevyžadujeme znalost teorie pravděpodobnosti a statistiky. Cíle lekce 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í |"). • 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 Í4^J = 85900584.1 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 (í), 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 splňuje -P(0) = O, P(í)) = l, - P (A U B) = P (A) + P (B) pro disjunktní A, B C Q. Jev je libovolná podmnožina ACfia 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 Q, neboli také příslušná jednoprvková podmnožina. Jev v obecnosti je jakákoliv podmnožina prostoru Q, tedy se skládá z několika elementárních jevů. 15 Definice: Jevy A, B jsou disjunktní, pokud nemohou nastat zároveň, tj. pokud A n 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 ít a pravděpodobnostmi elementárních jevů - prvků ít. Pro A = {a\,..., a&} C ft 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 Q přiřazena funkcí P(A) = \A\ / \Q\, 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 fl. 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í: ít = {0,1} a P(0) = P(l) = \. - Při hodu kostkou: ít = {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: ít 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: ít je tvořena všemi 7-prvkovými kombinacemi z 49 čísel a každá .7 > kombinace má pravděpodobnost l/(, N 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. O 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ě ít = {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(ll) = £ = i P(4) = P(10) = ± = ± P(5) = P(9) = 4 - l 36 — 12' [_ _ 1 36 9' 16 P(6)=P(8) = i, P(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ě. □ O 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 fl' = [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)}, S7 = {(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)}, Ss = {(2, 6), (3, 5), (4,4), (5, 3), (6, 2)}, 512 = {(6,6)}. Jelikož pravděpodobnost jedné dvojice hozených čísel, tj. jednoho elementárního jevu v ft', 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ší. □ ? Doplňkové otázky (2.2.1) Jsou různé elementární jevy vždy disjunktní? (2.2.2) Udejte příklad dvou různých jevů, které nejsou disjunktní. (2.2.3) Hoďme dvěma kostkami. Jsou jev padl součet 6 a jev padl součin 8 disjunktní? **(2.2.4) Může mít pravděpodobnostní prostor nad všemi přirozenými čísly (tedy nekonečná spočetná množina ft) uniformní pravděpodobnost? Jinými slovy lze uniformně vybrat náhodné přirozené číslo? *(2.2.5) Lze obdobně vybrat uniformně náhodné reálné číslo? Úlohy k řešení (2.2.6) Jaká je pravděpodobnost, že na kostce padne liché číslo? (2.2.7) Hoďme dvěma kostkami. Jaká je pravděpodobnost, že padne součin 12? (2.2.8) 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 17 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 n B) = P{A) ■ P (B). 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 P(AnB) _ P(B) P(A) - W) ■ Jelikož -P(íí) = 1, uvedený vztah je ekvivalentní definičnímu P(AnB) = 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 L^ ' se také říká podmíněná pravděpodobnost jevu B za předpokladu, že nastal jev A. Značí se P(B\A). :r\> Příklad 2.5. Hodíme dvěmi stejnými kostkami najednou. Jaká je pravděpodob-'"' I nost, ž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 \} obdobně je \} že na druhé padne 5. Obě možnosti najednou padnou s pravděpodobností po vynásobení \-\ = ■§§• 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 18 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 = ^ + ^ = -^ . □ ? Doplňkové otázky (2.3.1) Jsou dva různé elementární jevy nezávislé? (2.3.2) Je vůbec možné, aby dva disjunktní jevy byly nezávislé? (2.3.3) Je prázdný jev nezávislý s libovolným jiným jevem? *(2.3.4) Mějme tři jevy takové, ze každá dvojice z nich je nezávislá. Je pak celkově nezávislá i celá trojice? Úlohy k řešení (2.3.5) Ze zamíchaných karet rozdáme dvěma hráčům popěti kartách. Jsou výběry karet, které dostanou, nezávislé? (2.3.6) Hodíme dvěma stejnými kostkami. Je jev na obou padne stejné číslo nezávislý s jevem na první padne dvojka? (2.3.7) Jaká je pravděpodobnost, ze při současném hodu třemi stejnými kostkami padnou čísla 1, 3 a 5? (2.3.8) Jaká je pravděpodobnost, ze při pěti hodech mincí padne vždy hlava? (2.3.9) 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 G {hi, /i2, • • •, /ifc}, kde Xi nastává s pravděpodobností pÍ7 a p\ + p2 + • • • + Pk = 1-Střední hodnotou proměnné X je pak číslo EX = pí ■ hi + p2 ■ h2 + ... + Pk ■ hk . 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í. 19 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 = \{l + 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{KX + 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(Kľ ■ 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 X» £ {0,1}, i = 1,..., n příslušejících jednotlivým hodům mince. Celkový počet hlav je dán náhodnou proměnnou X = X\ + ... + Xn. Takže průměrný počet hlav je dle Věty 2.6 1 i r? EX = E(X, + ... + Xn) = EX, + ... + EXn = - + ... + - = - . To přesně odpovídá našemu vnímání pravděpodobnosti jako relativní četnosti jevu. □ O Příklad 2.9. Kolik je třeba průměrně hodů mincí, aby vyšly tři stejné výsledky? Je snadno vidět, že nejdříve tři stejné výsledky mohou nastat po třech hodech a nejpozději po pěti hodech (z dvou hlav a dvou orlů pět hodů nesložíme). S jakou pravděpodobností získáme stejné výsledky při třech hodech? Jsou možnosti buď tři hlav, nebo tří orlů, takže 1 1 Až po pěti hodech získáme 3 stejné výsledky, pokud první čtyři hody budou rozděleny dva na dva (na posledním hodu pak již vlastně nezáleží). To se může stát v (t,) = 6 možnostech pro 4 hody, takže pravděpodobnost je R l 3 í>5 = 6-16 = 8- Možnost, že 3 stejné výsledky získáme po čtyřech hodech je doplňková k předchozím dvěma a v součtu musí mít pravděpodobnost 1, proto 20 Průměrný počet potřebných hodů je dle definice střední hodnoty 3 3 15 33 N = p3 ■ 3 +Vi ■ 4 + í>5 • 5 = - + - + — = — = 4.125 . (To je o trochu více než 4, což by jeden mohl intuitivně očekávat.) □ O Příklad 2.10. (varovný) Jaký je průměrný součin čísel horní a spodní stěny stejné kostky při hodech? Jak už víme, střední hodnota čísla na horní stěně je 3.5 a dolní stěně samozřejmě taky 3.5. Střední hodnota jejich součinu však není 3.5 • 3.5 = 12.25, protože tyto dva jevy nejsou nezávislé. Místo toho střední hodnotu součinu spočítáme podle definice -(l-6 + 2-5 + 3-4 + 4-3 + 5-2 + 6-l) = --56 = 9 + -. b b ó Proto si dávejme dobrý pozor na nezávislost jevů při násobení středních hodnot! □ Úlohy k řešení (2.4.1) Jaká je střední hodnota počtu šestek padlých při hodu 10 šestistěnných kostek? (2.4.2) Jaký je průměrný součet čísel horní a spodní stěny stejné kostky při hodech? (2.4.3) Kolik je třeba průměrně hodů mincí, aby vyšly dva stejné výsledky? * (2.4.4) Kolik je třeba průměrně hodů mincí, aby padla první hlava? Návod: Uvědomte si, že teoreticky hlava nemusí padnout nikdy, ale pravděpodobnost samých orlů jde k nule. 2.5 Náhodné výběry V závěrečném oddíle stručně shrneme nejčastěji se objevující typy konečných uniformních náhodných výběrů v diskrétní matematice: Náhodná podmnožina. Z dané n-prvkové množiny vybíráme libovolnou z 2n jejích podmnožin, každou s pravděpodobností 2~n. Náhodná permutace. Ze všech n! permutací dané n-prvkové množiny vybíráme libovolnou jednu s pravděpodobností 1/n!. Náhodná kombinace. Ze všech í™j A;-prvkových kombinací dané n-prvkové množiny vybíráme libovolnou jednu s pravděpodobností l/u)- Náhodná posloupnost bitů. Toto je poněkud jiný druh výběru - vybíráme libovolně dlouhou posloupnost z 0 a 1 tak, že každý další bit je vybírán s pravděpodobností \ zcela nezávisle na všech předchozích bitech. (Tj. každá vybraná podposloupnost této náhodné posloupnosti musí mít stejnou šanci se objevit.) 21 Poznámka: Kolem problému určit, nakolik náhodná je určitá posloupnost bitů, je vystavěna rozsáhlá matematická teorie, ale problém stále není vyřešený k plnému uspokojení (je to "velká věda"). M Úlohy k řešení (2.5.1) Jakou pravděpodobnost má náhodná 7-prvková podmnožina 10-prvkové množiny? (2.5.2) Jakou pravděpodobnost má náhodná permutace 4 prvků? (2.5.3) Jaká je pravděpodobnost, že náhodná podmnožina 5-prvkové množiny má jeden prvek? (2.5.4) Jaká je pravděpodobnost, že náhodná posloupnost tří bitů vyjde '011'? Shrnutí lekce Z uvedené látky si především vezměme: • Pravděpodobnostní prostor a jevy v něm. • Nezávislost jevů. • Střední hodnota a její použití. Rozšiřující studium Zájemce o hlubší studium pravděpodobnosti jako takové odkazujeme na klasické učebnice statistiky, kterými se zde nezabýváme. Pro rozšíření znalostí o specifícké oblasti kombinatorické pravděpodobnosti doporučujeme [o, Kapitola 9], která se mimo jiné široce věnuje i použití tzv. pravděpodobnostních důkazů. Pokud čtenáře zajímají základy použití kombinatorické pravděpodobnosti v algoritmech, odkazujeme jej nejprve na [3]. 22 Cvičení 2.6 Úlohy na pravděpodobnost i?\ Čas ke studiu cvičení: 2.5 h. Cíle cvičení V tomto cvičení čtenáři předkládáme další příklady a úlohy diskrétní pravděpodobnosti, které kombinují přístupy prezentované v Lekci 2 a vyžadují i další úvahy. O Příklad 2.11. Představme si, že hodíme dvěma poctivýma kostkama -jednou 8-stěnnou a druhou 12-stěnnou. Jaká je pravděpodobnost, že na obou padne stejné číslo? Na menší kostce může padnout vlastně cokoliv. Pak máme šanci ^, že se hod větší kostky trefí zrovna do toho samého čísla. Výsledek tedy je 1 12 ' D $y\, Příklad 2.12. Jaká je pravděpodobnost, že první i poslední karta v náhodně * zamíchaném balíčku klasických 32 karet budou srdce? Jelikož nás vůbec nezajímá pořadí karet mimo první a poslední, počítáme s 32-31 elementárními jevy určenými volbou první karty a následně volbou poslední karty různé od první. Z toho jev obě budou srdce má 8 • 7 možností - volba prvního srdce je libovolná z osmi, druhé srdce musí být voleno ze zbylých sedmi srdcí. Výsledek tedy při uniformní pravděpodobnosti je 8-7 7 32-31 ~ 124 ' $~\, Příklad 2.13. Hodíme najednou dvěma šestistěnnýma kostkama. Jaká je * pravděpodobnost, že menší z obou čísel bude 3 ? Hody obou kostek jsou nezávislé, ale my si (jako v Příkladě 2.5) musíme dát pozor, na které kostce padne 3 jako menší z obou čísel. Nechť kostky jsou třeba červená a zelená. Úloha se nám rozpadá na tři disjunktní možnosti - na červené padne menší číslo, nebo na zelené padne menší, nebo na obou padne stejně. Vezměme třeba první možnost, kde pravděpodobnost 3 na červené kostce je | a pravděpodobnost čísla většího než 3 na zelené kostce je \. Tyto jevy jsou nezávislé. Obdobná úvaha platí pro další dvě možnosti, takže sečtením vyjde 111111 7 p =---------1-----------1--------= — . 622666 36 D 23 :t\, Příklad 2.14. Představme si, ze házíme dvěma odlišenýma šestistěnnýma ——-I kostkama. Pro každý hod vynásobíme číslo první kostky součtem obou čísel. Jaká je střední hodnota výsledku ? Bohužel se nejedná o nezávislé jevy, takže nelze přímo aplikovat Větu 2.7. Označme K a K' náhodné veličiny udávající čísla padlá na našich kostkách. Úkolem tedy je spočítat střední hodnotu E(K ■ (K + K')) . Dle definice můžeme rozepsat tuto střední hodnotu na celkem 36 sčítanců. My však lépe můžeme náhodnou veličinu roznásobit a použít Větu 2.6, která nevyžaduje nezávislost: E(K-(K + K')) = E [K2 + K ■ K') = E (K2) + E (K ■ K') Nyní již dle Věty 2.7 vypočteme E (K ■ K') = E{K) ■ E(K') = í a dle definice spočteme 1 91 E{K2) = - • (1 + 4 + 9 + 16 + 25 + 36) = — 6 6 Celkový výsledek je 49 91 E(K.(K + K')) = ^ + ^. D Úlohy k řešení (2.6.1) Představme si, že hodíme najednou dvěma kostkama -jednou 10-stěnnou a druhou 6-stěnnou. Jaká je pravděpodobnost, že na obou padne stejné číslo? (2.6.2) Jaká je pravděpodobnost, že první i poslední karta v náhodně zamíchaném balíčku klasických 32 karet budou esa? (2.6.3) Jaká je pravděpodobnost, že první čtyři karty v náhodně zamíchaném balíčku klasických 32 karet budou esa? (2.6.4) Jaká je pravděpodobnost, že při 6 hodech mincí vyjdou výsledky hlava/orel přesně napůl? (2.6.5) Zamícháme náhodně 32 klasických karet (A barvy po 8 kartách) a vytáhneme první 2 z nich. Jaká je pravděpodobnost, že to a) budou obě esa, b) budou král a dáma (v tomto pořadí), c) nebude žádné eso, d) budou obě stejné hodnoty (různé barvy) ? Návod: Nemusíte uvažovat všech 32! permutací, stačí brát jen všechny možné výběry na první a druhou kartu. 24 (2.6.6) Ve třídě je 17 studentů a 7 studentek. Z nich vybereme uniformně náhodně jednu neuspořádanou dvojici. Jaká je pravděpodobnost, že vybraná dvojice je a) stejného pohlaví, b) různého pohlaví? (2.6.7) Jaká je pravděpodobnost, že po zamíchání balíčku 32 karet nebude mezi prvními pěti kartami žádné eso? Návod: Přestože úloha muví o zamíchání karet, uvědomte si, že není třeba se ohlížet na jejich pořadí. (2.6.8) Hodíme najednou dvěma šestistěnnýma kostkama. Jaká je pravděpodobnost, že větší z obou čísel bude 3 ? *(2.6.9) Jaká je střední hodnota počtu políček, o které se vaše figurka v kole přesune ve hře "Člověče, nezlob se", pokud se po třetí šestce za sebou již znovu nehází? (Uvažujeme hody šestistěnnou kostkou, znovu házíme jen padne-li na kostce 6, až tři hody za sebou. Součet hodů určuje počet políček.) *(2.6.10) V šuplíku máme volně rozházených po 6 ponožkách od každé z barev žlutá, modrá, zelená. Kolik jednotlivých ponožek průměrně musíme poslepu vytáhnout, abychom dostali jednobarevný pár? Formálně se jedná o výpočet střední hodnoty počtu vytažených ponožek. Ponožky jsou stejné až na barvu, není ani rozlišení mezi levou a pravou. Návod: Nejdříve získáme jednobarevný pár po vytažení dvou ponožek, nejpozději po vytažení čtyř. Pak stačí spočítat pravděpodobnosti jednotlivých vytažení a udělat vážený průměr podle definice. *(2.6.11) Hoďme dvěma kostkama. Nechť A^ je jev "na první kostce padlo k a Bs je jev "na obou padl součet s". Pro jaká k, s jsou jevy Aj,, Bs nezávislé? Návod: Fyzický postup výběru jevů Aj, a Bs zajisté nezávislý není, neboť hod první kostky ovlivní i součet obou. Přesto za jistých podmínek lze nezávislost ověřit dle definice. Pokuste se o to. *(2.6.12) Jak jistě víte, každý magnet má dva opačné póly které se přitahují. Barevné dětské magnetky mají na sobě umělohmotnou čepičku překrývající celou jejich stranu, takže jen druhá strana, tj. jeden z jejich pólů, je dostupná k přitáhnutí. Tyto magnetky jsou balené po 40 kusů, 10 od každé ze čtyř barev. Předpokládejme, že nezakryté póly těchto magnetků jsou zvoleny náhodně s pravděpodobností \. Jaká je pak pravděpodobnost, že těchto 40 magnetků lze pospojovat do 5 x 4 stejnobarevných dvojic (že každá dvojice se navzájem přitahuje opačnými nezakrytými póly) ? Návod: Kolik asi musí být magnetků od každého nezakrytého pólu v každé barvě? Shrnutí cvičení Z uvedené látky si především vezměme: • Jak správně zvolit pravděpodobnostní prostor. • Jak skládat pravděpodobnosti dílčích výběrů. • Jak prakticky poznat nezávislé jevy. 25 Petr Hliněný: Diskrétní Matematika 26 Lekce 3 Důkazy v diskrétní matematice sr. :/: Čas ke studiu lekce: 3.5 h. Průvodce studiem Jednou z hlavních deviz matematiky je její exaktnost, tedy její schopnost jednoznačně (mimo jakoukoliv pochybnost) dokazovat svá tvrzení. Koncept matematického důkazu má za sebou dlouhý historický vývoj již od dob Euklida a jeho axiomů geometrie, přes Bolzanovy práce formalizující moderní koncept důkazu, až po bouřlivý rozvoj matematické logiky v počátcích 20. století po objevení Russelova paradoxu. V moderním pohledu je matematický důkaz nahlížen jako posloupnost ověřitelných elementárních kroků vedoucích od známých a předpokládaných faktů k požadovanému tvrzení. Když se nad tímto konceptem hlouběji zamyslíme, vidíme, že pokud se chceme někam dostat, nemůžeme začínat "z ničeho". Proto, jak si uvědomil v dávných dobách již zmíněný Euklides, každá matematická teorie potřebuje své základní předpoklady, zvané "axiomy". V diskrétní matematice jsou tyto základní předpoklady tvořeny axiomy tzv. Pe-anovy aritmetiky, což je vlastně vznešený název pro dobře známá základní fakta o přirozených číslech, doplněná principem matematické indukce. Schopnost podat exaktní matematický důkaz svých tvrzení je však důležitá i mimo oblast matematiky samotné. Například při návrhu kritických informačních systémů, na jejichž správné funkci závisí lidské životy, je více než žádoucí podat skutečný důkaz jejich správné funkce ve všech případech, ne jen v testovacích simulacích. Důkazové metody diskrétní matematiky, obzvláště princip matematické indukce, jsou v těchto situacích vhodné a dobře použitelné. Předpoklady ke studiu Předpokládáme především znalosti o přirozených číslech a množinách shrnuté v Lekci 1. Dále je třeba znát kombinační čísla. Cíle lekce Obecným cílem je ukázat čtenáři principy, na kterých staví exaktní matematické důkazy, a naučit jej předkládané důkazy správně chápat. Tyto znalosti a schopnosti budou (mlčky) předpokládány pro celý zbytek studijního textu. (To však neznamená, že by se studenti měli učit uvedené důkazy nazpaměť, byla by to naprosto zbytečná ztráta času! Jde o pochopení principů.) U studentů, kteří aspirují na nejlepší známku, očekáváme i schopnost formulovat vlastní důkazy běžných (a nepříliš složitých) tvrzení. 3.1 Základní logické symboly Pro začátek si zopakujeme základní logické pojmy a symboly, které byste již měli znát z předchozího studia. Úvodní opakování z matematické logiky... • Logické hodnoty jsou 1/0, neboli True/False (Pravda/Nepravda). • Logické spojky jsou ^X (NOT), X A Y (AND), X V F (OR). • Implikace X =>- 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: — \/x : P(x) znamená, že P(x) je pravdivé pro všechny volby proměnné x (z dohodnuté či vyznačené množiny u\/x G M"). — 3x : P (x) znamená, že P (x) je pravdivé pro aspoň jednu volbu proměnné x (z dohodnuté či vyznačené množiny "žb G 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 b je 1 (True) právě když a, b mají různé logické hodnoty, což je přesně negací ekvivalence, tj. a XOR b = ^{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 odvozo-vacích pravidel, 27 a kde poslední krok obsahuje jako výrok závěr tvrzeni 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. Pro ilustraci konceptu matematického důkazu jsme zvolili dobře známý fakt z algebry. :r\, Příklad 3.1. Dokažme v libovolném algebraickém (polo)okruhu pravidlo "agresi-'"' I vity 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,6, c: a + c = 6 + c=>a = 6 (2) Va,6, c: a • (6 +c) = a • 6 +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 ir-0 = ir-0 + ir-0. - Dosazením a = x ■ 0 do (1) dále vyjde i£-0 = 0 + ir-0 = i£-0 + ir-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ů.) □ 28 ? Doplňkové otázky (3.2.1) Co je špatného na následujícím "důkaze"? Ukážeme, že platí 2 = —2: Umocněním na druhou vzejde 22 = 4 = (—2)2, což je platná rovnost, a proto i původní vztah 2 = —2 je platný. (3.2.2) Co je špatného na následujícím "důkaze"? Nechť a, b jsou celá čísla. Vyjdeme z předpokladu a = b a ukážeme, že a = —b. (Tj. po dosazení a = b = 2 opět vyjde 2 = —2.) Umocněním výchozího předpokladu a = b získáme a2 = b2, neboli 0 = a2 — b2 = (a + 6) (a — b). Dle výsledku Příkladu 3.1 je pak iO-(a-b) = 0 = (a + b) (a — b) a dále po zkrácení 0 = a + b, tedy a = —b. 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(n0) je pravdivé, kde n0 = 0 či 1, nebo i pro obecné celén0-(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 > n0. 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. Věta 3.3. Každán-prvková množina máprávě2n podmnožin (včetněprázdné). Formálně 2X\ = 2^. Důkaz matematickou indukcí podle n: • Pro n = 0 tvrzení platí, neboť prázdná množina má jedinou podmnožinu, opět prázdnou. 29 • Nechť nyní tvrzení platí pro n > 0. Vezmeme libovolnou množinu X o n + 1 > 0 prvcích. Zvolme prvek a £ 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+1 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 B \A\ \B\ 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. f Doplňkové otázky (3.3.1) Jak byste formulovali důkaz Věty 3.4 matematickou indukcí? Použijte postup analogický důkazu Věty 3.3. (3.3.2) Kde je chyba v následujícím "důkaze"? Indukcí podle n dokážeme, že každých n čísel je sobě rovných, tj. x i = X2 = ... = xn. Pro n = 1 tvrzení jasně platí x\ = x\. Nechť tedy tvrzení platí pro obecné n a podívejme se nan+ 1 čísel x\, X2, ■ ■ ■, xn, xn+\. Dle indukčního předpokladu je x\ = X2 = • • • = xn, ale stejně tak i X2 = ■ ■ ■ = xn = xn+\. Z toho už tranzitivitou odvodíme X\ = X2 = • • • = xn = xn+\. 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 n\, 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 E 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. □ 30 Věta 3.6. Počet všech k-prvkových variací z n-prvkové množiny je r^, 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 A;-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)\ různých způsobů. Z různých variací tímto 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 A;-prvkových variací z n-prvkové množiny, lze výše popsaným postupem vytvořit právě x • (n — k)\ všech různých permutací n-prvkové množiny. Proto platí x ■ (n — k)\ = n!, n! x (n - k)\ ' D Věta 3.7. Počet všech k-prvkových kombinací z n-prvkové množiny je (?h pro každé n>k>0. Důkaz metodou dvojího počítání: Nyní budeme dvojím způsobem počítat všechny A;-prvkové variace z n-prvkové množiny. Na jednu stranu už víme, že jich je r^|, na druhou stranu můžeme z jedné k-prvkové kombinace vygenerovat celkem k\ různých variací uspořádáním prvků této kombinace. Označíme-li tedy x neznámý počet všech A;-prvkových kombinací z n-prvkové množiny, dostaneme obdobně jako v předchozím důkaze n! x ■ k\ (n-ky.1 n\ k\-(n-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í ín\ ín\ = 1. 31 Fakt. Pro všechna n > k > 0 platí \k) = \n-k)' Leraa 3.8. Pro všechna n > k > 0 platí ín\ í n \ ín+ l\ \k) + \k+l) = [k+l)' Důkaz: (n\ í n \ n\ n\ \k) \k+lj k\-(n-k)\ (k + 1)! • (n - k - 1)! n! • (k+ l) + n! • (n- k)___n!-(n+l) _/^+!N (fc+l)!-(n-fc)! (k + 1)\ ■ (n - k)\ ~ U + 1. D Tyto tři uvedené fakty mohou také posloužit jaJco dennice kombinačních čísel. (Viz. Pascalův trojúhelník.) Pascalův trojúhelník 0 - - 0- G)- 0- 0- 0- S- 0- ö- ©- e)- o- o- o- cd- s- o- a- o- o- a- 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. 32 Věta 3.9. Tzv. binomická věta říká pro všechna n > O (i+*v-(g+(g..+(g^+...+(B:1)-^+(3^. 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 n xk vyjde tolikrát, kolik je možností (neuspořádaně) vybrat k z n činitelů-závorek. To jest právě u) krát. □ Důsledek 3.10. Z binomické věty plyne (pro přirozená n > 0 a druhé pro n > 0) (ô)+C)+6)+C)+-+(--i)+(")-'- ? Doplňkové otázky (3.5.1) Jak byste zdůvodnili platnost Lema 3.8 úvahou o výběrech prvků? (3.5.2) Jak byste zdůvodnili platnost Věty 3.3 pomocí binomické věty? *(3.5.3) Jak byste zdůvodnili platnost Lema 3.8 pomocí binomické věty? Úlohy k řešení (3.5.4) Upravte následující výraz na jediné kombinační číslo: [n-lj + [n + 2j *(3.5.5) Upravte následující výraz na jediné kombinační číslo: ín\ (n + í\ (n + 2\ (n + r\ 0 + 1 H 2 + 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: 33 Metoda 3.11. Dirichletův princip Rozmístíme-li £+ 1 (nebo více) objektů do £ přihrádek, v některé přihrádce musí být aspoň dva objekty. :r\\ Příklad 3.12. Mezi čtyřmi přirozenými čísly vždy najdeme dvě, jejichž rozdíl je '"s I 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. □ 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. O Příklad 3.13. Na 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í. □ O 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 < (o) = 28, jedna dvojice nám zde schází. □ Ú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? Shrnutí lekce Z uvedené látky si především vezměme: 34 • Co je matematické tvrzení a důkaz. • Princip matematické indukce a jeho použití. • Pascalův trojúhelník a základní vzorce s kombinačními čísly. • Dirichletův princip. 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. 35 Cvičení 3.7 Příklady matematických důkazů Čas ke studiu cvičení: 1.5 h. Cíle cvičení V tomto cvičení předvedeme několik krátkých ukázkových důkazů matematických tvrzení. Příklady jsou určeny především pro rozšiřující studium pro studenty aspirující na lepší známky. Příklad 3.15. Dokažme indukcí podle k, že číslo (2 — 1) je dělitelné sedmi. O • 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 (26k — 1) při zvětšení k o jedna: 26(fe+i) _ A _ í26k - l) = 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 (26k — 1) bylo dělitelné sedmi podle indukčního předpokladu, bude sedmi dělitelné i 26(fc+!) - 1. Formálně tento indukční krok zapíšeme následovně: Nechť dle indukčního předpokladu 26k — 1 = 71, kde i je nějaké přirozené číslo. Pak 26(fe+i) _ i] = 26 • 26fc - 1 = (26 - 1) • 26k + 26k - 1 = 63 • 26k + 7£ = = 7 ■ (9 • 26k + í) takže i tento výraz je dělitelný sedmi. D O Příklad 3.16. Dokažme následující identitu s kombinačními čísly: 6H3M3v-H-i),+(»y-(») Představme si 2n-prvkovou množinu A = [l,2n], rozloženou na dvě disjunktní podmnožiny B = [1, 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í 36 • Na druhou stranu si představme, že vybereme A;-prvkovou podmnožinu B' C B a A;-prvkovou podmnožinu C C C, pro libovolné k G [0, n]. Vytvoříme pak množinu K = B' U (C \ C). To lze podle principu nezávislých výběrů udělat právě u) způsoby. • 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é D fc=o O Příklad 3.17. Mějme 30 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 10 a 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 — 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 Q) < (™) ? Dokažte, že pak už uvedená nerovnost je stále platná. (3.7.3) Dokažte vztah: + ...+ 37 N(3.7.4) Dokažte nerovnosti: 'n+ 1 n n/2 < n! < *(3.7.5) Dokažte platnost následujícího vztahu pro všechna přirozená n > 1: n 53(2i - 1) • 3* = (n - 1) • 3ra+1 + 3 í=i 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. Shrnutí cvičení Z uvedené látky si především vezměme: • Jak dokazovat tvrzení indukcí nebo úvahou a počítáním. • Jak si vybrat správnou důkazovou metodu. 38 Petr Hliněný: Diskrétní Matematika 39 Lekce 4 Relace a zobrazení ^ Čas ke studiu lekce: 3 h. Průvodce studiem 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í. Předpoklady ke studiu Opět předpokládáme především znalosti o množinách a přirozených číslech shrnuté v Lekci 1. Dále je třeba chápat prezentované matematické důkazy, viz Lekce 3. Cíle lekce 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) :aeA,beB}. Definice 4.1. Relace R na množině A je libovolná podmnožina kartézského součinu A x A = A2, tj. R d A2. Takto definovaná relace se také rozšířeně nazývá binárni relace. Píšeme buď (x, y) E R, nebo zkráceně xRy (třeba x = y, x < y). Komentář: Jak již název napovídá, relace se využívají k popisu vztahů mezi prvky množiny (objekty). Dobře si uvědomme, že dvojice prvků buď v relaci je nebo není, třetí možnost není přípustná. Binární relace mluví o uspořádaných dvojicích prvků. V obecnosti se však může relace týkat i n-tic prvků, jak ukazuje další definice. Definice 4.2. n-ární relace S na množině A je libovolná podmnožina kartézské mocniny An, tj. S- (y, x) G R pro všechna x, y G A, • antisymetrická pokud z (x, y), (y, x) E R vyplývá x = y pro všechna x, y G A, • tranzitivní pokud z (x, y), (y, z) E R vyplývá (x, z) E R pro všechna x, y, z E A. Komentář: Praktické příklady relací: — Relace rovnosti = je reflexivní, symetrická, tranzitivní i antisymetrická. Relace menší < je antisymetrická a tranzitivní, < je navíc reflexivní. Relace | dělitelnosti je také reflexivní, antisymetrická a tranzitivní. — Pro příklad "manželství" je typicky symetrická relace. Vztah "má rád" je obvykle reflexivní, ale často není symetrický ani tranzitivní. Vlastnost "silnější než" je antisymetrická a obvykle i tranzitivní. — Příkladem vícečetných (n-árních) relací je třeba výčet všech sehraných 11-členných výběrů mužstva na fotbal, které trenér může z dostupných hráčů sestavit. ? Doplňkové otázky (4.1.1) Kdy může být nějaká relace R na množině A zároveň symetrická i antisymetrická? (4.1.2) Výše jsme poznamenali, že relace dělitelnosti je antisymetrická. To platí nad přirozenými čísly. Platí to však i nad celými čísly? (4.1.3) Má nějaký význam l-ární (unární) relace nad množinou A? *(4.1.4) Jaký význam má definice antisymetrie relace u ostrého uspořádání x < y? Vždyť přece tam nemůže nastat x < y i y < x zároveň! 40 Úlohy k řešení (4.1.5) Kolik uspořádaných dvojic nad množinou {1, 2, 3,4, 5} patří do relace rovnosti = ? (4.1.6) Kolik uspořádaných dvojic nad množinou {1,2,3,4,5} patří do relace menší < ? (4.1.7) Kolik uspořádaných dvojic nad množinou {1,2,3,4,5,6} patří do relace dělitelnosti? N(4.1.8) Mějme relaci soudělnosti nad přirozenými čísly, kde dvě čísla x,y jsou v relaci pokud mají společného dělitele většího než 1. Které z vlastností z Definice 4.3 tato relace má? 4.2 Uspořádání a ekvivalence To jsou dva typy relací, se kterými se nejčastěji setkáme... Definice 4.4. Částečné uspořádání -< je reflexivní, antisymetrická a tranzitivní binární relace na množině. Pro vysvětlení, slovo "částečné" v definici znamená, že ne každé dva prvky lze vždy v částečném uspořádání porovnat. To je ostatně vidět třeba při relaci dělitelnosti. Dále si všimněme podmínky reflexivity v definici, tj. že prvek je sám se sebou v relaci. V praxi se této vlastnosti uspořádání říká neostrá nerovnost a značí se vodorovnou čárkou pod znaménkem nerovnosti -<. Pochopitelně z neostré nerovnosti snadno získáme ostrou vyloučením rovnosti a naopak také. Obrázek 4.1: Hasseův diagram- standardní způsob zobrazení částečného uspořádání (zde relace dělitelnosti) diagramem, kde "větší" prvky jsou kresleny výše než ty "menší" a kde od menších je kreslena šipka k "bezprostředně větším" prvkům (tj. šipky, které nevyplývají z tranzitivity relace). Komentář: Příklady částečných uspořádání: — Relace inkluze C (podmnožiny) mezi množinami. Dvě množiny mohou snadno být neporovnatelné inkluzí, jako třeba {1,2} a {1,3,4}. — Relace dělitelnosti | na přirozených číslech (viz také Obrázek 4.1). 41 - Srovnávání "lepších" a "horších" počítačů - ne každou dvojici lze rozhodnout. (Klíčovými kritérii jsou třeba cena, rychlost procesoru, velikost paměti, rychlost disku, atd.) K částečným uspořádáním se dále vztahují následující pojmy. Definice: Říkáme, že prvky a, b v částečném uspořádání -< jsou neporovnatelné, pokud neplatí ani a 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,1) G" i?. D -j^\v Příklad 4.13. 8 děvčat a 5 chlapců sedí okolo kulatého stolu rozesazeni tak, ——-I ž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 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.) □ -jTy» 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) Na 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) Na množině všech slov-řetězců nad běžnou abecedou definujme 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 VSB (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í, 50 d) stejný rok narození a stejné pohlaví. Jaké vlastnosti má tato relace (jako reňexivní, symetrická, antisymetrická, tranzitivní)? Jedná se treba o částečné uspořádání nebo o ekvivalenci? *(4.6.4) Mezi všemi studenty na přednášce DIM defínujeme následující binární relaci: Každý student je v relaci sám se sebou, tj. je to reňexivní relace. Každý student A je v relaci s jiným studentem B, právě když B sedí a) ve stejné radě 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) Na množině všech přirozených čísel od O do 1000 defínujeme 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. *(4.6.13) Jaká je poslední nenulová číslice ve "složeném" kombinačním čísle (§')■ Shrnutí cvičení Z uvedené látky si především vezměme: • Umět pracovat s pojmy vztahujícími se k relacím a zobrazením. • Umět skládat zobrazení (permutace). • Umět správně zdůvodnit svá řešení úloh. 51 Petr Hliněný: Diskrétní Matematika 52 Lekce 5 Algoritmizace diskrétních struktur Čas ke studiu lekce: 2 h. ^. 7 Průvodce studiem JVa 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.) Předpoklady ke studiu Předpokládáme zvládnutí učiva předchozích lekcí, především jejich příkladů a aplikací. Dále očekáváme znalost programovacího jazyka C, v němž jsou převážně zapsány ukázky programového kódu. Cíle lekce 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 (<2o, ) implementujeme obvykle jako jednorozměrné pole a[ ], kde a[i] = a«. Zobrazení / : A —► B implementujeme třeba obdobně jako posloupnost - pokud A = {di,... ,an} a B = {b\,..., bm}, použijeme pole f [ ], ve kterém f [i]=j vyjadřuje /(ať) = 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 = {di,... ,an} dvourozměrným polem (maticí) r[ ] [ ], ve kterém je r [i] [j]=0 pokud (dijdj) (£ R a r [i] [j]=l pokud (aj, clj) G R. O 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): for (i=0; i (Pro vysvětlení algoritmu, pole u [] zde značí, který prvek jsme již v některém cyklu vypsali. Druhá smyčka vždy hledá první nevypsaný prvek x a pak začíná vypisovat iterativně nový cyklus obsahující x, dokud se iterací zobrazení p [] nedostane zpět do x.) D O Příklad 5.2. Relace: Mějme pro tento příklad binární relaci R na množině {0,l,...,n — 1}, reprezentovanou dvourozměrným polem r[] [] jako výše. a) Otestovat, zda relace r je symetrická, je velmi jednoduché: 53 for (i=0; i b) Test tranzitivity dané relace lze provést třeba takto: Vi,j,k: r[i\[j] A r\j][k] => r[i][k] for (i=0; i } • Další základní operace se zobrazeními nebo relacemi by se implementovaly analogicky, nemělo by to, s použitím zdejších příkladů, činit velké potíže. D 5.2 Implementace množin Množiny se ze všech základních struktur implementují (kupodivu) nejobtížněji. To plyne z jejich principiální neuspořádanosti - nevíme totiž, kde "který prvek uložit" a kde jej pak zase jako prvek množiny najít. Proto se používají různé postupy jak s pevným umístěním prvků (kdy se však velmi plýtvá pamětí pro potenciální prvky, které zatím prvky množiny nejsou), tak i s proměnným umístěním prvků (kdy je zase obtížné prvek v množině vyhledat). Charakteristická funkce podmnožiny: Předpokladem je, že předem známe celé univerzumU, ze kterého jsou naše prvky vybírány. Nechť U = {u\,..., un}, pak podmnožinu ICW implementujeme jako polex[ ], kde x[i]=l pro Ui G X a x [i] =0 jinak. Zde se velmi snadno hledají prvky množiny, sjednocení je funkcí OR, průnik funkcí AND... Velkou nevýhodou je však použitelnost jen pro malá univerza U\ Seznam prvků množiny: Množinu X implementujeme jednoduchým seznamem všech jejích prvků. Pokud je seznam prvků X uložen v poli x[ ], pak můžeme psát X = {x[l],x[2],...,x[k]} pro pole x[ ] délky k. 54 Implementace je vhodná i pro velmi velká a předem neurčená univerza. Často je lepší místo pole použít dynamický spojový seznam prvků, pak lze snadno přidávat a vypouštět prvky kdekoliv v seznamu. Nevýhodou je, že vyhledání prvku množiny (obvykle nejčastější požadovaná operace) je zdlouhavé - musí se projít celý seznam. Uspořádaný seznam prvků množiny Jedná se o variantu předchozí implementace, kdy prvky v seznamu jsou navíc lineárně uspořádány podle předem daného klíče, třeba dle velikosti v případě čísel, nebo dle abecedy u jmen, atd. Hlavním přínosem je možnost binárního vyhledávání prvků v množině metodou půlení intervalu v seznamu (viz Příklad 5.4). Pokročilé datové struktury jako stromy, haldy, hashovací tabulky a jiné už nepatří do této lekce... O Příklad 5.3. Sjednocení dvou množin daných polí prvků a[] ,b [] do pole c [] : for (i=0; i D O Příklad 5.4. Binární vyhledávání čísla k v uspořádaném poli p [ ] délky n: a = 0; b = n-1; while (a if (p[a]!=k) printf("Cislo k neni v seznamu."); Všimněme si, že oproti běžnému vyhledávání projitím všech prvků zde uděláme pouze |~log2n] vyhledávacích kroků. □ 5.3 Generování výběrů Častým programátorským úkolem je procházet všechny možné výběry určitého typu. My si zde ukážeme netriviální postupy, jak procházet zobrazeními, variacemi a kombinacemi z předem daných prvků. 55 Jednoduché procházení dvojic (trojic, atd...): Všechny uspořádané dvojice indexů i, j projdeme jednoduše dvojí smyčkou 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í m 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 // zpracujeme kombinaci (select[0],...,select [K-l]) i—; } (Všimněme si, že už není třeba testovat opakované výběry, protože prvky generované kombinace jsou ostře seřazené.) □ 5.4 Generátory náhodných čísel Neboli skutečné generování náhodné posloupnosti bitů v počítači. Komentář: Kde všude potřebujeme používat náhodná čísla/bity? - Vytváření náhodných (velkých) privátních klíčů, třeba v SSL certifikátech. 57 - Použití náhodného hesla při šifrování SSL přenosu (zde musí být heslo skutečně náhodné, jinak by jej mohl nepřítel uhodnout). - Řešení kolizí paketů na ethernetu náhodně dlouhým čekáním s příštím vysíláním. - Využití při pravděpodobnostních algoritmech, které dokážou mnohdy využít náhodné bity pro výrazné statistické urychlení běhu výpočtu. - Při statistické analýza algoritmů a reálných procesů, různé modelování chaotických fyzikálních dějů, atd. Typy náhodných generátorů Primitivní pseudonáhodné generátory využívají aritmetické vzorce typu x := (A ■ x + B) mod C , které se pořád dokola iterují a vybrané bity x vytvářejí posloupnost. Nevýhody - velká závislost bitů na sobě a snadná předvídatelnost. Pseudonáhodné generátory s vnějším vstupem využívají podobné vzorce jako předchozí typ, ale navíc přidávají vstupy z okolních fyzických procesů (jako prodlevy stisků kláves, zpoždění operací disku, statistika síťových paketů, atd.). Problémy - závislost na okolí a ovlivnitelnost vnějšími podmínkami, také velká "cena" každého bitu. Hardwarové náhodné generátory jsou založeny na různých kvantových šumech (třeba přechodové stavy polovodičů), které se převádějí na posloupnost bitů. Problémy - jak převést šum na posloupnost uniformních bitů, také jaká je naše důvěra v kvantovou mechaniku. Komentář: Zkuste si v Linuxu spustit 'cat /dev/random' a sledovat, co se stává po stiscích kláves čí hýbání myší... O jaký typ generátoru se asi jedná? 5.5 Kombinatorická "exploze" Při programátorském řešení problémů spjatých s diskrétní matematikou často používáme algoritmy ve stylu projdi všechny možnosti a podle nich rozhodni. V takových případech však často narážíme (a hodně tvrdě!) na fenomén zvaný exponenciální kombinatorická exploze prohledávaných možností. Jen se podívejte, jak rychle roste funkce faktoriál. (Mimochodem, tento úkaz je už známý z dávné historie - vzpomeňme si na pohádkový příběh se zrnky obilí na polích šachovnice...) Matematicky popsáno, počet prohledávaných možností obvykle roste nějakou "divokou" exponenciální funkcí, a tudíž při zvětšení vstupu o 1 se potřebný čas výpočtu 58 zmnohonásobí. Pak se například stává, že výpočet pro vstup o velikosti 10 zvládne každý starý šrot, ale vstup o velikosti 15 nelze spočítat ani na nejvýkonnějších počítačích na světě. Takže pozor, mějte tento fenomén na paměti, až budete programovat procházení možností "hrubou silou"! m, Shrnutí lekce Z uvedené látky si především vezměme: • Jakými datovými strukturami implementovat množiny, relace a zobrazení. • Jak s nimi pracovat a procházet je. • Dávat si pozor na zrádný efekt kombinatorické exploze. Rozšiřující studium Pokud má čtenář zájem o širší popis algoritmické implementace diskrétních struktur, doporučujeme knihu L. Kučery [ ] nebo nový interaktivní projekt [4]. Asi nejrozsáhlejší učebnicí věnující se implementaci struktur a algoritmů je Knuthova [2] v angličtině. 59 Část II Úvod do Teorie Grafů 60 Petr Hliněný: Diskrétní Matematika 61 Lekce 6 Pojem grafu Čas ke studiu lekce: 2.5 h. Průvodce studiem Třebaže grafy jsou jen jednou z mnoha struktur v diskrétní matematice, vydobyly si svou užitečností a názorností tak důležité místo na slunci, až se dá bez nadsázky říci, že teorie grafů je asi nejdůležitější součástí soudobé diskrétní matematiky. Proto se i větší část našeho učebního textu věnuje grafům a jejich praktickému použití. Neformálně řečeno, graf se skládá z vrcholů (představme si je jako nakreslené puntíky) a z hran, které spojují dvojice vrcholů mezi sebou. (Pozor, nepleťme si graf s grafem funkce!) Obrázek 6.1: Úvodní ukázky grafů. Takový graf může vyjadřovat souvislosti mezi objekty, návaznosti, spojení nebo toky atd. Své důležité místo v informatice si grafy získaly dobře vyváženou kombinací svých vlastností - snadným názorným nakreslením a zároveň jednoduchou zpracovatelností na počítačích. Díky těmto vlastnostem se grafy prosadily jako vhodný matematický model pro popis různých, i komplikovaných, vztahů mezi objekty. Předpoklady ke studiu Pro zavedení základů teorie grafů předpokládáme zběhlost v práci s množinami a dobrou znalost zobrazení a relací, především bijekce a ekvivalence. Cíle lekce Prvním cílem této lekce je formálně defínovat, co je to graf a jaké jsou nejzákladnější grafové pojmy Také jsou zde uvedeny některé obvyklé typy grafů, jako cesty, kružnice, či úplné grafy. Především je však důležité, aby čtenář pochopil pojem isomorfísmu grafů a dobře si jej procvičil v následujícím cvičení. 6.1 Definice grafu Hned na úvod přistoupíme k formální definici grafu. Bude se jednat o základní definici tzv. obyčejného grafu; přičemž možné rozšiřující definice zmíníme krátce v závěru, ale stejně se budeme převážně zabývat obyčejnými grafy. V základní definici popisujeme hrany mezi dvojicemi vrcholů pomocí dvouprvkových podmnožin těchto vrcholů. Definice 6.1. Graf (rozšířeně obyčejný či jednoduchý neorientovaný graf) je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů. Značení: Hranu mezi vrcholy u a v píšeme jako {u, v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední Na množinu vrcholů známého grafu G odkazujeme jako na V(G), na množinu hran E{G). Fakt: Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace. Poznámka: Grafy se často zadávají přímo názorným obrázkem, jinak je lze také zadat výčtem vrcholů a výčtem hran. Například: V = {1,2,3,4}, £={{1,2}, {1,3}, {1,4}, {3,4}} 1 Běžné typy grafů Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Kružnice délky n má n > 3 vrcholů spojených do jednoho cyklu n hranami: 4 3 U„ 7 • • • n Cesta délky n má n + 1 vrcholů spojených za sebou n hranami: P 1 2 3 4 ... n n+1 62 Úplný graf na n > 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem í") hran): 2 Kr. Úplný bipartitní graf na m > 1 a íi > 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 Kn n ? Doplňkové otázky (6.1.1) Mohou být dva vrcholy obyčejného grafu spojeny dvěma hranami zároveň? (6.1.2) Může být graf bez hran? (6.1.3) Kolik hran může mít graf s jedním vrcholem? (6.1.4) Může být graf bez vrcholů? Úlohy k řešení (6.1.5) 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á? (6.1.6) Pro jakou hodnotu n je úplný graf Kn zároveň cestou? (6.1.7) Pro jakou hodnotu n je úplný graf Kn zároveň kružnicí? (6.1.8) Pro jaké hodnoty m, n > 0 je úplný bipartitní graf Km,n zároveň kružnicí? (6.1.9) Pro jaké hodnoty m, n > 0 úplný bipartitní graf Km,n neobsahuje žádnou kružnici? (6.1.10) Kolik hran musíte přidat do kružnice délky 6, aby vznikl úplný graf na 6 vrcholech ? (6.1.11) Má více hran. úplný graf Kg nebo úplný bipartitní graf Kq^? 63 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\ < d■ 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,0,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: 1,1,1,1,1,1,2,2 0,1,1,1,1,1,1 D O 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 1 1 s——i 1-------- --------1 1------i» w c t;--------1 1-------- --------1 1---------—* 71 Postupujme systematicky: Všechny tři grafy mají po 10 vrcholech a všechny vrcholy stupňů 3. Takto jsme je tedy nijak nerozliš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 A a odpovídající bijekce je na pohled zřejmá. (Doplňte si ji společným očíslováním vrcholů obou grafů.) □ O 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: 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 72 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 B: 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 isomorfísmus mezi následujícími dvěma grafy na 8 vrcholech: (6.6.7) Vyznačte isomorfísmus mezi následujícími dvěma grafy na 8 vrcholech: *(6.6.8) Existují dva neisomorfní grafy s posloupnostmi stupňů B: 2,2,3,3 ? U možnosti, kde dva neisomorfní grafy existují, je nakreslete. Pokud neexistují, 73 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.) A B C A A y~^ Aw A A d\_7 Návod: Pokud vám třeba jedno očíslování pro isomorfismus nevyjde, musíte zkoušet další a další a probrat tak všechny možnosti. (6.6.10) Jaká je nejdelší kružnice a nejdelší indukovaná kružnice obsažená v grafech A a B z Úlohy 6.6.9? *(6.6.11) Kolik podgrafů úplného grafu K\o je isomorfních kružnici C 4? *(6.6.12) Najděte všechny neisomorfní grafy se stupni 3, 3, 3, 3, 2,2, 2. Návod: Uvědomte si, že vrcholy stupně 2 lze "zanedbat" - nahradit hranami. Ve výsledku pak zbudou 4 vrcholy stupňů 3, ale mezi nimi mohou být násobné hrany nebo i smyčky. Kreslete si obrázky. (6.6.13) Vraťte se zpět k příkladům a úlohám z Oddílu 6.3 a zkuste, zda je se znalostí nových metod jste schopni řešit lépe a elegantněji. (6.6.14) Kolik nejvíce vrcholů obsahuje nezávislá množina v nakreslených grafech? Tuto největší nezávislou množinu si v grafech vyznačte. Shrnutí cvičení Z uvedené látky si především vezměme: • Poznat, zda existuje graf s danými stupni. Rozeznat isomorfní a neisomorfní grafy. 74 Petr Hliněný: Diskrétní Matematika 75 Lekce 7 Souvislost grafu ^ :/: Čas ke studiu lekce: 2.5 h. Průvodce studiem Pokud máme graf, který modeluje nějaká spojení či síť, přirozeně nás zajímá, jakou máme možnost se dostat odněkud někam v tomto grafu. To má množství praktických motivací - například počítačové, dopravní, telefonní či potrubní sítě. Je pochopitelné, že v takových sítích chceme mít možnost se dostat z každého místa do každého jiného. Grafům s takovou vlastností říkáme souvislé. (Abychom si ujasnili terminologii, když mluvíme o souvislosti, nejedná se o žádné "hledání souvislostí grafů s něčím jiným", ale o možnost procházení mezi vrcholy jednoho grafu po jeho hranách.) Pro ukázku se podívejme na následující obrázky tří grafů: Poznáte, který z nich je nesouvislý? Všechny tři vypadají "spojeně", ale podívejte se důkladně na ten prostřední - v něm není žádné propojení mezi vrchním a spodním vrcholem po hranách (křížení se nepočítají). Další potřebnou znalostí je umět souvislý graf algoritmicky celý procházet. Zde si uvedeme obecnou kostru algoritmu pro procházení grafu a zmíníme některé konkrétní variace tohoto algoritmu. (Znáte algoritmus pro procházení bludiště? V grafech je to v obecnosti podobné.) Také se později zmíníme i o vyšších stupních souvislosti grafu - o zálohování spojení v grafech pro případy výpadku. Předpoklady ke studiu Je potřebné dobré zvládnutí základů teorie grafů z Lekce 6 a pojmů souvisejících s relacemi. Cíle lekce Tato lekce defínuje pojmy souvislosti a komponent grafu. Cílem je ukázat, jak se souvislostí grafu pracovat a jak algoritmicky graf procházet po jeho hranách. Zmíněny jsou i vyšší stupně souvislosti. 7.1 Spojení vrcholů, komponenty Nejprve bychom si měli přesně ujasnit, jak se pohybujeme grafem, tedy co je vlastně procházkou v grafu. Tento pojem by měl postihnout základní věc, že v grafu procházíme hranami vždy z vrcholu do sousedního vrcholu, a přitom ponechat dostatek volnosti pro vracení se a zacyklení procházek. Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran Vo,ei,Vi,e2,v2,...,en,vn, ve které vždy hrana e» má koncové vrcholy Wj_i, Ví. Komentář: Sled je vlastně procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). Lema 7.1. Mějme relaci ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy u ~ v 'právě když existuje v G sled začínající v u a končící ve v. Pak ~ je relací ekvivalence. Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou sledem délky 0. Symetrická je také, protože sled zudo» snadno obrátíme na sled z v do ti. Stejně tak je ~ tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. □ Definice: Třídy ekvivalence výše popsané (Lema 7.1) relace ~ na V(G) se nazývají komponenty souvislosti grafu G. Jinak se taky komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence. Připomeňme si, že cesta je vlastně sledem bez opakování vrcholů. Věta 7.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. Důkaz. Nechť u = vo, e\, v\,..., en, vn = v je sled délky n mezi u a v v G. Začneme budovat nový sled W z vrcholu wq = u, který už bude cestou: Předpokládejme, že nový sled W už má počátek vj0, e\, vj\,..., Wi (na začátku i = 0, tj. jen wq bez hran), kde Wi = Vj pro některé j G {0,1,... ,n}. Najdeme největší index k > j takový, že Vk = v j = vjí, a sled W pokračujeme krokem ... ,Wi = Vj = Vk,čk+i,Vk+i = vJí+i- Zbývá dokázat, že nový vrchol vjí+\ = Vk+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo wi = vjí+\, l < i, pak bychom na vrchol vjí+\ "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: 76 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). Poznámka: Prázdný graf je souvislý. ? Doplňkové otázky (7.1.1) Které ze základních grafů uvedených v Oddíle 6.1 jsou souvislé? Úlohy k řešení (7.1.2) Který z těchto dvou grafů je souvislý? (7.1.3) 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, 77 — 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; stav (všechny vrcholy a hrany G ) = iniciační; úschovna U = {libovolný vrchol Vq grafu G}; stav(ü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í z v) { if (stav(e)==initiač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/ případný přechod na další komponentu G if (U je prázdná kk 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 Uje implementovaná jako zásobník, tj. dále prohledáváme od posledních nalezených vrcholů. 78 • Procházení "do šířky" - úschovna Uje 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 vq. (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. f Doplňkové otázky (7.2.1) Zamyslete se, proč implementace úschovny jako zásobníku v Algoritmu 7.4 projde graf do šířky. (7.2.2) Zamyslete se, proč implementace úschovny jako fronty v Algoritmu 7.4 projde graf do hloubky. 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ý. 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 k — 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ů). # m 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í: 79 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. ? Doplňkové otázky (7.3.1) Dosahuje cesta nebo kružnice vyššího stupně souvislosti? Úlohy k řešení (7.3.2) Jaký stupen souvislosti má úplný bipartitní grafKn,n? (7.3.3) Kolik nejméně vrcholů musíte vypustit z nakresleného grafu, nezbyla žádná cesta mezi vrcholy x a y? Zdůvodněte. v nem (7.3.4) 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. 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ě.) 80 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ě. ? íSM Doplňkové otázky (7.4.1) Kolik otevřených tahů budeme potřebovat na nakreslení grafu se čtyřmi vrcholy lichého stupně? Úlohy k řešení (7.4.2) Lze tento graf nakreslit jedním otevřeným tahem? (7.4.3) Kolik hran musíte přidat ke grafu z předchozí otázky aby se dal nakreslit jedním uzavřeným tahem? Shrnutí lekce Z uvedené látky si především vezměme: • Deňnice komponent a souvislosti grafu. • Schéma algoritmu procházení grafu. • Stručně o vyšších stupních souvislosti grafu. 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 [3] a demonstrovány i v [4]. 81 Cvičení 7.5 Příklady na souvislost grafů is\ Čas ke studiu cvičení: 1.5 h. Cíle cvičení Cílem tohoto cvičení je především předvést ukázku procházení grafu Algoritmem 7.4. Dále je uvedeno několik jednoduchých příkladů o souvislosti grafů. O Příklad 7.8. Ukázka průchodu následujícím grafem do hloubky z vrcholu a. /*- 9 *: ------* e \ d h *■ —__ l/\_-2--* c \ / i / a *-- --k b 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. 82 Tímto zpracování zadaného grafu skončilo. Mimo jiné jsme zjistili, že graf má jedinou komponentu souvislosti. □ O Příklad 7.9. Ukázka průchodu následujícím grafem do šířky z vrcholu a. f*: ■-* e 9 f^------------i J ~—p—-\ I > a *------------*c o > á -* c V této ukázce budeme obrázky znázorňovat stavy Algoritmu 7.4 stejně jako v předchozím příkladě. c h c h 83 > d g 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? □ O Příklad 7.10. Mějme graf Hs, 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 H^, 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. H$ má 10 vrcholů.) Rozhodněte, zda je H$ souvislý graf, a napište, kolik má H$ hran. (7.5.6) Kolik nejméně hran musí mít graf na 12 vrcholech, aby stupeň jeho souvislosti byl 3 ľ (7.5.7) Kolik nejvíce hran může mít graf na 10 vrcholech, a) který se skládá ze tří komponent souvislosti, 84 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ňů A: 2,2,2,3,3, 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é.) *(7.5.9) Existují dva neisomorfní grafy se stejnou posloupností stupňů A: 2,2,2,1,1, B: 2,3,3,3,3 ? *(7.5.10) Existují dva neisomorfní grafy se stejnou posloupností stupňů A: 2,2,2,2,2, 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 grafu 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) Shrnutí cvičení Z uvedené látky si především vezměme: • Poznat souvislost a komponenty grafu. • Chápat, jak probíhá algoritmický průchod grafem. 85 Petr Hliněný: Diskrétní Matematika 86 Lekce 8 Vzdálenost a metrika ^ 7 Čas ke studiu lekce: 2 h. Průvodce studiem 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). Předpoklady ke studiu Předpokládáme především znalost základních grafových pojmů, grafové souvislosti a principu matematické indukce. Dále očekáváme znalost programovacího jazyka C, ve kterém jsou prezentovány ukázky algoritmů. Cíle lekce Prvním cílem této lekce je defínovat 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, f2, • • •, e„, vn, ve které hrana e» má koncové vrcholy Wj_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 dc(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ě dc{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á dc{u, v) = dc{v,u). Leraa 8.2. Vzdálenost v grafech splňuje trojúhelníkovou nerovnost: \/u,v,wEV(G) : dc(u,v) + dc(v,vj) > dc(u,vj). Důkaz. Nerovnost snadno plyne ze zřejmého pozorování, že na sled délky dc(u, v) mezi u, v lze navázat sled délky dc(v, w) mezi v, w, čímž vznikne sled délky dc(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 dc(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ť dc(u,v) = d > 0 a označme v' souseda vrcholu v bližšího k u, tedy dc(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 nima 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álenosti z vrcholu u: 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. Doplňkové otázky (8.1.1) Jaká je vzdálenost dvou vrcholů ze stejné komponenty souvislosti grafu? 87 (8.1.2) Jaká je vzdálenost dvou vrcholů z různých komponent souvislosti? (8.1.3) Jestliže některé dva vrcholy grafu G mají vzdálenost 22, lze pak nalézt v G jiné dva vrcholy se vzdáleností 18 ? Úlohy k řešení (8.1.4) Jaká je největší vzdálenost dvou vrcholů v úplném grafu? (8.1.5) Jaká je největší vzdálenost dvou vrcholů v úplném bipartitním grafu -ří33,44 ? (8.1.6) Jaká je největší vzdálenost dvou vrcholů v kružnici C\\ ? (8.1.7) 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 00 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: — 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 00 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í.) 88 Algoritmus 8.6. Výpočet metriky grafu Tento algoritmus, prv graf s N vrcholy daný matici 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 0 pro všechny hrany e. Definice: Mějme (kladně) vážený graf G, w. Délkou váženého sledu S = Vo, e\, V\,-č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 cÍq(u, v) = min{dg(5') : S je sled s konci u, v} . Lema 8.8. Vážená vzdálenost v kladně vážených grafech také splňuje trojúhelníkovou nerovnost. 89 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, 6? Ne, není to 6, ale najdeme kratší cestu délky 5. -4 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. ? Doplňkové otázky (8.3.1) Co když zakážeme sledy s bezprostředním opakováním téže hrany. Lze stále získat v předchozím obrázku vpravo sled mezi vrcholy x,y s libovolně nízkou zápornou délkou? Úlohy k řešení (8.3.2) Jaká je nejdelší vzdálenost mezi dvěma vrcholy v předchozím obrázku vlevo? (8.3.3) O kterém vrcholu v předchozím obrázku vlevo se dá říci, že má "centrální pozici", tj. zeje z něj do všech ostatních vrcholů nejblíže? Jaká je z něj největší vzdálenost do ostatních vrcholů? 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. 90 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 z u do v; 1/ 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^ \ l / \ / 2 x-v\ OO f ^ 5/\ ^ oo / \ / / 1 / ^^ / / / / 1 OO J( \x5 ""^ oo \ / \ / x / \ y 2 \ x \ / 2 \ 0 x \ / V------------------V oo w i 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í: 94 95 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 Dijkstrův 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. (8.5.3) Kolik (neuspořádaných) dvojic vrcholů v následujícím grafu 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. 96 (8.5.5) Jaká je největší vzdálenost mezi dvojicí vrcholů v tomto váženém grafu? 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 4.) Pomineme-li izolované vrcholy 11 a 13, jaká je největší vzdálenost mezi zbylými vrcholy tohoto grafu? Shrnutí cvičení Z uvedené látky si především vezměme: • Správně určovat vzdálenosti v grafu. 97 Petr Hliněný: Diskrétní Matematika 98 Lekce 9 Stromy a les Čas ke studiu lekce: 3.5 h. Průvodce studiem 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? 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. Předpoklady ke studiu Předpokládáme znalost základních grafových pojmů, grafové souvislosti a principu matematické indukce. (Tato lekce nesouvisí se vzdálenostmi v grafech.) Cíle lekce Úkolem této lekce je hlavně defínovat 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 grafu 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 lesech 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. Leraa 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 stromě 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á přesně n — 1 hran pro n > 1. 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. Mezi 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. □ 99 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. O 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, / 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. □ ? Doplňkové otázky (9.1.1) Ja prázdný graf (bez vrcholů a hran) stromem? (9.1.2) Které ze základních typů grafů z Oddílu 6.1 jsou stromy? (A nezapomněli jste najeden podtyp?) (9.1.3) Lze o některém ze základních typů grafů z Oddílu 6.1 říci, ze to určitě nebude strom ? Úlohy k řešení (9.1.4) Kolik je neisomorfních lesů na třech vrcholech? Nakreslete si je. (9.1.5) Kolik je neisomorfních stromů na čtyřech vrcholech? Nakreslete šije. *(9.1.6) 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. 100 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 v a v 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 "prarodič" ^^ \. rodič / \^ \y ^^ / ^r^-^^ ^\ potomci *r é \ ^"--« \ Č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. 101 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: • 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" C T 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. O Příklad 9.9. Ilustrací definice 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. □ 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í. 102 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. ? Doplňkové otázky (9.2.1) Který strom nemá žádné centrum? (9.2.2) U jakého typu stromu trvá nalezení centra podle definice největší počet kroků (vzhledem k velikosti stromu) ? A u jakého nejmenší počet kroků ? *(9.2.3) Jaká je souvislost nejdelší cesty obsažené ve stromu s jeho centrem? Úlohy k řešení (9.2.4) 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, 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.5) Určete centra následujících dvou stromů: (9.2.6) Mějme libovolný strom s 33 vrcholy. Kolik jeho listů postupně odebereme, než určíme centrum? (Je to jednoznačné?) 103 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ší. í 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: ( ((()()())()) (()(())) ) ((000) 0) ( 000) ( 0 (0)) (0) o o 104 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. :r\\ 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 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 = centrumiX); 105 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 lexikografícky (abecedně) podle klíče k[l]<=k[2]<=. . .<=k[d] ; return "("+k[l]+...+k[d]+")"; } ? Doplňkové otázky (9.3.1) Proč při hledám isomorfísmu stromů (Algoritmus 9.12) volíme kořeny v centrech stromů a ne třeba ve vrcholu největšího stupně? Úlohy k řešení (9.3.2) Odvoďte správný závorkový kód pro tento pěstovaný strom: (9.3.3) 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. 106 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. O 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. □ 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 in-ternetem, 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,vj 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 J^ w(e) kostra TCG \eSE(T) Jak brzy uvidíme, zadaný problém má velmi jednoduché algoritmické řešení. 107 Hladové algoritmy Asi nejjednodušším způsobem řešení různých optimalizačních úloh je "ber 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". 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,vj s nezáporným ohodnocením hran w. - Seřadíme hrany grafu G vzestupně podle jejich ohodnocení, tj. w(e1) < 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 TU{ej} 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(ei) < w{e,2) < • • • < 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 T0 = T, algoritmus pracoval správně. Předpokládejme tedy, že T0 ^ T, a ukážeme spor, tj. že toto nemůže ve skutečnosti nastat. Označme j > 0 takový index, že se množiny T0 a T shodují na prvních j — 1 hranách e\,..., e^-i, ale neshodují se na Cj. To znamená, že e j G T, ale ej (É T0. (Jistě nemůže nastat ej (É T, ale ej G T0.) Podle Důsledku 9.5 obsahuje graf na hranách T0 U {e^} právě jednu kružnici C. Kružnice C však nemůže být obsažena 108 v nalezené kostře T, a proto existuje hrana e^ v C, která e^ ^ T a zároveň A; > j. Potom však je w(ek) > w(ej) podle našeho seřazení hran, a tudíž kostra na hranách (T0 \ {e&}) U {e,} (vzniklá nahrazením hrany e& hranou ej) není horší než T0 a měli jsme ji v naší úvaze zvolit místo T0. 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. 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 Primoví, 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]. ? Doplňkové otázky (9.4.1) Co se stane, pokud v Algoritmu 9.17 seřadíme hrany naopak, tedy sestupně? (9.4.2) Proč v důkaze Algoritmu 9.17 nemůže nastat e j <£ T, ale ej G Ti? Úlohy k řešení (9.4.3) Kolik koster má kružnice délky 2004? *(9.4.4) Zkuste sami vlastním počítáním odvodit, že počet koster úplného grafu K$ 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? 109 Shrnutí lekce Z uvedené látky si především vezměme: • Dennici a základní vlastnosti stromů. • Kořenové a uspořádané stromy jejich kódování závorkami. • Pojem kostry grafu a problém minimální kostry. • Hladový postup a jeho užití pro hledání minimální kostry. 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 [ ']. Zájemci o hlubší studium počítání koster v grafech si mohou přečíst (poměrně obtížnou) [ , Kapitola 7]. 110 Cvičení 9.5 Příklady o stromech, kostrách a hladovém postupu v2 l 1 \ / \ / ii---------------------------------><---------------------------------m------------------ 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 N- A •A 1 1 1 ''• i ---------A / \ Příklad 9.23. Najděme minimální kostru grafu z Příkladu 9.22 J arnikovým I 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 \- A •A 2 1 i 1 ''• i ----4 / \ Čas ke studiu lekce: 2.5 h. Průvodce studiem 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. Předpoklady ke studiu Předpokládáme znalost běžných grafových pojmů, speciálně znalosti o stromech, a principu matematické indukce. Také je dobré mít jistou geometrickou představivost. Cíle lekce Prvním cílem této lekce je defínovat barevnost grafů a naučit se s ní pracovat. Druhým cílem je defínovat 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 xiß) pro které existuje obarvení grafu G pomocí xiß) 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. O Příklad 10.2. Určete barevnost grafu 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. □ V obecnosti lze o barevnosti grafů říci následující. Lema 10.3. Nechť G je jednoduchý graf (bez smyček) nan vrcholech. Pakxiß) < n a rovnost nastává právě když G ~ Kn je úplný graf. Důkaz: Stačí každý vrchol obarvit jinou barvou a máme skutečné obarvení n barvami dle definice. Navíc pokud některá dvojice u, v vrcholů není spojená hranou, můžeme volit lepší obarvení c{u) = c(v) = 1 a zbylé vrcholy různými barvami 2, 3,..., n — 1, tj. pak xiß) < n. □ O Příklad 10.4. Vraťme se k příkladu barvení mapy z úvodu lekce a ukažme si, jak souvisí s grafy a jejich barevností. 118 Označme si státy na mapě písmeny a, b,... ,h. Jednotlivé oblasti na mapě (předpokládáme, že každý stát má souvislé území, tj. státy = oblasti) prohlásíme za vrcholy našeho grafu a sousední dvojice států spojíme hranami. Nezapomeňme přitom, že "sousední" znamená sdílení celého úseku hranice, ne jen jednoho rohu. Výsledkem bude graf nakreslený vpravo. Podíváme-li se nyní zpátky na definici barevnosti grafu, vidíme, že se jedná přesně o ten samý problém jako u barvení původní mapy. Při troše snahy také najdeme lepší obarvení uvedené mapy využívající pouhých tří barev: D Podívejme se, které grafy mají nízkou barevnost. Je jasné, že jedna barva stačí, jen pokud graf nemá hrany. Grafy obarvitelné dvěma barvami už tvoří zajímavější třídu a jsou obvykle nazývané jedním slovem bipartitní Poměrně jednoduchý popis bipartitních grafů je uvedený v následujícím tvrzení. Věta 10.5. Graf G má barevnost 1 právě když nemá žádné hrany. Graf G má barevnost 2 právě když nemá žádnou kružnici liché délky jako podgraf Důkaz: Pokud graf nemá hrany, můžeme všechny vrcholy obarvit stejnou barvou 1. Naopak pokud mají všechny vrcholy stejnou barvu, nemůže graf mít žádnou hranu. Druhá část je už trochu složitější, proto důkaz jen naznačíme. Na jednu stranu, lichou kružnici nelze obarvit dvěma barvami, viz obrázek. Na druhou stranu si představme, že zvolíme libovolný vrchol v grafu G s barvou 1 a ostatní vrcholy obarvíme takto: Vrcholy, jejichž vzdálenost od v je lichá, obarvíme 2. Vrcholy, jejichž vzdálenost od v je sudá, obarvíme 1. Pokud bychom tak získali třeba dva vrcholy v sudé vzdálenosti spojené hranou, nalezneme při troše snahy lichou kružnici procházející touto hranou, což nelze. Stejně tak pro dva vrcholy v liché vzdálenosti. Proto naše obarvení za daných předpokladů 119 nemůže dát stejnou barvu sousedním vrcholům, a tudíž dvě barvy stačí. 2jk V A 1 1 2 ?? D Poněkud nepříjemnou skutečností je, že o barvení a určování barevnosti grafů nemůžeme v obecnosti říci o mnoho více, než jsme uvedli výše. Jedná se o problém algoritmicky ještě obtížnější než byl problém isomorfismu a nepředpokládá se, že by se barevnost grafu dala algoritmicky určit jinak, než hrubou silou probráním (téměř) všech možných obarvení. ? Doplňkové otázky (10.1.1) Který graf má barevnost Oľ (10.1.2) Pokud graf není souvislý a každá z jeho komponent má barevnost k, kolik je barevnost celého grafu? (10.1.3) Může mít podgraf větší barevnost než celý graf? Úlohy k řešení (10.1.4) Kolika nejméně barvami korektně obarvíte graf pravidelného osmistěnu? (10.1.5) Kolik nejméně barev je třeba na korektní obarvení tohoto grafu? Příslušné obarvení vyznačte. (10.1.6) Jaká je barevnost stromu? (10.1.7) Kolik barev vždy stačí na korektní obarvení grafu vzniklého z kružnice délky 2004 přidáním jedné nové hrany? *(10.1.8) Představme si, že nějaký velký graf má všechny vrcholy stupně nejvýše 101. Kolika barvami takový graf jistě obarvíme? 120 10.2 Rovinné kreslení grafu Dalším důležitým grafovým pojmem úzce svázaným s problémem čtyř barev je rovinné nakreslení, tj. nakreslení bez překřížených hran. Jen málokteré grafy rovinné nakreslení mají, ale důležitost grafů s rovinným nakreslením je motivována jak esteticky (nakreslení bez křížení hran vypadají hezky a jsou snadno "čitelná"), tak jejich teoretickým významem i praktickými aplikacemi (představme si jednostranný plošný spoj jako graf obvodu - hrany při jeho realizaci fyzicky nemůžeme křížit bez drátových propojek). Definice 10.6. Rovinným nakreslení grafu G myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body v rovině a hrany jako oblouky (čili křivky) spojující body svých koncových vrcholů. Přitom hrany se nesmí nikde křížit ani procházet jinými vrcholy než svými koncovými body. Graf je rovinný pokud má rovinné nakreslení. Komentář: Důležitým příkladem rovinných grafů jsou grafy (třírozměrných Euklidovských) mnohostěnů, třeba graf čtyřstěnu, krychle, osmistěnu, dvanáctistěnu, atd. Platí, že grafy mnohostěnů jsou vždy rovinné a 3-souvislé. Naopak každý rovinný 3-souvislý jednoduchý graf je grafem nějakého mnohostěnu. (Důkaz tohoto tvrzení je obtížný.) Geometrický příklad grafů mnohostěnů také přináší část terminologie rovinných kreslení a hlavně motivuje důležitý slavný Eulerův vztah (Věta 10.7). Definice: Stěnami rovinného nakreslení grafu nazýváme souvislé oblasti roviny ohraničené tímto nakreslením grafu. Komentář: Rovinný graf může mít více podstatně různých nakreslení, jak vidíme na uvedeném ilustračním obrázku, ale platí, že 3-souvislý rovinný graf má ve všech svých rovinných nakresleních stejné stěny. To intuitivně znamená, že ze znalosti grafu mnohostěnu můžeme odvodit přibližný tvar původního tělesa. Podívejte se zpět na konstrukci použitou v Příkladě 10.4 - oblasti, neboli stěny, mapy jsme nahrazovali vrcholy nového grafu a spojovali jsme hranami sousedící dvojice oblastí. Tuto konstrukci lze formálně zobecnit na stěny nakreslení libovolného grafu: 121 Definice. Duální graf rovinného nakreslení grafu G získáme tak, že stěny nahradíme vrcholy duálu a hranami spojíme sousedící dvojice stěn. Komentář: Duální graf k rovinnému grafu je vždy rovinný, což je snadné dokázat. Pro příklad odvození duálního grafu se podívejme na obrázek: Nyní si uvedeme zajímavý a vlastně "jediný rozumný" kvantitativní vztah o rovinných nakresleních grafů. Jedná se o slavný Eulerův vztah, který říká: Věta 10.7. Nechť rovinné nakreslení neprázdného souvislého grafu G má f sten. Pak \V(G)\ + f-\E(G)\ = 2. Důkaz: Nechť počet vrcholů v G je v a hran h. Důkaz této důležité věty pouze naznačíme, detaily lze najít v literatuře. • Pokud je G strom, tj. nemá kružnice, má ve svém nakreslení jedinou stěnu a dle Věty 9.3 má přesně h = v — 1 hran. Potom platí v + f — h = v + 1 — (v — 1) = 2. • Pokud G obsahuje kružnici C, pak vypustíme jednu její hranu e. Tím se počet hran sníží o 1, ale zároveň se sníží o 1 počet stěn, protože kružnice C původně oddělovala dvě stěny přilehlé k hraně e od sebe, ale nyní tyto dvě stěny splynou v jednu. Počet vrcholů se nezmění. Proto se nezmění hodnota v + f — h = v + (/-l)-(e-l) = 2. Tvrzení tak plyne z principu matematické indukce. □ Poznámka: Všimněte si dobře, že Eulerův vztah vůbec nezávisí na tom, jak je graf G nakreslený, je to vlastnost grafu jako takového. Tento jednoduše vypadající vztah má mnoho aplikací a důsledků, z nichž část si uvedeme i dokážeme. Důsledek 10.8. Jednoduchý rovinný graf na v > 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 > \ ■ 3/, neboli |e > /. Dosazením do vztahu Věty 10.7 získáme 2 1 2 = v + j — e < v + -e — e = v — —e 122 e< 3(u-2) = 3u-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 |e > /. Dosazením do vztahu Věty 10.7 získáme e < v H—e ~~ 4 v + f e< 2(u-2) 1 v-----e 2 2u-4. Tím jsme hotovi. D Důsledek 10.9. Každý rovinný graf obsahuje vrchol stupně nejvýše 5. Každý rovinný graf bez trojúhelníků obsahuje vrchol stupně nejvýše 3. Důkaz: Pokud by všechny vrcholy měly stupně alespoň 6, celý graf by měl aspoň ! • 6t> = 3t> hran, což je ve sporu s Důsledkem 10.8. Některý vrchol musí tudíž mít menší stupeň než 6. Obdobně postupujeme u druhého tvrzení. □ ? Doplňkové otázky (10.2.1) V jakém případě stěnu rovinného nakreslení grafu neohraničuje kružnice grafu? *(10.2.2) Jakou podmínku o grafu G musíme dodatečně požadovat, aby každé jeho rovinné nakreslení mělo všechny stěny ohraničené kružnicemi? *(10.2.3) Jak bude znít Eulerův vztah pro nesouvislý rovinný graf s k komponentami? Úlohy k řešení (10.2.4) Nakreslete rovinně tento graf: (10.2.5) Graf pravidelného dvacetistěnu má 12 vrcholů a 20 stěn. Kolik má hran? (10.2.6) Co je duálním grafem k rovinnému nakreslení grafu krychle? (10.2.7) K rovinnému nakreslení stromu přidáme dvě nekřížící se hrany. Kolik bude mít výsledný graf stěn? 123 10.3 Rozpoznání rovinných grafů Při praktickém využití rovinných grafů je potřeba umět abstraktně zadaný graf rovinně nakreslit bez křížení hran. Na rozdíl od problému určení barevnosti grafu se naštěstí jedná o efektivně algoritmicky řešitelný problém. Fakt. Existují algoritmy, které pro zadaný graf efektivně (rychle) rozhodnou, zda je to rovinný graf, a případně naleznou rovinné nakreslení. Tyto algoritmy však nejsou jednoduché. Místo obecných algoritmů pro rovinné kreslení grafů se zde podíváme na otázku, jak odůvodnit nerovinnost (malého) grafu. O Příklad 10.10. Dokažme, že následující dva grafy, K$ a A3 3 nejsou rovinné. Při zdůvodnění využijeme znalosti předchozího oddílu. Všimněme si, že graf K§ má 5 vrcholů a 10 > 3 • 5 — 6 hran. Podobně graf Ks^ 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 K3t3 nejsou rovinné. Význam grafů K5 a K3>3 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ělení grafů K$ nebo -^3,3 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ů K5 nebo Ks^. (Ve skutečnosti tuto obtížnou větu ani nepotřebujeme ke zdůvodnění 124 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 Ks,3 než grafu K$. O 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: y Graf B na druhou stranu rovinný není podle Věty 10.12, protože je v něm obsaženo podrozdělení grafu Ks,3, 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. ? Doplňkové otázky (10.3.1) Kdy je úplný bipartitní graf' Km,n rovinný? (10.3.2) Platí Věta 10.14 pro grafy s násobnými hranami nebo se smyčkami? * (10.3.3) Proč je každý graf vzniklý přidáním dvou hran k libovolnému stromu rovinný.' ? Úlohy k řešení .3.4) Pro která n je úplný graf Kn rovinný': (10 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ě z a s 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/(e)-E^ \e*—z e—*z / \e^s e—>s ? Doplňkové otázky *(11.1.1) Nechť U je množina vrcholů sítě obsahující zdroj a neobsahující stok. Rozmyslete si, proč lze velikost toku mezi zdrojem a stokem lze spočítat také z rozdílu součtů toků na všech hranách vycházejících z U a hranách přicházejících doU. 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 síť 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. 134 Komentár: 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í definice a věta. Definice 11.4. Řez v síti S = (G, z, s, w) je podmnožina hran G C E (G) taková, že v podgrafu G — G (tj. po odebrání hran G z G) nezbude žádná orientovaná cesta ze z do s. Velikostí řezu G rozumíme součet kapacit hran z G, tj. ||G|| = 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 definice ř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. Definice: Mějme síť S 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 e\, e2,..., em, kde /(e») < w(ei) pro e» ve směru z u do v a /(e») > 0 pro e» v opačném směru. 135 Hodnotě w(e^ — f (ei) pro hrany e« ve směru z ti do ti a hodnotě f(ci) 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. 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); tokf = 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 e U ); 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: j., -, , -, /(e) = w(e) Sie) = 0 Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e <— U (odcházející z U) plný tok f(e) = w(e) a každá hrana e —► U (přicházející do U) tok f(e) = 0. Velikost toku / ze z do s se také dá psát jako ii/ii = E m - E m = E m = E *>& = \\c\\ ■ 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: 136 Důsledek 11.7. Pokud jsou kapacity hran site 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. ? Doplňkové otázky (11.2.1) Co by se stalo s úlohou o maximálním toku, pokud by graf sítě obsahoval násobné hrany? *(11.2.2) Co by se stalo s úlohou o maximálním toku a s Algoritmem 11.6, pokud bychom povolili i záporné kapacity hran? Úlohy k řešení (11.2.3) Jaký je maximální tok touto sítí ze z do s? 3 (11.2.4) Co obsahuje výsledná množina U Algoritmu 11.6 v předchozím příkladě? (11.2.5) Kde je minimální řez v této síti mezi zas? ___1 2 ' ' 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íť, 137 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. 3. V síti lze najednou přepravovat více substancí. To vede na problém tzv. víceko-moditní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ÍY (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. 138 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íť 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 bipar-titní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ý. 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 u a v 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 — 1 vrcholů různých od u,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ť M\, M2,..., M\. jsou neprázdné množiny. Systémem různých reprezentantů množin M\, M2,..., M\. nazýváme takovou posloupnost různých prvků (xi, X2, ■ ■ ■, Xk), že Xi G 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. 139 Věta 11.10. Nechť Mi, M2,..., M^ jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, pravé když platí VJC{l,2,...,fc}: U > \J\ neboli pokud sjednocení libovolné skupiny z téchto množin má alespoň tolik prvků, kolik množin je sjednoceno. Důkaz: Označme X\, X2, ■ ■ ■, xm po řadě všechny prvky ve sjednocení M\ U M2 U ... U Mfc. Definujeme si bipartitní graf G na množině vrcholů {1,2,... ,k} U {x\, X2, ■ ■ ■, xm}U{u, v}, ve kterém jsou hrany {u, i} pro i = 1,2,... ,k, hrany {v, Xj} pro j = l,2,...,ma hrany {i, Xj} pro všechny dvojice i, j, pro které x j G Mj. Komentář: Konstrukce našeho grafu G je obdobná konstrukci sítě v Metodě 11.8: Vrcholy uav 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 Mj. Systém různých reprezentantů tak odpovídá k disjunktním cestám mezi uav. Nechť X je nyní libovolná minimální množina vrcholů v G, po jejímž odebrání z grafu nezbude žádná cesta mezi uav. 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 {x\,..., xm} (aby nevznikla cesta mezi u, v), a proto LU^i 'j&J \Xn{xi,...,xm}\ = \X\- \X n {!,...,k}\ = \X\ -k + \J\. Vidíme tedy, že \X\ > k pro všechny (minimální) volby oddělující X, právě když \Jj£j Mj > \J\ pro všechny volby J, což je dokazovaná podmínka naší věty. □ 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íť. ? Doplňkové otázky Úlohy k řešení (11.3.1) Najděte maximální párování v tomto bipartitním grafu: 140 (11.3.2) Najděte maximální 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ů? \ Shrnutí lekce Z uvedené látky si především vezměme: • Deňnice sítě a toku, úloha o nalezení toku. • Algoritmus pro nalezení maximálního toku a minimálního řezu. • Aplikace toků na bipartitní párování a na výběr různých reprezentantů. i \ \ Rozšiřující studium ------1 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 [3] nebo v [7]. 141 Cvičení 11.4 Příklady toků v sítích Čas ke studiu cvičení: 0.5 h. Cíle cvičení V tomto cvičení uvedeme příklad průběhu Algoritmu 11.6 pro nalezení maximálního toku v dané síti. O Příklad 11.11. Jaký je maximální tok touto sítí ze z do s? _____3 5 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). 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. 142 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. 2 (11.4.2) Najděte maximální tok v následující síti. 143 (11.4.3) Najděte maximální tok v následující síti. 1 3 (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}. Shrnutí cvičení Z uvedené látky si především vezměme: • Chápat a použít Algoritmus 11.6 pro nalezení maximálního toku v síti. 144 Část III 145 Klíč k řešení úloh í.i.i 1.1.2 1.1.3 1.1.4 1.1.5 1.1.6 1.1.7 1.1.8 1.1.9 Samozřejmě ano, prvky se v posloupnosti mohou opakovat. Prázdná množina. Ano, prázdnou množinu. Protože dle definice neexistuje vůbec žádná uspořádaná dvojice (a, b) kde 6 G 0. Ano, třeba A = 0 a B = {$}. 91 990 3 1.1.10) -4 1.1.11) 4 1.1.12) -3 1.1.13) 16 1.1.14) 12 1.1.15)* [x + 0.5\ 1.2.1) Protože je právě jeden způsob, jak 0 prvků (prázdnou množinu) seřadit do posloupnosti. 1.2.2) Protože každý výběr k prvků lze zaměnit s jeho doplňkem, který má n — k prvků. 1.2.3) Protože svou roli hraje pořadí, které nelze zaměňovat s pořadím doplňku. 1.2.4) Nezávislé pouze pokud tažená čísla vracíme zpět. 1.2.5) n(6n-l)(6n-2) 1.2.6) 720, permutace 1.2.7) 210, kombinace 1.2.8) 420, variace 1.2.9) Nezávislé dva výběry, takže 49 • 49. 1.2.10)* 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.11)* Nezávislými výběry kombinací (3) • (2)- (1.3.1) O permutace s opakováním. (1.3.2) Kombinace s opakováním, vzhledem k nerozeznatelnosti kuliček vybíráme opakované barvy bez pořadí. (1.3.3)* Ještě lze definovat složení po řadě nezávislých k výběrů z n prvků, neboli výběr posloupnosti (s povoleným opakováním prvků) délky k nad n-prvkovou množinou. Tomuto výběru se také říká variace s opakováním, viz Lekce . (1.3.4) Permutace s opakováním 3 x A, 2 x N, výsledek 3360. (1.3.5) § (1.3.6) Kombinace s opakováním C*(3, 7) = 36. 146 (1.3.7)* Kombinace s opakováním C*(4, 6) = 84. (1.3.8)* 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) Ano. (2.2.2) Například při hodu kostkou jev padlo sudé číslo a jev padla jednička nebo dvojka. (2.2.3) Nejsou, součet 2 + 4 = 6 a zároveň součin 2-4 = 8. (2.2.4)** Nelze, neboť spočetný součet nulových pravděpodobností je 0, ale spočetný součet kladných pravděpodobností je vždy oo. Obojí je v rozporu s definicí P (ft) = 1. (2.2.5)* Ano, lze, vybereme prostě uniformní náhodný bod přímky. (Rozdíl proti přirozeným číslům je v tom, že reálných čísel je nespočetně mnoho a lze na nich definovat infinitezimálně malé hodnoty pravděpodobnosti dir —> 0, jejichž integrál přes všechna reálná čísla dá výsledek 1. Pamatujete z analýzy?) (2.2.6) \ (2-2-7) é = \ (2.2.8) 32 = § (2.3.1) Nejsou, neboť jsou disjunktní, tudíž jejich průnikem je 0 s pravděpodobností 0, což nemůže být součin kladných pravděpodobností těchto dvou jevů. (2.3.2) Ano, ale jen pokud jeden z nich má pravděpodobnost 0, tj. je prázdný. (2.3.3) Ano, násobící pravidlo je splněno P(0) • P (A) = 0 • P(A) = 0 = P(0 n A). (2.3.4)* Není - představte si hod třemi mincemi A, B, C najednou a tři jevy: podlo stejné na A, B, padlo stejné na i?, C a padlo stejné na A, C. Pak každá dvojice je nezávislá, ale trojice není - pokud padne stejné na A, B i stejné na A, C, už z toho plyne, že padlo stejné na B,C. (2.3.5) Nejsou, například pokud jeden dostane pikové eso, druhý ho už dostat nemůže. (2.3.6) Ano, je. Ať na první padne cokoliv, druhá má stejnou šanci se trefit do stejného čísla. (2.3.7) 3! • gs = gg (2.3.8) Tři nezávislé hody, (±)5 = ^. (2.3.9) Královský pokr může dostat 28 způsoby z (352) (neuspořádaných) rozdání, takže 28/(352) pro jedno rozdání a [28/(352)]2 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. (2.4.3) \ -2 + \ -3 = 2.5 147 (2.4.4)* I.l + I.2 + i-3 + ^-4 + ... (2.5.1) Y^Q, kombinace! j_ 24 5 2^ 1 8 J_ 10 4-3 _ _3_ 32-31 248 4! 32-31-30-29 (6\ /06 (2.5.2) (2.5.3) (2.5.4) (2.6.1) (2.6.2) (2.6.3) (2.6.4) (g)/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) ff (2.6.6) a) (ft7)+ ©)/(=?), b)(17-7)/(224). (2-6.7) (258)/(352) = ii i (2.6.8) ě'3 + 3'6 + 6'6 = 36 (2-6.9)* f+ § + ^ = ^=4.18 (2.6.10)* £ = 2.^ + 3- (l-^-i|.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 I?7 může být nezávislý na jevu Aj,. Dosazením do definice nezávislosti ověříme, že skutečně Aj~ 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.2.1) Špatné je, že byl použit obrácený postup kroků - od neznámého závěru tvrzení zpět ke známým faktům, důkaz však musí jít vždy od známého k závěrům. (3.2.2) Nyní je postup kroků správný, ale chybné je krácení výrazem (a — b), neboť a — b = 0 a nulou se nesmí krátit. (3.3.1) Každý další prvek množiny B přidá a možností svého zobrazení do množiny A, podle principu nezávislých výběrů se to pak vynásobí. (3.3.2) Chybně je položen základ indukce - indukční krok je zcela správný, ale funguje až od n > 2, kdežto jako základ indukce jsme ověřili jen n = 1. (Pro n = 2 tvrzení prostě neplatí.) (3.5.1) Vybírejme k + 1 z n + 1 prvků a z vybrané kombinace odeberme (pokud v ní je) prvek číslo n + 1. (3.5.2) Dosaďte x = 1. (3.5.3)* Rozepíšeme (1 + x)n+l = (1 + x)(l + x)n = (1 + x)n + x(l + x)n. (3-5.4) C+1) (3.5.5)* f+4) (Uvědomte si nejprve, že Q = ("+1).) (3.6.1) Ano, posledních čtyřčíslí je 10000 a studentů kolem 17000. (3.6.2) Ano, Q < 500. (3.7.1) Indukcí, nebo rozkladem n3 — n = (n — l)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ů. 148 ;3.7.5)* (n-l)3ra+1+3 + (2(n + l) - l)3ra+1 = (n-l)3ra+1 + (2n + l)3ra+1+3 =n3ra+2 + 3 4.1.1) Jedině pokud R obsahuje jen dvojice (a, a) pro a G A, tj. R je relace rovnosti =. ;4.1.2) Ne, 2| - 2 a -2|2, ale 2 ^ -2. 4.1.3) Má, je to výběr některých prvků A, tj. podmnožina. 4.1.4)* Má stále tentýž logický význam, zx 3, třeba jako šestiboký hranol. 7.5.7) a) 28: Ks + Kx+Kl} b) 9: K3 + K3 + K3 + Kx 7.5.8)* Jen v A: graf K3í3 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í K3^. 151 (7.5.13) Ano, ale jen otevřeným. (8.1.1) Vždy konečná - přirozené číslo. (8.1.2) Nekonečno oo. (8.1.3) Ano, na téže nejkratší cestě, která spojovala první dvojici vrcholů. (8.1.4) 1, ale jen 0 pro graf na jednom vrcholu. (8.1.5) 2 (8.1.6) 5 (8.1.7) 3, najdete příslušnou dvojici vrcholů? (8.2.1) Ano, ale jen pokud jsou délky hran kladné. (8.2.2) Vyjde /O 1 2 1\ 10 12 2 10 1 Vl 2 1 O/ (8.3.1) Ano, hrana —4 tvoří kružnici s dalšími třemi hranami váhy 1, takže každou iterací této kružnice snížíme délku o —1. (8.3.2) 5 (8.3.3) 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.4.1) Krok výběru dalšího vrcholu ke zpracování - i když bereme nejbližší nezpracovaný vrchol, z jiného, vzdálenějšího, vrcholu se lze přes hranu záporné délky dostat do vybraného vrcholu "kratší" cestou. (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) Ano, neobsahuje nic, takže neobsahuje ani kružnici, ani jej nelze rozdělit na komponenty. (9.1.2) Jsou to cesty Pn a úplné bipartitní grafy K\,n. (9.1.3) Lze, ale jenom o kružnici. Úplné grafy K\ a Ki totiž stromy jsou. (9.1.4) 3, jeden bez hran, jeden s jednou hranou a poslední strom s dvěma hranami. (9.1.5) 2, cesta P3 a "hvězda" K1>3. 152 (9.1.6)* Nenajdete, to by bylo v rozporu s Důsledkem 9.5. (9.2.1) Prázdný graf - strom. (9.2.2) Nejdelší u cesty Pn - [n/2\ kroků, nejkratší u hvězdy K\,n - 1 krok. (9.2.3)* Centrum vždy bude ležet na té nejdelší cestě. Bude tvořeno jedním vrcholem, pokud je nejdelší cesta sudé délky, a hranou, pokud je liché délky, li (9.2.4) * » 1U 10 * 21 (9.2.5) Centra jsou vyznačená: (9.2.6) 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) Protože vrcholů stejného největšího stupně může být více a nebyli bychom schopni mezi nimi jednoznačně vybrat. (Jinými slovy, vybrali-li bychom mezi více vrcholy stejného stupně, bylo by jen na náhodě, zda se u isomorfních stromů trefíme do stejného kořene. U centra takový problém není.) (9.3.2) ((()(()()()))((()())(()))) (9.3.3) (9.4.1) Nalezneme kostru s největším ohodnocením. (9.4.2) Protože pokud e j G To, ej nevytváří v j-tém kroku algoritmu kružnici, a proto musí být vloženo i do T. (9.4.3) 2004 (9.4.4)* 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. 153 (9.5.9) (™) - n + 1 (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 K\ 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) Prázdný, bez vrcholů. (10.1.2) Také k, použijeme stejné barvy na každou komponentu. (10.1.3) Ne. (10.1.4) 3 (10.1.5) Méně než 4 barvy nestačí, protože najdeme úplný podgraf na 4 vrcholech. Obarvení 4 barvami je snadné. (10.1.6) 1 pokud má jeden vrchol a jinak 2 podle Věty 10.5 - stromy totiž nemají žádné kružnice. (10.1.7) 3 (10.1.8)* 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) Například (10.2.2)* Vrcholovou 2-souvislost - pak takové stěny jako v předchozím příkladě nebudou možné. (10.2.3)* Jako v — e + f = 1 + k. Všimněte si, že za každou novou komponentu sice na pravé straně vztahu "přibude" 2, ale jedna vnější stěna se sdílí dohromady mezi všechny komponenty, a proto skutečně se pravá strana s každou komponentou zvýší o +1. (10.2.4) Je to graf krychle. (10.2.5) v = 12, / = 20, v + / - e = 2, tedy e = 12 + 20 - 2 = 30. (10.2.6) Graf pravidelného osmistěnu. (10.2.7) 3 (10.3.1) Jen pokud m < 2 nebo n < 2, jinak v sobě obsahuje Ks^. (10.3.2) Nemůže platit, jak byste nakreslili smyčku úsečkou? Jak by se dvě úsečky mezi stejnými konci mohly neprotínat? (10.3.3)* Protože nemůže obsahovat podrozdělení K$ and ^3,3, nemá totiž v sobě dost kružnic (viz. Příklad 9.7). (10.3.4) Pron = 1,2,3,4. (10.3.5) Rovinný jen B. (10.3.6) 3 - takto z kružnice délky 6 vytvoříme graf ^3,3, nakreslete si to. (10.4.1) Protože úplný graf K4 je rovinný. (10.4.2) Protože každá lichá kružnice je rovinná a potřebuje 3 barvy. (10.4.3)* Protože každý rovinný graf lze obarvit 4 barvami a mezi 13 vrcholy čtyř barev je jedna barva aspoň na 4 vrcholech, mezi kterými pak nemohou být hrany. 154 A, <> (10 (10 (10 (10 (10 (10 (10 (10 (10 (10 (11 (11. ill. (11 (11 (11. (11. (11 (11 (11 (11 (11 (11 (11 (11 ill. 5.1) 3 5.2) 4, všimněte si, že graf obsahuje K4. 5.3) 3 5.4) 1 5.5)* Buď 13, pokud vypustíme tři hrany jednoho trojúhelníku, nebo 12, pokud vypustíme tři disjunktní hrany. 5.6) Ano, stačí dolní levé dva vrcholy překreslit nahoru. 5.7) Ne, obsahuje podrozdělení Ks^, najdete jej? 5.8) 8 5.9) 11 5.10) Má 10 vrcholů podle Eulerova vztahu. 1.1)* Je to přirozené, neboť množství přenášené substance se dle definice ve všech ostatních vrcholech zachovává. 2.1) Nic zvláštního, stačilo by všechny (stejně orientované!) násobné hrany nahradit jednou a sečíst jejich kapacity. 2.2)* Byl by to jen formální problém - zápornou hranu lze nahradit opačně orientovanou hranou s opačnou (tj. už kladnou) kapacitou. I pokud bychom záporné hrany neobraceli, můžeme použít náš algoritmus, ale záporné hrany by se "sytily" ze záporných hodnot toku na nulu. 2.3) Tok 5. 2.4) Jen zdroj z. i-. -~ 3 1 2.5) Řez velikosti 4 zde: 3.1) Velikosti 5: 3.2) Velikosti 4: i /:. 1 /. 3.3) Ano, reprezentanti jsou zapsaní první: (1,2,3), (2,1,4), (3,1,4), (4,2,3). 3.4) Ne, všech podmnožin je (g) = 10, ale prvků k reprezentaci jen 5. 4.1) 12 4.2) 13 4.3) 11 4.4) 9 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. 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. 155 Reference P. Hliněný, Web stránky předmětu DIM (2004), http://www.es.vsb.cz/hlineny/vyuka/DIM.html. D. Knuth, The Art of Computer Programming, Volumes 1-3, Addison-Wesley Pub Co, 2nd edition 1998. L. Kučera, Kombinatorické Algoritmy, SNTL, Praha, 1983. L. Kučera, Algovize, http://kam.mff.cuni.cz/~ludek/Algovision/Algovision.html. J. Matoušek a J. Nešetřil, Kapitoly z Diskrétní Matematiky, Karolinum, UK Praha, 2000. J. Matoušek and J. Nešetřil, Invitation to Discrete Mathematics, Oxford University Press, 1998. E. Ochodková, Grafové Algoritmy, http://www.es.vsb.cz/ochodkova/courses/gra/. 156