1 Přírodovědecká fakulta DISKRÉTNÍ MATEMATIKA pro učitele Eduard FUCHS MASARYKOVA UNIVERZITA Brno, 2000 Obsah 1 Kombinatorika 3 1 Co to je kombinatorika a kdy vznikla....................... 3 2 Základní kombinatorické funkce......................... 7 3 Základní kombinatorické pojmy......................... 14 4 Rozklady konečných množin........................... 24 5 Princip inkluze a exkluze............................. 31 6 Rozklady přirozených čísel na sčítance...................... 38 7 Rozdělování do přihrádek............................. 45 8 Řešení rekurentních formulí ........................... 48 9 Vytvořující funkce ................................ 59 10 Bloková schémata, latinské čtverce a konečné roviny.............. 69 2 Teorie grafů 86 1 Co to je teorie grafů a kdy vznikla........................ 86 2 Základní pojmy..................................90 3 Souvislé grafy...................................97 4 Stromy.......................................100 5 Mosty, artikulace a některé grafové charakteristiky...............114 6 Eulerovské a hamiltonovské grafy........................119 7 Rovinné grafy...................................126 8 Barvení grafů...................................136 9 Zobecnění pojmu graf...............................146 přílohy 150 Literatura 156 Rejstřík 157 2 Kapitola 1 Kombinatorika 1 Co to je kombinatorika a kdy vznikla Jak uvidíme, neexistuje na otázky v nadpise jednoduchá odpověď. Částečnou odpovědí na první část otázky je — v jistém smyslu — celá první kapitola. Tak jak je obtížné sdělit, co to je vůbec matematika, je nesnadné charakterizovat i její jednotlivé části. Pokusme se alespoň stručně naznačit, co je předmětem kombinatoriky (nazývané též kombinatorická analýza, kombinatorická teorie apod.) a jakými metodami se v kombinatorice pracuje. Často se podle autora jedné z prvních učebnic kombinatoriky E. Netta (kniha Lehrbuch der Combinatorik vyšla v roce 1901) říká, že „kombinatorika je část matematiky zabývající se rozdělováním, uspořádáváním, nebo výběrem prvků nějaké množiny". Z modernějšího hlediska je centrálním pojmem kombinatoriky tzv. konfigurace, což je pojem, který bychom mohli charakterizovat jako „zobrazení nějaké množiny objektů do konečné abstraktní množiny se zadanou strukturou" (viz Bergeovu knihu [1]). Uvedená formulace sice pěkně zní, čtenář z ní však patrně těžko pochopí, co to konfigurace vlastně je. Objasnění tohoto pojmu vyplyne z dalšího textu, neboť v něm budeme studovat řadu nejrozmanitějších konfigurací. Kromě těch nej elementárnějších, tj. variací, permutací a kombinací (čtenáři dobře známých již se střední školy), to budou např. rozklady konečných množin, rozklady přirozených čísel na sčítance, rozdělování předmětů do přihrádek, latinské čtverce, bloková schémata, konečné afinní roviny a další. Jaký je hlavní okruh otázek s těmito konfiguracemi spojený? Konfigurace jsou nejčastěji studovány z následujících aspektů: (1) Existuje jistá konfigurace nebo nikoliv? (Budeme například řešit, zda existují ortogonální latinské čtverce daného řádu, zda existuje jistá afinní rovina a podobně.) 3 4 7. KOMBINATORIKA (2) Kolik existuje předepsaných konfigurací? (Středoškolská kombinatorika v podstatě spočívá v určení počtu variací, permutací a kombinací daného typu. My se však budeme zabývat i podstatně komplikovanějšími problémy.) (3) Lz,e najít metodu, jak vypsat všechny konfigurace daného typu? (Je zřejmé, že jde o kvalitativně odlišnou úlohu než je popsána v bodě (2).) (4) Jaké je „asymptotické" chování počtu daných konfigurací? (Vzhledem k tomu, že budeme téměř neustále pracovat s konečnými množinami, bude počet konfigurací daného typu téměř vždy konečný. Proto by se mohlo zdát, že nejjednodušší určení počtu všech konfigurací spočívá prostě ve vypsání všech možností. To je však ve většině případů prakticky vyloučeno, neboť počet daných konfigurací je tak obrovský, že vypočítat všechny možnosti nelze - stačí si například jen uvědomit, jak rychle roste funkce n\. I když často známe např. rekurentní formuli pro počet k(n) konfigurací daného typu (pro všechna n e N), roste funkce k(n) tak rychle, že již pro poměrně malá n nelze k(n) přesně vyčíslit ani pomocí počítačů. Pak se alespoň snažíme najít nějakou „jednoduchou" funkci, která popisuje, „jak rychle" k(n) roste.) (5) Jak najít z konfigurací daného typu tu, která optimálne vyhovuje zadaným předpokladům ? (Úlohy tohoto typu mají řadu konkrétních aplikací v matematice i mimo ni. Uvedeným problémem se zabývá intenzivně rozvíjená část kombinatoriky - tzv. teorie „kombinatorických algoritmů".) O většině uvedených aspektů se v dalším alespoň stručně zmíníme. Přesto zůstává řada závažných částí kombinatoriky, o nichž nemůžeme pojednat ani ve zkratce. Jmenujme za jiné alespoň kombinatorickou teorii uspořádaných množin, Pólyovu teorii enumerace či teorii kódování. K popsání uvedených teorií nemáme k dispozici dostatečný matematický aparát, ani nám to neumožňuje rozsah tohoto textu. Metody v kombinatorice užívané můžeme rovněž popsat jen částečně. Jak alespoň naznačíme, užívá se v kombinatorice výrazně i těch nejkomplikovanějších metod algebry, reálné i komplexní analýzy i geometrie. Kromě toho si kombinatorika vytvořila i své specifické metody, z nichž se později zmíníme například o metodé inkluze a exkluze a o teorii vytvořujících funkcí. Jak uvidíme, řadu kombinatorických problémů lze velmi snadno zformulovat, avšak jejich řešení je velmi často obtížné. Prozatím jsme se pokusili alespoň naznačit, co to kombinatorika je. Nyní stručně k její historii. První „kombinatorické" výsledky či alespoň náznaky jsou až překvapivě staré. Pravděpodobně nejstarší „konfiguraci" lze nalézt v jednom z nejstarších dochovaných textů v historii 1. Co to je kombinatorika a kdy vznikla? 5 lidstva. V posvátné knize taoismu I-tíng, (tj. Kniha proměn) z roku přibližně 2200 př. n. 1. jsou dvě konfigurace, nazývané Lo-šu a Říční mapa. Na obrázku 1.1 je konfigurace Lo-šu. # #ooooooooo# • o o o o o o o o o o o o o o • o • • • • • o • • • • • • Obr. 1.1: Konfigurace „Lo-šu" Na následujícím obrázku 1.2 je tato konfigurace převzatá ze středověkého textu. 0 < 1 + i ^ Obr. 1.2: Konfigurace „Lo-šu" ve středověkém textu Nahradíme-li znázorněné skupiny bodů čísly, obdržíme známý magický čtverec (nazývaný též Saturn): 4 9 2 3 5 7 8 1 6 6 7. KOMBINATORIKA V tomto čtverci je součet čísel v každém řádku, sloupci i úhlopříčce roven číslu 15. Druhá konfigurace, kterou podle pověsti měla na svém krunýři znázorněnu posvátná želva vylézající z řeky Ho, je znázorněna na obr. 1.3. o o o o o o o o o Obr. 1.3: Konfigurace „Říční mapa" Znázorníme-li toto schéma čísly, obdržíme 7 2 10 10 8 3 5 4 9 10 10 1 6 Toto schéma je pozoruhodné svou „středovou symetrií". Platí například 5 + 3 = 8, 5+1 = 6 atd., 3 +10+ 2 = 8 +7, 3 +10+1 = 8 + 6 atd. Rada kombinatorických pojmů je doložena například ve staré indické matematice. Kombinatorika jakožto matematická disciplína se však začíná konstituovat až cca v 16. až 17. století, prakticky — vcelku evidentně — současně se vznikem teorie pravděpodobnosti. Kombinatorické úvahy lze vysledovat v díle B. Pascala, P. Fermata a dalších. První publikovanou prací z kombinatoriky je Leibnizovo dílo Disertatio de Arte Combinatoria z roku 1666. V 18. století k rozvoji kombinatoriky zvlášť významně přispěl L. Euler. Opravdu bouřlivý rozvoj však kombinatorika prodělává až ve 20. století, zejména pak v posledních třiceti letech, kdy se v souvislosti s rozvojem výpočetní techniky rozvíjí celá tzv. diskrétní matematika, jejíž významnou součástí je právě kombinatorika. 2. Základní kombinatorické funkce 7 2 Základní kombinatorické funkce 2.1. Definice. Funkci n\ (čti n faktoriál) definujeme pro všechna n e No takto: II pro n = 0 1 • 2 • ... • n pro n > 0. Pro všechna w e No tak platí: (n + l)\ =(n+l)-n\ 2.2. Příklad. Pro funkci n \ lze dokázat řadu vztahů, od elementárních po velmi komplikované. Například v matematické analýze se dokazuje, že ~ 1 1 1 1 ^ n\ 0! 1! n\ n=0 (Připomeňme, že součtem nekonečné řady an rozumíme následující limitu (pokud existuje): lim sn, kde sn = a^ + a\ + ■ ■ ■ + an.) n—?oo Odtud například plyne oo 1oo t oo1oo1 En — í x—v í x—v í x—v í ^ = Et—7T7-E^ = E^-^-2) = ^-1)-^-2) = 1-n\ Á—' (n — 1)! z—' n\ Á—' n\ n=2 n=2 n=2 n=\ 2.3. Poznámka. Zobecněním funkce n\ na všechna kladná reálná čísla je tzv. Eulerova funkce gama definovaná takto: oo 0 Lze dokázat, že pro každé přirozené číslo n platí: T(n) = (n — 1)!. Funkce T(x) je přitom spojitá v celém definičním oboru. Hodnoty n \ rostou s rostoucím n „velmi rychle". Pro alespoň částečnou představu uvádíme v tabulce na straně 151 hodnoty n\ pro n e {1, ..., 25}. K přibližnému výpočtu hodnot n \ pro velká n se nejčastěji užívá tzv. Stirlingovy formule ú ~ V2Ťrrä • e~n ■ n", 8 7. KOMBINATORIKA kde symbol ~ značí, že podíl výrazů na obou stranách pro n —> oo konverguje k 1. 2.4. Definice. Bud k e N libovolné. Funkci (x)k definujeme pro všechna reálná x takto: (x)k = x ■ (x — 1) • (x — 2) • ... • (x — k + 1). Dále klademe (x)0= 1. 2.5. Definice. Bud k e N libovolné. Funkci (x)(i) definujeme pro všechna reálná x takto: (x)w = x • (x + 1) • (x + 2) • ... • (x + k - 1). Dále klademe (x)(0)= 1. 2.6. Definice. Buď k e No libovolné. Pro každé reálné číslo x definujeme x\ (x)k x ■ (x — 1) • (x — 2) • ... • (x — & + 1) £7 jfc! jfc! Pro celé záporné číslo k pokládáme 2.7. Poznámka. Symbol (*) (čti „x nad k") se obvykle nazývá binomický koeficient. (Toto pojmenování je spojeno se jménem významného algebraika 16. století Michaela Stifela.) Pro n, k e No se (^) nazývá také kombinační číslo. O kombinatorickém významu funkcí w!, {x)k, (x)(i) a (^) budeme hovořit v následujících paragrafech. 2.8. Příklad. (a) Pro každé x e M platí Q = 1, zejména Q = 1. (b) (1)=(-4)-(-5)-(-6)=-20. (c) (I) = k (I) • (4) • (-1) • (Í) 4/ 24 128 5 (d) Pro n, k e N0, n < k platí Q = 0, neboť (ra)* = 0. 2. Základní kombinatorické funkce 9 (e) Pro n, k e N0, n > k platí ("k) = ^* "! Jk! (n-k)!-k! (f) Pro každé ra e N0 platí =i\ = ^ /2n\ = (-1T /2n - 1 n) 22n U/ 22"-1 U-l Vskutku, pro n = 0 je tvrzení evidentní. Nechť je tedy n > 0. Pak -i 2i 1 / 1\ / 3\ / 2/i-3\ / 2/i-l w / w' V 2/ \ 2/ \ 2 / \ 2 1 (-1)" (2n)! _ (-1)" (2n)! n! 2" ' 2-4-...-(2/i-2)-2/i ~ 22" '(n!)2 (-1)" /2/A (-1)" (2n - ť 22" \ n ) 22"-1 \n-l (g) Pro každé n e No platí i\ _ (-I)"'1 (2n - 2 Kn/ n ■ 22n 1 \ n — 1 Vskutku, podle definice platí i\ _ 1 /1 \ / 1 \ í 2n Kn) n\ \ 2 / \ 2, Dosadíme-li za součin n\'\ 2J'\ 2, výraz z příkladu (f), dostáváme lx (-I)"-1 (2n - 1\ 1 22"-1 \ n - 1 J 2w-l (-1)"-1 (2n-l)! 1 _ (-I)""1 (2n-2)! 22"-1 ' nl(n - 1)! ' 2ra - 1 ~ n • 22"-1 ' (n - l)!2 (-1)"-1 (2n-2^ n ■ 22"-1 \ n — 1 Dosadíme-li do posledního vztahu n +1 místo ra, obdržíme „symetričtější" vzorec (platný pro každé n e No): (-1)" /2zi w + 1/ (w + 1) • 22n+1 V n 10 7. KOMBINATORIKA 2.9. Definice. Podle definice je (x)„ = x(x — l)(x — 2)... (x — n +1) polynom ra-tého stupně. Označíme-li koeficient u xk symbolem s(n,k), dostáváme Koeficienty s(n,k) se nazývají Stirlingova čísla 1. druhu. 2.10. Věta. Pro Stirlingova čísla 1. druhu platí následující rekurentní formule: s(n + 1, k) = s(n, k — 1) — n ■ s(n, k), s(n,0) = s(n,n) = 1. Důkaz. Tvrzení s (n, 0) = s (n, n) = 1 je zřejmé. Dokažme tedy první vztah. Podle definice platí (x)„+1 = (x)„ • (x - n), takže, opět podle definice, • • • + s(n + 1, k)xk + ••• = (••• + s(n, k — l)xk~l + s(n, k)xk + . .. )(x — n). Porovnáním koeficientů u xk na levé a pravé straně poslední rovnosti obdržíme dokazovanou formuli. • 2.11. Poznámka. Rekurentní formule z věty 2.10 nám umožňuje, jak se čtenář může snadno přesvědčit, postupně počítat čísla s(n, k). Některé hodnoty uvádíme v tabulce na straně 153. 2.12. Věta. Pro každé celé číslo k a každé reálné číslo x platí: (x)„ = s(n, 0) + s(n, l)x + s(n, 2)x + • • • + s(n, ri)xn. Důkaz. Pro k < 0 je tvrzení splněno triviálně. Nechť tedy je k > 1. Pak (k + 1) • x(x — 1) • • • (x — k + 1) + x(x — 1) • • • (x — k) (*+l)! x(x — 1) • • • (x — k + 1) • (k + 1 + x — k) (*+l)! = (x + l)k+i _ íx+ 1\ (Jfc+1)! ~\k+l)' Tím je důkaz hotov. 2. Základní kombinatorické funkce 11 2.13. Poznámka. Z definice binomických koeficientů a z věty 2.12 plyne platnost následující rekurentní formule: Pro n, k e N, n > k platí Tato formule nám umožňuje postupně počítat hodnoty (^). Tabulce hodnot (^) se obvykle říká Pascalův trojúhelník. (Viz tabulku v příloze na straně 152.) Jak si čtenář jistě již při nejrůzněj-ších příležitostech uvědomil, je většina pojmů nazvaných po dřívějších osobnostech, po nich pojmenována neoprávněně. Nejinak tomu je i v tomto případě, byť jde o název v evropské tradici obvyklý. Blaise Pascal (1623-1662) toto schéma popsal ve své slavné knize Traité du triangle arithmétique (tj. Pojednání o aritmetickém trojúhelníku), avšak prokazatelně dříve je znali například arabský astronom al-Tusi (1265), čínský matematik Chu Si-Chie (1303) či indický matematik Narajána Pandita (1365). Dokonce i v evropské literatuře se toto schéma vyskytlo před Pascalem - v knize Petra Apiana (1495-1552). To však nic nemění na skutečnosti, že je toto schéma mnohdy užitečné, jak si ostatně čtenář jistě uvědomil již na střední škole. Pro kombinační čísla lze dokázat řadu rovností, tzv. kombinatorických identit, které se v matematice uplatňují v nej neočekávanějších souvislostech. Důkazy některých těchto identit vyžadují důmyslných metod — viz např. knihu [6]. V následující větě shrneme jen několik nej elementárnej ších. 2.14. Věta. Buďte n > k nezáporná celá čísla. Pak platí: oo CD = C-J. (b) Í 0 = 2"> k=0 (c) £k-(Ů = n-2»-\ n (d) XX-1)*© = 0 Pro každé přirozené číslo n. k=0 Důkaz, (a) Tvrzení plyne přímo z definice. (Řádky Pascalova trojúhelníka jsou tedy „symetrické".) (b) Indukcí. Pro n = 0 je tvrzení triviální. Nechť tedy formule platí pro dané n > 0. Pak k=o v 7 k=l n\ x—v /n\ I n k) + u + 1. 12 7. KOMBINATORIKA k=0 (c) Protože Q = (n"_k), platí = 2" + 2" = 2n+1. fn\ í n \ ín\ n Odtud i=0 k=0 , = - -2" = n ■2"-1. k 2 (d) Přímým výpočtem dostáváme n-l\ ín-l k - 1/ + V k n-1 i=0 n-1 7 i=i v n-1 k=0 n - 1 n-l i=0 n - 1 = 0. Často je užívána i následující formule. 2.15. Věta. Pro každé reálné x a každé n e No platí ť x + k E k=0 x\ /x+l\ /x + 2\ íx+n 0 H 1 H 2 + " + n x + n + 1 Důkaz. Indukcí. Pro n = 0 je rovnice správná. Nechť tedy uvedený vztah platí pro n > 0. Pak n+l E /fc=0 X + & ■^-^ íx + k\ /x + n + 1 = k ) + { n + l x + ra + 1\ /x + w+1 n I \ n + 1 x + n + 2 n+l Dosadíme-li ve větě 2.15 n — k místo & a x místo x + n, dostaneme okamžitě tvrzení následujícího důsledku. 2. Základní kombinatorické funkce 13 2.16. Důsledek. Cvičení 1. Dokažte, že n £(*■*!) = (n+1)!-1. k=l 2. Dokažte, že pro Stirlingova čísla 1. druhu platí vztah n ^s(n,k) = 0, n > 1. k=l 3. Dokažte identitu k=0 \ / \ / \ / k=1 4. Tzv. Catalanovu posloupnosti, 2, 5, 14, 42, 132, 429, 1 430, 4 862, ... definovanou vztahem c -Ä n + 1 studoval již Euler. Dokažte, že platí: a) c2 = 2ci b) c3 = 3c2 - ci C) C4 = 4c3 — 3c2 d) c5 = 5c4 — 6c3 + c2 e) c6 = 6c5 — ioc4 + 4c3 f) c7 = 7c6 — 15C5 + ioc4 — c3 «»=(** - ř2" - ó=ŕ2") - (^ j \ ra — 1 / \ n+l J \n J \n — 1 / _ (2ra + 2) • (2n + 1) h) cn+l — Z 77" ' 77 ' cn (n + 2) • (n + 1) 14 7. KOMBINATORIKA 3 Základní kombinatorické pojmy Nejprve zavedeme označení, které budeme v celém dalším textu dodržovat. 3.1. Označení. Kardinální číslo konečné množiny X značíme \X\. Symbolem P(X) označíme, jak je obvyklé, množinu všech podmnožin množiny X. Pro k e No označme Pk{X) = {A\ A c X,\A\=k}. Mnoho kombinatorických úvah je založeno na následujícím zřejmém faktu. 3.2. Věta. Buďte A, B konečné množiny. Pak \A x B\ = \A\ ■ \B\. 3.3. Poznámka. Jinými slovy je věta 3.2 často formulována jako tzv. pravidlo součinu následovně: Lze-li objekt X vybrat r způsoby a po každém takovém výběru lze objekt Y vybrat s způsoby, pak lze uspořádanou dvojici [X, Y] vybrat r ■ s způsoby. Jako aplikaci věty 3.2 uveďme tvrzení, které v roce 1935 odvodili maďarští matematikové P. Erdôs a G. Szekeres. 3.4. Věta. Každá posloupnost a\, a^, ■ ■ ■, amn+i mn + 1 navzájem různých celých čísel nutně obsahuje klesající vybranou podposloupnost o více než. m prvcích nebo rostoucí vybranou podposloupnost o více než. n prvcích. Důkaz. Pro každé i = 1,2, ..., mn + 1 označme kt počet čísel v nejdelší klesající pod-posloupnosti s prvním prvkem a, a analogicky nechť r, je počet prvků v nejdelší rostoucí podposloupnosti začínající prvkem a,. Předpokládejme, že tvrzení věty neplatí. Pak pro každé i platí 1 < k, < m, 1 < r, < n, takže zobrazení a, -> [kt, r,] je zobrazením množiny {a\, a^, ■ ■ ■, amn+i} do kartézského součinu {1,2, ... ,m] x {1,2, ... ,n}. Ukážeme, že toto zobrazení je prosté. Nechť je i < j. Pak platí a, < a j nebo a, > a j (neboť čísla at, a j jsou podle předpokladu různá). Je-li a, < a j, pak platí zřejmě r, > ry, je-li at > a j, platí zase kt > k j. V obou případech je [ki, r,] ý [k j, r7-]. To je však spor, neboť nemůže existovat injekce množiny o mn + 1 prvcích do množiny o mn prvcích. • 3.5. Definice. Buďra e N, |X| = n. Pro k e N, k < n nazveme variacík-té třídy v X každý řetězec (A, <), kde A e Pk(X). 3.6. Věta. Buďte k < n přirozená čísla. Nechť \X\ = n. Počet variací k-té třídy v X je roven číslu (w)i = n ■ (n — 1) • .. . • (n — k + 1). 3. Základní kombinatorické pojmy 15 Důkaz. Tvrzení plyne z pravidla součinu. První prvek lze vybrat n způsoby, druhý n — 1 způsoby atd. • 3.7. Poznámka. Počet uspořádaných k-úc bez opakování z n prvků je tedy roven číslu (n)^ pro libovolná n,k & N (neboť pro k > n je (n)^ = 0 podle definice). 3.8. Důsledek. Buďte X, Y konečné množiny, \X\ = k, \Y\ = n. Pak pro množinu inj (XY) všech injekcí X do Y platí \mi(X¥)\ = (n)k. 3.9. Definice. Variace n-té třídy z n prvkové množiny se nazývají permutace této množiny. Z věty 3.6 okamžitě plyne. 3.10. Věta. Počet permutací n prvkové množiny je roven číslu (n)n = n \. 3.11. Poznámka. Je-li X = {1, 2, ..., n], je podle definice permutací množiny X každý řetězec {a\ < a^ < • • • < a„], kde a, e X pro každé i. Zapíšeme-li tento řetězec jako uspořádanou ra-tici [ a\, a^, ..., a„ ], můžeme danou permutaci ztotožnit se zobrazením i —»- a,. Toto zobrazení je obvyklé zapisovat ve tvaru 1 2 ... n a\ a2 ... an Jinými slovy, za permutace množiny X můžeme považovat bijekce množiny X na sebe. Odtud a z věty 3.10 okamžitě plyne 3.12. Důsledek. Buďte X, Y konečné množiny. Pak pro množinu bij (Yx) všech bijekcí X na Y platí , y i Í0 je-li \X\ ý\Y\, bij(7x) = \ J 1 1 je-li \X\ = \Y\. 3.13. Definice. Buď X konečná množina, k e No buď libovolné. Kombinací k-té třídy z X rozumíme každou k prvkovou podmnožinu množiny X. (Množina /Pk(X) je tedy množinou všech kombinací &-té třídy z X.) Z vět 3.6 a 3.10 bezprostředně plyne 16 7. KOMBINATORIKA 3.14. Věta. Buď X konečná množina, \X\ = n. Pak pro každé k e No platí (n) í ín\ lft(X)l = ir = U- 3.15. Příklad. Kolika způsoby můžeme na šachovnici (o 64 polích) rozestavit 8 věží tak, aby se žádné dvě z, nich vzájemně neohrožovaly! Tomu, kdo ví, jak v šachu tahá věž, je zřejmé, že hledáme právě všechna taková rozestavění věží, kdy v každé řadě a v každém sloupci stojí právě jedna věž. Očíslujeme-li pevně řady a sloupce čísly 1, ..., 8, je poloha každé figury na šachovnici jednoznačně určena dvojicí [i, j], kde i je číslo řady a j číslo sloupce. Odtud je zřejmé, že hledaných rozestavení je 8! = 40 320. 3.16. Příklad, (a) Kolika způsoby můžeme rozestavit 6 dětí do kruhu! Do řady lze rozestavit 6 dětí 6! = 720 způsoby. Protože z každé řady utvoříme evidentním způsobem kruh, je počet takto vzniklých kruhů rovněž 720. Vzhledem k tomu, že však nerozlíšime dva kruhy lišící se jen pootočením, je hledaný počet ™ = 120. (b) Kolik náhrdelníků lze utvořit z,e 6 korálků 6 různých barev! Mohlo by se zdát, že podle (a) je správná odpověď 120. Protože však nerozlíšime dva náhrdelníky, z nichž jeden vznikl „převrácením" druhého, je hledaný počet ^ = 60. 3.17. Příklad. Buď A množina všech možných pořadí 16 oddílů v 1. fotbalové lize. Pro x, y & A položme x ~ y ^=>- v x, y je stejné pořadí na prvních třech místech a stejné dva oddíly sestupují. Určete |A/~|. Ze zadání plyne, že \A\ = 16!. Relace ~ je zřejmě ekvivalence na A, takže má smysl se ptát po počtu prvků faktormnožiny A/~. Protože pořadí mužstev na prvních třech místech je možno určit (16)3 způsoby a ze zbývajících mužstev můžeme dvě sestupující určit ) způsoby, platí /13\ 13-12 |A/-.| = (16)3 ■ í ) = 16 ■ 15 ■ 14 ■ —j— = 262080. Prozatím jsme hovořili o variacích, permutací a kombinacích bez opakování. Nyní budeme uvažovat případy, kdy se prvky dané množiny mohou v uvedených výběrech opakovat. 3.18. Definice. Buď X konečná množina, \X\ = n. Pro libovolné k e No označme V (n, k) počet všech uspořádaných k-úc prvků z X, v nichž se tyto prvky mohou opakovat. Tyto &-tice nazýváme k-variace s opakováním z prvků množiny X. 3.19. Věta. Pro každé n, k e No platí V (n,k) = nk. 3. Základní kombinatorické pojmy 17 Důkaz. Indukcí vzhledem k číslu k. Tvrzení V (n, 0) = n° = 1 je zřejmé. Nechť tedy V (n, k) = = nk. Buď [ a\, ..., a/c ] libovolná ^-variace s opakováním. Je zřejmé, že počet (k + l)-variací tvaru [a\, ..., ak, x ] je roven číslu n. Odtud plyne, že V (n, k + 1) = n ■ V (n, k) =n-nk = nk+1. • 3.20. Příklad. Buďte X, Y konečné množiny. NechťX = {a\, ..., ak\. Přiřadíme-li každému zobrazení f:X—>Y uspořádanou &-tici [ f(a\), ..., /(a^) ], vidíme okamžitě, že \YX\ = V(\X\,\Y\) = \Y\^. 3.21. Definice. Buď íěN libovolné. Buď dáno n předmětů k druhů. Nechť w, značí počet předmětů /-tého druhu, i = 1, ..., k. (Tj. n\ + • • • + ra* = n.) Symbolem P(n\, ..., n^) označme počet prvků množiny všech uspořádaných ra-tic těchto předmětů. Tyto ra-tice nazýváme permutace s opakováním. Z věty 3.10 okamžitě plyne 3.22. Věta. Pro každá čísla n\, ..., n^ e No platí («! + •• • + nky. P {ni, ■ ■■ ,nk) = 3.23. Příklad, (a) Kolik různých čísel lze utvořit z čísla 3 855 835 přeskupením cifer? Protože dané číslo obsahuje dvě cifry 3, tři cifry 5 a dvě cifry 8, je hledaný počet 7! P(2,3,2) =-= 210. 2! • 3! • 2! (b) Když Christian Huygens objevil Saturnův prstenec, zašifroval svůj objev, jak bylo v té době časté, do následujícího tzv. anagramu: aaaaaaa ccccc d eeeee g h iiiiiii 1111 mm nnnnnnnnn oooo pp q rr s ttttt uuuuu Náležitým uspořádáním písmen dostaneme zprávu Annulo cingitur tenui, piano, nusquam cohaerente, ad eclipticam inclinato. Česky Obklopen prstencem tenkým, plochým, nikde nezaveseným, nakloněným k ekliptice. Určíme, za jak dlouho by počítač, který by vypsal milión permutací Huygensova anagramu za sekundu, vypsal všechny permutace. 18 7. KOMBINATORIKA Spočtěme, kolik je všech permutací daného anagramu. Z počtu jednotlivých písmen v anagramu plyne, že všech permutací je 62! P(7,5, 1,5, 1, 1,7,4,2,9,4,2, 1,2, 1,5,5) = 9! • (7!)2 • (5!)4 • (4!)2 • (2!)3' Toto číslo je přibližně rovno číslu 3,573 • 1060. Počítač by tedy potřeboval více než 1054 sekund. O velikosti tohoto čísla si uděláme představu, když si uvědomíme, že trvání našeho vesmíru — tj. přibližně 15 miliard roků —je méně než 1017 sekund. 3.24. Poznámka. Zajímavé aplikace čísel P( n\, ..., nk) lze najít například v úvahách o tzv. svazu k-tic. Buď& přirozené číslo. Symbolem Nq označme množinu všech uspořádaných k-úc \a\, ..., ak] nezáporných celých čísel. Defmujeme-li na Nq relaci < takto: [ a\, ..., ak ] < [ b\, ..., bk ] <í==^ cii < bt pro všechna i = 1, ..., k, je zřejmé, že relace < je uspořádání na množině Nq- Přitom je evidentní, že (Nq , < ) je svaz, v němž sup {a, Z?} = [ max (a\, b\), ..., max (ak, bk) ], iní{a,b} = [ min (a\, b\), ..., min (a^, b^) ]. Svaz Nq můžeme reprezentovat následujícím způsobem. Bod [ a\, ..., a^ ] e Nq znázorníme jako bod eukleidovského prostoru e* a dva body a = [ a\, ..., a^ ], b = [ b\, ..., ] spojíme šipkou směřující z a do b právě tehdy, když existuje index i takový, že pro j jí i, pro j = i. (Tzn., že z a do b vede šipka práve tehdy, když a pokrývá b ve svazu (Nq , <).) Nyní se pokusme určit počet „cest" z bodu a do bodu b pro každé dva prvky a, b e Nq, a < b. (Cestou rozumějme posloupnost na sebe napojených šipek.) Tak například v Nq existuje 10 cest z bodu 032 do bodu 000 znázorněných v tabulce 1.1. Buďte nyní a = [ a\, ..., a* ], b = [ b\, ..., b^ ] libovolné dva prvky v Nq , takové, že a < b. Označme a,■ — b,■ = n,■, i = 1, ..., k. Definujme pro i = 1, ..., k zobrazení a,: Nq —»- Nq takto: at[xi, . .. ,xk ] = [xi, . .. ,Xí-i,Xí - l,xI+1, ...,xk]. Nyní přiřaďme každé cestě z a do b odpovídající posloupnost zobrazení a,-. (Tak např. cestě z bodu 032 do bodu 000 uvedené na prvním řádku v tabulce 1.1 odpovídá posloupnost 3. Základní kombinatorické pojmy 19 032 -> 022 -> 012 -> 002 -> 001 -> 000 032 -> 022 -> 012 -> 011 -> 001 -> 000 032 -> 022 -> 012 -> 011 -> 010 -> 000 032 -> 022 -> 021 -> 011 -> 001 -> 000 032 -> 022 -> 021 -> 011 -> 010 -> 000 032 -> 022 -> 021 -> 020 -> 010 -> 000 032 -> 031 -> 021 -> 011 -> 001 -> 000 032 -> 031 -> 021 -> 011 -> 010 -> 000 032 -> 031 -> 021 -> 020 -> 010 -> 000 032 -> 031 -> 030 -> 020 -> 010 -> 000 Tabulka 1.1: Cesty z bodu 032 do bodu 000 «2, «2, «2, «3, «3, poslední cestě pak posloupnost «3, «3, «2, «2, «2-) Je zřejmé, že popsané přiřazení je bijekcí množiny cest z a do b na množinu všech posloupností utvořených z a, tak, že se v nich a, vyskytuje w, -krát. Odtud plyne, že hledaných cest je . .. , nk) = (al - b^l ■ ... ■ (ak - bk)l 3.25. Definice. Mějme dostatečný počet prvků n druhů. Symbolem C (n, k) označme počet všech možností, jak z těchto předmětů vybrat skupinu vytvořenou z k objektů (bez ohledu na pořadí). Těmto skupinám říkáme k-kombinace s opakováním. 3.26. Věta. Pro každé n, k e No platí C (n,k) = ("+^ :). Důkaz. Pro n = 0 nebo k = 0 je tvrzení triviální. Nechť tedy n ý 0 7^ k. Každou &-kombinaci s opakováním lze velmi jednoduše (a jednoznačně) popsat pomocí posloupnosti nul a jedniček takto: nechť je dána posloupnost a\,ai, ■ ■ ■, ak+„-i, v níž je k jedniček a n — 1 nul. Přiřaďme této posloupnosti &-kombinaci s opakováním, v níž je tolik předmětů 1. druhu, kolik jev dané posloupnosti jedniček před první nulou, tolik předmětů druhého druhu, kolik jev dané posloupnosti jedniček mezi první a druhou nulou atd. Zřejmě nyní platí: (n + k—l)\ ín + k—l\ ín + k — l C(n,k) = P(k,n- 1) = ' * ' k\(n - 1)! V k ) \ n - 1 20 7. KOMBINATORIKA 3.27. Příklad. Buďte X, Y konečné řetězce. Zjistíme, kolik existuje izotonních zobrazení X do Y. Nechť X = {xi < X2 < • • • < Xk], Y = {yi < j2 < • • • < yn}- Buď f:X—>Y izotonní zobrazení. Pak platí f(x\) < f(xi) < ... < f(xk), takže izotonních zobrazení X do Y je tolik jako všech neklesajících k-úc prvků z Y. To, že &-ticím (v nichž se prvky mohou opakovat) předepíšeme pevně pořadí, je totéž, jako když pořadí prvků v &-ticích nerozlišujeme. Podle věty 3.26 je tedy izotonních zobrazení X do Y 3.28. Příklad, (a) Kolika způsoby můžeme mezi 4 chlapce rozdělit 50 stejných kuliček! Postupujeme jako v důkazu věty 3.26. Přidejme k 50 kuličkám 3 kamínky. Poskládáme-li kuličky s kamínky do řady, rozdělí 3 kamínky posloupnost na 4 úseky. Označíme-li chlapce A, B,C, D a chlapci A dáme všechny kuličky z prvního úseku, chlapci B všechny kuličky z druhého úseku atd., je ihned zřejmé, že všech rozdělení je (b) Pozměňme příklad (a) tak, že budeme požadovat, aby každý chlapec dostal alespoň jednu kuličku. Podle (a) tedy chceme zjistit, v kolika posloupnostech 50 kuliček a 3 kamínků nejsou žádné dva kamínky vedle sebe a rovněž není kamínek ani na prvním ani na posledním místě posloupnosti. Tento počet zjistíme jednoduchým obratem. Dáme-li každému chlapci předem jednu kuličku, zůstane jich 46, které pak již můžeme rozdělit libovolně. Hledaných rozdělení je tak Následující úloha je velmi jednoduchá, v dalším se však na ni budeme několikrát odvolávat. 3.29. Příklad. Mějme p prvků 1. druhu a q prvků 2. druhu. Kolik existuje permutací s opakováním těchto prvků takových, ž.e žádné dva prvky 1. druhu nestojí vedle sebe! Hledaných permutací je zřejmě tolik, kolika způsoby lze rozmístit p prvků 1. druhu do q — 1 mezer mezi prvky 2. druhu a před první a za poslední z nich, tj. celkem na q + 1 míst. Tzn., že hledaný počet je (9+ ) pokud je p < q + 1 a je roven 0, pokud p > q + 1. 3. Základní kombinatorické pojmy 21 3.30. Příklad. Buď dán (c + m)-úhelník A\, A2, ■ ■ ■, Ac+m, kde c, m e N, c + m > 3. Kolika způsoby lze obarvit jeho vrcholy tak, aby jich bylo c červených, m modrých a žádné dva sousední vrcholy nebyly červené! Označme hledaný počet obarvení t (c, m). Je zřejmé, že pro c > m je t (c, m) = 0. Nechť tedy c < m. Úlohu lehce vyřešíme pomocí úlohy 3.29. Označíme-li výsledek příkladu 3.29 symbolem r (p, q), je zřejmě takových „přípustných" obarvení vrcholů, při nichž je vrchol A\ červený, celkem r (c — 1, m — 2). Přípustných obarvení, při nichž je A\ modrý, je r (c, m — 1). Odtud t (c, m) = r (c — 1, m — 2) + r (c, m — 1) 3.31. Příklad. Muž prodávající Večerník (za 5 korun) u sebe nemá na začátku prodeje žádné peníze. Ihned se před ním utvořila fronta m + k lidí, přičemž, m lidí má u sebe pouze desetikorunovou minci a k lidí pouze pětikorunu. Kolika způsoby se tito lidé mohou postavit do fronty tak, aby měl prodávající vždy nazpět na desetikorunu! (Rozlišujeme rozestavení „pětikorun" a „desetikorun" a nikoliv jednotlivé lidi se stejnou mincí.) Počet všech možných rozestavení „pětikorun" a „desetikorun" do fronty je počet příslušných permutací s opakováním, tj. (m + k)\ ím+k\ P(m,k) = --- = m\-k\ \ k J Dále je zřejmé, že úloha má alespoň jedno řešení právě tehdy, když m < k; jinak se totiž prodej nutně zastaví. V dalším tedy předpokládáme, že platí 0 < m < k. Každé rozestavení lidí ve frontě můžeme evidentně zapsat jako posloupnost m jedniček (označujících lidi s desetikorunou) a k pětek (označujících lidi s pětikorunou). Podle zadání hledáme počet „příznivých" permutací, tj. takových permutací (a\, ..., a^m) m jedniček a k pětek, které mají následující vlastnost: pro každé d takové, žel• U c V). rozkladech. Bq přitom značí počet rozkladů, kdy a leží ve třídě o mohutnosti n + 1, tj. Bq = 1. Počet všech rozkladů na X\ je roven součtu všech výše uvedených možností. To je však právě dokazovaná formule. • 4. Rozklady konečných množin 25 4.3. Příklad. Z rekurentní formule 4.2 okamžitě plyne: B0 = l,Bi = 1, B2 = 2,B3 = 5, B4 = 15, B5 = 52, B6 = 203, ... 4.4. Poznámka. Podle příkladu 4.3 existuje na 4-prvkové množině {a, b, c, d] celkem 15 rozkladů. S uspořádáním popsaným v úvodu paragrafu tvoří tyto rozklady úplný svaz, jehož hasseovský diagram je na obr. 4.4. [a,b,c,d} a},{b,c,d} {b},{a,c,d} a},{b},{c,d} {a},{c},{b,d} {a},{d},{b,c} {b},{c},{a,d} {b},{d},{a,c} {c},{d},{a,b} a},{b},{c},{d} Obr. 4.4: Svaz rozkladů čtyřprvkové množiny Podle počtu prvků v jednotlivých třídách výše uvedeného rozkladu je nej větší prvek prvkem „typu" 4, nejmenší prvek je prvkem typu 1+1+1+1, pod největším prvkem leží rozklady typu 1+3, respektive 2+2 a konečně nejmenší prvek pokrývají prvky typu 1+1+2. Tento intuitivně zcela zřejmý popis nyní precizujeme. 4.5. Definice. Buď A konečná množina. Nechť rozklad A obsahuje A, tříd mohutnosti i, (i = 1, ..., k) a neobsahuje třídu o mohutnosti větší než k. Pak říkáme, že A je rozklad typu 1 + 1 + -- - + 1+ 2 + 2+ -- -+ 2+---+& + &+ -- - + &. nebo též typu lll2l2 ...kkk. 26 7. KOMBINATORIKA 4.6. Příklad. Rozklad množiny {1, 2, 3, 4, 5, 6} na třídy {1}, {2, 4}, {3, 6}, a {5} je rozklad typu 1+1+2+2 nebo též typu 1222. 4.7. Věta. Počet rozkladů typu Ý~x2}"2 .. . klk na n-prvkové množině je roven číslu n\ • (2!)^ ... (k\)}* ■Xl\-X2\...Xk\ pokud X\ + 2Á2 + • • • + fcA,* = n. Je-li X\ + 2Á2 + • • • + fcA,* 7^ ra, je počet rozkladů uvedeného typu roven nule. Důkaz. Je zřejmé, že rozklad typu lk*2k2... kkk na ra-prvkové množině existuje právě tehdy, když Aj + 2X2 + • • • + kkk = n, neboť počet prvků jednotlivých tříd je roven počtu prvků celé množiny (neboť třídy rozkladu jsou po dvou disjunktní). Určeme tedy počet rozkladů daného typu za předpokladu Áj + 2X2 + • • • + kXk = n. Každý rozklad typu lkl2kl... kkk vznikne tak, že v následujícím schématu k k {x}, . .. , {x}, {x, X }, . .. , {x, X }, . .. , {x, X, . . . , X }, . .. , {x, X, . . . , X } místo x vepíšeme postupně nějakou permutaci prvků dané w-prvkové množiny. Těchto permutací je n\. Různé permutace však neudávají nutně různé rozklady. Především udávají týž rozklad permutace, lišící se jen pořadím tříd o stejné mohutnosti. Protože tříd o mohutnosti i je A,, můžeme z těchto tříd utvořit A,! různých permutací. Celkový počet n\ všech permutací je proto nutno vydělit číslem X\! • X2I... X^l. Pořadí prvků v každé třídě rozkladu, která má i prvků, lze zapsat i! možnostmi. Protože těchto tříd je A,, můžeme pořadí prvků ve všech těchto třídách zapsat celkem /! ■ il... i! = (i!)^' způsoby, aniž se změní množiny, tvořící jednotlivé třídy. Celkový počet permutací je tak nutno vydělit ještě číslem (l!)^1 • (2l)kl... (kl)kk. Odtud již plyne dokazované tvrzení. • 4.8. Příklad. Na čtyřprvkové množině má podle věty 4.7 existovat 4! (I!)2 • (2!)1 -2! • 1! ~ rozkladů typu 1221. Na obrázku 4.4 vidíme, že tomu tak opravdu je. 4.9. Definice. Buďte n > m přirozená čísla. Označme S(n, m) počet rozkladů w-prvkové množiny na m tříd. Čísla S(n, m) se nazývají Stirlingova čísla 2. druhu. Dále defmitoricky klademe 5(0, 0) = 1, 5(0, n) = 0 pro n e N. 4. Rozklady konečných množin 27 4.10. Příklad. Z obrázku 4.4 je vidět, že například 5(4, 2) = 7. 4.11. Věta. Buďte X, Y neprázdné konečné množiny, \X\ = n, \ Y\ = k, n > k. Pak pro množinu surj (Yx) všech surjekcí X na Y platí |surj(7x)| =k\ ■ S(n,k). Důkaz. Buď /: X —> Y surjekce. Tato surjekce určuje rozklad množiny X na k tříd; jednotlivé třídy jsou úplné vzory prvků množiny Y. Každý rozklad množiny X na k tříd přitom určuje kl surjekcí X na Y. Odtud plyne tvrzení. • 4.12. Věta. S(n + 1, k) = S(n, k — 1) + k ■ S(n, k) pro 1 < k < n, S(n,n) = S(n, 1) = 1. Důkaz. Představme si všechny rozklady (n + l)-prvkové množiny {a\, ..., a„+i} na k tříd. V některých rozkladech tvoří prvek a„+1 jednoprvkovou třídu. Těchto rozkladů je S(n, k — 1). Ve všech ostatních rozkladech je prvek a„+1 prvkem některé třídy o více prvcích. Prvek a„+1 je tedy v těchto rozkladech přidán k některé třídě rozkladu množiny {a\, ..., an} na k tříd. Těchto rozkladů je S(n, k) a prvek an+\ můžeme přidat ke kterékoliv z uvedených k tříd. Odtud plyne dokazovaná formule. • 4.13. Poznámka. Rekurentní formule z věty 4.12 nám umožňuje postupně počítat hodnoty čísel S(n,k). V tabulce na straně 154 uvádíme některé hodnoty Stirlingových čísel druhého druhu. Této tabulce se také říká Stirlingův trojúhelník. Z Pascalova a Stirlingova trojúhelníka lze snadno odvodit tabulku 1.2, shrnující výsledky tvrzení 3.8, 3.12 a 4.11 o zobrazeních ra-prvkové množiny do množiny &-prvkové. Pro n < k je počet injekcí zřejmě (k)„ = a pro n = k je počet bijekcí n\. 4.14. Věta. Pro všechna reálná x a každé přirozené n platí n xn = J^S(n,k)(x)k. k=l Důkaz. Nechť \A\ = m < \X\ = n. Počet zobrazení X do A je podle příkladu 3.20 roven číslu mn. Buď nyní /: X —> A libovolné zobrazení. Pak je / surjekce X na množinu f(X) = A\. Je-li |/(X)| = k, existuje podle věty 4.11 celkem kl ■ S(n,k) surjekcí množiny X na množinu 28 7. KOMBINATORIKA k = 1 2 3 4 5 6 ... n = 1 1 2 3 4 5 6 ... 2 1 2 6 12 20 30 ... 3 1 6 6 24 60 120 ... 4 1 14 36 24 120 360 ... 5 1 30 150 240 120 720 ... 6 1 62 540 1560 1800 720 ... Tabulka 1.2: Pro n > k je počet surjekcí k\S(n, k) A\. Avšak ^-prvkových podmnožin v A je (™). Odtud plyne, že existuje (™) • &) surjekcí X na &-prvkovou podmnožinu v A. Dokázali jsme tak, že /fc=l ^ ^ lc=l n Polynomy ra-tého stupně x" S(n, k(x)ic se tedy shodují v n + 1 hodnotách 0,1, ... ,n. Jak z matematické analýzy vime, plyne odtud rovnost těchto polynomů. • 4.15. Věta. S(n+l,k) = (j)5^ ~ 1)- Důkaz. Představme si rozklady (ra+1) -prvkové množiny {a\, ..., a„+i} na k tříd. Když v každém z těchto rozkladů vyškrtneme třídu obsahující prvek a„+1, zůstanou nám právě všechny rozklady všech množin K c {aj, ..., a„] na k — 1 tříd. Odtud plyne dokazovaná formule. • 4.16. Poznámka. Z definice je zřejmá souvislost Bellových čísel se Stirlingovými čísly 2. druhu; platí Bn = S(n, 1) + S(n, 2) + • • • + S(n, n) = S(n, k). k=l Odtud a z věty 4.15 lze snadno odvodit rekurentní formuli z věty 4.2. Když pro jednoduchost 4. Rozklady konečných množin 29 položíme S (n, k) =0 pro k > n (jak je to ostatně vyznačeno již v tabulce ma straně 154), platí oo oo n / \ Bn+1 = £s(n+l,*) = ££rj-S(i,*-l) = k=l k=l i=0 \l ' - ž(;)(£>*-i>)-i:(;). ŕ=0 V 7 \k=\ I 1=0 v 7 S,- Pro Bellova čísla je známa řada důležitých vztahů. Na ukázku si odvoďme alespoň dva z nejběžnějších. 4.17. Věta. Pro každé reálné číslo t platí oo Y^tn=e(e'-l)_ ^ n\ Důkaz. Uvedený vztah odvodil již E. T. Bell v roce 1934. My však uvedeme elegantní důkaz, který v roce 1964 uveřejnil americký matematik G. C. Rota. Označme F množinu všech reálných funkcí

M je zobrazení (takovým zobrazením se iíkáfunkcionál), nazývá se / lineárnífunkcionál, jestliže pro každé vektory u, v a každá reálná čísla a, p platí f (au + /3w) = af(u) + /3/(w). oo Nyní ukážeme, že zobrazení L : F -> R definované vztahem L ( 1 _ v \k)n ^ (k)n ~k\~ ^ (k - h)\~ ^~kT' ~ ^ ~kT' k=0 k=n y ' k=n k=0 (neboťpro k = 0, ..., n — 1 je (k)„ = 0). Pro funkcionál L definovaný v důkazu věty 4.17 platí: kl k=0 Pro funkci -= ra 1--+---+ ••• + t— k\ VI! 2! 3! /fc=0 5.5. Příklad. Pomocí příkladu 5.4 snadno vyřešíme následující tzv. problém šatnářky. Představme si, ž.e do šatny odevzdalo n osob svůj klobouk. Jaká je pravděpodobnost qn toho, ž.e když. všichni ztratili lístek od šatny a šatnářka jim klobouky při odchodu vydávala zcela nahodile, dostal alespoň jeden člověk svůj klobouk? K šatně mohlo n osob přicházet celkem v n\ pořadích. (Přitom samozřejmě předpokládáme, že všechna pořadí jsou stejně pravděpodobná.) Z příkladu 5.4 okamžitě plyne, že pravděpodobnost toho, že nikdo nedostane svůj klobouk, je rovna číslu 1 1 1 (-1)" p„ = \--+---+ ••• +-. v 1! 2! 3! n\ Pravděpodobnost toho, že alespoň jeden člověk svůj klobouk dostane, je proto 1 1 1 (-1)"+1 q„- ~ Pn - yj ~ 2\ + 3! + " ' + n\ ' 5.6. Poznámka. Jak jsme uvedli již v důkazu věty 4.17, platí pro každé reálné číslo x vztah ex = —. Zejména tedy platí 1 ^(-1)" 111 e = — = > -= 1---h----!-••• = hm p„. e ^ n\ 1! 2! 3! n^ooFn Odtud plyne, že lim q„ = 1 --(= 0,632121 ...). Navíc posloupnost (q„)^íi konverguje „velmi rychle", neboť například qx = l;q2 = 0,5; q3 = 0,6; q4 = 0,625; ^5 = 0,63; ...;q8 = 0,63211 ... Odtud plyne překvapující zjištění, že pravděpodobnost qn se s rostoucím n prakticky nemění. 5. Princip inkluze a exkluze 35 5.7. Příklad. Metodou inkluze a exkluze lze vyřešit i jiný známý kombinatorický problém, tzv. úlohu o hostech (v literatuře běžně nazývanou Probléme des Ménages). Formulace tohoto problému je jednoduchá: Kolika způsoby můžeme rozsadit kolem kulatého stolu n manželských párů tak, aby se muži a ženy pravidelné střídali a žádní dva manželé přitom nesedeli vedle sebe? Nejprve se dohodněme, která rozesazení budeme považovat za různá. Úlohu vyřešíme nejprve tak, ža dvě rozesazení budeme považovat za různá, existuje-li alespoň jedna židle, která je v těchto rozesazeních obsazena různými osobami. Když tento výsledek vydělíme číslem 2n, nerozlišujeme rozesazení, z nichž jedno vzniklo „pootočením" druhého. Všechna rozesazení rozdělme do 2 • n! disjunktních skupin podle toho, jak se rozesadí ženy. Nyní určíme počet rozesazení v těchto skupinách. Nechťjsou tedy ženy již jistým způsobem rozesazeny. Hledáme počet r (n) všech rozesazení mužů, při nichž žádný muž nesedí vedle své ženy. Všech možných rozesazení mužů je n\. Označme a, následující vlastnost těchto rozesazení: i-tý muž sedí vedle své ženy. Pak platí: n r(n) = n\ — ^ M(ai) + ^ M(at, a,-) — ^ M(at, aj,ak) + ■ ■ ■ + (—l)"Ař(ori, ..., a„). i=l i 1 označme

) = i-E-+E------+ (-1)*-=— pi/ V Pij V p*/ ^ pí ~^ píPj Pi---Pk Dokázali jsme tak, že 1 \ / 1 \ / 1 " k = „i__m__...m__=„ V Pi/ V Pij V PkJ *=1A V Pí Známe-li tedy rozklad čísla n na součin prvočinitelů, lze hodnotu n je tento počet roven nule, pro k = 1 nebo k = n je pak roven jedné. Pro 2 < k < n — 1 je těchto možností více. Musíme se však dohodnout, která rozložení čísla n budeme považovat za různá. Konkrétně jde o to, zda nám záleží nebo nezáleží na pořadí sčítanců. Nejprve vyřešíme jednodušší případ, kdy pořadí sčítanců rozlišujeme. d\n 6. Rozklady přirozených čísel na sčítance 39 6.1. Definice. Kompozicí čísla n na k sčítanců rozumíme každou uspořádanou &-tici [ x\, ..., Xk ] přirozených čísel takovou, že x\ + X2 + ■ ■ ■ + Xk = n. Počet všech kompozicí čísla n na k sčítanců označme K (n, k). (Termín kompozice zavedl Percy A. MacMahon.) 6.2. Věta. Pro každá přirozená čísla n, k platí ''n - 1 K (n, k) = , Důkaz. Postupujeme analogicky jako v příkladu 3.28. Mějme n jedniček a přidejme k nim k — 1 nul. Všech permutací těchto jedniček a nul je P(n, k — 1) = (n^1)- Je-li cl\, ■ ■ ■, an+k-i některá z těchto permutací, rozdělí ji k — 1 nul na k úseků. Označme x, počet jedniček v /-těm úseku. Dostaneme tak &-tici [ x\, ..., x^ ] takovou, že x\ + x^ + • • • + x^ = n. Tato &-tice však obecně není kompozicí čísla n, neboť některá x, mohou být rovna nule. Abychom zajistili, že všechna x, jsou nenulová, umístíme do každého úseku jednu jedničku předem a zbývajících n — k jedniček pak můžeme rozdělit libovolně, tj. P(n — k, k — 1) způsoby. Dokázali jsme tak, že (n-k + k-l)l (n-l K{n,k) = P{n-k,k-\)= ' (n -k)\ ■ (k - 1)! Vfc-1 6.3. Poznámka. V průběhu důkazu věty 6.2 jsme ukázali, že kompozicí čísla n na nejvýše k sčítanců je P(n-k,k-l) = 6.4. Příklad. Podle věty 6.2 lze číslo n = 7 rozložit na tři sčítance celkem K (7, 3) = = 15 způsoby. Příslušné kompozice jsou následující: 5 + 1 + 1 4 + 2 + 1 3 + 2 + 2 3 + 3 + 1 1 + 5 + 1 2 + 1 + 4 2 + 3 + 2 3 + 1 + 3 1 + 1 + 5 1 + 2 + 4 2 + 2 + 3 1 + 3 + 3 4 + 1 + 2 2 + 4 + 1 1 + 4 + 2 40 7. KOMBINATORIKA Pokud bychom však pořadí sčítanců nebrali v úvahu, lze číslo 7 rozložit na tři sčítance čtyřmi způsoby (sloupce v hořejším rozpisu). Jak uvidíme, je situace s určením počtu rozkladů čísla n na k sčítanců bez ohledu na jejich pořadí podstatně komplikovanější. 6.5. Definice. Buďte n, k přirozená čísla. Rozkladem čísla n na k sčítanců rozumíme každou (neuspořádanou) &-tici přirozených čísel x\, ..., xk takovou, že x\ + ■ ■ ■ + x/c = n. Počet všech rozkladů čísla n na k sčítanců označme p (n,k). 6.6. Poznámka. To, že v rozkladu x\ + • • • + xk čísla n na k sčítanců na pořadí těchto sčítanců nezáleží je totéž, jako když se dohodneme na jistém přesně stanoveném pořadí, v jakém budeme tyto rozklady zapisovat. Nadále budeme proto rozklady psát tak, že x\ > X2 > ... > xk. Předpokládejme nyní, že n = X\ + X2 + ■ ■ ■ + xk je rozklad čísla n na k sčítanců. Pak n — k = (xi — 1) + (x2 — 1) + • • • + (xk — 1) je rozklad čísla n — k na k nebo méně sčítanců (neboť některá x, se mohla rovnat jedné). Přitom uvedené přiřazení (x1; ..., xk) —> (xj — 1, ..., x^ — 1) je evidentně bijekcí množiny všech rozkladů čísla n na k sčítanců na množinu všech rozkladů čísla n — k na nejvýše k sčítanců. Dokázali jsme tak, že platí následující věta. 6.7. Věta. k p (n, k) = ^2 P (n — k, i); p (n, 1) = p (n, n) = 1. í=i 6.8. Poznámka. Uvedená rekurentní formule nám umožňuje postupně počítat všechny hodnoty p (n, k). Tyto hodnoty pro čísla n, k = í, ..., 10 uvádíme v tabulce na straně 152. k 6.9. Poznámka. Číslo q (n, k) = ^2 p (n, i) udává počet rozkladů čísla n na nejvýše k sčítanců. í=i Přitom lze číslo q (n, k) najít přímo mezi čísly p (x, y). Podle věty 6.7 totiž zřejmě platí q (n, k) = p (n + k, k) 6. Rozklady přirozených čísel na sčítance 41 takže například q (6, 3) = p (9, 3) = 7. V roce 1942 dokázal F. C. Auluck, že pro velká n je q (n, k) přibližně rovno číslu— glí). To potvrzuje vcelku očekávanou skutečnost, že počet kompozicí čísla n na k sčítanců je přibližně k\ krát větší než počet rozkladů čísla n na nejvýše k sčítanců. Číslo p(n) := q (n, n) 1 = ^2 p (n, k) J udává počet všech rozkladů čísla n. Podle výše uvedeného platí p(n) = p (2n, n), takže i čísla p (n) lze zjistit z tabulky čísel p (n, k). (Kromě toho je p (n) samozřejmě rovno součtu všech čísel v ra-tém sloupci této tabulky.) Tabulka čísel p(n) je uvedena v příloze na straně 153. Z tabulky čísel p(n) je zřejmé, že již pro poměrně malé hodnoty n je výpočet hodnot p(n) pomocí rekurentní formule pro p (n, k) zdlouhavý a komplikovaný. (O výhodnějším způsobu výpočtu hodnot p(n) se zmíníme v paragrafu 9 - viz větu 9.6.) Vzhledem k tomu, že není znám jednoduchý explicitní vzorec pro pro přímý výpočet čísel p (n, k), respektive p (n), byly odvozeny alespoň vztahy popisující asymptotické chování těchto čísel. Tak například Hardy a Ramanujan odvodili, že Í2n 4n lgp(n) ~ Jt^y -lg—. V roce 1937 odvodil H. Rademacher, že p(n) lze vyjádřit jakou součet jisté konvergentní nekonečné řady. Pro ukázku jeho výsledek uveďme: 9=1 kde sinh P(n) = ^2Lq(n) ■ Ýq(n), 2 V"-5t Iq d f q (n) = Jt 2 dn / i Lq(n) = ^2wpq • e n~24 2npjzi 1 kde wpq je 24. odmocnina z jedné a p probíhá všechna celá čísla nesoudělná s q menší nebo rovna číslu q. 42 7. KOMBINATORIKA 6.10. Poznámka. V řadě úvah o rozkladech přirozených čísel na sčítance jsou velmi užitečné tzv. Ferrersovy diagramy, v nichž každému sčítanci odpovídá řádek bodů v rovině. I bez přesné definice je jistě vše zřejmé z následujícího příkladu: o o o o o o o o o 5 + 4+1 + 1 —► o o Je-li a rozklad čísla n, pak tzv. adjungovaný rozklad a* k rozkladu a obdržíme tak, že Ferrersův diagram rozkladu a přečteme, jednoduše řečeno, po sloupcích. Tak například adjungovaný rozklad k výše uvedenému rozkladu 5 + 4 + 1 + 1 je rozklad 4 + 2 + 2 + 2+ 1. Platí-li a = a*, nazývá se rozklad a samoadjungovaný. Pokusme se nyní zjistit, kolik má číslo n samoadjungovaných rozkladů. Nejprve uvažme následující jednoduchý příklad. Samoadjungovaným rozkladem čísla 13 je například rozklad 5+3+3+1+1. Ferrersův diagram tohoto rozkladu je následující: o—o—o—o—o I 0 o—o 1 I 0 o o 1 o Když sečteme v uvedeném diagramu navzájem propojené body, obdržíme rozklad 9+3+1. Zamyslíme-li se nad tím, jak rozklad 9+3+1 vznikl, uvědomíme si jistě okamžitě, že jde zákonitě o rozklad s navzájem různými lichými sčítanci (pokud byl samozřejmě původní rozklad samoadjungovaný). Když si nyní navíc uvědomíme, že obrácením uvedeného postupu zase naopak každému rozkladu čísla n na navzájem různé liché sčítance přiřadíme evidentně samoadjungovaný rozklad čísla n, přičemž popsané zobrazení je zřejmě bijektivní, je jasné, že jsme dokázali následující tvrzení. 6.11. Věta. Počet samoadjungovaných rozkladů čísla n je roven počtu rozkladů čísla n na navzájem různé liché sčítance. Pomocí Ferrersových diagramů lze okamžitě — pouhou záměnou řádků a sloupců — odvodit i další tvrzení. 6.12. Věta. Počet rozkladů čísla n na sčítance nepřevyšující číslo k je stejný jako počet rozkladů čísla n na nejvýše k sčítanců. 6. Rozklady přirozených čísel na sčítance 43 Na množině Y všech rozkladů (všech přirozených čísel) je obvyklé definovat vhodné uspořádání následujícím způsobem. (Pro formální jednoduchost nyní ztotožníme rozklad a\ > > a2 > .. . > ak s posloupností (a\, . .. , ak, 0, .. ., 0, . ..).) 6.13. Definice. Buď Y množina všech nerostoucích posloupností nezáporných celých čísel, jejichž součtem je přirozené číslo (tj. všechny členy každé posloupnosti jsou od jistého indexu i > 2 rovny nule). Definujeme relaci < na Y tak, že pro libovolná a = (a„)^l5 fJ = (bn)^Li platí: a < (3 <í=^ ai < bi pro každé i e N. Okamžitě z definice je zřejmé, že platí následující věta. 6.14. Věta. Relace < definovaná v 6.13 je uspořádání na množině Y a (Y, < ) je svaz, v němž. a v fJ = (max {a\, b\], max {a2, bj\, ...) a A 13 = (min {a\, b\}, min {a2, b2}, ■ ■ ■)■ 6.15. Poznámka. Svaz (Y, <) je obvykle nazýván Youngův svaz. Je zřejmé, že card Y = Ko. Část tohoto svazu najdete na obr. 6.5. n = 5 n = 4 n = 3 n = 2 n= 1 Obr. 6.5: Youngův svaz Počet prvků „výšky" n v (Y, < ) je zřejmě p(n). Snadná je též odpověď na otázku, kolik prvků prvek a e Y pokrývá a kolika prvky je pokryt. Je zřejmé, že když rozklad a obsahuje k různých sčítanců, pak a pokrývá k prvků a je pokryt k + 1 prvky. 44 7. KOMBINATORIKA Cvičení 1. Srinivasa Ramanujan dokázal řadu vlastností čísel p(n, k) a p(n), například skutečnost, že pro každé n e No je p(5n + 4) násobkem 5. Ověřte tuto skutečnost pro n = 0, 1,2. 2. Označme t (n) počet rozkladů čísla n, jejichž každý sčítanec je mocninou čísla 2 (včetně 2° = 1). (a) Vypočtěte t (n) pro 1 < n < 6. (b) Dokažte, že t(2n + 1) = f(2ra). (c) Dokažte, že t (n) je sudé pro všechna n > 1. 3. Již Galileo Galilei řešil problém, proč při házení kostkami nepadá stejně často součet 9 a) Ukažte, že čísla 9 a 10 mají stejný počet rozkladů na tři sčítance, které jsou nejvýše rovny 6. b) Zdůvodněte, proč přesto nepadá součet 9 stejně často jako součet 10. 4. Dokažte, že p(2r + k, r + k) = p(2s + k, s + k) pro každé r, í e N. 5. Dokažte, že číslo p(r + k, k) je rovno: A + l\ a) počtu rozkladu čísla r + I I na & navzájem razných sčítanců; b) počtu rozkladů čísla r na sčítance nejvýše rovné k. 6. Pomocí Ferrersových diagramů dokažte rovnost p (n) = p (2n, n). 7. Hardy a Ramanujan v r. 1919 dokázali, že Porovnejte hodnotu p(70) podle tohoto tvaru s přesnou hodnotou (viz tabulku na straně 153). a 10. 7. Rozdělování do přihrádek 45 7 Rozdělování do přihrádek V tomto paragrafu v podstatě jen shrneme některé výsledky odvozené již dříve, přeformulované však do jazyka tzv. „přihrádkové" kombinatoriky. Mnohé úlohy lze totiž převést na následující problém: kolika způsoby lze n předmětů rozdělit do k přihrádek! Vzhledem k tomu, že jak předměty, tak přihrádky mohou být vzájemně rozlišitelné, respektive nerozlišitelné, a na rozmístění mohou být kladeny další omezující podmínky (např. aby všechny přihrádky byly neprázdné, aby počet prvků v různých přihrádkách byl různý apod.), lze úloh tohoto typu zformulovat celou řadu. Řešení některých z nich může být velmi komplikované. Četné aplikace těchto výsledků lze najít i mimo matematiku, např. ve statistické fyzice. Ještě před řešením úloh uvedeného typu si zformulujeme následující evidentní tvrzení, známé jako Dirichletův princip. 7.1. Věta. Při každém rozdělení n předmětů do k přihrádek, kde k < n, existuje alespoň jedna přihrádka obsahující alespoň dva předměty. Jakkoliv je Dirichletův princip jednoduchý, umožňuje řešení řady úloh. Radu zajímavých příkladů lze najít například v [5]. 7.2. Příklad. Dokažte, ž.e když. v obdélníku o rozměrech 6 cm x 4 cm vybereme libovolně 25 bodů, pak mezi nimi existují alespoň dva, které mají vzdálenost menší než 1,5 cm. Leží-li dva body v jednotkovém čtverci, je jejich vzdálenost rovna nejvýše což je méně než 1,5. Kdybychom tedy chtěli 25 bodů rozmístit tak, aby každé dva měly vzdálenost alespoň 1,5 cm, mohli bychom do každého čtverce o straně 1 cm ležícího v daném obdélníku umístit nejvýše jeden bod. Obdélník však lze pokrýt nejvýše 24 takovými čtverci. Podle věty 7.1 tedy mezi libovolnými 25 body jsou alespoň dva ze stejného čtverce. 7.3. Věta. Buďte k, n libovolná přirozená čísla. Pak lze n rozlišitelných předmětů rozmístit do k rozlišitelných přihrádek právě k" způsoby. Důkaz. Je-li X = {xj, ..., x„] množina n předmětů a Y = {yi, ..., yk] množina k přihrádek, pak je evidentní, že rozdělení předmětů do přihrádek je totéž jako zobrazení množiny X do množiny Y. (Prvek x, se zobrazí na tu přihrádku, do které je umístěn.) Odtud a z věty 3.20 okamžitě plyne tvrzení. • Při popsaných rozmístěních předmětů do přihrádek existují samozřejmě přihrádky, které mohou zůstat prázdné. Chceme-li předměty X rozmístit do přihrádek Y tak, aby žádná přihrádka nezůstala prázdná, je to zřejmě totéž, jako sestrojit surjekci X na Y. Odtud, z věty 4.11 a z příkladu 5.9 plyne následující tvrzení. 46 7. KOMBINATORIKA 7.4. Věta. Buď dáno n rozlišitelných předmětů a k rozlišitelných přihrádek, n > k. Počet rozdělení těchto předmětů do přihrádek, při nichž, žádná přihrádka nezůstane prázdná, je roven číslu *!S(/U) = £(-!)''q (*-i)B. í=0 Podobně z důsledku 3.8 plyne 7.5. Věta. Buď dáno n rozlišitelných předmětů a k rozlišitelných přihrádek, k > n. Počet rozdělení předmětů do přihrádek, při nichž, každá přihrádka obsahuje nejvýše jeden prvek, je roven číslu (k)n = k- (k - 1) • ... • (k-n + l). Nyní uvažujme případ, kdy máme opět k rozlišitelných přihrádek avšak n vzájemně nerozlišitelných předmětů. Uvědomíme-li si, že za předměty můžeme vzít například cifry 1 (v počtu n) a přihrádky můžeme označit x\, ..., x^, je okamžitě zřejmé, že tato úloha je ekvivalentní s určením počtu kompozicí čísla n. Chceme-li přitom, aby v každé přihrádce bylo alespoň r předmětů, můžeme nejprve do každé přihrádky r předmětů vložit a zbývajících n—kr předmětů pak rozdělit libovolně. Odtud, z věty 6.2 a poznámky 6.3 okamžitě plyne následující tvrzení. 7.6. Věta. Buďte k, n libovolná přirozená čísla. Pak lze n nerozlišitelných předmětů rozmístit do k rozlišitelných přihrádek právě ín + k — T V k - 1 způsoby. Chceme-li, aby v každé přihrádce bylo alespoň r předmětů, je těchto možností n — kr + k — 1 k - 1 Mají-li zejména být všechny přihrádky neprázdné, je možností celkem n - 1 k - 1 Nyní uvažme případ, kdy jsou přihrádky nerozlišitelné. Nechť tedy je dáno k nerozlišitelných přihrádek a n rozlišitelných předmětů. Rozdělit tyto předměty do přihrádek tak, aby právě p těchto přihrádek bylo neprázdných, evidentně značí utvořit rozklad na množině předmětů na právě p tříd. Podle definice 4.9 udává počet těchto rozkladů Stirlingovo číslo 2. druhu S(n, p). Odtud okamžitě plyne 7. Rozdělování do přihrádek 47 7.7. Věta. Počet rozmístění n rozlišitelných předmětů do k nerozlišitelných přihrádek je roven číslu k S(n, 1) + S(n, 2) + • • • + S(n, k) = J2 S(n, i). í=i Chceme-li zejména, aby všechny přihrádky byly neprázdné, je těchto možnostíprávě S(n, k). Zbývá nám poslední možný případ, kdy jsou nerozlišitelné i předměty i přihrádky. Protože za předměty můžeme vzít cifry 1 a za přihrádky sčítance, jejichž pořadí nerozlišujeme, je tento případ evidentně popsán pomocí rozkladů přirozených čísel. Odtud a z věty 6.9 okamžitě plyne následující tvrzení. 7.8. Věta. Je-li dáno n nerozlišitelných předmětů, lze je do k nerozlišitelných přihrádek rozdělit k p (n, 1) + p (n, 2) + • • • + p (n, k) = p (n, i) = p (n + k,k) í=i způsoby. Chceme-li, aby všechny přihrádky byly neprázdné, je těchto možností právě p {n, k). 7.9. Poznámka. Uvedené výsledky můžeme shrnout do tabulky 1.3, v níž je uveden počet všech rozdělení (bez jakýchkoliv omezujících předpokladů). Počet všech n předmětů rozmístění rozlišitelných nerozlišitelných k přihrádek rozlišitelných k" \ k-1 ) nerozlišitelných Es(n,i) i=i k i=i Tabulka 1.3: Umísťování předmětů do přihrádek 7.10. Příklad. Ilustrujme si rozdíly mezi počty možností v jednotlivých případech například pro 10 předmětů a 4 přihrádky. (a) kn = 410 = 1048576, 48 7. KOMBINATORIKA (b) Cf-71) = (?) = 286, k (c) J2 S(n, i) = 5(10, 1) + 5(10, 2) + 5(10, 3) + 5(10, 4) = í=i = 1 +511 +9330 + 34105 = 43947, k (d) E p (n, i) = p (10, 1) + p (10, 2) + p (10, 3) + p (10, 4) = 23 . í=i Cvičení 1. Do 15 přihrádek je rozmístěno 100 míčků. Dokažte, že alespoň dvě přihrádky obsahují stejný počet míčků. 2. Dokažte, že v každé skupině (alespoň dvou) lidí existují alespoň dva lidé, kteří znají stejný počet členů skupiny. (Návod: Uvažujte množinu lidí, kteří neznají nikoho). 3. Ukažte, že mezi sedmi různými přirozenými čísly vždy existují čísla x, y taková, že x + y nebo x — y je dělitelné deseti. 4. Máme čtyři bílé koule, čtyři černé koule a čtyři červené koule. Kolika způsoby je můžeme rozdělit do 6 rozlišitelných přihrádek? (2 000 376) 8 Řešení rekurentních formulí S rekurentními formulemi jsme se setkali již několikrát. Tak například ve větě 4.2 jsme odvodili rekurentní formuli pro výpočet Bellových čísel B„, ve větě 6.7 pak rekurentní formuli pro výpočet počtu p(n,k) rozkladů čísla n na k sčítanců. Mezi právě uvedenými formulemi je — kromě jiného — jeden zásadní rozdíl. Čísla B„ závisejí na jediné hodnotě (tj. n), čísla p (n, k) na dvou hodnotách (tj. n, k). V tomto paragrafu se budeme zabývat formulemi 1. typu, tj. formulemi pro výpočet členů posloupnosti pomocí předcházejících členů. Předpokládejme, že je tedy dána rekurentní formule pro výpočet hodnot f(n). Obecně nám taková formule umožňuj e výpočet členu f(n + í), známe-li hodnoty /(l), ..., f(n) (respektive f(0),...,f(n) apod.). Jednotlivé formule se však mohou lišit tím, kolik předcházejících členů fakticky potřebujeme k výpočtu členu následujícího. Tak například ve formuli 4.2 pro výpočet čísel B„ potřebujeme k určení B„ všechny členy předcházející. Ve formuli f(n + 2) = f(n + + !) + /(«) potřebujeme jen předcházející dva členy. 8. Řešení rekurentních formulí 49 Má tedy smysl následující definice. 8.1. Definice. Řekneme, že rekurentní formule pro výpočet hodnot f (ji) je řádu k e N, jestliže pro každé n e N lze f (n + k) určit pomocí f (n), f (n + 1)..., f (n + k — 1), přičemž k je nejmenší přirozené číslo s uvedenou vlastností. 8.2. Příklad. (a) f (n + 3) = f (n + 2) - log f (n) je formule 3. řádu, (b) f(n + 2) = f(n+l) + f(n) je formule 2. řádu, n (c) r„+1 = Tk není formule konečného řádu. k=0 8.3. Definice. Buď dána rekurentní formule &-tého řádu pro výpočet čísel f (n), n e N. Řekneme, že posloupnost (a,,)^ je řešením této rekurentní formule, jestliže pro každé i e N dostaneme po dosazení čísel ai+j za f(n + j), j = 0, ..., k, identitu. 8.4. Příklad. Posloupnost (2n)^=l je řešením rekurentní formule 2. řádu /(n + 2) = 3 ■ /(« + 1) - 2 ■ /(n), neboť pro všechna n e N platí 2«+2 = 3 • 2"+1 -2-2". 8.5. Poznámka. Rekurentní formule &-tého řádu zřejmě může obecně mít nekonečně mnoho řešení, neboť prvních k členů posloupnosti, která je řešením, můžeme volit zcela libovolně. Nyní se bude zabývat otázkou, zda lze alespoň v některých případech pro danou rekurentní formuli určit člen f(n), aniž bychom museli počítat postupně všechny členy předcházející. Uvidíme, že se nám to podaří pro speciální typ formulí — pro tzv. lineární rekurentní formule s konstantními koeficienty. 8.6. Definice. Rekurentní formule tvaru f(n + k) = a\ ■ f(n + k — 1) + a2 ■ f(n + k — 2) + ■ ■ ■ + ak ■ f(n), (8.1.) kde a\, .. ., ak jsou reálná čísla, ak ý 0, se nazývá, lineární rekurentní formule k-tého řádu s konstantními koeficienty. 50 7. KOMBINATORIKA 8.7. Věta. Jsou-li posloupnosti (fi(n))%í1 , (fiin))^ , ■ ■ ■, (/s(w))^i řešením formule 8.1., je také jejich libovolná lineární kombinace (ci/i(n) + c2f2(n) + ■■■ + csfs(n))Zi řešením formule 8.1.. Důkaz. Je zřejmé, že stačí dokázat, že každá lineární kombinace libovolných dvou řešení formule 8.1. je opět řešením formule 8.1.. Nechť tedy (g(ji))™=l, jsou řešení formule 8.1., tj. platí g(n + k) = aig(n + k — 1) + a2g(n + k — 2) + • • • + a^gin) h(n + k) = a\h(n + k — 1) + a2h(n + k — 2) + • • • + a^hin) pro všechna n e N. Potřebujeme dokázat, že pro libovolná čísla c\,c2 e R je (r(n))^=l, kde r(n) = c\g(ji) + c2h(n), také řešením formule 8.1.. Pro každé n e N platí: r(n + k) = c\g(n + k) + c2h(n + k) = c\[a\g(n + k — 1) + • • • + akg(n)] + + c2[a\h(n + k — 1) + • • • + akh{n)\ = = a\[c\g(n + k — 1) + c2h(n + k — 1)] + • • • + ak\c\g(n) + c2h(n)] = = a\r{n + k — 1) + • • • + a^riji), což znamená, že (r(n))^=1 je řešením formule 8.1.. • 8.8. Příklad. Mějme dánu rekurentní formuli 2. řádu /(n + 2) = 5 ■ /(« + 1) - 6 ■ /(n). Pouhým dosazením lze snadno ověřit, že posloupnosti (2")^ a (3")^ jsou lineárně nezávislá řešení dané formule. Nyní ukážeme, že každé řešení (gin))^ zadané formule je vhodnou lineární kombinací uvedených dvou řešení, tj. existují konstanty c\,c2 e R takové, že pro každé n e N platí: g(n) = (c1-2n+c2-3n)™1- Jak tyto konstanty nalezneme? Protože řád dané formule je 2, je řešení (g(n))^=l jednoznačně určeno volbou hodnot g (1) a g (2). Nechť tedy g(l) = a, g(2) = b. Potřebujeme dokázat, že existují konstanty c\, c2 takové, že 2c\ + 3c2 = a Aci +9c2 = b 8. Řešení rekurentních formulí 51 Tento systém rovnic má však právě jedno řešení 3a — b b — 2a Cl = -, Co = -. 2 3 8.9. Poznámka. Je zřejmé, že množina všech posloupností reálných čísel se sčítáním definovaným po složkách a s obvyklým násobením reálnými čísly tvoří vektorový prostor nekonečné dimenze na R. Z věty 8.7 plyne, že všechna řešení lineární rekurentní formule daného řádu tvoří podprostor tohoto prostoru. V příkladu 8.8 jsme ukázali, že dimenze vektorového prostoru všech řešení zadané rekurentní formule druhého řáduje 2; posloupnosti (2n)^=l a (3")^ tvoří bázi tohoto vektorového prostoru. Ponecháme na čtenáři, aby si promyslel, že postup uvedený v příkladu 8.8 lze snadno zobecnit na případ lineární rekurentní formule s konstantními koeficienty libovolného řádu k Libovolné řešení (g(n))^=1 takové rekurentní formule je totiž jednoznačně určeno hodnotami S(l)> g (2), ■ ■ ■, g(fc).Existují-li lineárně nezávislá řešení (fi (n))™=1 , ifcin))™=l ifkin))™=l, pak jistě existují konstanty c\, c2, ..., cu £ R takové, že pro každé n £ N platí: gin) = crfrin) + ■ ■ - + ckfkin). K tomu totiž stačí ukázat, že systém rovnic ci/i(l) + c2/2(l) + ...+ct/t(l) = gil) c1f1i2) + c2f2i2) + ---+ckfki2) = gi2) cifiik)+c2f2ik) + ---+ckfkik) = gik) má řešení. Z lineární nezávislosti posloupností (/l(Cl.(/2(Cp-.-(A(C, však snadno plyne, že daný systém rovnic má právě jedno řešení c\, c2, ..., ck. V dalším (viz důsledek 8.17) ukážeme, že takový systém lineárně nezávislých řešení vskutku existuje. Celkem se takto snadno odvodí následující tvrzení. 8.10. Věta. Dimenze podprostoru všech řešení lineární rekurentní formule s konstantními koeficienty je rovna řádu této formule. Z výše uvedeného tedy plyne, že má smysl následující definice. 52 7. KOMBINATORIKA 8.11. Definice. Nechťje dána lineární rekurentní formule f (n + k) = a\ ■ f (n + k — 1) + a2 ■ f (n + k — 2) + • • • + ak ■ f (n) řádu k s konstantními koeficienty. Nechť ■■■.(/*(»))"! jsou lineárně nezávislá řešení dané formule. Pak se posloupnost kde pro každé n e N platí g (n) = cifi(n) + ■ ■ -+ckfk(n), nazývá obecné řešení dané rekurentní formule. Otázkou nyní zůstává, zda alespoň v některých případech obecné řešení najdeme. Buď nyní dána lineární rekurentní formule &-tého řádu s konstantními koeficienty f(n + k) = a\f (n + k — 1) + • • • + akf (n). Zjišťujeme, zda pro některé r e R je posloupnost (r")^ řešením této formule. Pokud je posloupnost (r")^ řešením, musí pro každé n e N platit rn+k = airn+k-1 + ■ ■ ■ + akrk. Pokud je r = 0, je tato rovnost splněna triviálně. Je-li r ý 0, musí tedy platit k k—i rK = a\r + ■ ■ ■ + ak. Odtud a z věty 8.7 plyne 8.12. Věta. Je-li reálné číslo r řešením rovnice k k—i x = axx + ■ ■ ■ + ak, je každá posloupnost (crn)^=l, cěM libovolné, řešením rekurentní formule 8.1.. 8.13. Poznámka. Rovnice xk = a\xk~x + • • • + ak se nazývá charakteristická rovnice formule f (n + k) = a\f(n + k — 1) + • • • + akf (n). Charakteristickou rovnicí rekurentní formule &-tého řádu je tedy algebraická rovnice &-tého řádu. Tato algebraická rovnice má tedy k kořenů (počítáme-li každý kořen tolikrát, jaká je jeho násobnost). Uvědomme si přitom, že když je formule 8.1. &-tého řádu, je koeficient ak nenulový, takže také všechny kořeny charakteristické rovnice jsou nenulové. 8. Řešení rekurentních formulí 53 Odtud plyne následující věta 8.14. Věta. Buď f (n + k) = a\f (n + k — 1) + • • • + akf (n), ak ý 0, lineární rekurentní formule k-tého řádu s konstantními koeficienty. Nechť charakteristická rovnice xk = axxk 1 + + ak má jednoduché navzájem různé reálné kořeny r\, . .. , rk. Pak obecné řešení dané rekurentní formule je tvaru (cirí + c2rn2 + • • • + ckrnk)™=1 . Důkaz. Posloupnost [c\r" + c^r^ + • • • + ckrf)^_x je řešením dané formule podle vět 8.12 a 8.7. Podle poznámky 8.13 jsou všechna čísla r,-, i = 1, ..., k různá od nuly. Posloupnosti (r")^ , i = 1, ..., k jsou evidentně lineárně nezávislé. Zbývá tak pouze dokázat, že každé řešení dané rekurentní formule lze získat vhodnou volbou konstant c,. To dokážeme analogicky jako v poznámce 8.9. Buď libovolné řešení zadané rekurentní formule. Toto řešení je jednoznačně určeno hodnotami g(l), ..., g(k). Zvolme tedy tyto hodnoty libovolně, ale pevně. Je potřeba dokázat, že systém k rovnic o k neznámých c\, ..., ck c\r\ + c2r2 + ■ ■ ■ + ckrk = g(l) c\r\ + c2r\ + ---+ckr\ = g(2) c\r\ + c2r2 + ■ ■ ■ + ckrk = g(k) má řešení. Protože však jsou všechna čísla r, nenulová, je determinant r\ r2 2 2 rl r2 rk rk rk rovněž nenulový, takže daný systém rovnic má právě jedno řešení. 8.15. Příklad. Vyřešme rekurentní formuli z příkladu 8.2(b): f(n + 2) = f(n + l) + f(n). Charakteristická rovnice je tvaru x = x + 1. 54 7. KOMBINATORIKA Její kořeny jsou takže obecné řešení je tvaru *1,2 = 1 ± y/5 + C2 I n=l Hledejme takové řešení (gin))^ zadané formule, že g(í) = 1, g(2) = 1. Pak musí platit i +Vš i - Vš + C2- Cl + C2 i - VšN = i = i. 2 j y 2 Tento systém rovnic má právě jedno řešení cj = — c2 = Odtud plyne, že 'l + v/Š\ /l-VŠN + 2 j y 2 Toto řešení (g(n))'^L1 je tzv. Fibonacciova posloupnost 1,1,2,3,5,8,13,21,34,... členy této posloupnosti jsou tzv. Fibonacciova čísla, která hrají důležitou roli v různých částech matematiky i v řadě pozoruhodných aplikací. Poznamenejme pouze, že posloupnost Fibonacci-ových čísel je obvyklé značit symbolem (Fn)™0. Ve větě 8.14 jsme popsali, jak lze nalézt obecné řešení v případě, že charakteristická rovnice má pouze jednoduché reálné kořeny. Dobře však víme, že algebraická rovnice může mít i kořeny imaginární a násobnost kořenů může být větší než jedna. V dalším popíšeme obecně alespoň ten případ, kdy všechny kořeny charakteristické rovnice jsou reálné. 8.16. Věta. Nechť charakteristická rovnice formule 8.1. má reálný nenulový p-násobný kořen r. Pak jsou posloupnosti ('T-i ■ (»• r")Zi . ■ ■ ■. i-"-1 ■ ňZi lineárně nezávislá řešení formule 8.1.. 8. Řešení rekurentních formulí 55 Důkaz. Je zřejmé, že pro r ý 0 jsou posloupnosti (rn)^=l, ..., (np~l ■ r")^ lineárně nezávislé. Zbývá tak dokázat, že všechny tyto posloupnosti jsou řešením formule 8.1.. Nechť tedy r je /?-násobný kořen charakteristické rovnice. Potřebujeme dokázat, že pro s = 1, ..., p — 1 je (ns ■ rn)^=l řešením formule 8.1., tj. že platí (n + k)srn+k = ax(n + k- \)srn+k-1 + a2(n + k- 2)srn+k-2 + ■■■+ aknsrn. Vydělíme-li tuto rovnici r", obdržíme (n + k)srk = ai(n + k - \)srk~l + a2(n + k - 2)srk~2 + ■ ■ ■ + akns. Dokažme pro jednoduchost tento vztah pouze pro s = 1. Předpokládejme tedy, že číslo r jí 0 je alespoň dvojnásobným kořenem rovnice k k— 1 k—9 x = a\x + a2x + ■ ■ ■ + ak. Z algebry vime, že dvojnásobný kořen polynomu je nutně kořenem derivace tohoto polynomu, takže r je kořenem rovnice kxk~l = ai(k - \)xk~2 + a2(k - 2)xk~3 + ■ ■ ■ + ak_x. Odtud plyne, že platí krk-1 =ai(k- \)rk-2 + a2(k - 2)rk~3 + ■■■ + ak^. Za těchto předpokladů potřebujeme dokázat správnost následující rovnosti: (n + k)rk = ai(n + k — l)rk~l + a2(n + k — 2)rk~2 + • • • + ak(n + k — k). Upravme tuto rovnost následovně: nrk + krk = n ■ [a^^1 + a2rk~2 + ■ ■ ■ + ak] + ai(k - \)rk~l + a2(k - 2)rk~2 + + ■ ■ ■ + ak(k — k). Rovnost výrazů stojících u n na obou stranách rovnosti nyní plyne z toho, že r je kořenem charakteristické rovnice, rovnost zbývajících členů plyne z toho, že kořen r je alespoň dvojnásobný. • Z věty 8.16 okamžitě plyne 8.17. Důsledek. Buď f(n + k) = axf(n + k — 1) + a2f(n + k — 2) + + akf(n) 56 7. KOMBINATORIKA lineární rekurentní formule k-tého řádu s konstantními koeficienty. Nechť jsou všechny kořeny r\, . .. , r j charakteristické rovnice této formule reálné. Nechť kořen r\ je p\-násobný, r2 je p2-násobný, . .., r j je p j-násobný (tj. p\ + ■ ■ ■ + p j = k). Pak obecným řešením dané rekurentní formule je posloupnost, jejíž, n-tý člen je roven výrazu r\ ■ (c11+c12n + --- + clpinP1-1) + rn2 ■ (c21 + c22n + ■ ■ ■ + c2p2nP2'1) + ■ ■ ■ + + r) ■ (cn + cj2n + ■■■ + CjpjnPJ-1). 8.18. Příklad. Najděte obecné řešení formule f(n + 4) = 3f(n + 3) + 3f(n + 2) - + 1) + 6f(n). Charakteristická rovnice této formule je x4 = 3x3 + 3x2-llx + 6. Snadno lze ověřit, že tato rovnice má dvojnásobný kořen 1 a jednoduché kořeny —2 a 3. Obecným řešením zadané formule je tedy posloupnost (g(n))^Lv kde g(n) = ci ■ 1" + c2n ■ 1" + c3(-2)n + c43n = cr + c2n + c3(-2)B + c43". Cvičení 1. Název „Fibonacciova čísla" pro posloupnost 1, 1, 2, 3, 5, 8, ... zavedl francouzský matematik Eduard Lucas. Tzv. Lucasovaposloupnost {L„ je definována stejnou rekurentní formulí L„+2 = Ln+\ + L„, avšak Lq = 1, L\ = 3. Vypočtěte Ljo, ^20- 2. Známý hlavolam Hanojská věž uveřejnil v r. 1833 tajemný francouzský profesor „Claus". Až v r. 1884 publikoval H. de Parville článek v časopise La Nátur, v němž uvedl, že „Claus" je anagram, který užil výše zmiňovaný Eduard „Lucas". Hlavolam tvoří tři vertikální tyčky, na nichž je navlečeno n kruhových disků s otvory uprostřed. Tyto disky mají navzájem různé poloměry a jsou poskládány do věže tak, že poloměr každého disku je větší než poloměr kteréhokoliv disku nad ním (viz obrázek 8.6). Hlavolam spočívá v tom, přenést věž na jinou tyčku tak, že v každém kroku lze přenést pouze jeden disk z jedné tyčky na druhou a nikdy přitom nesmí být položen větší disk na menší. Parville v uvedeném článku uvádí legendu, podle níž mniši v utajovaném tibetském klášteře pracují na přemístění věže tvořené 64 zlatými disky. Ve chvíli, kdy práci dokončí, nastane konec světa. Kdy tato skutečnost nastane? Označme H„ minimální počet kroků potřebných k přemístění věže. 8. Řešení rekurentních formulí 57 Obr. 8.6: Hlavolam Hanojská věž a) Dokažte, že (H„)^í0 je řešením rekurentní formule Hq = 0, Hn+i = 2H„ + 1. b) Najděte obecné řešení uvedené formule. c) Vypočtěte, kolik století by trvalo přemístění věže ze 64 disků, kdyby se na úkolu pracovalo nepřetržitě a přemístění každého disku by trvalo jednu sekundu. 3. Dokažte, že pro členy Fibonacciovy posloupnosti (F,)^ platí: (a) F2 + F4 + ■ ■ ■ + F2„ = F2n+Í - 1, (b) Fi + F3 + ■ ■ ■ + F2„_! = F2n, (c) F12 + F22 + --- + Fn2 = F„-F„+1. 4. Dokažte, že Fibonacciova posloupnost (Fn)^í0 splňuje: a) F4 = F2 + 2F\ + Fq b) F5 = F3 + 2F2 + Fi c) F6 = F3 + 3F2 + 3Fi + F0 d) F7 = F4 + 3F3 + 3F2 + Fj e) F" = Ž(_1)B+t(fc) ^-1) f) Ft+n = FtFi + Ft-iFi-i g) Ft dělí čísla F2i+1 a F3k+2. 5. Takzvaná (3w + l)-funkce g:~H —> N je definována vztahem _ í I' Pro w su^ íW " ( ^fi, pro n liché. Zdá se pravděpodobné, že pro každé n e N dospěje posloupnost g (n), g2 (n), g3 (n), ... k číslu 1. (Zatím to je prokázáno pro všechna n < 240.) Prověřte tuto vlastnost pro počáteční hodnoty 341, 96, 104, 336, 133. 58 7. KOMBINATORIKA 6. Buď n e N pevné. Pro každé x e No položme g(x) = V + 2X + --- + (n-\f. Ukažte, že: a) g(0) = n-l, b) g(l) = \n2 - \n, c) g(2) = \r? - \n2 + \n, d) g(3) = \rŕ - i«3 + \n, e) g(A) = \n5 - \nA + \r? - ±n. 7. k-té Bernoulliovo číslo bk (pojmenované po Jacobu Bernoullim) je definováno jako koeficient u členu n ve funkci g (k) (viz cvičení 1). Jacob Bernoulli dokázal, že '(w-ÉtŤtCK""" Pomocí této identity ověřte vyjádření čísla g (4) ve cvičení l(e). (Tabulka Bernoulliových čísel je uvedena v tabulce na straně 154.) 8. Bernoulliova čísla splňují vztah ín+l\ E(t>-o. "... Pomocí tohoto vztahu a Pascalova trojúhelníka (strana 152) ukažte, že b$ = 0, b(, = 42' 30' ~~ 66' ~ 2730- bi - 0, b& - — ^r, bio - tz, b n - 691 9. Nechť pro x e R značí [x] celou část čísla x, tj. největší celé číslo n takové, že n < x. Nechť S„ je množina všech permutací w-prvkové množiny {1, 2, ..., n}. Řekneme, že permutace p e S„ je fluktuační, když platí: p(2k - 1) < p(2k) pro 1 < k < , .'n - 1 p(2k + 1) > p(2it) pro 1 < k < 9. Vytvořující funkce 59 Tak například v S4 existují následující fluktuační permutace: (1, 3, 2, 4), (1, 4, 2, 3), (2,3, 1,4), (2, 4, 1,3), (3, 4, 1, 2). Označme počet fluktuačních permutací v S„,£o = 1-Tato čísla se nazývají Eulerova. Platí: = 1,1, 1,2,5, 16,61,... a) Vypište 16 fluktuačních permutací v S$. b) Platí rekurentní formule: Ukažte, že £7 = 272. 9 Vytvořující funkce 9.1. Poznámka. (O nekonečných řadách funkcí.) Předpokládejme znalost nekonečných číselných řad. Shrneme zde některé elementární poznatky teorie nekonečných řad funkcí. Nechť (fn(x))^Li Je posloupnost funkcí definovaných na množině M c R. Nekonečnou řadou funkcí nazýváme symbol £ /"M = /lW + /2(*) + ' ' ' + fn(x) + ... . n=l 00 Řekneme, že tato řada konverguje v bodě xq £ M, jestliže konverguje číselná řada VJ fn(xo). n=l 00 Řekneme, že řada funkcí fn(x) konverguje na množině K, jestliže konverguje v každém n=l bodě jeř. Součtem řady VJ fn(x) na množině K nazýváme funkci f(x) definovanou takto: n=l 00 pro každé xq £ K platí f (xq) = /n(*o)-Mocninnou řadou nazýváme řadu funkcí tvaru En 2 n anx = ao + a\x + a^x + • • • + anx + . .. , n=0 60 7. KOMBINATORIKA kde ao, ai, a2, ■ ■ ■ jsou reálná (respektive komplexní) čísla - tzv. koeficienty řady. Jistě existuje lim sup ■s/\an\ = u (může být i u = +00). Číslo r = - (kde ^ = 00, — = 0) nazýváme poloměr 00 konvergence mocninné řady Y anx" ■ Snadno lze dokázat, že tato mocninná řada konverguje na intervalu (—r, r) a diverguje v každém bodě x e R, |x| > r. V matematické analýze se dokazuje, že například 00 x" x x^ x" ex = — = 1 + — + — + ••• + — + ... pro každé iéI (tj. r = 00). ^-^ n\ 1! 2! n\ Odtud například plyne, že 111 1 , 111 — + — + — + ..., - = e =1--+--- 1! 2! 3! e 1! 2! 3! což jsou vztahy, které jsme použili již v příkladu 2.2. Zobecněním známé binomické věty je následující tvrzení: Pro každé reálné číslo a platí «-*-£(;MK>+G) x2 + ■■■+{ Ix" + přičemž, poloměr konvergence uvedené řady je r = 1 (tj. uvedená rovnost platí pro všechna X G (-1,1)). Tak například Vm = (1 + x)3 = ^2 j + jjy + jx2 + ... + ( 2 jx« + Podle příkladu 2.8 (c) tedy platí ^ n • 22"-1 V n - 1 J Je-li Y anx" mocninná řada a r její poloměr konvergence, lze uvnitř intervalu (—r, r) tuto řadu derivovat a integrovat člen po členu, tj. pro každé x e (—r, r) platí ^ anxn i = ^(a„x")' = ^2 n ■ anx" 1 \ n=0 I n=0 9. Vytvořující funkce 61 přičemž zderivovaná řada má stejný poloměr konvergence jako řada původní. Dále pro každý interval [a, b] c (—r, r) platí / ( anx" J dx = I / a„x"dx I oo oo Mocninné řady E anx", E Z?„x" podle definice považujeme za sobě rovné, jestliže pro každé «éN platí an =bn. Konečně součet, součin a podíl mocninných řad definujeme následovně: ^í/„.v" + ^h„.\" = ^(í/„ + h„).\". 77=0 77=0 77=0 OO OO oo ^ anx" • ^ ^77-^" = ^ c„x", kde cn = «0^77 + flifen-i + • • • + fl„feo, rc=0 rc=0 n=0 y ] anx oo "53 = E ' E bnX" "=° n=0 kde E ^nx" Je ta mocninná řada, pro kterou platí n=0 ^ ^ Z7ttX • ^ ^ r/^X — ^ ^ dnX . n=0 n=0 n=0 9.2. Definice. Vytvořující funkcí posloupnosti (an)^0 nazýváme mocninnou řadu E anx" (na množině, kde tato řada konverguje). 9.3. Příklad, (a) Víme, že pro x e (—1, 1) platí 9 1 1+x+x + ■ ■ ■ + x" + ■ ■ ■ =- (geometrická řada). 1 — x 62 7. KOMBINATORIKA 1 To znamená, že 1 -x je vytvořující funkce posloupnosti 1,1,1,1,.... (b) Najdeme vytvořující funkci posloupnosti 1, 2, 3, 4, .... Podle poznámky 9.1 víme, že pro x e (—1, 1) platí (1+x+x2 + • • •+x" + ...)' = l+2x + 3x2 + ---+rax"~1 + --- = n=l (c) Víme, že pro každé n e N a každé iéI platí ,. ">»=£(';>« (binomická věta). To znamená, že funkce (1 + x)n je vytvořující funkcí konečné posloupnosti ( ], ( ],...,( ] (tj. řádku Pascalova trojúhelníka). Vytvořující funkce jsou mocným nástrojem k řešení řady kombinatorických úloh, především těch, které vedou na rekurentní formule. K řešení komplikovanějších případů bychom však potřebovali hlubší znalosti o řadách funkcí. Proto se omezíme jen na několik jednodušších příkladů. 9.4. Příklad. Řezem v řetězci (tj. úplně uspořádané množině) A ý 0 rozumíme uspořádanou dvojici [X, Y] neprázdných podmnožin množiny A takových, žeXnľ=0,XUľ = Aa pro každé dva prvky x e X, y e Y platí x < y (tj. x < y). Je zřejmé, že v konečném ra-prvkovém řetězci A = {a\ < a2 < ■ ■ ■ < an} existuje n —í řezů, protože „dolní třídou" X může být právě jen některá z množin {a\ < a2 < ■ ■ ■ < a,}, kde i může nabýt hodnot 1, ..., n — 1. Dělením řetězce A = {a\ < a2 < ■ ■ ■ < a„] nazveme každou posloupnost sestrojenou následovně: v prvním kroku utvořme nějaký řez [X, Y] v A. Ve druhém kroku utvořme řez ve třídě X i Y, pokud tyto třídy nejsou jednoprvkové. Ve třetím kroku utvoříme řez v každé z nově vzniklých tříd obsahujících alespoň dva prvky atd. Posloupnost ukončíme v okamžiku, kdy jsou všechny vzniklé třídy jednoprvkové. Je-li například A = {a\ < a2 < < < as}, je dělením na A například posloupnost [ {ai, a2}, {a3,a4, a5} ] [ {a\}, {a2}, W, {«4, a5] ] [ {a\}, {a2}, W, , {a*}, {as} ] 9. Vytvořující funkce 63 Náš úkol nyní zní: Kolik existuje dělení na konečném řetězci! Označme Rn počet dělení (n + 1)-prvkového řetězce. Představme si první krok nějakého dělení tohoto řetězce. Jak jsme již uvedli, můžeme tento krok utvořit n způsoby (dolní třída může obsahovat 1, ..., n prvků). Podle toho kolik prvků dolní třída tohoto prvního řezu obsahuje, rozdělíme všechna dělení do n skupin. Do k-té skupiny patří dělení, v nichž dolní třída 1. řezu obsahuje k prvků. Spočtěme nyní počet dělení patřících do k-té skupiny. Protože dolní třída obsahuje k prvků, existuje na ní Rk-i řezů. Horní třída prvního řezu obsahuje n + 1 — k prvků, proto na ní existuje R„-k řezů. Odtud zřejmě plyne rekurentní formule Rn = RoRn-i + R\Rn-2 + • • • + Rn-\Ro, Ro = 1- Vzhledem k tomu, že uvedená formule není konečného řádu, nemůžeme ji vyřešit pomocí metod odvozených v paragrafu 8. Ukážeme však, jak lze řešení nalézt pomocí vytvořující funkce posloupnosti (R„)™Q. Vytvořující funkcí je v tomto případě funkce oo F(x)=YJRnXn- n=0 Platí OO OO oo F2(x) = F(x) ■ F(x) = J2Rn*n -J2R"xn = J2C»X"> 77=0 77=0 77=0 kde cn = RqR„ + RiRn-i + • • • + RnRo = Rn+1, tj- OO F2(x)=Y,Rn,lXn. n=0 Defmujeme-li nyní funkci G(x) vztahem G(x) = x • F (x), platí OO G2(x) = x2 • F2(x) = x2 • Rn+ixn. Platí tak OO G(x) = x • ^ Rnxn = R0x + Rix2 + R2x3 + ... oo G2(x) = x2 • Rn+ix" = Rix2 + R2x3 + ... . n=0 64 7. KOMBINATORIKA Odtud Z rovnice plyne G2 (x) = G (x) - R0x = G (x) - x (neboť R0 = 1). G2(x) - G (x) +x = 0 G(x) = 1 ± VI - 4x Protože v bodě x = 0 řada XI konverguje, existuje G(0). Z posledního vztahu plyne n=0 G(0) = i±VT í i, 2 [ 0, přičemž podle definice musí být G(0) = 0. Tzn., že 1 - VI -4x G(x) =-^--. Funkci V1 — 4x však umíme rozvinout v mocninnou řadu. Podle poznámky 9.1 platí Vl - 4x = (1 -4x)3 = ^(-1)"( 2 )(4x)", n=0 ^"7 G(x) = n=0 ^"7 / 9„ i 4" (2n-2^ ^ n\n- \ ) ^n+l n=l v 7 n=0 ra • 22"-1 \í!-l 1 (2n Protože G(x) = x • F(x), plyne odtud n=0 —" V 7 n=0 I (2n n + 1 \ n 9. Vytvořující funkce 65 9.5. Poznámka. Na příkladu 9.4 lze názorně demonstrovat, jak lze často úlohy na první pohled zcela odlišné převést na řešení téže rekurentní formule. V příkladu 3.31 jsme řešili problém, kolika způsoby se mohou lidé postavit do fronty na Večerník tak, aby měl prodávající vždy nazpět. Zjistili jsme, že když má k lidí desetikorunu a k lidí pětikorunu, je těchto možností 1 (2k k+\\k Nyní všechny „příznivé" permutace k jedniček a k pětek (viz příklad 3.31) rozdělme do k tříd takto: permutace a\, ..., a^k patří do í-té třídy právě tehdy, když s je nejmenší přirozené číslo takové, že mezi ciframi a\, ..., a2s je právě s jedniček a s pětek (například permutace 55151151 patří do 3. třídy). Je zřejmé, že když příznivá permutace patří do í-té třídy as < k, pak cifra na místě 2s + 1 musí být 5; jinak by daná permutace nebyla příznivá. Nyní zjistíme, kolik permutací je obsaženo v í-té třídě. Buď tedy d\, . . . , Cl2s, . . . , Cl2k permutace í-té třídy. Pak mezi členy a\, ..., a^s je s jedniček a s pětek, přičemž pro každé r < s je mezi členy a\, ..., air více pětek než jedniček. Snadno však lze dokázat, že takových permutací a\, ..., a^s je celkem - (2sJ,2). Mezi členy a2s+i. ■ ■ ■. a2k Je nyní k — s jedniček a s k — s pětek. Přitom permutace a2s+i. ■ ■ ■. a2k musí být evidentně rovněž příznivá. Počet těchto příznivých permutací je podle příkladu 3.31 1 Í2k - 2s k — s + l \ k — s Odtud ovšem plyne, že v í-té třídě je celkem — • ( SJ, )---( , ~ s) permutací. Vzhledem s k — s +l VKS/ k tomu, že počet všech příznivých permutací je, jak jsme již uvedli, k + 1 V k 2k plyne odtud identita A k + 1 Í2s - 2\ Í2k - 2s\ _ Í2k j-f s(k-s+l) \s - l J \ k -s ) ~ \ k Zavedeme-li nyní označení 1 Í2s s + 1 \s = T — J- .v ■ 66 7. KOMBINATORIKA lze uvedenou identitu přepsat na tvar ToTk-i + T\Tk-i + • • • + Tk-iTo = Tk, což je formule, kterou jsme ve zcela jiné souvislosti řešili v příkladu 9.4. Řešení příkladů 3.31 a 9.4 je proto zákonitě stejné. Nyní ukážeme, jak vypadají vytvořující funkce posloupností, udávajících počty rozkladů přirozených čísel, o nichž jsme hovořili v paragrafu 6. 9.6. Věta. Pro vynořující funkci posloupnosti (p(n))%í1 platí OO OO j Y^P(n)xn = Y[ 1 _x„ (pro\x\<\), položíme-li definitoricky p(0) = 1. Důkaz. Potřebujeme dokázat, že , 111 1 + p{\)x + p(2)x + • • • + p{n)x + ■ x — 1 1— x2 1 — x" Buďte a, e R libovolná čísla, i = 1,2,... . Víme, že když |a,x! | < 1, pak platí 1 1 — O-iX Odtud plyne 1 - = 1 + atxl + afx + • • • + a"xm + ... (součet geometrické řady). (1 — a\x) ■ (1 — 02X2) • .. . • (1 — akXk) = (1 + aix + a\x2 + fljX3 + ...)• • (1 + a2X2 + a\xA + a\x6 + ...)•...• (1 + akXk + ajx2k + a\x^k + ...)•••• = = 1 + a\x + (a2 + a2)x2 + • • • + (a^a^2 . .. arkk + .. . )x" + .. . . V koeficientu u x" určuje každý sčítanec ar^ar22 ... arkk právě jeden rozklad čísla n, totiž (1 + 1 + • • • + 1) + (2 + 2 + • • • + 2) + • • • + (k + k + ■ ■ ■ + k) = n. (Například koeficient u x2 je roven součtu a\ + a\a\, jehož sčítanci určují po řadě rozklady 1 + 1 a 2 čísla 2.) Když nyní položíme a\ = a2 = ■ ■ ■ = 1, obdržíme dokazované tvrzení. • 9. Vytvořující funkce 67 9.7. Poznámka, (a) Poloměr konvergence vytvořující funkce p(n)xn je tedy roven 1. n=0 (b) Inverzní funkcí k vytvořující funkci p(n)xn je nekonečný součin oo oo Y\(l - x") = (1 - x) • (1 - x2) • . .. • (1 - x") ■ ■ ■ ■ = J2 cnxn. Koeficienty c„ mají rovněž jednoduchou kombinatorickou interpretaci. Platí c„ = A(n) - B(n), kde A(n) je počet rozkladů čísla n na sudý počet navzájem různých sčítanců a B(n) je počet rozkladů čísla n na lichý počet navzájem různých sčítanců. (c) Již Euler, který první odvodil vytvořující funkci posloupnosti (p(n))^=1, dokázal, že „většina" koeficientů c„ je rovna nule. Přesněji řečeno, odvodil následující vztah, dnes běžně nazývaný Eulerova identita: oo oo / 2 2 \ n-r—v ;, / 3k2-k 3k2+k \ (l-x") = l+J](-l)i- íx—+x—j n=l k=l ^ ' Důkaz této identity, který je nejvýhodnější provádět pomocí Ferrersových diagramů, zde uvádět nebudeme. (d) Eulerovu identitu lze zřejmě v řeči rozkladů přirozených čísel interpretovat — při označení uvedeném v (b) — takto: Nechť přirozené číslo n lze psát ve tvaru 3k^k, kde k je vhodné přirozené číslo. Pak A(n) = B(n). Je-li přirozené číslo n výše uvedeného tvaru, pak A(n) - B(n) = (-l)k. 9.8. Poznámka. Ideu použitou v důkazu věty 9.6 lze samozřejmě použít v řadě analogických případů. Chceme-li například zjistit počet rozkladů čísla n na sčítance, z nichž každý je roven některému z čísel s\, ..., s^, přičemž sčítanci jsou navzájem různí, utvoříme výraz (l+xsl)(l+xS2)...(l+xs,0. Po roznásobení obdržíme evidentně výraz, v němž koeficient u x" udává počet hledaných rozkladů. 9.9. Poznámka. Vytvořující funkcí posloupnosti (p (n, k))^=l je funkce G(x) = xk (1 -x)(l -x2)...(l -xk) 68 7. KOMBINATORIKA Vytvořující funkci posloupnosti udávají počty rozkladů čísla n na liché sčítance je funkce 1 H(x) = (1 -x)(l -x3)(l -x5) Konečně vytvořující funkcí posloupnosti udávající počet rozkladů čísla n na navzájem různé sčítance, je funkce oo K(x) = (1 + x)(l + x2)(l + x3) • • • = \\(\ + xk). k=l Ukažme si, jak lze pomocí uvedených vytvořujících funkcí snadno odvozovat tvrzení o rozkladech přirozených čísel. Platí například H(x) = 1 (1 -x)(l -x3)(l -x5)... (1 -x2)(l -x4)(l -x6)(l -x8) (1 -x)(l -x2)(l -x3)(l -x4)... [(1 - x)(l + x)] • [(1 - x2)(l + x2)] • [(1 - x3)(l + x3)] . . . (1 -x)(l -x2)(l -x3)(l -x4)... ~ = (1 +x)(l +x2)(l +x3) • • • = K(x). Dokázali jsme tak právě, že platí následující věta. 9.10. Věta. Počet rozkladů čísla n na navzájem různé sčítance je roven počtu rozkladů čísla n na liché sčítance. Cvičení 1. Dokažte, že vytvořující funkce Fibonacciovy posloupnosti je Kx) = y>„x« = -— . 1 — X n=0 2. Buď (B„) posloupnost Běhových čísel. oo a) Dokažte, že řada Y^, B„xn diverguje pro všechna i^O. ^ Bn b) Dokažte, že řada 2^ —x" absolutně konverguje na R. 10. Bloková schémata, latinské čtverce a konečné roviny 69 10 Bloková schémata, latinské čtverce a konečné roviny Jedním z centrálních pojmů moderní kombinatoriky jsou tzv. bloková schémata, nazývaná též konfigurace, designy i jinak. Teorie blokových schémat je intenzívně rozvíjena a je velmi složitá. Proto se zmíníme jen o nejzákladnějších pojmech a zavedeme některé jednoduché typy. 10.1. Definice. Buďte v,b,k,r,X přirozená čísla, A konečná množina, \A\ = v. Systém podmnožin X\, X2, ■ ■ ■, Xb množiny A se nazývá blokové schéma typu (v, b, k, r, X) v množině A, jestliže \X\\ = \X2\ = = • • • = \Xb\ = k, každý prvek a e A je prvkem právě r množin X, a pro každé dva různé prvky a, b e A je {a, b] podmnožinou právě X množin X,. Množiny X, se nazývají bloky daného blokového schématu. Je samozřejmé, že nemusí existovat blokové schéma libovolného předepsaného typu. Jak však ukážeme v příkladu 10.2, může blokové schéma existovat. 10.2. Příklad. Buď A = {1,2, 3, 4, 5, 6, 7}. Blokovým schématem typu (7, 7, 3, 3, 1) je například systém množin Xi = {1,2,4} X4 = {4,5,7} X7 = {1,3,7} X2 = {2,3,5} X5 = {1,5,6} X3 = {3,4,6} X6 = {2,6,7} 10.3. Věta. Existuje-li blokové schéma typu (v, b, k, r, X), platí bk = vr, r(k - 1) = X(v - 1). Důkaz. První rovnice je evidentní; levá i pravá strana zřejmě udává číslo \X\ \ + • • • + \Xb\- Ve druhé rovnici sečítáme počty dvojic obsahujících daný prvek a, e A. Prvek a, je obsažen v r blocích a v každém z nich tvoří dvojice se zbývajícími k — 1 prvky. Současně však a, tvoří X dvojic s každým z v — 1 zbývajících prvků. • 10.4. Definice. Blokové schéma typu (v, b, 3, r, X) se nazývá systémem trojic. Pro X = 1 se systém trojic nazývá Steinerův. 10.5. Poznámka. Steinerovým systémem trojic je například blokové schéma z příkladu 10.2. 70 7. KOMBINATORIKA J. Steiner v roce 1853 zformuloval následující problém: Pro která přirozená čísla n lze rozdělit n písmen do trojic tak, aby se každá (neuspořádaná) dvojice písmen vyskytovala v právě jedné trojici? Protože se ve Steinerových trojicích každé písmeno vyskytuje s každým jiným písmenem právě jednou, musí být číslo n — 1 sudé, tj. n = l(mod 2). (Stačí si totiž uvědomit, že každé písmeno je ve trojici s dalšími dvěma písmeny.) Dále víme, že každá trojice obsahuje tři dvojice a každá dvojice se v trojicích vyskytne , x n(n — 1) právě jednou. Odtud plyne, že celkový počet dvojic, což je číslo (2j =---, musí být násobek tří. Celkově odtud plyne, že číslo n musí být tvaru 6k+l, respektive 6k + 3, k e N (tj. n=\, 3(mod6)). V roce 1859 dokázal M. Riess, že tato nutná podmínka je současně postačující, tj. platí následující tvrzení, které uvedeme bez důkazu. 10.6. Věta. Blokové schéma typu (n, b, 3, r, 1) existuje právě tehdy, když, n = 6k+l nebo n = 6k + 3, &eNo,ra>3. Buď dán Steinerův systém trojic typu (n, b, 3, r, 1). Jak jsme již uvedli v poznámce 10.5, je počet všech dvojic roven číslu n{n~X). Každá trojice obsahuje tři dvojice, takže počet b všech blokuje roven číslu íííLdl. Podle věty 10.3 dále platí r ■ 2 = n - 1, tj. r = Odtud a z věty 10.6 plyne 10.7. Věta. Na n-prvkové množině existuje systém Steinerových trojic právě tehdy, když, n = n(n — 1) = 6k + l nebo n = 6k + 3 (k e No, ra > 3). V tom případě je těchto trojic - a každý 10.8. Příklad. Uveďme Steinerovy systémy trojic pro nejmenší tři možné hodnoty n, tj. n = 3, n = 7 a n = 9. n=3: 1 2 3 n = 7 123 167 257 356 145 246 347 123 179 278 369 n=9: 145 249 348 467 168 256 357 589 10. Bloková schémata, latinské čtverce a konečné roviny 71 10.9. Poznámka. Úlohu vedoucí na Steinerův systém trojic zformuloval ještě před Steinerem v roce 1847 anglický matematik R. T. Kirkman. Jde o známý Kirkmanův problém 15 dívek: 15 školaček chodí denně na procházku seřazeno do pěti trojic. Lz.e je řadit do trojic tak, aby každá s každou šla během 7 dnů ve trojici právě jednou? Kladná odpověď je vcelku jednoduchá. Rozpis procházek může být následující: 123 147 15 13 168 19 10 4 5 6 2 5 10 2 4 12 2 11 13 2 7 14 7 8 9 6 11 14 6 7 15 4 10 15 3 5 15 10 11 12 9 12 15 8 10 14 5 9 14 4 8 11 13 14 15 3 8 13 3 9 11 3 7 12 6 12 13 1 11 15 1 12 14 2 6 9 2 8 15 3 4 14 3 6 10 5 8 12 4 9 13 7 10 13 5 7 11 Jde o Steinerův systém trojic s parametry v = 15, b = 35, k = 3,r = 7,X = 1, přičemž musí být splněna ještě další podmínka: trojice musí být rozděleny na sedm tříd po pěti trojicích tak, aby byl každý prvek v každé třídě právě jednou. Dodnes není známo, pro která n má Kirkmanův problém, přesněji řečeno jeho příslušné přeformulování, řešení. Úzkou souvislost s teorií blokových schémat mají tzv. latinské čtverce. 10.10. Definice. Buď dána libovolná ra-prvková množina A(ne N). Latinský čtvercem řádu n rozumíme čtvercovou tabulku o n řádcích a n sloupcích takovou, že v každém řádku a každém sloupci je permutace všech prvků množiny A. 10.11. Příklad. 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 12 3 5 12 3 4 1 2 3 4 5 2 14 5 3 3 4 5 1 2 4 5 2 3 1 5 3 12 4 jsou latinské čtverce řádu 5. 72 7. KOMBINATORIKA 10.12. Poznámka. Je zřejmé, že existují latinské čtverce každého řádu n e N. Z každého latinského čtverce řádu n > 1 můžeme snadno utvořit další latinské čtverce například tak, že změníme pořadí řádků, respektive sloupců, nebo provedeme nějakou permutaci prvků množiny A nebo eventuálně uvedené postupy zkombinujeme. Řekneme, že dva latinské čtverce jsou ekvivalentní, jestliže výše uvedeným způsobem lze jeden převést na druhý. Lehce lze dokázat, že každý latinský čtverec 5. řádu je ekvivalentní právě s jedním z latinských čtverců z příkladu 10.11. Latinské čtverce se vyskytují v nejrůznějších souvislostech. Utvoříme-li například obvyklou tabulku násobení v libovolné konečné grupě, obdržíme zřejmě latinský čtverec. Latinské čtverce mají rovněž jednoduchou geometrickou interpretaci. Považujme každé z n2 míst v latinském čtverci za „bod" a představme si následující „spojnice" bodů: (1) řádky latinského čtverce, (2) sloupce latinského čtverce, (3) body v nichž je vepsán stejný prvek. Tyto spojnice tvoří tzv. 3-síť s n2 uzly. Každá spojnice je tvořena n body, spojnice téhož „typu" se neprotínají a každým bodem prochází právě jedna spojnice každého ze tří uvedených typů. Naopak každou 3-síť lze interpretovat jako latinský čtverec. 10.13. Definice. Buďte dány dva latinské čtverce ra-tého řádu utvořené z prvků množiny A. Označme atj, respektive btj, prvek ležící v průsečíku /-tého řádku a y-tého sloupce prvního, respektive druhého latinského čtverce. Protože \A2\ = n2, lze všechny prvky kartézského čtverce A2 vepsat do schématu utvořeného z n řádků a n sloupců. Řekneme, že tyto dva čtverce a (bij) jsou ortogonální, když ve čtverci , bij) je každý prvek z A2 právě jednou. 10.14. Příklad. Čtverce 1 2 3 2 3 1 2 3 1 a 12 3 3 12 3 12 jsou zřejmě ortogonální, neboť když z nich utvoříme popsaným způsobem čtverec 12 23 31 21 32 13 33 11 22 10. Bloková schémata, latinské čtverce a konečné roviny 73 jsou v tomto čtverci všechny prvky kartézského součinu {1, 2, 3} x {1, 2, 3} (přičemž prvek [i, j] jsme zapsali stručně jako ij). Je zřejmé, že neexistují ortogonální latinské čtverce 2. řádu. Jediné latinské čtverce 2. řádu jsou totiž čtverce 12 2 1 2 1 a 12 a ty nejsou ortogonální, neboť ve čtverci 12 21 21 12 nejsou všechny prvky součinu {1,2} x {1,2}. Problematiku existence ortogonálních latinských čtverců 6. řádu zpopularizoval Euler, když v roce 1782 zformuloval slavnou úlohu o 36 důstojnících: Sestavte 36 důstojníků 6 různých hodností z.e 6 různých pluků do čtverce tak, aby v žádné řadě ani žádném zástupu nestáli dva důstojníci stejné hodnosti ani dva důstojníci z.e stejného pluku. Je zřejmé, že tato Eulerova úloha vede na konstrukci dvou ortogonálních latinských čtverců 6. řádu. Protože se konstrukce těchto čtverců Eulerovi nedařila, vyslovil hypotézu, že neexistují dva ortogonální latinské čtverce řádu n = Ak + 2, k = 0, 1, 2, ... . (Podrobnosti viz ve cvičení 3 na konci této kapitoly.) Pravdivost této hypotézy pro k = 0 jsme ukázali výše. Samotný Euler se nedožil vyřešení tohoto problému pro k > 0. Teprve v roce 1900 dokázal francouzský matematik G. Tarry, že neexistují dva ortogonální latinské čtverce 6. řádu. Vzhledem k tomu, že latinských čtverců 6. řádu je téměř 25 000 000 a Tarry své tvrzení odvodil jistým systematickým výčtem, je jeho výkon opravdu pozoruhodný. (O počtu latinských čtverců řádu n viz kapitolu 2, poznámku 8.16). Eulerova hypotéza byla dlouho považována za správnou. Vyvrácena byla až v roce 1959, kdy R. C. Bose a S. Shrikhande sestrojili dva ortogonální latinské čtverce 22. řádu. Později Bose, Srikhande a E. T. Parker dokázali dokonce následující tvrzení: 10.15. Věta. Pro každé přirozené n > 2 kromě n = 6 existují ortogonální latinské čtverce n-tého řádu. Důkaz. Důkaz nebudeme provádět, neboť přesahuje rámec tohoto textu. K jeho provedení je třeba řady tvrzení o blokových schématech. • 74 7. KOMBINATORIKA 10.16. Příklad. Ukažme dva ortogonální latinské čtverce 10. řádu. 00 49 17 96 28 83 75 61 52 34 76 11 59 27 90 38 84 03 63 45 85 70 22 69 37 91 48 13 04 56 58 86 71 33 09 47 92 24 15 60 93 68 80 72 44 19 57 35 26 01 67 94 08 81 73 55 29 46 30 12 39 07 95 18 82 74 66 50 41 23 21 32 43 54 65 06 10 77 88 99 42 53 64 05 16 20 31 89 97 78 14 25 36 40 51 62 03 98 79 87 Ortogonální latinské čtverce 10. řádu si můžeme znázornit také barevně (viz obr. 10.7): Obr. 10.7: Ortogonální latinské čtverce 10. řádu Z tohoto příkladu tedy plyne nesprávnost Eulerovy hypotézy již pro k = 2. Důležitou částí kombinatoriky, těsně propojenou s teorií blokových schémat, jsou tzv. konečné geometrie. Ukažme souvislost některých pojmů konečných geometrií s teorií latinských 10. Bloková schémata, latinské čtverce a konečné roviny 75 čtverců. 10.17. Definice. Buď A ý 0 konečná množina, ČR c P(A). Nechť platí: (1) Pro každé x, y e A, x ý y, existuje právě jedna množina P e P tak, že {x, y] c P. (2) Pro každou množinu P & 3i a pro každý prvek x e A, x ^ P, existuje právě jedna množina Q e 3i taková, žexegaPng = 0. (3) Existují tři navzájem různé prvky x, y, z £ A takové, že {x, y, z] není podmnožinou žádné množiny P e 3i. Pak se dvojice (A, ČR) nazývá konečná afinní rovina. Prvky množiny A se nazývají Ŕotŕy a prvky množiny ^ přímky této roviny. Ve shodě s obvyklou geometrickou terminologií zavedeme následující definici. 10.18. Definice. Dvě disjunktní přímky nazveme rovnoběžkami. Směrem v afinní rovině nazveme systém všech rovnoběžek s danou přímkou. Skutečnost, že přímky P, Q jsou rovnoběžné, budeme značit symbolem P || Q. 10.19. Věta. Nechť P, Q, R jsou přímky v konečné afinní rovině. Nechť P \\ Q, Q \\ R, P ý R. Pak R || P. Důkaz. Připusťme, že existuje a e P D R. Pak by bodem a procházely dvě rovnoběžky s přímkou Q, což není možné. • 10.20. Věta. Všechny přímky v konečné afinní rovině mají stejný počet bodů. Důkaz. I. Nejprve dokážeme, že stejný počet bodů mají všechny přímky téhož směru. Nechť tedy v konečné afinní rovině (A, ČR) existuje přímka P tvořená n body a\, ..., a„. Buď b e A libovolný bod neležící na přímce P (existence takového bodu plyne z vlastnosti (3)). Podle (2) prochází tímto bodem právě jedna rovnoběžka Q s přímkou P. Nyní dokážeme, že |<2| = n. Pro každý bod a, e P existuje podle (1) právě jedna přímka i?, taková, že {a,, b] c Rt. Pro a, a j je zřejmě i?, ý Rj. (Kdyby totiž i?, = Rj, ležely by body a,, ay, b na téže přímce, avšak at, a j určují přímku P ab £ P.) Zvolme cii e P libovolně. Podle (2) prochází každým bodem a j e P, aj ý at, právě jedna přímka disjunktní s Rt. Označme tuto přímku Sj. Kdyby byly přímky S j a Q rovnoběžné, musela by se přímka S j rovnat přímce P, protože bodem aj prochází jediná rovnoběžka s Q. To by však znamenalo, že a, e Rt n S j, což je spor s předpokladem. 76 7. KOMBINATORIKA Přímka S j proto protne přímku Q v jednom bodě s j různém od b (neboť S j n R j = {aj}). Pro j jí k přitom zřejmě platí s j jí sk. Na přímce Q tak leží body b, s j, j jí i. Přitom je zřejmé, že na Q nemůže ležet žádný další bod. (Předpokládejme totiž, že existuje na Q další bod c. Podle (2) existuje přímka C tak, že c e C, C n i?, = 0, tj. C ý Q, neboť b e g n i?,. Je-li c ^ í j, je C 7^ S j. Pak ale C protne přímku P v bodě různém od a, pro všechna i, což je spor.) Dokázali jsme tak, že \Q\ = n. II. Nechť nyní A, B jsou dvě různé přímky, které nejsou rovnoběžné. Připusťme, že A je tvořena n body a\, ..., a„ a na Z? leží navzájem různé body /jj, ..., bn+i. Zvolme označení tak, že průsečík přímek A, B je a\ = b\. Podle definice bodem bn+i prochází rovnoběžka C s přímkou A. Tato rovnoběžka má podle první části důkazu n bodů; označme je c\, ..., c„ = bn+\. Označme S\ přímku procházející body b\,c\ a zvolme na B libovolný bod bt ý b\. Tímto bodem prochází jediná rovnoběžka S, s přímkou S\. Tato rovnoběžka nutně protne přímky A, B. Kdyby totiž byly například přímky A a S, rovnoběžné, procházely by bodem a\ dvě rovnoběžky s přímkou S,, a to přímky A a S\. Označme 5, n A = a*, Si D B = b*. Pro i 7^ 7 však podle tvrzení 10.19 platí a* ý a*, b* jí b*. To však není možné, neboť na přímce B je víc bodů než na přímkách A a C. Přímky A, B tedy musí obsahovat stejný počet bodů. • 10.21. Definice. Řádem konečné afinní roviny rozumíme počet bodů ležících na přímkách v této rovině. Snadno lze dokázat následující tvrzení. 10.22. Věta. Konečná afinní rovina řádu n má n2 bodů an2 + n přímek. Na každé přímce leží n bodů a každým bodem prochází n + 1 přímek. Všechny přímky lze rozdělit do n + 1 směrů a každý směr obsahuje n rovnoběžek. Nyní je ovšem přirozená otázka, zda nějaká afinní konečná rovina vůbec existuje. 10.23. Příklad. V tabulce 1.4 je popsána konečná afinní rovina 4. řádu. Podle věty 10.22 musí obsahovat 16 bodů (jsou označeny arabskými číslicemi) a 20 přímek (jsou označeny římskými číslicemi). Každý z pěti směrů obsahuje čtyři přímky. 10.24. Poznámka. Sportovně založený čtenář může postřehnout, že afinní rovina 4. řádu uvedená v tabulce 1.4 je rozpisem rozjížděk při klasické ploché dráze, kdy 16 jezdců absolvuje 20 rozjížděk tak, že každý jezdec jede s každým právě v jedné rozjížďce. Tabulka 1.4 je důkazem, že konečné afinní roviny vskutku existují. Tím však vůbec není zodpovězena otázka, zda existuje konečná afinní rovina libovolného řádu n e N. Alespoň částečnou odpověď na tuto otázku nám dává teorie latinských čtverců. 10. Bloková schémata, latinské čtverce a konečné roviny 11 I 1 2 3 4 První II 5 7 6 8 směr III 10 11 9 12 IV 15 14 16 13 V 13 1 5 9 Drahý VI 14 10 2 6 směr VII 11 15 7 3 VIII 4 8 12 16 IX 6 16 1 11 Třetí X 12 5 15 2 směr XI 8 9 3 14 XII 13 4 10 7 XIII 7 12 14 1 Čtvrtý XIV 2 13 8 11 směr XV 16 3 10 5 XVI 9 6 4 15 XVII 1 8 10 15 Pátý XVIII 2 7 9 16 směr XIX 3 6 12 13 XX 4 5 11 14 Tabulka 1.4: Konečná afinní rovina 4. řádu 78 7. KOMBINATORIKA Jak latinské čtverce souvisejí s afinními rovinami si ukážeme na rovině uvedené v tabulce 1.4. (Porovnej následující konstrukci s definicí 3—sítě v poznámce 10.12.) Seřaďme nejprve 16 bodů dané roviny do následující tabulky: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Na první pohled je vidět, že řádky v této tabulce jsou přímky 1. směru a sloupce přímky 2. směru v dané rovině. Nyní si ukážeme, jak lze zapsat přímky dalších tří směrů. Uvažujeme 3. směr, tj. přímky IX - XII. V uvedené čtvercové tabulce pak na místa bodů první z těchto přímek, tj. přímky číslo IX, vepišme číslo 1. (Tj. nahradíme jedničkou čísla 1,6,11,16.) Podobně cifrou 2 nahradíme body přímky číslo X (tj. vepíšeme dvojku místo čísel 2,5,12,15). Když tuto úpravu provedeme analogicky i pro přímky číslo XI a XII, obdržíme čtverec 12 3 4 2 14 3 3 4 12 4 3 2 1 Nyní si uvědomme, že jsme zákonitě obdrželi latinský čtverec 4. řádu. Vzhledem k tomu, že přímky 3. směru se neprotínají (jsou to rovnoběžky), nemůže se stát, aby jedno a totéž místo mělo být obsazeno různými ciframi. Protože každá přímka 3. směru protne každou přímku 1. směru (zapsanou v některém řádku čtvercové tabulky) právě jednou a rovněž každou přímku 2. směru (zapsanou v některém sloupci) protne právě v jednom bodě, je v každém řádku a každém sloupci vzniklého čtverce opravdu permutace čísel 1, 2, 3, 4, takže vzniklý čtverec je nutně latinský. Když nyní provedeme analogickou úvahu i pro přímky 4. a 5. směru, obdržíme latinské čtverce 1 2 3 4 1 2 3 4 3 4 1 2 4 3 2 1 a 4 3 2 1 2 1 4 3 2 1 4 3 3 4 1 2 Popsaným způsobem jsme pomocí roviny 4. řádu sestrojili tři latinské čtverce 4. řádu. Jak se čtenář může snadno přesvědčit, jsou každé dva z těchto čtverců vzájemně ortogonální. Současně je snadné si uvědomit, že ortogonalita těchto čtverců je zákonitá. 10. Bloková schémata, latinské čtverce a konečné roviny 79 Popsanou konstrukci však nyní můžeme snadno obrátit. Budou-li dány libovolné tři vzájemně ortogonální latinské čtverce 4. řádu, sestrojíme z nich zpětně snadno afinní rovinu 4. řádu. Uvedenou úvahu můžeme zcela analogicky provést pro každé přirozené n a tak dokázat následující tvrzení. 10.25. Věta. Konečná afinní rovina řádu n > 3 existuje právě tehdy, když. existuje n — 1 latinských čtverců n-tého řádu, z. nichž, každé dva jsou ortogonální. Jak jsme již uvedli, neexistují ani dva ortogonální latinské čtverce 6. řádu. Proto z věty 10.25 okamžitě plyne 10.26. Důsledek. Neexistuje konečná afinní rovina 6. řádu. (Kdyby sportovní činovníci znali tento výsledek, pravděpodobně by nikdy nevznikla tzv. „dlouhá plochá dráha", při níž jezdí v jedné rozjížďce 6 jezdců. Pro tuto soutěž podle důsledku 10.26 nelze sestrojit analogický „spravedlivý" rozpis jako pro klasickou plochou dráhu.) 10.27. Poznámka. Dodnes není obecně známo, pro která n konečná afinní rovina ra-tého řádu existuje. Jsou známy jen některé dílčí výsledky. Tak například metodami analytické geometrie lze odvodit tvrzení: Je-li n = pk, kde p je prvočíslo a k přirozené číslo, pak existuje konečná afinní rovina řádu n. Podstatně komplikovanější je důkaz následujícího tvrzení: Nechť číslo n není součtem čtverců dvou přirozených čísel a nechť n = = \(mod 4) nebo n = 2(mod 4). Pak neexistuje afinní rovina řádu n. Podle uvedeného tvrzení neexistuje například afinní rovina 14. řádu. Je však řada případů, kdy pro dané n neumíme rozhodnout, zda afinní rovina řádu n existuje. Nejmenším takovým číslem je n = 10. Ke konstrukci afinní roviny 10. řádu bychom potřebovali mít k dispozici 9 vzájemně ortogonálních latinských čtverců 10. řádu. Podle příkladu 10.16 dva ortogonální latinské čtverce 10. řádu existují. Ani pomocí počítačů však dodnes nebyla nalezena ani jedna trojice vzájemně ortogonálních latinských čtverců 10. řádu. Existence afinní roviny 10. řádu tak dodnes nebyla ani dokázána ani vyvrácena. Pro velkou obtížnost tohoto problému se mu často říká matematický „problém století", i když mnohé jiné problémy jsou známější a populárnější. Kromě konečných afinních rovin jsou intenzivně studovány i konečné projektivní roviny, jejichž definice je v některých rysech obdobná. 80 7. KOMBINATORIKA 10.28. Definice. Buď A ý 0 konečná množina (její prvky budeme opět nazývat body), a množina 3i c P(A) (její body budeme opět nazývat přímky). Nechť platí: (1) Pro každé x, y e A, x ý y, existuje právě jedna množina P e 3i tak, že {x, y] c P. (2) Každé dvě různé přímky se protínají v jediném bodě. (3) Existují čtyři navzájem různé prvky, z nichž žádné tři neleží na téže přímce. Pak se dvojice (A, 31) nazývá konečná projektivní rovina. Základní vlastnosti projektivních rovin se odvíjejí od následujícího tvrzení, jehož důkaz je elementární a proto jej přenecháme čtenáři. 10.29. Věta. V konečné projektivní rovině existují čtyři navzájem různé přímky, z. nichž, žádné tři se neprotínají v temže bodě. Z definice 10.28 a z věty 10.29 plyne základní vlastnost projektivních rovin, tzv. princip duality: 10.30. Věta. Každé tvrzení v teorii konečných projektivních rovin zůstane v platnosti, když. v něm vzájemně zaměníme pojmy bod a přímka. Snadné je odvodit i následující tvrzení. 10.31. Věta. V každé projektivní rovině platí: (1) všechny přímky mají stejný počet bodů; (2) každým bodem prochází stejný počet přímek; (3) počet bodů na přímkách je stejný jako počet přímek procházejících jednotlivými body. Má tedy smysl následující definice. 10.32. Definice. Nechť každá přímka konečné projektivní roviny obsahuje n + 1 bodů. Pak se číslo n nazývá řád dané roviny. Z věty 10.31 a z definice 10.32 je zřejmé následující tvrzení. 10.33. Věta. Konečná projektivní rovina řádu n má n2 + n + 1 bodů an2 + n + 1 přímek. 10. Bloková schémata, latinské čtverce a konečné roviny 81 10.34. Poznámka. Konečná projektivní rovina 2. řádu by měla, pokud existuje, obsahovat 7 bodů a 7 přímek. Čtenář snadno ověří, že takovou rovinou je například Steinerův systém trojic pro n = 7 v příkladu 10.8. Odpověď na otázku, pro která n existuje konečná projektivní rovina tohoto řádu je stejná jako u afinních rovin: konečná projektivní rovina n-tého řádu existuje právě tehdy, když. existuje n — 1 navzájem ortogonálních latinských čtverců řádu n. Cvičení 1. Zkonstruujte dva latinské čtverce pátého řádu, které mají shodný právě jeden řádek. 2. Dokažte, že mezi latinskými čtverci řádu n jich může existovat nejvýše n — 1 navzájem ortogonálních. 3. Existuje zajímavá souvislost latinských čtverců se čtverci magickými, o nichž jsme se již několikrát zmínili. Připomeňme, že magickým čtvercem řádu n rozumíme tabulku o n řádcích a n sloupcích, do níž jsou zapsána čísla 1,2, ..., n2 tak, že součet čísel ve všech řádcích, sloupcích a obou diagonálách je stejný. Snadno se ukáže, že uvedený součet v tomto případě musí být n ■ (n2 + 1) ---. Vynecháme-li požadavek, aby daný součet byl v diagonálách, dostaneme definici tzv. polomagického čtverce. Není divu, že magické čtverce přitahovaly svými fascinujícími vlastnostmi lidi již před mnoha staletími. Již v úvodním paragrafu jsme se zmínili o magickém čtverci nazývaném Saturn, který vznikne přepsáním konfigurace Lo-šu (viz obrázky 1.1a 1.2). Magické čtverce se objevovaly například i ve výtvarném umění. Uveďme za mnohé obraz Albrechta Dúrera Melancolia (viz obrázek 10.8; na obrázku 10.9 je detail magického čtverce). Již ve 13. století popsal čínský matematik Jang-Hui řadu konstrukcí magických čtverců 3. až 10. řádu. Rada těchto konstrukcí byla velmi důmyslná. Uveďme na ukázku například konstrukci magického čtverce 9. řádu, nazývaného Veliký Lo-šu. Očíslujme řádky a sloupce čtverce Lo-šu čísly 0, 1,2. Dostaneme tak 0 1 2 0 4 9 2 1 3 5 7 2 8 1 6 82 7. KOMBINATORIKA Obr. 10.9: Detail Dürerova obrazu Melancolia 10. Bloková schémata, latinské čtverce a konečné roviny 83 Označme číslo v /-tém řádku a y-tém sloupci tohoto čtverce symbolem L(i, j), (takže například L(l,2) = 7). Čtverec „Veliký Lo-šu" dostaneme tak, že při analogickém očíslování jeho řádků a sloupců čísly 0, 1, 2, ..., 8 jsou jeho prvky G(i, j) vytvořeny podle pravidla: G(3a + b,3c + d) = L(a, c) + 9 • [L(b, ď) - 1], a, b, c, d = 0, 1, 2 . Např.: G(7, 2) = L(2, 0) + 9 • [L(l, 2) - 1] = 8 + 9 • (7 - 1) = 62 Dostaneme tak 0 1 2 3 4 5 6 7 8 0 31 76 13 36 81 18 29 74 11 1 22 40 58 27 45 63 20 38 56 2 67 4 49 72 9 54 65 2 47 3 30 75 12 32 77 14 34 79 16 4 21 39 57 23 41 59 25 43 61 5 66 3 48 68 5 50 70 7 52 6 35 80 17 28 73 10 33 78 15 7 26 44 62 19 37 55 24 42 60 8 71 8 53 64 1 46 69 6 51 Jiný zajímavý magický čtverec zkonstruoval známý vědec a politik Benjamin Franklin. Je to čtverec 8. řádu 52 61 4 13 20 29 36 45 14 3 62 51 46 35 30 19 53 60 5 12 21 28 37 44 11 6 59 54 43 38 27 22 55 58 7 10 23 26 39 42 9 8 57 56 41 40 25 24 50 63 2 15 18 31 34 47 16 1 64 49 48 33 32 17 Tento čtverec je tzv. supermagický: když ho rozdělíme na 4 bloky o 4 řádcích a 4 sloupcích, je každý z těchto bloků pseudomagický: součet každého řádku a každého sloupce v těchto blocích je 130, avšak jednotlivé bloky nejsou složeny z čísel 1,2, 16. 84 7. KOMBINATORIKA Intenzívně se magickými čtverci zabýval v 18. století Euler. Slavný se stal jeho magický čtverec 8. řádu 1 48 31 50 33 16 63 18 30 51 46 3 62 19 14 35 47 2 49 32 15 34 17 64 52 29 4 45 20 61 36 13 5 44 25 56 9 40 21 60 28 53 8 41 24 57 12 37 43 6 55 26 39 10 59 22 54 27 42 7 58 23 38 11 Tento čtverec totiž, kromě toho, že je magický, ukazuje postup šachového koně, který preskáče celou šachovnici (když z pole n skáče na pole n + 1). (Srovnej s příkladem 6.10 ve 2. kapitole.) Euler také odvodil mimořádně zajímavou souvislost mezi magickými a latinskými čtverci. Často je mu připisována následující konstrukce magických čtverců lichého řádu, kterou však již v 17. století objevil francouzský velvyslanec v tehdejším Siamu S. de la Loubére. Tato konstrukce čtverce ra-tého řádu pro liché n je následující. Vepíšeme číslo 1 doprostřed prvního řádku. Máme-li již vepsáno číslo n, napíšeme číslo n + 1 o jeden řádek výš a jeden sloupec doprava, přičemž „nad" prvním řádkem je poslední řádek a „vpravo" od posledního sloupce je první sloupec. Pokud je číslo n + 1 již obsazeno, napíšeme n + 1 pod číslo n. Ilustrujme to na příkladu čtverce 5. řádu. Předepsaným postupem dostáváme 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9 Euler ukázal, že když v takto vzniklém magickém čtverci ra-tého řádu odečteme od každého čísla jedničku a výsledek vyjádříme nikoliv dekadicky, ale v soustavě o základu n (přičemž číslo 1 napíšeme jako 01, 2 jako 02 atd.), dostaneme popis ortogonálních latinských čtverců ra-tého řádu. Tak například z výše uvedeného magického čtverce dostaneme (neboť 16 dekadicky je 31 v pětkové soustavě apod.) 10. Bloková schémata, latinské čtverce a konečné roviny 85 31 43 00 12 24 42 04 11 23 30 03 10 22 34 41 14 21 33 40 02 20 32 44 01 13 Uvedeným postupem lze tedy sestrojit ortogonální latinské čtverce pro každé liché n. Tyto úvahy Eulera přivedly k formulaci úlohy o 36 důstojnících. Kapitola 2 Teorie grafů 1 Co to je teorie grafů a kdy vznikla Odpověď na uvedené otázky je tentokrát poněkud jednodušší než tomu bylo u analogických otázek v 1. kapitole. Teorie grafů je relativně samostatná část diskrétní matematiky; pochopení základních pojmů této teorie nevyžaduje hluboké znalosti jiných matematických disciplín. Většina pojmů o nichž budeme v této kapitole hovořit, má vcelku jednoduchou a názornou interpretaci. Podobně jako v 1. kapitole si však musíme uvědomit, že se budeme zabývat pouze těmi nejjednoduššími pojmy a že jednoduchá formulace problematiky vůbec nepředznamenává jednoduchost řešení daných problémů. V matematice se s pojmem „graf" setkáváme často a v nejrůznějších souvislostech. Běžně například hovoříme o „grafech funkcí". Teorie grafů se však zabývá objekty zcela jiného druhu. V tomto paragrafu ještě nepodáme zcela přesnou definici pojmu „graf. Pokusíme se pouze o vysvětlení intuitivního velmi názorného smyslu tohoto pojmu, stručně uvedeme, jak a kdy se tento pojem v matematice objevil a naznačíme, proč má teorie grafů četné aplikace nejen v matematice, ale i v řadě nematematických oborů. Ve světové literatuře patrně neexistuje učebnice teorie grafů, v níž by se dříve nebo později neobjevila známá úloha o sedmi mostech města Královce, neboť v souvislosti s touto úlohou se v matematice poje „graf objevil poprvé. Jak tato úloha zní? Městem Königsberg (česky Královec, dnešní Kaliningrad v Rusku) teče řeka Pregel. V této řece jsou dva ostrovy, které byly s pevninou a vzájemně propojeny sedmi mosty. Na obrázku 1.1 je schéma popisované situace na dobové kresbě. Když si obrázek překreslíme do schématu na obrázku 1.2, dostaneme následující schéma: Úkolem je zjistit, zda je možné vyjít z, jednoho místa, projít po každém mostě právě jednou a skončit procházku ve výchozím bodě. 86 1. Co to je teorie grafů a kdy vznikla? 87 Obr. 1.1: Kresba 7 mostů v Konigsbergu Obr. 1.2: Schéma 7 mostů v Konigsbergu 88 II. TEORIE GRAFŮ Tuto úlohu řešil (a vyřešil) v roce 1736 L. Euler. Ten samozřejmě dobře věděl, že řešení nezávisí na délce mostů, šířce řeky a podobně, ale pouze na tom, které části města jsou jednotlivými mosty propojeny. Znázorníme-li si jednotlivé části města jako kroužky v rovině a mosty jako spojnice příslušných částí, je okamžitě zřejmé, že vyřešit uvedenou úlohu znamená, názorně řečeno, „namalovat jedním tahem" „graf na obr. 1.3. Euler samozřejmě řešil nejen uvedenou úlohu (čtenář pravděpodobně ví, že požadovanou procházku uskutečnit nelze), ale vyřešil obecně, které „grafy" lze jedním tahem namalovat (jak o tom budeme hovořit v paragrafu 6). Po uvedeném Eulerově výsledku se více než 100 let „grafová" problematika v matematice neobjevila. Až v polovině 19. století se anglický matematik A. Cayley zabýval otázkou, kolik existuje izomerů uhlovodíku C„H2„+2- (Jak čtenář patrně ví, první tři členy uhlovodíkové řady, tj. metan, etan, propan, mají jediný izomer, čtvrtý člen již má izoméry dva - butan a izobutan). Cayley udělal v podstatě tutéž abstrakci jako Euler. Když si znázornil jednotlivé atomy jako kroužky v rovině a spojil „hranou" kroužky znázorňující ty atomy, mezi nimiž je chemická vazba, převedl „chemický" problém na problém nalezení počtu „různých" grafů předepsaného typu, jak je uvádíme na obr. 1.4. (Kroužky, z nichž „vycházejí" čtyři hrany, odpovídají atomům uhlíku, kroužky, z nichž vychází jediná hrana, odpovídají atomům vodíku. Jak uvidíme v paragrafu 4, jsou uvedené grafy případem tzv. „stromů".) Analogicky se přirozeným způsobem k pojmu „graf" dostal G. Kirchhoff ve svých pracech o elektrických obvodech. V téže době, tj. zhruba v polovině 19. století, začíná historie jednoho z nej slavnějších problémů teorie grafů, tzv. problému čtyř barev. O tomto problému budeme podrobněji hovořit v paragrafu 8. První „grafovou" práci v české matematické literatuře publikoval v roce 1926 O. Borůvka, když vyřešil otázku, jak elektrifikovat danou skupinu měst sítí minimální délky (o tomto problému budeme obecněji hovořit v paragrafu 4). První monografii o teorii grafů uveřejnil v roce 1936 maďarský matematik D. König. Jeho ■o- ■o- Obr. 1.3: Grafová interpretace úlohy o 7 mostech 1. Co to je teorie grafů a kdy vznikla? 89 o -o- o -o- o -o- 0 1 -o—o I o o (a) (b) (c) (d) (e) Obr. 1.4: Grafy izomerů uhlovodíku kniha Theorie der endlichen und unendlichen Graphen byla vpravdě průkopnická a po dlouhá desetiletí ve světě prakticky jediná. Doslova bouřlivý rozvoj prodělává teorie grafů v posledních zhruba čtyřiceti letech, kdy se neustále rozšiřuje spektrum aplikací této teorie. Nyní je snad již alespoň částečně zřejmé, jaké objekty se tedy v teorii grafů studují. Buď dána nějaká množina V ^0 (ve většině případů konečná). Její prvky nazveme vrcholy nebo též uzly. Představme si tyto vrcholy jako malé kroužky v rovině. Některé dvojice vrcholů mohou být vzájemně spojeny tzv. hranou. V některých „grafech" mohou být dva vrcholy spojeny i více než jednou hranou (takový je například graf na obr. 1.3), někdy je přípustná mezi vrcholy nejvýše jedna hrana (jako například v grafech na obr. 1.4). V některých grafech jsou hrany „orientovány", tj. je vyznačen směr, od kterého uzlu ke kterému příslušná hrana vede; takové hrany nazýváme šipky. V některých grafech se připouštějí tzv. smyčky, tj. hrany vedoucí z uzlu do sebe samého. Někdy se dokonce připouštějí „hrany" spojující více než dva uzly. (Pak hovoříme obvykle o tzv. hypergrafu.) Přitom je jistě zřejmé (a později to přesně ukážeme), že „grafy" ve výše uvedeném smyslu lze definovat abstraktně, nezávisle na způsobu jejich konkrétního „nakreslení". Toto kreslení bude důležité jen v některých případech (například v paragrafu 7, kde se budeme zabývat tzv. rovinnými grafy). Některé případy, které lze popsat pomocí grafů, jsme uvedli na začátku tohoto paragrafu. Čtenář si jistě dovede představit řadu dalších situací, které lze takto charakterizovat. Grafem je například automapa ČR. Vrcholy jsou jednotlivé obce, hrany jsou příslušné silnice. Tento graf je navíc tzv. ohodnocený - jednotlivým hranám jsou připsána kladná čísla (vzdálenosti). Grafem je schéma zapojení barevného televizoru i plán vodovodní sítě města Brna. Pomocí grafů lze popsat výrobní procesy i vztahy mezi pracovníky v daném závodě. Pomocí pojmů teorie grafů lze charakterizovat strukturu programu pro počítač i rozpis sportovní 90 II. TEORIE GRAFŮ soutěže atd. Za grafy lze považovat hasseovské diagramy uspořádaných množin a vůbec každou množinu, na níž je definována binární relace. I pro teorii grafů platí to, co jsme uvedli již v 1. kapitole. Chceme-li například v konečném ohodnoceném grafu najít „nejkratší cestu" z jednoho vrcholu do druhého, mohlo by se zdát nejjednodušší všechny cesty vypsat (je jich přece pouze konečně mnoho), a pak mezi nimi vybrat tu nejkratší. Nemožnost tohoto postupu vyplývá z toho, že již pro poměrně „malé" grafy je všech možností tak mnoho, že ani pomocí počítačů není uvedený postup realizovatelný. U řady jednoduše fomulovatelných úloh není dodnes nalezen „efektivní" algoritmus pro jejich řešení. Jmenujme za mnohé alespoň tzv. problém obchodního cestujícího: Obchodní cestující má projít danou množinou měst a vrátit se tam, odkud vyšel. Náklady na jeho cestu přitom mají být co nejmenší. Je zřejmé, že tuto situaci lze popsat ohodnoceným grafem, v němž vrcholy jsou jednotlivá města, hranou spojíme města mezi nimiž je přímé dopravní spojení a každé hraně přiřadíme náklady spojené s cestováním mezi danými vrcholy. Jakkoliv jednoduchý se uvedený problém zdá, jde o jeden z nejkomplikovanějších problémů diskrétní matematiky. V závěru tohoto paragrafu je nutno ještě uvést, že terminologie v této oblasti není ustálená a jednotná ani ve světové ani v české matematické literatuře. Dokonce i samotný pojem „graf může mít v různých knihách odlišný význam, podle toho, jaký cíl autor sleduje. My budeme v dalším grafem rozumět to, co se často nazývá obyčejný graf (neorientovaný graf bez smyček a bez násobných hran). Vzájemný poměr jednotlivých typů grafů (orientovaných, neorientovaných, multigrafů, hypergrafů atd.) popíšeme v paragrafu 9. 2 Základní pojmy 2.1. Definice. Buď U ý 0 libovolná množina, buď H c P2(U). Uspořádanou dvojici [U, H] nazýváme graf. Prvky množiny U nazýváme uzly (nebo též vrcholy) grafu, prvky množiny H hrany grafu [U, H]. 2.2. Poznámka, (a) Uvědomme si, že podle definice je množina uzlů vždy neprázdná, avšak množina hran může být prázdná. (b) Nechť U je tříprvková množina {x, y, {x, y}}, H buď množina {{x, y}, {x, {x, y}}}. Pak je podle definice 2.1 [U, H] graf. Popis tohoto grafu je však nepřehledný, neboť {x, y} je současně jeden z uzlů i jedna z hran. Abychom se vyhnuli podobným nepříjemnostem, budeme nadále automaticky předpokládat (respektive označení volit tak), že unH = &. 2. Základní pojmy 91 (c) Uvědomme si, že v grafu [U, H] každé dva uzly tvoří nejvýše jednu hranu. (d) Je-li [U, H] graf, pak jsou hrany dvouprvkové podmnožiny množiny U. Místo {x, y] e e H budeme obvykle užívat jednoduššího zápisu xy e H, tj. budeme hovořit o hranách xy, uv, ab a podobně. (Přitom je zřejmé, že xy e H právě tehdy, když yx e H, tj. hrany jsou podle definice „neorientované".) Je-li x e U, není xx hrana (tj. v našem grafu neexistují „smyčky"). (e) Podle dennice může být množina uzlů grafu [U, H] konečná i nekonečná. Říkáme, že [U, H] je konečný graf, je-li U konečná množina. V dalším budeme převážně hovořit o konečných grafech. (f) Grafy si budeme často představovat tak, jak jsme to uvedli již v paragrafu 1. Je-li [U, H] graf, představíme si uzly jako malé kroužky v rovině, dva uzly x, y pak spojíme nějakou křivkou (nejčastěji — ne však nutně — úsečkou) právě tehdy, když xy e H. Získaný obrázek je v mnoha případech užitečný, uvědomme si však, že jeden a tentýž graf lze znázornit obrázky, z nichž nemusí být vůbec zřejmé, že jsou to nakreslení téhož grafu. Je-li například U = {a, b, c, d] a H = /p2(U),je na všech obrázcích 2.5a-c nakreslen tento graf [U, H]. (a) (b) (c) Obr. 2.5: Různá nakreslení grafu K4 (g) Terminologie teorie grafů často vychází z takto konstruovaných obrázků. Tak například říkáme, že x, y jsou koncové uzly hrany xy, o uzlech u,v e U říkáme, že jsou sousední, pokud uv e H, hrana ab spojuje uzly a, b, hrana xy je incidentní s uzly x, y atd. 2.3. Definice. Úplným grafem na množině U ý 0 rozumíme graf [U, PiiU)]. (Tzn., že v úplném grafu jsou každé dva uzly spojeny hranou.) Úplný graf na množině U je obvyklé značit symbolem Kn, kde n = \U\. 92 II. TEORIE GRAFŮ Na obrázcích 2.5a-c je tedy nakreslen graf K4. 2.4. Definice. Buďte dány grafy §j = [U\, H\], §2 = [U2, H2]. Pak říkáme, že: (a) gi = £2, jestliže Ul = U2, #1 = H2, (b) %\ je podgrafem grafu $2> jestliže t/j c U2, /řj c //2, (c) §j je faktorem grafu §2. j e-li podgrafem grafu §2 a £A = £^2> (d) gij je vlastním podgrafem grafu §2. je-li podgrafem tohoto grafu a přitom §j 7^ §2. (e) $i> §2 jsou disjunktní, jestliže t/i n {/2 = 0, (f) §2 jsou komplementární, jestliže t/i = í/2, H\ D H2 = 0, HiU H2 = P2(U). 2.5. Příklad. Na obr. 2.6a,b jsou vzájemně komplementární vlastní podgrafy grafu ^4. Oba uvedené grafy jsou současně faktory grafu K4. (a) (b) Obr. 2.6: Komplementární podgrafy grafu K4 2.6. Definice. Buď [U, H] graf. Řekneme, že uzel x e U je konečného stupně, jestliže inciduje s konečným počtem hran. V opačném případě je x uzel nekonečného stupně. Je-li x uzel konečného stupně, označíme počet hran, které s tímto uzlem incidují, symbolem stx. Toto číslo nazýváme stupeň uzlu x. Je-li st x = 0, nazývá se uzel x izolovaný. 2.7. Poznámka, (a) Platí stx = \{y e U; xy £ H}\ . 2. Základní pojmy 93 (b) V grafu na obr. 2.6a platí st a = st b = st d = 2, st c = 0, takže c je izolovaný uzel tohoto grafu. V grafu na obr. 2.6b platí sta = stb = std = 1, ste = 3. V grafu Kn je zřejmě stupeň každého uzlu roven číslu n — í. (c) Je zřejmé, že v konečném grafu je každý uzel konečného stupně. I v nekonečném grafu však mohou být samozřejmě všechny uzly konečného stupně. Například na obr. 2.7 je nekonečný graf, jehož každý uzel má stupeň 2. Obr. 2.7: Graf, jehož všechny uzly mají stupeň 2 Zvolíme-li však za množinu uzlů například množinu R všech reálných čísel a defmujeme-li množinu H hran takto: x, y e R, xy e H •<=>• |x — y\ £ Q, je zřejmě [R, H] nekonečný graf, v němž jsou všechny uzly nekonečného stupně. Tento graf samozřejmě nakreslit (ani schématicky) dost dobře není možné. 2.8. Věta. Bud'[U, H] konečný graf. Pak platí £stx = 2 • \H\. Důkaz. Indukcí vzhledem k číslu \ H\. Je-li \ H\ = 0, tj. H = 0, je tvrzení zřejmé, neboť st x = 0 pro každý uzel x & U. Nechť tvrzení platí pro každý graf na množině uzlů U, který má nejvýše h hran. Buď nyní § = [U, H] takový graf, že | H | = h + l.Buďxy e H libovolná hrana. V grafu %* = [U,H — {x, y}] je h hran, takže v %* platí stx = 2 ■ h. Stupně všech uzlů v % a %* jsou však stejné až na uzly x, y, které mají v § stupeň o jedničku větší než v §*. Odtud zřejmě plyne, že v § platí stx = 2 • h + 2 = 2 • (h + 1). • V důkazu věty 2.11 využijeme následujícího označení. 2.9. Definice. Buď § = [U, H] konečný graf, k e No buď libovolné. Pak klademe °k{%) = \{x e U; stx = k}\. 94 II. TEORIE GRAFŮ Symbol 2j + X()Xi' Xl, X}X2, ■ ■ ■ , xn — \ , xn — \xn, xn se nazývá sled začínající v uzlu xq a končící v uzlu x„. Uzly x\, ..., x„_j nazýváme vnitřní uzly tohoto sledu, číslo n (tj. počet hran ve sledu) nazýváme délkou tohoto sledu. 3.2. Příklad. V grafu na obr. 2.10 je například 1, 15,5,52,2,25,5,53,3 sled délky 4 začínající v uzlu 1 a končící v uzlu 3. 3.3. Poznámka, (a) Podle definice je každý uzel sledem nulové délky. (b) Existuje-li mezi dvěma různými uzly sled, existuje mezi nimi zřejmě nekonečně mnoho sledů. Můžeme totiž, jednoduše řečeno, kteroukoliv hranu v daném sledu libovolně mnohokrát opakovat. Například v grafu na obr. 2.10 existují mezi uzly 1 a 2 sledy 1, 15,5,52,2 1, 15,5,52,2,25,5,52,2 1, 15, 5, 52, 2, 25, 5, 52, 2, 25, 5, 52, 2 atd. Vzhledem k tomu, že ve sledu se mohou hrany i uzly opakovat, má smysl následující definice. 3.4. Definice. Sled, v němž se neopakuje žádná hrana, se nazývá tah v daném grafu. Je-li počáteční uzel tahu roven koncovému, nazývá se tah uzavřený. V opačném případě se tento tah nazývá otevřený. Sled, v němž se neopakuje žádný uzel, se nazývá cesta. 98 II. TEORIE GRAFŮ 3.5. Poznámka. Je zřejmé, že každá cesta je tahem, avšak opačné tvrzení obecně neplatí. Například v grafu na obrázku 2.10 je 2, 25, 5, 53, 3, 36, 6, 65, 5, 51, 1 otevřený tah, avšak není to cesta, neboť se opakuje uzel 5. 3.6. Věta. Nechťv grafu [U, H] existuje mezi uzly x, y e U, x ý y sled. Pak mezi nimi existuje v daném grafu alespoň jedna cesta. Důkaz. Tvrzení je vcelku zřejmé. Nechť je dán sled mezi uzly x, y: x — xq , xqX\ , .. ., xn _ \, xn _ \ xn, xn — y. Pokud tento sled není cestou, existují x,, Xj,i < y,tak, že x, = x j. Pak ale je xq, ..., x,, XjX7+1, x7+1, ..., x, opět sled mezi uzlu x, y. (Z původního sledu jsme „vyškrtli" úsek od x, do x j.) Není-li takto získaný sled cestou, musí se v něm nějaký uzel opakovať Příslušnou část sledu pak můžeme opět vyškrtnout. Po konečném počtu kroků pak z původního sledu jistě zůstane cesta z x do y. • 3.7. Příklad. V grafu na obr. 2.10 existují mezi uzly 1 a 3 dvě cesty: jedna má délku 2, druhá délku 3. 3.8. Definice. Graf, v němž mezi každými dvěma uzly existuje sled, se nazývá souvislý. 3.9. Poznámka. Podle poznámky 3.3a je každý graf tvořený jediným uzlem souvislý. Souvislý je i graf na obr. 2.10, avšak graf na obr. 2.6a souvislý není, neboť v něm neexistuje sled například mezi uzly a ac. V dalším budeme potřebovat následující tvrzení. 3.10. Věta. Bud'[U, H] souvislý graf x e U, st x = 1, xy e H hrana incidentní s uzlem x. Pak je graf [U — {x}, H — {xy}] souvislý. Důkaz. Buďte u, v e U — {x} libovolné dva navzájem různé uzly. (Kdyby takové dva uzly neexistovaly, bylo by U = {x, y], H = {xy} a graf [U — {x}, H — {xy}] by byl [{y}, 0], což je souvislý graf podle poznámky 3.9). Protože je [U, H] souvislý, existuje v něm sled mezi uzly u, v a podle věty 3.6 existuje mezi těmito uzly alespoň jedna cesta. Nyní si stačí uvědomit, že na žádné cestě mezi uzly u, v nemůže ležet hrana xy. (Uzel x by totiž musel být vnitřním uzlem této cesty. Protože x inciduje pouze s hranou xy, obsahuje daná cesta úsek ..., y, yx, x, xy, y, .... Pak to ale není cesta, neboť v daném sledu se opakuje uzel y.) Každá cesta mezi u, v je tedy sledem v [U — {x}, H — {xy}], takže tento graf je souvislý. • 3. Souvislé grafy 99 3.11. Poznámka. Graf [U — {x}, H — {xy}] je tedy souvislý vlastní podgraf grafu [U, H] (za předpokladů věty 3.10). Buď [U, H] libovolný graf. Definujeme-li na množině U relaci ~ takto: x ~ y <í==^ existuje sled mezi uzly x,y, je zřejmé, že relace ~ je ekvivalence na množině U. (Reflexivita plyne z poznámky 3.9, symetrie a tranzitivita je zřejmá.) Tato ekvivalence určuje rozklad U/~ na množině U. Pro každý uzel x e U označme U (x) tu třídu tohoto rozkladu, v níž leží uzel x. Je tedy U (x) = {t e U; existuje sled mezi uzly t, x}. Označíme-li H (x) = {uv G H; u G U (x), v e U (x)}, je zřejmě [U (x), H (x)] podgraf grafu [U, H] (pro každý uzel x e U). 3.12. Definice. Buď [U, H] graf, x e U libovolný uzel. Podgraf [U (x), H (x)] grafu [f/, /ř] se nazývá komponenta grafu [U, H] příslušná uzlu x. 3.13. Poznámka. Je zřejmé, že graf [U, H] je souvislý právě tehdy, když má právě jednu komponentu. Komponenty grafu jsou —jinak řečeno — maximální souvislé podgrafy daného grafu. 3.14. Poznámka. Souvislé grafy lze rovněž považovat za metrické prostory. Je-li totiž [U, H] souvislý graf a x, y e U libovolné uzly, existuje mezi těmito uzly podle věty 3.6 alespoň jedna cesta. Mezi cestami z uzlu x do uzlu y jistě existuje cesta minimální délky. Označme její délku q (x, y). Pro čtenáře bude jistě snadným cvičením ověření toho, že pro každé tři uzly x, y, z e U platí: (a) q (x, y) = 0 právě tehdy, když x = y, (b) q (x, y) = q (y, x), (c) q (x, y) + q (y, z) > Q (x, z). To však právě znamená, že (U, q) je metrický prostor. Lze tedy na souvislé grafy aplikovat i metody teorie metrických prostorů. 100 77. TEORIE GRAFŮ Jak uvidíme, budou v dalším hrát souvislé grafy důležitou roli. Zvláště významné pak budou souvislé pravidelné grafy. Například na obr. 2.7 je souvislý pravidelný graf 2. stupně. Nás však budou zajímat především konečné souvislé pravidelné grafy 2. stupně. 3.15. Definice. Konečný souvislý pravidelný graf druhého stupně se nazývá kružnice. Počet uzlů v kružnici nazýváme její délkou. 3.16. Příklad. Na obrázku 3.11a je kružnice délky 3, na obrázku 3.11b kružnice délky 6. Obr. 3.11: Kružnice Graf na obrázku 3.11a se — vcelku pochopitelně — rovněž nazývá trojúhelník. (V teorii grafů je tak trojúhelník zvláštním případem kružnice.) V dalších úvahách uvidíme, že jednou z důležitých charakteristik grafu bude to, zda obsahuje jako podgraf nějakou kružnici. Například graf na obr. 2.10 obsahuje právě jednu kružnici (trojúhelník o vrcholech 3,5,6), graf na obr. 2.9a obsahuje kružnic celou řadu, avšak grafy na obr. 1.4 neobsahují jako podgraf žádnou kružnici. Právě takovými grafy se nyní budeme zabývat. 4 Stromy Stromy tvoří jednu z nejdůležitějších tříd grafů. Mají řadu aplikací v nejrůznějších oborech. Jak jsme uvedli již v paragrafu 1, patří mezi první grafy, které byly v matematice zkoumány. 4.1. Definice. Konečný souvislý graf neobsahující jako podgraf žádnou kružnici, se nazývá strom. Graf, jehož každá komponenta je stromem, se nazývá les. 4. Stromy 101 4.2. Poznámka. Les je tedy graf neobsahující žádnou kružnici. Strom je konečný souvislý les. Pojmenování „strom" a „les" souvisí s tím, jak lze tyto objekty nakreslit. Príklad „odpovídajícího" nakreslení je na obr. 4.12. Stromy lze charakterizovat různými způsoby. V následujícím tvrzení uvedeme některé nutné a dostatečné podmínky toho, aby graf byl stromem. 4.3. Věta. Buď[U, H] konečný graf. Pak jsou následující tvrzení ekvivalentní: (a) [U, H] je strom. (b) Mezi každými dvěma uzly v [U, H] existuje právě jedna cesta. (c) [U, H]je souvislý a platí \ H\ = \U\ — 1. (d) [U, H] neobsahuje kružnici a \ H\ = \U\ — 1. Důkaz. Dokážeme postupně implikace (a)=^(b), (b)=^(c), (c)=^(d), (d)=^(a). (a) =í> (b): Strom [U, H] je souvislý, takže podle věty 3.6 existuje mezi každými dvěma uzly alespoň jedna cesta. Potřebujeme proto pouze dokázat, že nemohou existovat dva uzly, mezi nimiž je více cest. To je však zřejmé. Kdyby totiž existovaly uzly u, v e U, mezi nimiž by existovaly dvě různé cesty, pak by zřejmě v [U, H] existovala kružnice, což podle definice stromu není možné. (b) =3- (c): Existuje-li mezi každými uzly u,v e U cesta, je [U, H] souvislý. Zbývá tedy pouze dokázat rovnost \ H\ = \U\ — 1. Důkaz provedeme indukcí vzhledem k \ U\. Pro \ U\ = 1 je tvrzení zřejmé. Nechť tedy uvedená rovnost platí pro všechny grafy splňující (b) s počtem 102 II. TEORIE GRAFŮ uzlů nejvýše n. Nechť[t/, H] je graf splňující (b) takový, že \U\ = n+l.Buďuv e H libovolná hrana. Graf [U, H — {xy}] není souvislý a zřejmě má právě dvě komponenty (jsou to U (x) a U (y)). Podle indukčního předpokladu je v každé z těchto komponent počet hran o jedničku menší než počet uzlů. V grafu [U, H — {xy}] je tedy n — l hran, tj. v grafu [U, H] je n = \ U \ — 1 hran, což jsme chtěli dokázat. (c) =>• (d): Nechť graf [U, H] splňuje podmínku (c). Potřebujeme dokázat, že v tomto grafu neexistuje kružnice. Připusťme tedy, že v grafu [U, H] kružnice existuje. Je-li xy e H libovolná hrana ležící na této kružnici, pak jejím vynecháním vznikne souvislý graf [U, H — {xy}]. (Souvislost tohoto grafu je zřejmá; libovolné dva uzly dovedeme v tomto grafu jistě spojit vhodným sledem, roli hrany xy v případě potřeby supluje zbylá část kružnice.) Kdyby v grafu [U, H — {xy}] opět existovala nějaká kružnice, vynecháme v ní rovněž některou hranu. Po konečném počtu kroků obdržíme souvislý graf neobsahující žádnou kružnici, tj. strom. Počet hran v tomto stromu je však menší než \U\ — 1, neboť tolik hran měl podle předpokladu graf [U, H]. To je však spor, neboťjsme již dokázali, že (a)=^(c), tj. strom obsahuje nutně \U\ — 1 hran. (d) =>• (a): Potřebujeme dokázat, že graf splňující (d) je nutně souvislý. Předpokládejme tedy, že graf [U, H] splňuje podmínku (d) a není souvislý. Pak je tvořen komponentami §!,...,§„ (n > 2). Každá z těchto komponent je stromem (neboť [U, H] je podle (d) les). Označme g, = [Ut, Ht]. Protože (a)=Kc), platí |ířr| = |t/,| - 1 pro i = 1, ..., n. Odtud n n |íř|=£|ířI-|=£(|f/I-|-l) = |f/|-«, í=i í=i kde n > 2. To je však spor, neboť podle předpokladu platí \ H\ = \U\ — 1. • 4.4. Věta. Každý strom s alespoň dvěma uzly obsahuje alespoň dva uzly prvního stupně. Důkaz. Buď [U, H] strom, \ U\ > 2. Podle vět 2.8 a 4.3 platí £stx = 2 • \H\ = 2 • (\U\ - 1) = 2 • \U\ - 2. Přitom stx > 1 pro každý uzel x & U. Kdyby alespoň dva uzly neměly stupeň 1, bylo by číslo st x větší než 2 • | U | — 2. • 4.5. Příklad. Buď n > 2 libovolné přirozené číslo. Pak jistě existuje strom o n uzlech, který obsahuje právě dva uzly 1. stupně. Takový strom se nazývá had. Pro n > 3 může ve stromu o n uzlech evidentně existovat nejvýše n — l uzlů 1. stupně. Strom, který má právě n — l uzlů 1. stupně (z celkového počtu n), se nazývá hvězda. Na obr. 4.13a je had a na obr. 4.13b hvězda pro n = 6. 4. Stromy 103 (a) o (b) Obr. 4.13: Had a hvězda V definici 2.4 jsme definovali faktor grafu [U, H] jako podgraf, jehož množina uzlů je rovněž U. V dalším nás budou zajímat podgrafy a faktory bez kružnic. 4.6. Definice. Kostrou grafu [U, H] rozumíme takový faktor [U, H\\, který je stromem. 4.7. Příklad, (a) Graf z obr. 2.10 obsahuje tři kostry, které jsou znázorněny na obr. 4.14. Obr. 4.14: Kostry grafu z obr. 2.10 (b) Kružnice délky n zřejmě obsahuje n koster; každá kostra vznikne vynecháním právě jedné hrany. (c) Strom obsahuje právě jednu kostru - sebe sama. Nyní je přirozená otázka, které grafy kostru obsahují. Protože kostra grafu je souvislý podgraf, nemůže samozřejmě kostru obsahovat graf, který sám není souvislý. Jak je tomu v souvislých grafech uvádí následující tvrzení. 4.8. Věta. Každý konečný souvislý graf obsahuje alespoň jednu kostru. Důkaz. Buď [U, H] konečný souvislý graf. V tomto grafu jistě existuje nějaký podgraf, který je stromem. Stačí totiž zvolit libovolný uzel x e U a podgraf [{x}, 0] je strom. Označme S 104 II. TEORIE GRAFŮ množinu všech stromů v [U, H]. Protože je graf [U, H] konečný, obsahuje pouze konečně mnoho podgrafů, takže tím spíše je i množina S konečná (a víme, že neprázdná). Protože S je konečná, obsahuje alespoň jeden maximální prvek (tj. strom, který není podgrafem žádného jiného stromu). Buď tedy [U*, H*] některý maximální prvek v S. Zřejmě stačí dokázat, že U = U* (pak je totiž [U*, H*] faktor a tedy kostra v [U, H]). Připusťme, že je U ý U*, tj. existuje y e U — U*. Zvolme x e U* libovolně. Protože je [U, H] souvislý, existuje v něm cesta z x do y. V této cestě pak ale nutně existuje alespoň jedna hrana vw e H taková, že v e U*, w U*. Pak je ale zřejmě [U U {w}, H U {vw}] strom v [U, H]. (Souvislost je zřejmá, neboť [U*, H*] je souvislý; přidáním hrany vw jsme přitom evidentně nemohli uzavřít žádnou kružnici.) To je však spor, neboť [U*, H*] je vlastním podgrafem takto vzniklého stromu a tak není maximální v S. • V příkladu 4.7 jsme viděli, že graf může mít více koster. Proto je přirozená otázka, jak určit počet koster daného grafu. Jeden ze základních poznatků v tomto směru dokázal již v roce 1899 Cayley. 4.9. Věta. Počet koster v úplném grafu K„ je roven číslu nn~2. Důkaz. Důkaz tohoto tvrzení nebudeme provádět. • 4.10. Poznámka. Jak v dalším uvidíme, je zdánlivě jednoduchý postup, totiž postupné prověřování všech možností, již u poměrně „malých" grafů prakticky neuskutečnitelný (i při použití počítačů). Obecná metoda, pro praktický výpočet však nepříliš pohodlná, je založena na výpočtu determinantu vytvořeného z tzv. Laplaceovy matice sousednosti daného grafu. Tato matice je definována následovně: Je-li [U, H] konečný graf, U = {1, ..., n], je příslušná matice (a,j)"7=1 definována takto: — 1, jestliže i j e H, st i, jestliže i = j, 0, jestliže i ý j, i j £ H. Následující příklad uvádíme z toho důvodu, že ilustruje užitečnost vytvořujících funkcí zavedených v 1. kapitole. 4.11. Příklad. Žebřík Zn je graf s 2n uzly definovaný tak, jak je znázorněno na obr. 4.15. Naším úkolem je určit počet A„ koster v žebříku Z„. (p„-faktorem v Z„ nazveme takový faktor, který je utvořen dvěma disjunktními stromy (viz definici 2.4), z nichž jeden obsahuje uzel x„ a druhý uzel y„. (Příkladem ^„-faktoru v Z„ je faktor, jehož jeden strom obsahuje všechny uzly x, a druhý všechny uzly v,-.) Počet ^„-faktorů v Z„ označme B„. Je zřejmé, že platí A\ = B\ = \. 4. Stromy 105 -o ľl Y2 Y3 ľn-1 y„ Obr. 4.15: Žebřík Nyní odvodíme rekurentní formule pro výpočet hodnot A„, B„. Předpokládejme, že známe A\, ..., A„, Bi, ..., B„. Uvažme, jak můžeme zkonstruovat kostru v Z„+1. Je zřejmé, že to lze právě jedním z následujících dvou způsobů: (a) K některé kostře v Z„ přidáme některé dvě z hran x„x„+1, x„+1 y„+i, y„ y„+i. Z každé kostry v Z„ tak získáme tři kostry v Z„+1. (b) K některému ^„-faktoru v Z„ přidáme všechny tři hrany x„x„+i, x„+iv„+i, ynyn+\. Odtud plyne formule A„+i = 3A„ + Bn. Stejně jednoduše lze odvodit formuli Bn+\ = 2An + Bn. Takto získané rekurentní formule nyní vyřešíme pomocí vytvořujících funkcí. Položme F(x) = J^Anxn, G(x) = J^Bnxn. Pak platí 3F(x) + G(x) = J](3A„ + Bn)x" = An+1x", n=l n=l x[3F(x) + G(x)] = x • ^ A„+1x" = ^ A„x" = F(x) - Axx = F(x) - x. Analogicky x[2F(x) + G(x)] = G(x) -x. Budeme-li stručně místo F(x) psát pouze F a místo G(x) pouze G, obdrželi jsme následující dvě rovnice pro neznámé F, G: x(3F + G) = F-x x(2F + G) = G-x. 106 II. TEORIE GRAFŮ Úpravou dostáváme F(3x - 1) +x(G+ 1) = 0 x(2F + 1) + G(x - 1) = 0. Ze druhé rovnice plyne c = x(2F+l) 1 -x ' takže dosazením do první rovnice máme x(2F + 1) + 1 - x F(3x - 1) + x • —---= 0. 1 — x Odtud F(x) = x2 — 4x + 1' Funkci F(x) nyní rozložíme v mocninnou řadu. Platí x2 - 4x + 1 = (x - a)(x - P), kde a = 2 + S, p = 2 - VŠ. Rozložme funkci F(x) na parciální zlomky: x x A 5 = -o—;-7 = ~,-r,-^ =-+ x2 — 4x + 1 (x — a)(x — B) x—a x — B Konstanty A, B určíme porovnáním koeficientů v rovnosti x = A(x — B) + B(x — a). Protože A- B- isfi ' ~ 2V3 dostáváme V3 + 2 1 y/3-2 1 1 / a B F(x) = ——---+ ' H 2sFh x - a 2^3 x - B 2^3 \x - a x - p l/l 1 \ l/l 1 \ 4. Stromy 107 Protože zlomky v závorce můžeme (pro vhodné x) považovat za součty geometrických řad s kvocientem j, respektive ^, dostáváme F(x) = 1 2^3 1 a -/3 Y -) -Y(-Y = — Y--1 X = j2(rn- U2 se nazývá izomorfismus grafu \U\, H\\ na graf [U2, H2], když platí: 1- / je bijekce, 2. xy e H\ právě tehdy, když f(x)f(y) e H2. Dva grafy jsou izomorfní, když mezi nimi existuje alespoň jeden izomorfismus. Čtenář si jistě okamžitě uvědomuje, že izomorfismus je ekvivalence na třídě všech grafů. V jistém slova smyslu důležitější než otázka, kolik existuje na n uzlech všech grafů, je problém, kolik na n uzlech existuje neizomorfních grafů. Tak například na čtyřech uzlech existuje 64 grafů, avšak jen 11 neizomorních grafů, jak je patrno z obr. 4.17. Odvození metody pro výpočet počtu h„ neizomorfních grafů na n uzlech přesahuje naše možnosti. (Jde o tzv. Pólyovu enumerační metodu, o níž jsme se zmiňovali již v paragrafu 1 1. kapitoly.) Existuje však jednoduchý odhad pro čísla h„; je totiž zřejmé, že platí 2© K > —-, 4. Stromy 109 o o o o- -o o o o o o o o o o o o- o o o o Obr. 4.17: Neizomorfní grafy na čtyřech uzlech neboť na ra-prvkové množině jistě existuje nejvýše n\ vzájemně izomorfních grafů. Uvedený odhad je při své jednoduchosti pro velká n velmi přesný. Lze totiž dokázat, že lim = 0. I posloupnost (hn)°^=\ roste „velmi rychle", jak lze vyčíst z následující tabulky: n 1 2 3 4 5 6 7 8 9 K 1 2 4 11 34 156 1034 12344 308 168 Dokonce i počet t„ neizomorfních stromů na n uzlech (při veškeré „jednoduchosti" stromů) roste pořád ještě tak rychle, že i jejich systematický přehled pro poměrně malá n je nemožný (viz tabulku na straně 155). Jak jsme uvedli již ve větě 4.8, obsahuje každý konečný souvislý graf alespoň jednu kostru. Viděli jsme, že kostra grafu obecně není určena jednoznačně. Uvědomme si však, že podle věty 4.3 mají všechny kostry stejný počet hran (roven početu uzlů zmenšený o jedničku). Abychom konečně uviděli nějakou aplikaci teorie grafů, budeme se nyní zabývat hledáním vhodných koster v tzv. ohodnocených grafech. K tomu však potřebujeme nejprve následující definici. 110 77. TEORIE GRAFŮ A B C D E F A 0 13 27 18 5 30 B 13 0 7 18 4 12 C 27 7 0 3 8 11 D 18 18 3 0 9 24 E 5 4 8 9 0 15 F 30 12 11 24 15 0 Tabulka 2.2: Náklady na vybudování železnice mezi městy 4.14. Definice. Nechť je [U, H] graf. Buď dáno zobrazení /: H -> R (respektive /: U -> -> R). Trojici [ U, H, f ] nazýváme hranově ohodnocený (respektive uzlově ohodnocený) graf. Číslo f(t) nazýváme ohodnocení hrany (respektive uzlu) t. 4.15. Definice. Buď [ U, H, f ] hranově ohodnocený konečný souvislý graf. Kostra [U, H*] grafu [U, H] se nazývá minimální kostra v [U, H, f ], když pro každou kostru [U, H\ \ grafu [Č7, ] platí 4.16. Poznámka. Protože konečný souvislý graf obsahuje pouze konečně mnoho koster, obsahuje nutně každý konečný souvislý hranově ohodnocený graf alespoň jednu minimální kostru. Současně je evidentní, že minimální kostra obecně není jednoznačně určena. 4.17. Příklad. Buď dána množina měst A, B, C, D, E, F. V tabulce 2.2 nechť jsou uvedeny náklady na vybudování železnice mezi jednotlivými městy (v miliónech Kč). Naším úkolem je nyní navrhnout mezi uvedenými městy železniční síť tak, aby každá dvě města byla vzájemně po železnici dosažitelná a aby přitom náklady na vybudování železnice byly minimální. Grafová formulace zadané úlohy je jednoduchá. Naším úkolem je zřejmě nalezení minimální kostry v úplném grafu K§ s uzly A, B, C, D, E, F, jehož hranové ohodnocení je dáno uvedenou tabulkou. Ke konkrétnímu řešení této úlohy se vrátíme za chvíli. Uvědomme si, že v zadaném případě bychom pravděpodobně minimální kostru našli poměrně brzy i bez nějaké teorie. V komplikovanějším případě je však nalezení minimální kostry bez znalosti vhodného algoritmu velmi 4. Stromy 111 obtížné. Proto si nyní jednoduchý algoritmus pro konstrukci minimální kostry uvedeme. (První algoritmus pro nalezení minimální kostry nalezl již v r. 1926 O. Borůvka, jak jsme se již zmínili v paragrafu 1 1. kapitoly. Podrobněji o historii tohoto algoritmu viz. např. v [11]). 4.18. Věta. Algoritmus pro hledání minimální kostry: Buď[U, H, f] konečný souvislý hranově ohodnocený graf. Všechny hrany sestavme do posloupnosti (h\, . .. ,hn) tak, aby posloupnost (f(hi)i ■ ■ ■ i f(nn)) byla neklesající. (Takové uspořádání hran vzhledem ke konečnosti grafu jistě existuje i když. obecně není určeno jednoznačně.) Požadovaný algoritmus nyní můžeme popsat takto: (1) Polož. Ho = 0, i = 1. (2) Obsahuje graf[U, íř,_i U {hi}] kružnici? Pokud ano, přejdi k bodu (4). Pokud ne, přejdi k bodu (3). (3) Polož Hi = Hi_x U {hi}. Přejdi k bodu (5). (4) Polož Hi = Hí-l (5) Je i = n? Pokud ano, pokračuj podle bodu (6). Pokud ne, přejdi k bodu (8). (6) Polož Hi = K. (7) KONEC. [U, K] je minimální kostra. (8) Zvětši hodnotu i o jedničku a vrať se k bodu (2). Popsaným způsobem skutečně v [U, H] sestrojíme minimální kostru [U, K]. To, že [U, K] je kostra, je evidentní. Nyní je však nutno dokázat, že tato kostra je minimální, tj. že pro každou kostru [U, L] v [U, H] platí ]T f(h) < ]T f(h). h€K h€L Tento důkaz nebudeme provádět. Jednoduše jej lze provést například pomocí teorie tzv. matroidů, o nichž v tomto textu nehovoříme. Řešení příkladu 4.17. Hrany grafu K(, uspořádáme do vhodné posloupnosti například následovně: (CD, BE, AE, BC, CE, DE, CF, BF, AB, EF, AD, BD, DF, AC, AF). Ohodnocení příslušných hran tvoří posloupnost (3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 18, 18, 24, 27, 30). Nyní podle algoritmu do kostry postupně vybereme hrany CD, BE, AE, BC, CF. (Viz obr. 4.18.) (Víme, že kostra musí obsahovat 5 hran.) Minimální náklady na železniční síťjsou tak 30 milionů Kč. 112 II. TEORIE GRAFŮ E D E Obr. 4.18: Minimální kostra Obr. 4.19: Minimální kostra v ohodnoceném grafu 4. Stromy 113 4.19. Příklad. Na obr. 4.19a je hranově ohodnocený graf, na obr. 4.19b jeho minimálni kostra. Ponecháme čtenáři, aby si promyslel, zdaje tato minimální kostra určena jednoznačně. Cvičení 1. Najděte sedm neizomorfních podgrafů grafu ^3. 114 II. TEORIE GRAFŮ 5 Mosty, artikulace a některé grafové charakteristiky V předcházejícím paragrafu jsme hovořili převážně o grafech neobsahujících žádnou kružnici. „Většina" grafů však pochopitelně kružnice obsahuje. V řadě úvah o grafech je nutno hrany rozlišovat podle toho, zda leží na nějaké kružnici nebo nikoliv. 5.1. Definice. Hrana grafu se nazývá most, když neleží na žádné kružnici. 5.2. Příklad, (a) Ve stromu je každá hrana mostem. (b) Graf na obr. 5.20 obsahuje právě jeden most - hranu xy. Obr. 5.20: 5.3. Věta. Buďxy most v souvislém grafu [U, H]. Pak je graf[U, H — {xy}] nesouvislý a má právě dvě komponenty. Důkaz. V grafu [U, H — {xy}] neexistuje sled mezi uzly x, y, takže tento graf je nesouvislý. Množina uzlů se rozpadne evidentně na dvě disjunktní množiny U(x) a U (y) (při označení z definice 3.12). • 5.4. Důsledek. Každá kostra konečného souvislého grafu obsahuje všechny mosty tohoto grafu. 5.5. Definice. Řekneme, že uzel x e U grafu [U, H] je artikulace, když existují hrany xy, xz £ H, xy ji xz, které neleží současně na žádné kružnici. 5.6. Příklad, (a) Ve stromu je artikulací každý uzel, jehož stupeň je alespoň 2. (b) Graf na obr. 5.21 má právě jednu artikulaci - uzel x. 5. Mosty, artikulace a některé grafové charakteristiky 115 b a O' ■O- x e ô- ■ód Obr. 5.21: 5.7. Definice. Buď § = [U, H] graf, uv e H libovolná hrana. Množinu H(uv) c H definujeme takto: je-li hrana uv mostem, je H(uv) = {uv}. Pokud uv mostem není, pak Pak je zřejmě \U(uv), H(uv){ podgrafem grafu §. Tento podgraf nazýváme člen grafu § příslušný hraně uv. 5.8. Příklad. Člen grafu z obr. 5.21 příslušný hraně ab je trojúhelník o vrcholech a, b, x, člen příslušný hraně cd je kružnice o vrcholech c, d, e, x. Buď[U, H] graf a ww, xy jeho libovolné navzájem různé hrany takové, že H(uv)DH(xy) ý ý 0. Nechť například ab e H(uv) n H(xy). Pak v [U, H] existuje kružnice Ri obsahující hrany uv i ab. Nechť Ri = [Ui, ířj, R2 = [U2, H2]. Podle předpokladu je \U\ n U2\ > 2, neboť a, b c U\fMJ2. Buďte r,s e U1CMJ2 libovolné navzájem různé uzly. Pak existuje v Ri cesta z r do s obsahující hranu uv. Protože U\ n t/2 je konečná množina, existují prvky ro, so £ t^i H U2 takové, že délka uvedené cesty je minimální. Označme tuto minimální cestu C\. Protože však ro, sq e U2, existuje mezi ro, so cesta C2 v R2 obsahující hranu xy. Spojením cest C\ a C2 však zřejmě v [U, H] obdržíme kružnici obsahující hranu uv i hranu xy. To však znamená, že xy e H(uv) a současně uv & H(xy). Odtud plyne H(uv) = H(xy). Právě jsme tak dokázali, že pro dvě hrany uv, xy e H platí buďto H(uv) n H(xy) = = 0 nebo H(uv) = H(xy). Protože pro libovolnou hranu uv e H platí uv e H(uv), je H(uv) ý 0. Odtud celkem plyne H(uv) = {xy e H; existuje kružnice v § obsahující xy i uv .} Dále položme U(uv) = {t e t/; f inciduje s některou hranou z H(uv)}. 116 II. TEORIE GRAFŮ 5.9. Věta. Systém množin {H(uv); uv e H} tvoří rozklad na množině H. Zatímco komponenty grafu tvoří disjunktní podgrafy, členy grafu obecně disjunktní pod-grafy daného grafu nejsou. Platí totiž 5.10. Věta. Uzel x je artikulací grafu [U, H] právě tehdy, když existují hrany xy ý xz„ Z. nichž, každá patří do jiného členu grafu. Důkaz. Je-li x artikulace, pak existují hrany xy, x z neležící na jedné kružnici. Pak ale H(xy) ý ý H(xz). Patří-li naopak hrany xy, xz různým členům grafu, neexistuje kružnice, která by obě hrany obsahovala. To však znamená, že x je artikulace. • Důležitou charakteristikou grafů je tzv. „cyklomatické číslo", nazývané též Bettiho číslo daného grafu. 5.11. Definice. Buď§ = [U, H] konečný graf. Cyklomatickým číslem grafu nazýváme číslo v(%) = \H\-\U\+k, kde k je počet komponent grafu §. 5.12. Věta. Cyklomatické číslo každého konečného grafu je nezáporné. Důkaz. Buď [U, H] konečný souvislý graf, tj. k = 1. Podle věty 4.8 existuje v [U, H] kostra [U, Hrf. Podle věty 4.3 platí = \U\ - 1. Protože < \H\, plyne odtud\H\ > \U\ - 1, tj- \H\ -\U\ + l>0. (b) Nechť [U, H] je konečný nesouvislý graf s komponentami [Ui, /řj], ..., [Uk, Hk]. Podle (a) pro každé i platí\H,■ | - \U,-\ + 1 > 0, takže k J2(\Hi\-\Ui\ + l) = \H\-\U\+k>0. i=l Z důkazu věty 5.12 a věty 4.3 okamžitě plyne 5.13. Věta. Cyklomatické číslo konečného grafu je rovno nule právě tehdy, když je tento graf lesem. 5.14. Poznámka. Z výše uvedeného je zřejmé, že cyklomatické číslo grafu udává v jistém smyslu „míru složitosti" tohoto grafu. Názorně řečeno, udává, kolik hran je v § nutno odstranit, aby v § nezůstala žádná kružnice. 5. Mosty, artikulace a některé grafové charakteristiky 117 Tak jsme výše popsaným způsobem charakterizovali, alespoň v jistém smyslu, „složitost" grafu. Je samozřejmě účelné umět vhodným způsobem popsat i jiné grafové charakteristiky. Ukažme si takovou charakteristiku alespoň na případě souvislosti grafů. Elementární odhad „míry souvislosti" grafu je evidentní - touto mírou je počet komponent. Popis „míry souvislosti" souvislého grafu je komplikovanější, i když čtenář patrně má jistou intuitivní představu o tom, co to znamená, že jeden graf je „souvislejší" než druhý. 5.15. Definice. Buď fy = [U, H] souvislý graf. Množina A c U se nazývá uzlový řez grafu [U, H], jestliže se souvislost grafu poruší, vyškrtneme-li z [U, H] všechny uzly množiny A a všechny hrany, které s těmito uzly incidují. (Tj. graf [U — A, H — {xy e H; xy n A jí 0}] je nesouvislý.) Uzlový stupeň souvislosti u(fy) grafu fy je minimální mohutnost uzlového řezu v fy. 5.16. Poznámka. Podle definice 5.15 lze určit uzlový stupeň souvislosti každého konečného souvislého grafu kromě úplných grafů K„ (promyslete si, které hrany musíme podle definice 5.15 vyškrtnout!). Pro tyto grafy defmitoricky klademe u(Kn) = n — 1. Podobně jako uzlový se definuje i hranový stupeň souvislosti. 5.17. Definice. Buď fy = [U, H] souvislý graf. Množina H\ c H se nazývá hranový řez v fy, je-li graf [U, H — H\\ nesouvislý. Hranový stupeň souvislosti h (fy) grafu fy je minimální mohutnost hranového řezu v fy. 5.18. Poznámka. Podle definice 5.17 lze určit h(fy) pro každý konečný souvislý graf kromě grafu Ki (tj. grafu o jednom uzlu). Pro tento graf defmitoricky klademe h(K\) = 0. 5.19. Příklad. Pro graf fy na obr. 5.22a platí u(fy) = 2, h(fy) = 3. Jeden z minimálních uzlových řezů je vyznačen plnými kroužky, jeden z minimálních hranových řezů je vyznačen tučnými hranami. Na obr. 5.22b, respektive 5.22c, je graf vzniklý „odstraněním" příslušného uzlového, respektive hranového, řezu. 5.20. Věta. Buď fy = [U, H] konečný souvislý graf. Pak platí u(fy) < h(fy) < min {stx; x e U}. 118 II. TEORIE GRAFŮ (a) (c) Obr. 5.22: Důkaz. Je-li h(fy) = 0, je také u(fy) = 0, neboť fy je v tom případě K\. Je-li h(fy) = 1, existuje hrana xy e H taková, že [U, H — {xy}] je nesouvislý graf. Pak je však zřejmě fy = K2 (a tedy u(fy) = 1 podle poznámky 5.16) nebo je {x}, respektive {y} uzlový řez v fy (takže opět u(fy) = D- Předpokládejme proto, že h(fy) > 1. Buď ířj hranový řez, \H\\ = h(fy). Zvolme hranu h & Hi libovolně. Na každé další hraně e e H\ zvolme uzel xe tak, že xe není incidentní s hranou h. Nyní z grafu fy odečteme všechny uzly xe (e e íři — {«}) a hrany s těmito uzly incidentní. Je-li takto vzniklý graf nesouvislý, platí w($) < V opačném případě obdržíme nutně uzlový řez, přidáme-li k uzlům xe ještě jeden z uzlů tvořících hranu h. Pak ale Dokázali jsme tak, že w($) < Druhá nerovnost ve větě je však zřejmá, neboť pro každý uzel x e U tvoří množina všech hran incidentních s x evidentně hranový řez. • Ve větě 2.8 jsme dokázali, že v konečném grafu [U, H] platí VJ st x = 2\H\. Odtud však xeU 21HI o okamžitě plyne, že min {stx; x e t/} < -^i. Z této nerovnosti a z věty 5.20 plyne důsledek. 5.21. Důsledek. Buď fy = [U, H] konečný souvislý graf. Pak 2\H\ \U\ Pro uzlovou i hranovou souvislost jsou známy významné charakterizační věty (Mengerova a Fordova-Fulkersonova). Vzhledem k jejich závažnosti v řadě aplikací je uvedeme, i když jejich důkazy přesahují rámec našeho textu. K formulaci těchto vět však potřebujeme následující jednoduchou definici. 5.22. Definice. Graf fy se nazývá uzlově, respektive hranově k-souvislý, jestliže platí w($) > > k, respektive h(fy) > k. 5.23. Věta. (Mengerova věta.) Graf fy je uzlově k-souvislý právě tehdy, když pro každé dva uzly x, y existuje k cest z. x do y, které jsou až. na uzly x, y vzájemně disjunktní. 6. Eulerovské a hamiltonovské grafy 119 5.24. Důsledek. Graf fy je uzlově 2-souvislý právě tehdy, když ke každým dvěma uzlům x, y existuje kružnice v fy, která je obsahuje. 5.25. Věta. (Fordova-Fulkersonova věta.) Graf fy je hranově k- souvislý právě tehdy, když pro každé dva uzly x, y existuje k cest z. x do y, které jsou hranově disjunktní. 6 Eulerovské a hamiltonovské grafy Kreslení obrázků „jedním tahem" je obvyklou součástí tzv. rekreační matematiky. Pravděpodobně každý čtenář si již jako dítě vyzkoušel, že „domeček" na obr. 6.23a lze jedním tahem nakreslit; a snadno lze ověřit, že obr. 6.23b jedním tahem nakreslit nelze. Obr. 6.23: Kreslení grafů jedním tahem Jak jsme uvedli již v paragrafu 1, vyřešil tuto problematiku již v 18. století Euler v souvislosti s problémem sedmi mostů města Královce. Připomeňme si ještě, že „tah" v grafu jsme definovali v definici 3.4. 6.1. Definice. Řekneme, že graf fy lze sestrojit jedním tahem, když v fy existuje tah obsahující všechny hrany tohoto grafu. V dalším udáme popis všech grafů, které lze jedním tahem sestrojit. 6.2. Definice. Konečný graf bez izolovaných uzlů, jehož každý uzel je sudého stupně, se nazývá eulerovský. 6.3. Věta. Každý uzel eulerovského grafu je obsažen alespoň v jedné kružnici. 120 II. TEORIE GRAFŮ Důkaz. Buď [U, H] eulerovský graf, x e U libovolný uzel. Protože x není izolovaný, existuje hrana xy s tímto uzlem incidentní. Tato hrana však nemůže být mostem, neboť v tom případě by podle věty 5.3 graf [U, H — {xy}] byl nesouvislý a komponenta obsahující bod x by obsahovala jediný uzel lichého stupně (totiž uzel x). To však podle věty 2.11 není možné. Odtud plyne, že hrana xy leží na nějaké kružnici, a tedy i x leží na kružnici. • 6.4. Věta. Konečný souvislý graf lze sestrojit jedním uzavřeným tahem právě tehdy, když. je tento graf eulerovský. Důkaz. I. Lze-li konečný graf sestrojit jedním uzavřeným tahem, je tento graf nutně souvislý. V uzavřeném tahu přitom z každého uzlu tolikrát vystoupíme, kolikrát jsme do něj vstoupili. Je tedy stupeň každého uzlu sudý. II. Buď fy = [U, H] souvislý eulerovský graf. Dokážeme, že fy lze sestrojit jedním uzavřeným tahem. Zvolme libovolně uzel u e U. Podle věty 6.3 leží tento uzel na nějaké kružnici, přičemž kružnice je uzavřeným tahem v fy. Množina A všech uzavřených tahů obsahujících uzel u je tedy neprázdná. Protože je A konečná, obsahuje tahy maximální délky. Nechť tedy cŕo e A je některý tah maximální délky. Předpokládejme nyní, že existuje hrana xy e H, která není obsažena v tahu ao- Označme H* = {xy e H; xy není obsažena v tahu ao}, U* = jiéO; existuje y & U tak, že xy e H*}. Pak je [U*, H*] podgraf grafu fy. Z definice grafu [U*, H*] je přitom okamžitě zřejmé, že je to eulerovský graf. Protože je fy souvislý, existuje nutně uzel v £ U*, který je obsažen v tahu ao- Protože je [U*, H*] eulerovský, je uzel v obsažen v nějaké kružnici C grafu [U*, H*]. Když nyní v fy utvoříme sled začínající v u, pokračujeme v něm až do uzlu v, nyní projdeme kružnici C až do uzlu v a pak dokončíme tah cŕo až do uzlu u, vytvoříme v fy uzavřený tah obsahující uzel u, jehož délka je větší než délka tahu ao. To je však spor s definicí ao. To znamená, že H* = 0, a tak cŕo obsahuje všechny hrany. • Pomocí věty 6.4 nyní snadno popíšeme i ty grafy, které lze sestrojit jedním otevřeným tahem. 6.5. Věta. Bud'fy konečný souvislý graf. Pak lze fy sestrojit jediným otevřeným tahem právě tehdy, když fy obsahuje právě dva uzly lichého stupně. Obsahuje-li fy právě dva uzly lichého stupně, pak otevřený tah v jednom z těchto uzlů nutně začíná a ve druhém končí. 6. Eulerovské a hamiltonovské grafy 121 Důkaz. I. Nechť lze souvislý graf § sestrojit jedním otevřeným tahem začínajícím v uzlu x a končícím v uzlu y. Pak jsou uzly x, y evidentně lichého stupně a všechny ostatní uzly jsou stupně sudého. II. Nechť § = [U, H] je konečný souvislý graf obsahující právě dva uzly x, y lichého stupně. Buď z ^ U libovolný prvek. Položme U\ = U\J {z}, H\ = H U {xz, y z}- Pak je [U\, H\\ souvislý eulerovský graf, takže podle věty 6.4 lze tento graf sestrojit jedním uzavřeným tahem. Uvažme takový uzavřený tah; jistě můžeme předpokládat, že začíná a končí v uzlu z. Když nyní z tohoto tahu „vyškrtneme" hrany xz, y z, dostaneme zřejmě požadovaný otevřený tah. • Jak si čtenář jistě mnohokrát povšimnul i v jiných matematických disciplínách, lze tutéž skutečnost často popsat na první pohled zcela odlišnými způsoby. Samozřejmě, že je tomu tak i v teorii grafů. Proto i tak jednoduchá tvrzení jako jsou věty 6.4 a 6.5 lze v literatuře najít ve zcela odlišných formulacích. Ukažme si to alespoň na jednom příkladu. 6.6. Definice. Jsou-li [U, H], [U\, H\\ grafy, nazveme zobrazení / : U —> U\ homorfismem grafu [U, H] do grafu \U\, H\\, jestliže pro každou hranu xy e H platí, že f(x)f(y) e H\ (tj. hrana se zobrazí na hranu). (Srovnej s definicí izomorfismu uvedenou v definici 4.13.) Vcelku snadno lze dokázat následující tvrzení, jehož důkaz přenecháme čtenáři. 6.7. Věta. Souvislý graf \U, H]je eulerovský právě tehdy, když je homorfním obrazem kružnice délky \H\. Přeformulování vět 6.4 a 6.5 je nyní zřejmé. Problematika, kterou se nyní budeme zabývat, jakkoliv je jednou z nejkomplikovanějších částí teorie grafů, má svůj prapůvod v hříčce, kterou v roce 1859 vymyslel irský matematik W. R. Hamilton (známý především objevem tzv. kvaternionů). Jak dobře víme, jedním z pěti pravidelných mnohostěnů je pravidelný dvanáctistěn, jehož povrch je tvořen shodnými pětiúhelníky. (O pravidelných mnohostěnech budeme podrobněji hovořit v poznámce 7.17.) Povrch tohoto dvanáctistěnu rozvinutý do roviny je na obr. 6.24a. Hamilton připojil ke každému z dvaceti vrcholů tohoto dvanáctistěnu jméno některého světového velkoměsta a nabídl jednomu výrobci hraček výrobu „hlavolamu", jehož řešením je „cesta kolem světa" po hranách daného dvanáctistěnu, během níž se vyjde z některého města, každým z dalších měst se projde právě jednou a cestovatel se nakonec vrátí do výchozího města. Grafová formulace tohoto „hlavolamu" je evidentní. Je dán graf o 20 uzlech (vrcholy dvanáctistěnu), hrany grafu odpovídají hranám dvanáctistěnu (jak v paragrafu 7 odvodíme, je těchto hran 30) a naším úkolem je v tomto grafu najít kružnici procházející všemi uzly. Na obr. 122 II. TEORIE GRAFŮ (b) Obr. 6.24: Povrch dvanáctistěnu 6.24b je znázorněno jedno z řešení. Hrany ležící na kružnici jsou vytaženy silněji. (Graf 6.24b jsme již viděli na obr. 2.9a.) Nyní uveďme standardní terminologii. 6.8. Definice. Graf se nazývá hamiltonovský, když v něm existuje kružnice procházející všemi uzly. Tato kružnice se nazývá hamiltonovská. 6.9. Poznámka, (a) V definici 2.13 jsme definovali pravidelný graf. Faktor, který je pravidelným grafem, nazýváme pravidelným faktorem. Pravidelný faktor 2. stupně obvykle nazýváme kvadratickým faktorem. Můžeme tedy říci, že hamiltonovská kružnice je souvislý kvadratický faktor daného grafu. (b) Graf na obr. 6.24b je hamiltonovský. Je však zřejmé, že existují grafy, které hamiltonov-ské nejsou. Takové jsou například všechny stromy; protože v nich neexistuje žádná kružnice, neexistuje v nich tím spíše kružnice hamiltonovská. Jakkoliv se na první pohled může zdát problém charakterizace hamiltonovských grafů jednoduchý, není dodnes známa žádná nutná a dostatečná podmínka této skutečnosti. Před uvedením některých známých výsledků ještě uveďme jeden příklad. 6.10. Příklad. S Eulerovým jménem je spojována i následující úloha: Může jezdec projít šachovnici (o 64 polích) tak, aby každým polem prošel právě jednou a posledním tahem se vrátil na výchozí pole? Grafová formulace je snadná. Uvažujeme graf, jehož uzly jsou jednotlivá pole na šachovnici. Dva uzly jsou pak spojeny hranou právě tehdy, když jezdec může skočit z jednoho pole na 6. Eulerovské a hamiltonovské grafy 123 drahé. Naším úkolem je nyní v tomto grafu najít hamiltonovskou kružnici - pokud ovšem existuje. Již dávno je známo, že popsaný graf je opravdu hamiltonovský. Dodnes se však například neví, kolik hamiltonovských kružnic vlastně v tomto grafu existuje. Nakreslit daný graf nemá smysl, neboť obrázek by byl značně nepřehledný. Popsat v něm hamiltonovskou kružnici je však velmi jednoduché. Do polí schématicky znázorněné šachovnice vepíšeme čísla 1,2,... ,64 v takovém pořadí, v jakém jimi bude jezdec postupně procházet. Řešení, které uvádíme v tabulce 2.3 (popsal je v roce 1862 šachista Jaenisch je mimořádně důvtipné tím, že je současně polomagickým čtvercem; součet čísel v každém řádku a každém sloupci je roven 260. (Srovnej s Eulerovským magickým čtvercem ve cvičení ke kapitole 10.) 50 11 24 63 14 37 26 35 23 62 51 12 25 34 15 38 10 49 64 21 40 13 36 27 61 22 9 52 33 28 39 16 48 7 60 1 20 41 54 29 59 4 45 8 53 32 17 42 6 47 2 57 44 19 30 55 3 58 5 46 31 56 43 18 Tabulka 2.3: Nyní tedy uveďme některé vlastnosti hamiltonovských grafů. Následující nutná podmínka plyne bezprostředně z důsledku 5.24 6.11. Věta. Je-li fy hamiltonovský graf je jeho uzlový stupeň souvislosti u(fy) > 2. Snadno však lze ukázat, že podmínka z věty 6.11 není pro existenci hamiltonovské kružnice postačující. Například graf na obr. 6.25 má uzlový stupeň souvislosti roven 2, je však snadné se přesvědčit, že není hamiltonovský. Nalezení dostatečných podmínek toho, aby graf byl hamiltonovský, bylo velmi obtížné. Jednu z nejznámějších odvodil v roce 1952 Dirac. n 6.12. Věta. Nechťfy = [U, H]je konečný graf \U\ = n > 3 a st x > — pro každý uzel x e U. Pak je fy hamiltonovský. Důkaz. Uvědomme si nejprve, že každý konečný graf je podgrafem nějakého hamiltonovského grafu. Zejména můžeme graf [U, H] doplnit o množinu uzlů V a o množinu hran {xy; x e e U, y e V] na hamiltonovský graf. Je-li totiž U = {wj, ..., u„], stačí položit V = {vi, ..., v„] 124 II. TEORIE GRAFŮ Obr. 6.25: Graf s u(fy) = 2, který není hamiltonovský (kde U n V = 0) a hamiltonovskou kružnicí je zřejmě kružnice procházející postupně uzly U\, V\, U2, V2, ■ ■ ■ , Un, Vn, U\. Nechť nyní graf fy = [U, H] splňuje předpoklady věty a připusťme, že není hamiltonovský. Označme k nejmenší možný počet uzlů, o které když doplníme spolu s hranami výše uvedeným způsobem graf fy, tak obdržíme hamiltonovský graf fy*. Je-li U = {u\, ..., u„], V = {«!,..., vk], U* = UUV,H* = HU {uiVj; Ui e U, vj e V}, je fy* = [U*, H*]. V fy* tedy podle předpokladu existuje hamiltonovská kružnice C, procházející postupně uzly X\ , X2, ■ ■ ■ , Xm, kde m = n + k > 4, neboť podle předpokladu je n > 3, k > 1. Označení uzlů jistě můžeme zvolit tak, že x\ = u\, x2 = V\, x3 = w2 (tj- kružnice začíná „doplněnou" hranou). V H nyní nemůže být hrana x\x3 (= u\U2). Kdyby totiž x\x3 e H, bylo by doplnění grafu fy 0 uzel X2 = v\ zbytečné a to je spor s minimalitou čísla k. Označme nyní K množinu hran z H*, které neleží na kružnici C. Je-li xjx, e K pro některé 1 ý 3, pak X3XI+i ^ K, tj. X3XI+i e íř*, neboť X3XI+i jistě není hrana kružnice. Kdyby totiž X3XI+1 e K, mohli bychom v fy* sestrojit kružnici procházející postupně uzly X\, Xi, X,-_i, X;_2, . . . , X3, X;+i, X;+2, . . . , X\. Tato kružnice je však hamiltonovská v grafu, který obdržíme z fy* odečtením uzlu X2 = v\ a všech hran s tímto uzlem incidentních. To je však spor s předpokladem, že k je nejmenší nutný počet dodaných uzlů. Nyní určíme, kolik je v K hran tvaru xjx,. Uvědomme si, že v fy* platí stu j > | + k pro každý uzel u j e U. (V fy je st u j > |, v fy* s uzlem w7- navíc sousedí uzly Wj, ..., 1^.) Protože v kružnici C sousedí s uzlem x\ dva uzly, je v K alespoň | + k — 2 hran tvaru xjx,. Podle výše uvedeného to však znamená, že v H* není minimálně | + & — 2 hran tvaru X3XJ (kromě hran X3XI+1 pro xjx,- e ^ je to, jak již víme, ještě hrana xj,x\.) 6. Eulerovské a hamiltonovské grafy 125 Nyní uvažme, co všechno o uzlu X3 víme. Vychází z něho alespoň \ +k hran x3x{, přitom však v fy* nesousedí minimálně s | + k — 1 uzly x, ^ X3. Protože však všech uzlů x, ^ X3 je n + k — 1, musí platit Odtud však plyne, že k < 0, což je spor s předpokladem, že fy není hamiltonovský, takže k > 1. V roce 1960 odvodil norský matematik O. Ore ještě obecnější dostatečnou podmínku existence hamiltonovské kružnice v daném grafu. Je okamžitě zřejmé, že Diracova věta je důsledkem následujícího Oreho tvrzení. 6.13. Věta. Buď[U, H] konečný graf \U\ > 3. Nechť pro každé dva uzly x,y e U, které nejsou sousední, platí 6.14. Poznámka. Jak jsme již uvedli, není dosud známa pro hamiltonovské grafy charakterizační věta, která by udávala nutnou a dostatečnou podmínku. Proto byly hledány takové podmínky alespoň pro některé důležité třídy grafů. Dlouho byla například nevyřešena Taitova hypotéza, že každý rovinný uzlově 3-souvislý 3-pravidelný graf je již nutně hamiltonovský. (O rovinných grafech budeme podrobněji hovořit v paragrafu 7. Jsou to jednoduše řečeno grafy, které lze v rovině nakreslit tak, že se jejich hrany neprotínají.) Z platnosti Taitovy hypotézy by mimochodem plynulo kladné řešení problému čtyř barev - viz paragraf 7. V roce 1956 však jeden z nejvýznamnějších odborníků v teorii grafů W. T. Tutte uvedenou hypotézu vyvrátil. Tutteův protipříklad je uveden na obr. 6.26. Tutte však dokázal, že každý rovinný uzlově 4-souvislý graf je již, nutně hamiltonovský. 6.15. Poznámka. Existuje-li v grafu cesta procházející všemi uzly, nazývá se tato cesta hamilto-novská. Graf, v němž existuje hamiltonovská cesta, se nazývá polohamiltonovský. Je zřejmé, že každý hamiltonovský graf je současně polohamiltonovský; stejně tak je evidentní, že obrácené tvrzení obecně neplatí. Například graf K2 je polohamiltonovský, avšak není hamiltonovský. 1. Najděte tři neizomorfní hamiltonovské grafy na čtyřech uzlech. 2. Najděte dva neizomorfní hamiltonovské grafy na pěti uzlech, které mají nejvýše šest stx + st v > \U\. Pak je graf[U, H] hamiltonovský. Důkaz. Důkaz tohoto tvrzení nebudeme provádět. Cvičení hran. 3. Najděte v K7 tři hamiltonovské kružnice, v nichž je obsaženo všech 21 hran grafu K7. 126 II. TEORIE GRAFŮ Obr. 6.26: 3-souvislý 3-pravidelný nehamiltonovský graf 7 Rovinné grafy V průběhu dosavadního výkladu jsme sice grafy „kreslili", intuitivně je jistě každému čtenáři zřejmé, jak se toto kreslení provádí, avšak fakticky jsme se mohli bez tohoto kreslení obejít, neboť žádná definice ani žádné tvrzení nebylo na tomto kreslení závislé. (I když je nutno si uvědomit, že právě možnost názorného kreslení je jedním z hlavních důvodů četnosti a rozmanitosti aplikací teorie grafů.) V tomto paragrafu však bude kreslení grafů hrát centrální roli. Proto je nutno některé pojmy precizovat. Nejprve však uzavřeme následující domluvu. 7.1. Dohoda. V celém paragrafu 7 pojem „graf" značí „konečný graf. 7.2. Definice. Buď dán graf [U, H]. Nakreslení tohoto grafu (v rovině) vznikne tak, že uzly znázorníme jako body eukleidovské roviny e2 a hranu xy e H znázorníme jako oblouk v e2 s koncovými body x, y. 7.3. Poznámka, (a) V teorii grafů se studují nakreslení grafů na různých plochách (například na sféře, na anuloidu apod.). Přes důležitost těchto nakreslení se v dalším budeme zabývat pouze nakreslením grafů v rovině. 7. Rovinné grafy 127 (b) Oblouk, jak známo, je topologický obraz úsečky. (Oblouk v rovině je tedy obraz intervalu [a, b] c Ej při zobrazení /: Ej -> E2, které je prosté, spojité a má tu vlastnost, že inverzní zobrazení je rovněž spojité.) Protože oblouků mezi dvěma body x, y e E2 existuje nekonečně mnoho, plyne odtud, že graf může mít v rovině nekonečně mnoho nakreslení. Na obr. 7.27a-d jsou oblouky mezi uzly x, y. Na obr. 7.27e je křivka s koncovými body x, y, která však není obloukem. Obr. 7.27: Křivky s koncovými body x, y (c) Grafy samozřejmě většinou kreslíme tak, že hrany znázorňujeme jako úsečky nebo jiné „jednoduše vyhlížející" křivky a nikoliv tak, jak je to provedeno například na obr. 1.21a. Přesto má obecně graf nekonečně mnoho nakreslení, neboť není jednoznačně předem dáno ani rozmístění uzlů v rovině. Ponecháme na čtenáři, aby si promyslel, že na obr. 7.28a-d je nakreslen tentýž graf. To, že je na výše uvedených obrázcích nakreslen jeden a tentýž graf, lze jinými slovy zformulovat tak, že každé dva grafy, které mají nakreslení na některém z obr. 7.28, jsou izomorfní. Uvážíme-li, že na těchto obrázcích jsme kreslili jednoduchý graf na šesti uzlech, není jistě překvapující, že obecně rozeznat, zda dané dva grafy jsou izomorfní, je jednou z nejtěžších otázek teorie grafů. Dodnes není znám efektivní algoritmus pro řešení tohoto problému. Při nakreslení grafu se hrany mohou, avšak nemusí, vzájemně křížit. Při některých úvahách a aplikacích je důležité zjistit, zda lze daný graf nakreslit tak, aby se hrany nekřížily. (Například v problematice tištěných spojů apod.) Tím je motivována následující definice. 128 II. TEORIE GRAFŮ Obr. 7.28: Izomorfní grafy na šesti uzlech 7. Rovinné grafy 129 7.4. Definice. Graf se nazývá rovinný (též planárnf), když existuje takové jeho nakreslení, že každé dvě různé hrany mají nejvýše jeden společný bod - uzel, který je případně s oběma hranami incidentní. Na první pohled je zřejmé, že například stromy nebo kružnice jsou rovinnými grafy. Dokázat, že nějaký graf je rovinný je však zřejmě jednodušší, než dokázat, že daný graf rovinný není. Častou hříčkou je například nalezení rovinného nakreslení grafu na obr. 7.28a. (Podle této známé rekreační úlohy se také tomuto grafu často říká tři domy a tři studně.) Jak v dalším uvidíme, nemá tato úloha řešení, neboť graf na obr. 7.28a není rovinný. 7.5. Příklad. Graf K4 je rovinný, i když jeho „běžné" nakreslení je takové, že se hrany protínají (obr. 7.29a). Důležité totiž je, že existuje nakreslení, v němž se hrany neprotínají (obr. 7.29b). Tentýž graf lze však nakreslit ještě mnohem „elegantněji" (obr. 7.29c). (a) (b) (c) Obr. 7.29: Různá nakreslení grafu K4 Existence nakreslení grafu K4 z obr. 7.29c zákonitě vyplývá z následujícího tvrzení, které odvodil Wagner v roce 1936. Důkaz tohoto tvrzení nebudeme uvádět. 7.6. Věta. Graf je rovinný právě tehdy, když. existuje jeho rovinné nakreslení takové, ž.e všechny jeho hrany jsou znázorněny úsečkami. Jedním z nejdůležitějších tvrzení o rovinných grafech je tzv. Eulerova věta. K její formulaci však potřebujeme následující definici. 7.7. Definice. Buď [U, H] rovinný souvislý graf. Buď dáno některé jeho rovinné nakreslení. Označme W množinu všech oblastí, na něž je tímto nakreslením rovina rozdělena (včetně „vnějšku"). Pak trojici [ U, H, W ] nazveme mapou. 130 II. TEORIE GRAFŮ 7.8. Poznámka. Oblast, jak známo, je otevřená souvislá množina. Například každá kružnice rozdělí rovinu na dvě oblasti - vnitřek a vnějšek. Mapa určená nakreslením grafu K4 na obr. 7.29c obsahuje 4 oblasti. Nakreslení téhož grafu na obr. 7.29a žádnou mapu neurčuje, neboť uvedené nakreslení není rovinné. 7.9. Věta. (Eulerova věta.) Buď[ U, H, W ] libovolná mapa. Pak |W| + |í/|-|íř|=2. (7.1.) Důkaz. Indukcí vzhledem k číslu \H\. Je-li H = 0, je nutně \U\ = 1, neboť graf [U, H] je souvislý. Pak ale | W\ = 1 a rovnost 7.1. je splněna triviálně. Předpokládejme nyní, že rovnost 7.1. platí pro všechny mapy [ U, H, W ] takové, že \H\ < n. Buď [ U, H, W ] mapa, \H\ = n + 1. Rozlišíme dva případy: (a) Graf [U, H] obsahuje most xy. Podle věty 5.3 je graf [U, H — {xy}] nesouvislý a má dvě komponenty \U\, H\\, [U2, Hi\ Protože \H\\ < n, IÍ/2I — n> Piatí podle indukčního předpokladu pro mapy [ U\, H\, W\ ] a [ U2, H2, W2 ] |Wi| + |í/i|-|íři| = |W2| + |í/2|-|íř2l=2. Dále platí + \H2\ + 1 = \H\ (neboť od H jsme odečetli hranu xy) a \Ui \ + \U2\ = \U\. Odečtením mostu se v dané mapě počet oblastí nezměnil, avšak v součtu | Wi | +1W21 je „vnějšek" započítán dvakrát. Proto | W\ \ + IW2I = | W| + 1. Odtud celkem dostáváme: |W| + |í/j-|íř| = (|Wi| + |W2|-l) + (|í/i| + |í/2|)- -(líř1l + líř2l + l) = = (|Wi| + |í/i| - |íři|) + (|W2| + \U2\ -\H2\) -2 = = 2 + 2-2 = 2. V případě, že [U, H] obsahuje most, je tak věta dokázána. (b) Nechť [U, H] neobsahuje most. Buď h e H libovolná hrana. Protože h není most, leží na nějaké kružnici. Označme C kružnici maximální délky, která obsahuje hranu h. Uvnitř kružnice C je nutně nějaká oblast, která vynecháním hrany h v mapě [ U, H, W ] zanikne. V mapě [U, Hi,W\] vzniklé z mapy [ U, H, W ] odečtením hrany h je tedy o jednu hranu a jednu oblast méně než v mapě původní. Protože | H\ \ = n, platí pro mapu [ U, H\, W\ ] rovnost 7.1., tj. 1^1 + \ U\ - \Hi \ = 2. Odtud však plyne platnost 7.1. i pro mapu [ U, H, W ]. • Pomocí Eulerovy věty lze snadno dokázat následující důležité tvrzení. 7.10. Věta. Graf K5 (tj. úplný graf na pěti uzlech) ani graf z. obr. 7.28a (tj. graf „3 domy a 3 studně") není rovinný. 7. Rovinné grafy 131 Důkaz, (a) Připusťme, že graf ^5 je rovinný. Nechť tedy [ U, H, W ] je mapa vzniklá některým jeho rovinným nakreslením. Platí =5, = 10, tj. \W\ =2+\H\ -\U\ =7. Každá oblast přitom musí mít hranici alespoň ze tří hran a každá hrana odděluje alespoň dvě oblasti (protože v ^5 neexistují mosty). Platí tak 2- 10 > 3 • \W\, tj. I W\ < 7, což je spor. (b) Analogicky. Kdyby [ U, H, W ] byla mapa vzniklá rovinným nakreslením grafu „3 domy a 3 studně", platilo by v této mapě, \U\ = 6, \H\ = 9, tj. \ W\ = 5. Každá oblast je opět omezena alespoň třemi hranami. Každá kružnice v [U, H] má jistě sudou délku (pravidelně se v ní musí střídat „domy" a „studně"), takže každá kružnice má délku nejméně 4. Odtud plyne 2-9 > 4- \W\, tj. I W\ < 5, což je spor. • 7.11. Poznámka. Jak dokázal v roce 1930 významný polský matematik K. Kuratowski, hrají grafy z věty 7.10 v charakterizaci planárních grafů zcela zásadní roli (viz věta 7.16). Proto se těmto grafům často také říká Kuratowského grafy. Pro jejich důležitost si tyto grafy ještě jednou nakresleme (obr. 7.30), i když jsme se s nimi již nejednou setkali. (a) Obr. 7.30: Kuratowského grafy 7.12. Definice. Buď [U, H] libovolný graf, xy e H jeho libovolná hrana. Buď z £ U U H libovolný prvek. Položme U* = U U {z}, H* = (H — {xy}) U {xz,yz}- Pak řekneme, že graf [U*,H*] vznikl z grafu [U,H] půlením hrany xy. 132 II. TEORIE GRAFŮ 7.13. Příklad. Graf na obr. 7.31b vznikl z grafu na obr. 7.31a půlením jedné z hran. (a) (b) Obr. 7.31: Půlení hrany I z názoru je zřejmé, že při kreslení grafů se takové dva grafy, z nichž jeden vznikl z druhého postupným půlením hran, „chovají stejně". Tím je motivována následující definice. 7.14. Definice. Řekneme, že grafy M jsou homeomorfní, jestliže existují konečné posloupnosti grafů $1 > $2 5 ■ ■ ■ 5 %>n IP np np ip takové, že : (a) je izomorfní s Mm; (b) v každé z těchto posloupností vznikl následující graf z předcházejícího půlením některé hrany. 7.15. Příklad. Každé dvě kružnice jsou homeomorfní. Nyní uvedeme bez důkazu již zmiňovanou Kuratowského větu. 7.16. Věta. Graf je rovinný právě tehdy, když. neobsahuje podgraf homeomorfní s některým Kuratowského grafem (tj. s některým grafem z obr. 7.30). 7. Rovinné grafy 133 7.17. Poznámka. Ukažme si, jak lze pomocí teorie rovinných grafů jednoduše zodpovědět jeden z klasických geometrických problémů. Již staří Rekové znali pět typů pravidelných mnohostěnů (tzv. Platónových těles): (a) pravidelný čtyřstěn, (b) krychli, (c) pravidelný osmistěn, (d) pravidelný dvanáctistěn, (e) pravidelný dvacetistěn. (Viz obr. 7.32). Obr. 7.32: Platónova tělesa Neuměli však dokázat, zda existují ještě jiné pravidelné mnohostěny. Metodami teorie grafů nyní ukážeme, že žádné další pravidelné mnohostěny neexistují. K tomu však potřebujeme několik jednoduchých pojmů. Omezená množina T c E3 se nazývá hvězdovitá, když existuje bod s e T takový, že každá polopřímka s počátečním bodem s má s hranicí množiny T právě jeden společný bod. Je zřejmé, že „běžná" konvexní tělesa (koule, hranol, válec apod.) jsou hvězdovité množiny. Snadno však lze ukázat, že existují i nekonvexní hvězdovitá tělesa. Z definice hvězdovité množiny okamžitě plyne, že její hranici lze zobrazit spojitou bijekcí na sféru. (Protože je T omezená, je částí nějaké koule v E3. Uvedená bijekce je realizována „promítáním" hranice na příslušnou kulovou plochu ze středu s.) Mnohostěn, který je zároveň hvězdovitou množinou, nazveme hvězdovitým mnohostěnem. Jak dobře víme, hvězdovitý mnohostěn se nazývá pravidelný, jestliže všechny jeho stěny jsou navzájem shodné pravidelné mnohoúhelníky. Ke každému pravidelnému mnohostěnu existují přirozená čísla n, p taková, že všechny stěny jsou shodné pravidelné w-úhelníky a v každém jeho vrcholu se stýká p hran. Uspořádaná dvojice [n, p] se nazývá Schlafliův symbol daného pravidelného mnohostěnu. 134 II. TEORIE GRAFŮ Schlafliův symbol Platónových těles je následující: pravidelný čtyřstěn má symbol [3, 3], krychle [4, 3], pravidelný osmistěn [3, 4], pravidelný dvanáctistěn [5, 3] a konečně pravidelný dvacetistěn [3,5]. Jak jsme uvedli, lze hranici každé hvězdo vité množiny zobrazit spojitou bijekcí na sféru. Zejména tedy lze takto na sféru zobrazit hranici (tj. povrch) každého pravidelného mnohostěnu. Uvedeným zobrazením povrchu mnohostěnu vznikne na sféře „mapa". (Definice mapy na sféře je analogická definici 7.7 mapy v rovině.) Užitím tzv. stereografické projekce však lze snadno dokázat, že pro mapy na sféře rovněž platí Eulerova věta 7.9. (Připomeňme si, že stereografická projekce je zobrazení sféry s vyjmutým jedním bodem na rovinu, definované následovně: Nechť se sféra S dotýká roviny E2 v bodě P. Buď P N průměr sféry S (viz obr. 7.33). Buď x e S libovolný bod různý od N. Bod f(x) e E2 je průsečík polopřímky N x s rovinou E2. Je zřejmé, že stereografická projekce / je bijekcí množiny S — {N} na E2 a zobrazení / i f^1 jsou spojitá. Nyní je také zřejmé, že při stereografické projekci se mapa na sféře zobrazí na mapu v rovině, přičemž se uzly zobrazí na uzly, hrany na hrany a oblasti na oblasti. Proto evidentně platí Eulerova věta i pro mapy na sféře.) N Obr. 7.33: Stereografická projekce Buď nyní T pravidelný mnohostěn. Označme R počet jeho stěn, M počet hran, N počet vrcholů, n počet stran jedné stěny, p počet hran sbíhajících se v jednom vrcholu. 7. Rovinné grafy 135 Protože každá hrana spojuje dva vrcholy a v každém vrcholu se sbíhá p hran, platí Np = 2M. (7.2.) Protože každá sténaje omezena n hranami a každá hrana sousedí se dvěma stěnami, platí Rn = 2M. (7.3.) Konečně, podle Eulerovy věty platí N + R - M = 2. (7.4.) Rovnice 7.2., 7.3., 7.4. jsou rovnice o neznámých M, N, R s parametry n, p přičemž tyto parametry jsou přirozená čísla větší nebo rovna 3. Z 7.2. - 7.4. dostáváme 2np An 4p M =---, N =-, R =---. (7.5.) 2p + 2n—np 2p + 2n—np 2p + 2n—np Protože všechna čísla M, N, P jsou kladná, musí platit 2p + 2n — np > 0, tj. (n -2)(p -2) < 4, n>3,p>3. Protože n — 2>0, p — 2>0, platí nutně (n — 2)(p — 2) e {1,2, 3}. Odtud dostáváme: (a) (n-2)(p-2)= 1 =>• n = 3, p = 3, (b) (n - 2) (p - 2) = 2 =^ ra = 3, p = 4 nebo n = 4, p = 3, (c) (n — 2)(p — 2) = 3 =^ n = 3, p = 5 nebo w = 5, p = 3. Pravidelným mnohostěnů proto existuje nejvýše pět druhů, tj. právě pět druhů. Hodnoty M, N, R, n, p těchto pravidelných mnohostěnů udává tabulka 2.4. Cvičení 1. Podle Wagnerovy věty 7.6 lze každý planární graf namalovat bez protínání hran, jimiž jsou úsečky. Namalujte tak Kuratowského grafy, z nichž je odebrána jedna hrana. 136 II. TEORIE GRAFŮ R M N n P Pravidelný čtyřstěn 4 6 4 3 3 Krychle 6 12 8 4 3 Pravidelný osmistěn 8 12 6 3 4 Pravidelný dvanáctistěn 12 30 20 5 3 Pravidelný dvacetistěn 20 30 12 3 5 Tabulka 2.4: Tabulka hodnot R, M, N, n, p pro Platónova tělesa 8 Barvení grafů Nejprve si na dvou jednoduchých problémech ilustrujme důvody, které vedly k problematice „barvení" grafů. 8.1. Problém. Mějme dánu množinu L různých druhů léků. Přitom je známo, které dvojice různých léků se pacientům nesmějí podávat současně. Na množině L chceme definovat rozklad tak, že léky ležící v jedné třídě rozkladu se sočasně podávat mohou. (Takový rozklad jistě existuje - například rozklad na jednoprvkové třídy.) Náš problém nyní zní: Jaký je minimální počet tříd takového rozkladu? Přeformulujme si problém následovně: Buď [L, H] graf, v němž pro x, y e L platí xy e H právě tehdy, když se léky x, y nesmějí podávat současně. Nyní si představme, že uzly grafu [L, H] obarvíme barvami (modře, červeně atd.) tak, že žádné dva sousední uzly nebudou obarveny stejnou barvou. Problém 8.1 nyní můžeme přeformulovat takto: Jaký minimální počet barev k výše uvedenému obarvení potřebujeme? 8.2. Problém. Je dána množina V rádiových vysílacích stanic a každá stanice x e V má určenu množinu ľjCV stanic, s nimiž má udržovat spojení. Ptáme se, jaký je minimální možný počet různých frekvencí, které musí být k dispozici, chceme-li zajistit, aby každá stanice x e V udržovala s každou ze stanic z množiny Vx spojení na jiné frekvenci? Grafová formulace je opět jednoduchá. Utvořme graf, v němž V je množina uzlů a dva uzly jsou spojeny hranou právě tehdy, když příslušné stanice mají udržovat spojení. Hledáme minimální počet barev nutný k takovému obarvení hran tohoto grafu, že každé dvě hrany, které mají společný uzel, jsou obarveny různě. Před uvedením základních výsledků o barvení grafů uzavřeme, podobně jako v paragrafu 7, následující dohodu. 8. Barvení grafů 137 8.3. Dohoda. V celém paragrafu 8 slovo „graf" značí „konečný graf". 8.4. Definice. Buď [U, H] graf. Zobrazení /:{/—»- N nazveme obarvení uzlů, jestliže pro každé dva sousední uzly x, y & U platí f (x) ý f (y) (tj. xy e H =>• f (x) ý f (y))-Řekneme, že graf [U, H] je uzlově k-chromatický, existuje-li obarvení / uzlů takové, že \f(U)\ 1, pak x(fy) = 2. Grafy s uzlovým chromatickým číslem 2 hrají v řadě aplikací důležitou roli. Jak nyní uvedeme, je charakteristika těchto grafů velmi jednoduchá. 8.6. Věta. Buď fy = [U, H] graf H ý 0. Pak x (fy) = 2 právě tehdy, když, neobsahuje kružnici liché délky. Důkaz. I. Nutnost podmínky je zřejmá, neboť k obarvení kružnice liché délky je nezbytné užít tří barev. II. Nechť fy = [U, H] neobsahuje kružnici liché délky. Dostatečnost této podmínky budeme dokazovat indukcí vzhledem k počtu kružnic v fy. Uvědomme si přitom, že důkaz stačí provést pro souvislé grafy, neboť obarvení uzlů v jednotlivých komponentách můžeme provádět samostatně a nezávisle na sobě. Neobsahuje-li fy žádnou kružnici, je fy strom a podle věty 8.5(b) platí x (fy) = 2. Nechť tedy tvrzení platí pro každý souvislý graf obsahující nejvýše n kružnic sudé délky. Buď nyní fy = [U, H] graf obsahující n + 1 kružnic sudé délky. Buď C libovolná kružnice v fy. Zvolme v C libovolně hranu xy. Graf fy* = [U, H — {xy}] obsahuje nejvýše n kružnic, takže podle předpokladu platí x(fy*) = 2. Odtud plyne existence obarvení uzlů /: U —>- {1,2} grafu fy*. Kružnice C bez hrany xy je had, v němž se obarvení uzlů pravidelně střídá. Protože tento had obsahuje sudý počet uzlů, je / (x) ý f (y). To však znamená, že / je současně obarvením grafu fy, čímž je důkaz hotov. • 138 II. TEORIE GRAFŮ 8.7. Definice. Nechť fy = [U, H] je graf a nechť lze množinu U rozložit na dvě neprázdné disjunktní podmnožiny U\, U2 tak, že každá hrana má jeden uzel v U\ a druhý uzel v U2- Pak se graf fy nazývá bipartitní. Uvedený bipartitní graf se obvykle zapisuje ve tvaru [U\, U2, H]. Bipartitní graf [ U, V, H ] se nazývá úplný, když pro každé dva uzly x e U, y e V platí xy e H. Je-li IU\ = m, \ V\ = n, značí se úplný bipartitní graf [ U, V, H ] symbolem Kmn. Tak například Kuratowského graf „3 domy a 3 studně" na obr. 7.30b je graf ^33. Pro bipartitní graf fy s neprázdnou množinou hran zřejmě platí x (fy) = 2. Bipartitní grafy jsou studovány zejména v souvislosti s tzv. párováním v grafech, což je jedna z nejzávažnějších částí kombinatoriky a teorie grafů. Zformulujme si nejprve jeden z klasických kombinatorických problémů, tzv. problém o svatbách. 8.8. Příklad. Je dána množina H hochů a množina D dívek, \D\ > \H\. Každý hoch zná alespoň jednu dívku. Jaká je nutná a dostatečná podmínka toho, aby se každý hoch mohl oženit s dívkou, kterou zná? Nalezení jednoduché nutné podmínky je snadné: kdyby existovala nějaká &-tice chlapců (k < \H\) taková, že všech dívek, které by znal alespoň jeden chlapec z této &-tice, by bylo méně než k, pak by jistě nebylo možné požadované svatby uskutečnit. Jak dokázal v roce 1935 Ph. Hall, je tato jednoduchá nutná podmínka současně také podmínkou dostatečnou. Hallova veto je jedním z nejdůležitějších kombinatorických tvrzení. 8.9. Věta. (Hallova věta.) Bud'dána množina Si, i = 1, . .. , n, neprázdných konečných množin. Pak jsou následující tvrzení ekvivalentní: n (a) Existuje prosté zobrazení f : {1, .. ., n} —>- U S, takové, ž.e f (i) e S, pro každé i I.....i: (b) Pro každou podmnožinu IÍ^A c [1.....n) platí \A\ < \ [J S,|. Grafová interpretace Hallovy věty je jednoduchá. Buď dán bipartitní graf [U,V, H ], \U\ < \ V\. Pro každý uzel x e U označme Vx = {y e V; xy e H}. 8.10. Definice. Párováním v daném bipartitním grafu [ U, V, H] nazveme každý jeho podgraf [U, V*, H* ], který je pravidelným grafem 1. stupně (tj. z každého uzlu vychází právě jedna hrana). 8. Barvení grafů 139 Z Hallovy věty okamžitě plyne, že v bipartitním grafu [ U, V, H ] existuje alespoň jedno párování [ U, V*, H* ] právě tehdy, když pro každou podmnožinu 0 ^ U\ c[í platí it/ii < x)iy*i- (8-L) xet/i Párování v bipartitním grafu se nazývá úplné, je-li faktorem daného grafu (tj. V* = V). Je zřejmé, že v [ U, V, H ] úplné párování existuje právě tehdy, když kromě podmínky 8.1. navíc platí\U\ = | V|. Jestliže v bipartitním grafu [ U, V, H ] párování neexistuje, je přirozené hledat maximální (vzhledem k počtu hran) podgraf v [ U, V, H ], který je pravidelným grafem 1. stupně. Takové podgrafy mají řadu aplikací v operačním výzkumu, v lineárním programování apod. Nejběžněj ší z algoritmů pro hledání tohoto maximálního podgrafu je tzv. maďarský algoritmus. Na obr. 8.34a je bipartitní graf, v němž neexistuje párování (je to faktor grafu ^55). Na obr. 8.34b je jeden z maximálních pravidelných podgrafu 1. stupně. (a) (b) Obr. 8.34: Maximální pravidelný podgraf 1. stupně v daném grafu Nyní se vraťme k problematice barvení uzlů v grafu. Jakkoliv je obecně určení čísla x ($) obtížné, je jednoduchá jeho následující majorizace. 8.11. Věta. Buďfy = [U, H] graf. Označme q = max {st x; x e U}. Pak platí Důkaz. Indukcí vzhledem k číslu \U\. Pro \U\ = 1 je tvrzení zřejmé. Nechť tedy tvrzení věty platí pro všechny grafy [U, H] takové, že \U\ < n. Buď nyní fy = [U, H] graf, \U\ = n + 1. Označme fy* graf, který vznikne z grafu fy odečtením některého uzlu x a všech hran s tímto 140 II. TEORIE GRAFŮ uzlem incidentních. Podle předpokladu platí x (fy*) < Q + 1, takže existuje obarvení uzlů grafu fy* f: (U — {x}) -> {1, ..., q + 1}. V grafu § však s uzlem x sousedí nejvýše q uzlů, takže uzly v fy můžeme obarvit následovně: pro t ý x, pro t = x, kde p e {1, ..., q + 1} je takový prvek, že p ^ f (u) pro všechny uzly u e U, tu e /ŕ. Pak je g obarvení daného grafu nejvýše q + 1 barvami. • Nyní se budeme zabývat barvením hran. 8.12. Definice. Buď [U, H] graf. Zobrazení /: H -> N nazveme obarvením hran, jestliže pro každé dvě hrany h\,h2 e /ř, /ij 7^ A2, takové, že h\ D h2 ý 0, platí /(Ai) 7^ f{h2). Řekneme, že graf [t/, H] je hranově k-chromatický, když existuje obarvení / hran takové, že|/(íř)| Q- Jak v roce 1964 dokázal ruský matematik G. V. Vizing, platí dokonce následující věta, kterou uvedeme bez důkazu. 8.13. Věta. Pro libovolný graf fy platí q < Xhify) < q + 1- 8.14. Poznámka. Hranové chromatické číslo daného grafu tedy může nabýt jen dvou hodnot: q nebo q + 1. Řekneme, že graf fy patří do první, respektive do druhé třídy, je-li Xhify) = q, respektive Xhify) = Q + 1- Je zřejmé, že například každá kružnice sudé délky patří do první třídy, každá kružnice liché délky do druhé třídy. Dodnes však není známa charakterizace příslušnosti grafů k těmto třídám. Přitom není zastoupení grafů v těchto třídách ani zdaleka rovnoměrné. Jak v roce 1977 dokázali P. Erdôs a R. J. Wilson, platí následující tvrzení: Označíme-li pí (n) počet grafů na n uzlech patřících do i-té třídy, platí lim ^ = 0. n^oo pi{n) Podle [10] existuje například 143 souvislých grafů s nejvýše šesti uzly a pouze 8 z nich patří do druhé třídy. Těchto 8 grafů je na obr. 8.35. 8. Barvení grafů 141 Obr. 8.35: Grafy druhé třídy na nejvýše šesti uzlech (a) (b) Obr. 8.36: Petersenův graf a jeho kvadratický faktor 142 II. TEORIE GRAFŮ 8.15. Příklad. Důležitým grafem patřícím do drahé třídy je tzv. Petersenův graf (obr. 8.36a). J. Petersen uveřejnil v roce 1891 práci v níž podrobně popsal vlastnosti pravidelných grafů; především pak studoval problém existence pravidelných faktorů v těchto grafech. Jak je okamžitě zřejmé, je Petersenův graf pravidelným grafem 3. stupně. Obsahuje pravidelný faktor 1. stupně (tzv. lineární'faktor) - hrany tohoto faktoru jsou na obr. 8.36a vyznačeny tučně. Petersenův graf obsahuje i pravidelný faktor 2. stupně (tj. kvadratický faktor); tento faktor je na obr. 8.36b. Tento kvadratický faktor však není souvislý. Ponecháme čtenáři, aby si promyslel, že souvislý kvadratický faktor (tj. hamiltonovská kružnice) v Petersenově grafu neexistuje. Petersenův graf proto není hamiltonovský. Lehce však lze ukázat, že je polohamiltonovský (viz poznámka 6.15). Na dokreslení toho, co jsme o znázorňování grafů uvedli v poznámce 7.3, nechť si čtenář promyslí, že všechny tři grafy na obr. 8.37 jsou izomorfní s Petersenovým grafem. (a) (b) (c) Obr. 8.37: Různá nakreslení Petersenova grafu 8.16. Poznámka. Hranové obarvení grafů překvapivě souvisí s latinskými čtverci, o nichž jsme hovořili v 1. kapitole, paragraf 10. Lehce lze dokázat, že úplné bipartitní grafy patří do první třídy. Evidentně platí Xh(Km,n) = Q = max (m, n). Buď n e N libovolné. Pak platí Xh(Kn,n) = n. Označme K„}„ = [ U, V, H ], U = = {u\, ..., u„], V = {v\, ..., v„], tj. H = {uíVj\ i = 1, ..., n, j = 1, ..., n}. Buď f: H —> —> {1, ..., n} obarvení hran. Definujme čtvercovou matici (a,j)"7=1 takto: = f(utVj). Pak je zřejmé, že tato matice je latinským čtvercem řádu n. Na obr. 8.38 je uvedené přiřazení provedeno pro obarvení hran grafu ^33. 8. Barvení grafů 143 Obr. 8.38: Obarvení grafu ^33 a příslušný latinský čtverec Hranové obarvení grafu Knn n barvami však současně evidentním způsobem určuje n různých úplných párování v K„}„ (Každá barva určuje jedno takové párování). Protože počet úplných párování v Kn _„ lze algebraickými metodami vypočítat (tento počet udává tzv. permanent matice sousednosti daného grafu — viz cvičení), lze odtud rovněž odvodit, že latinských čtverců řádu n je alespoň n!-(/i-l)!-(/i-2)!-...-l!. Například latinských čtverců 6. řáduje alespoň 6! • 5! • 4! • 3! • 2! = 24 883 220. 8.17. Poznámka. S problematikou barvení grafů úzce souvisí jeden z nejznámějších matematických problémů 20. století, tzv. problém čtyř barev. Formulace tohoto problému je jednoduchá: Mějme v rovině zeměpisnou mapu, na níž je několik států. Chceme, aby mapa byla vybarvena tak, jak je to obvyklé, tj. aby každý stát byl vybarven nějakou barvou tak, že žádné dva sousední státy nejsou obarveny stejně (viz například obraze 8.39). Naším úkolem je zjistit, jaký počet barev nezbytně potřebujeme, abychom mohli takto vybarvit každou zeměpisnou mapu. Aby formulace problému byla regulérní, je nutno upřesnit dvě skutečnosti: (a) předpokládáme, že území každého státu je „souvislé" (což v praxi není vždy splněno -viz například USA (Aljaška)); (b) dva státy považujeme za sousední, když mají společnou hraniční „čáru" (tj. nedotýkají se jen v izolovaných bodech). Lehce lze ukázat, že je nutno mít k dispozici alespoň čtyři barvy (obr. 8.40). Ve všech konkrétních příkladech se vždy podařilo najít obarvení čtyřmi barvami. Například na obrázku 8.41 je takto vybarvena mapa USA. Nalezení důkazu, že tomu tak je zákonitě, se však ukázalo být jedním z nej obtížnějších problémů moderní matematiky. Přeformulujme si nyní uvedený problém do grafové terminologie. Mějme dánu nějakou zeměpisnou mapu (splňující výše uvedené podmínky). Nyní zkonstruujme graf fy = [U, H] následovně. Na území každého státu zvolme jeden bod; tyto body tvoří množinu U. Dva uzly spojíme hranou právě tehdy, když příslušné státy sousedí. Takto získaný graf je jistě rovinný, neboťhrany můžeme kreslit tak, aby neprocházely územím žádného dalšího státu (hranici dvou států můžeme „překročit" v hraniční čáře). Tak například státům na obr. 8.40 odpovídá graf K4. 144 II. TEORIE GRAFŮ Contraí America nnd the Ciiribbean Obr. 8.39: Ukázka politické mapy Obr. 8.40: 8. Barvení grafů 145 Obr. 8.41: Vybarvení mapy USA čtyřmi barvami Obarvení zeměpisné mapy je nyní ekvivalentní s obarvením uzlů takto sestrojeného rovinného grafu. V grafové terminologii lze tedy problém čtyř barev přeformulovat takto: Platí pro každý rovinný graffy nerovnost x (fy) < 4? To, že i relativně komplikované grafy — viz například obrázek 8.42 — uvedenou podmínku splňují, samozřejmě ještě nic neznamená. Mlilllllilllll1 II II m Kl rTTTT m iiii r ľ r r i rtrrr rrrrr rrrrr r ľ ľ i Obr. 8.42: Vybarvení rovinného grafu čtyřmi barvami Historie toho problému sahá až do let 1840-1850, kdy se tímto problémem zabývali A. F. Möbius, A. de Morgan a další. Mnohokrát byl uvedený problém zdánlivě „vyřešen", vždy se 146 II. TEORIE GRAFŮ však ukázalo, že v důkazu byla nějaká chyba. V roce 1890 dokázal P. J. Heawood (právě při rozboru jednoho z chybných důkazů), že pro každý rovinný graf § platí x ($) < 5 (tzv. věta o pěti barvách). Definitivně problém čtyř barev vyřešili (pozitivně) až v roce 1976 K. Apple a W. Haken z univerzity v Illinois (USA), když dokázali, že vskutku pro každý rovinný graf § platí x(&) < 4. Důkaz tohoto tvrzení převedli na prověření vlastností téměř dvou tisíc speciálních grafů. Samotné prověření pak provedli na počítači, který na to spotřeboval 1200 hodin strojového času. I tyto údaje demonstrují obtížnost celého problému. Podrobněji o historii tohoto problému viz například v knize [11]. kde se sčítá přes všechny variace m prvků z množiny {1, 2, ..., n}. Vypočtěte permanent matic: Cvičení 1. Permanent matice A = typu m/n, m < n je definován jako per(A) = a. 9 Zobecnění pojmu graf Jak jsme uvedli již v paragrafu 1, není grafová terminologie v literatuře zdaleka jednotná. Ustálený význam nemá ani pojem graf. Nyní uvedeme definici tzv. „obecného grafu", která zahrnuje většinu běžně studovaných grafů jako speciální případy. 9. Zobecnění pojmu graf 147 9.1. Definice. Obecným grafem nazýváme trojici [U, H,(p ], kde U, H jsou disjunktní množiny, [/^0a(p://^[/2U[/U Pi(U). Prvky množiny U nazýváme uzly, prvky množiny H hrany a

P(U) buď libovolné zobrazení. Pak se dvojice [U, T] nazývá orientovaný graf. U je množina uzlů. Z uzlu x vede do uzlu y orientovaná hrana xy právě tehdy, když y e T (x). 9.7. Poznámka. Z výše uvedeného je zřejmé, co to znamená, že orientovaný graf [U, F] je reflexivní, symetrický, antisymetrický, tranzitivní a podobně. Radu pojmů lze z obyčejných grafů přenést na neorientované grafy prakticky beze změny - například pojem „podgraf", „izomorfismus grafů" atd. U některých pojmů dochází k jistým modifikacím. Tak například roli stupně uzlu x hrají dva tzv. polostupně |T(x)| a |r_1(x)| (tj. počty hran z uzlu x vycházejících a v uzlu x končících). Roli kružnice v orientovaných grafech hraje tzv. cyklus. Acyklický graf Je orientovaný graf neobsahující jako podgraf žádný cyklus. Důležitou třídou orientovaných grafů jsou tzv. turnaje. Areflexivní orientovaný graf se nazývá turnaj, jestliže pro každé dva různé uzly x, y platí, že jsou spojeny hranou xy, respektive yx. Přes veškeré odlišnosti mezi jednotlivými typy grafů však lze říci, že pro toho, kdo zvládne teorii pro jeden z typů, je snadné pochopení pojmů i pro zbývající typy. V aplikacích se pochopitelně užívá různých typů grafů, podle toho, jaký typ je pro popis zadané situace nej výhodnější. 9. Zobecnění pojmu graf 149 Zobecnění pojmu graf je však možno provést i jiným způsobem, než jak jsme to provedli v definici 9.1. Někdy je výhodné a potřebné studovat „grafy", jejichž hrany spojují více než dva uzly. Takovým grafům se říká obvykle hypergrafy. (V posledních letech se v české literatuře ujímá pro hypergrafy termín společnost, místo o hranách hypergrafu se pak hovoří o týmech společnosti.) Je zřejmé, že pojem hypergrafu úzce souvisí například s blokovými schématy, o nichž jsme hovořili v 1. kapitole, paragrafu 10. 9.8. Definice. Hypergraf je trojice [U, H,

(P(U) — {0}) je incidenční zobrazení. 9.9. Poznámka. Hypergraf je tedy — jednoduše řečeno — systém neprázdných podmnožin množiny uzlů. Některé množiny se přitom v tomto systému mohou opakovat. Existuje-li číslo k takové, že pro každou hranu h £ H platí \