2016

Diskr´ etn´ı matematika Petr Kov´aˇr [email protected] Vysok´ a ˇskola b´ an ˇsk´ a – Technick´ a univerzita Ostrava

DiM 470-2301/01, zimn´ı semestr 2015/2016

O tomto souboru

Tento soubor je zam´yˇslen pˇredevˇs´ım jako pom˚ ucka pro pˇredn´aˇsej´ıc´ıho. ˇ Radu d˚ uleˇzit´ych informac´ı v souboru nenajdete, protoˇze pˇredn´aˇsej´ıc´ı je ˇr´ık´a, ukazuje, pˇr´ıpadnˇe maluje na tabuli. Pˇredn´aˇsky jsou na webu k dispozici, aby studenti mohli snadno dohledat prob´ıran´a t´emata z pˇredn´aˇsek, kter´e zameˇskali. Pro samostatn´e studium doporuˇcuji skripta: M. Kubesa: Z´aklady diskr´etn´ı matematiky, v´yukov´y text ´ P. Kov´aˇr: Uvod do teorie graf˚ u, v´yukov´y text Pro pˇr´ıpravu ke zkouˇsce a p´ısemk´am doporuˇcuji cviˇcebnici: P. Kov´aˇr: Cviˇcen´ı z diskr´etn´ı matematiky, sb´ırka pˇr´ıklad˚ u Vˇse na http://homel.vsb.cz/~kov16/predmety dm.php

Pˇrehled pˇredn´ aˇsky

Kapitola Stromy motivace z´akladn´ı vlastnosti strom˚ u koˇrenov´e stromy isomorfizmus strom˚ u kostry graf˚ u

Kapitola Stromy Motivace Jedn´ım z nejbˇeˇznˇejˇs´ıch u ´tvar˚ u v pˇr´ırodˇe i v matematice jsou stromy (objekty se stromovou“ strukturou). ” Existuje cel´a ˇrada motivac´ı, kter´e m˚ uˇzeme popsat stromem“. ” rodokmeny evoluˇcn´ı strom elektrick´e rozvody hierarchick´e struktury (ˇs´ef a podˇr´ızen´y) vˇetven´ı pˇri vyhled´av´an´ı

Spoleˇcn´y rys: neobsahuj´ı cyklus“.

Z´ akladn´ı vlastnosti strom˚ u ˇ Rekneme, ˇze graf neobsahuje cyklus (kruˇznici), jestliˇze ˇz´adn´y jeho podgraf nen´ı isomorfn´ı cyklu. Graf je jedn´ım slovem acyklick´y. Definice Strom je souvisl´y graf, kter´y neobsahuje cyklus. Les je graf, jehoˇz komponenty jsou stromy.

Pozn´amka k n´azvoslov´ı: Les je jednoduch´y graf neobsahuj´ıc´ı cyklus. Strom je souvisl´y les. Coˇz nezn´ı tak pˇeknˇe. . .

Vrchol˚ um stupnˇe 1 budeme ˇr´ıkat list. Ostatn´ım vrchol˚ um budeme ˇr´ıkat nelistov´e vrcholy. Lemma Kaˇzd´y strom s v´ıce neˇz jedn´ım vrcholem m´a alespoˇ n jeden list. D˚ ukaz Souvisl´y graf s v´ıce neˇz jedn´ım vrcholem nem˚ uˇze m´ıt vrchol stupnˇe 0. Vezmeme strom T a v nˇem libovoln´y vrchol v . Sestroj´ıme co nejdelˇs´ı tah S v T , kter´y zaˇc´ın´a ve v . S zaˇcneme libovolnou hranou vych´azej´ıc´ı z v (jistˇe existuje, proˇc?). V kaˇzd´em dalˇs´ım vrcholu u tahu S bud’ u m´a stupeˇ n alespoˇ n 2 a tah S prodlouˇz´ıme o dalˇs´ı hranu a postup opakujeme, (vˇsimnˇete si: v tahu S se nem˚ uˇze zopakovat vrchol, protoˇze v T neexistuje cyklus) nebo v u je stupnˇe 1 (tah konˇc´ı hledan´ym listem). Protoˇze T je koneˇcn´y, jistˇe takov´y list ve stromu T najdeme.  Pozn´ amka Nen´ı tˇeˇzk´e uk´azat, ˇze v kaˇzd´em netrivi´aln´ım stromu existuj´ı alespoˇ n dva listy.

Ot´ azky Jak se jmenuje strom, kter´y m´a pr´avˇe 2 vrcholy stupnˇe 2 a ˇz´adn´y vrchol stupnˇe vyˇsˇs´ıho? Existuje strom, kter´y m´a vrchol stupnˇe k a m´enˇe neˇz k vrchol˚ u stupnˇe 1? Um´ıte vaˇse tvrzen´ı z pˇredchoz´ıho bodu dok´azat? Kolik mus´ıme vynechat hran z grafu Kn , abychom dostali strom?

Vˇ eta Strom s n vrcholy m´a pr´avˇe n − 1 hran. D˚ ukaz Postupujeme indukc´ı vzhledem k poˇctu vrchol˚ u n. Z´aklad indukce: (Trivi´aln´ı) strom s jedn´ım vrcholem m´a n − 1 = 0 hran. Indukˇcn´ı krok: Mˇejme netrivi´aln´ı strom T s n > 1 vrcholy. Pˇredpokl´adejme, ˇze kaˇzd´y strom s m´enˇe nˇeˇz n vrcholy m´a o jednu hranu m´enˇe neˇz vrchol˚ u. Strom T m´a alespoˇ n jeden list v (Lemma), oznaˇcme T 0 = T − v graf, kter´y vznikne z T odebr´an´ım vrcholu v (tzv. oholen´ım“). ” Odebr´an´ım listu neporuˇs´ıme souvislost grafu (ˇz´adn´a cesta mezi dvˇema vrcholy r˚ uzn´ymi od v nevede vrchol stupnˇe 1), T 0 je souvisl´y. Odebr´an´ım vrcholu/hrany nevznikne cyklus, T 0 je tak´e acyklick´y. To znamen´a, ˇze T 0 je strom s n − 1 vrcholy a podle indukˇcn´ıho pˇredpokladu m´a o jednu hranu m´enˇe neˇz vrchol˚ u. Strom T 0 m´a tedy (n − 1) − 1 hran a p˚ uvodn´ı strom T m´a o jeden vrchol a jednu hranu v´ıce, tj. strom T m´a (n − 1) − 1 + 1 = n − 1 hran. Podle principu matematick´e indukce je tvrzen´ı dok´az´ano. 

Pˇr´ıklad V datab´azi je 12 z´aznam˚ u (objekt˚ u) a 34 vazeb mezi nimi. Chtˇeli bychom strukturu datab´aze pˇrehlednˇe zn´azornit grafem, ve kter´em jsou objekty zn´azornˇeny jako vrcholy a vazby jako hrany. a) Bude takov´y graf stromem? b) M˚ uˇzeme tvrdit, ˇze takov´y v´ysledn´y graf bude souvisl´y? a) V´ysledn´y graf jistˇe nebude stromem, ale mus´ı obsahovat cykly. Strom s 12 vrcholy by musel m´ıt pr´avˇe 11 hran (vazeb). Ani kdyby vazeb bylo 11, nemohli bychom tvrdit, ˇze v´ysledn´y graf bude strom, proˇc? b) V´ysledn´y graf m˚ uˇze, ale nemus´ı b´yt souvisl´y. V´ysledek velmi z´avis´ı na struktuˇre dat. Mohlo by se st´at: graf bude
m´ıt jednu komponentu s 9 vrcholy a 3 izolovan´e vrcholy (K9 m´a 92 = 36 hran, m˚ uˇzeme vynechat 2 hrany). Pokud by dan´y graf mˇel 12 vrchol˚ u a v´ıce neˇz 55 hran, mus´ı uˇz b´yt souvisl´y. K12 m´a 66 hran a je hranovˇe 11-souvisl´y. Vynech´an´ım libovoln´ych m´enˇe neˇz 66 − 55 = 11 hran z˚ ustane v´ysledn´y graf souvisl´y.

Pozn´ amka (o d˚ ukazu vˇ et ve tvaru implikace A ⇒ B) A je pˇredpoklad vˇety, B je tvrzen´ı vˇety. D˚ ukaz pˇr´ım´y spoˇc´ıv´a v ˇradˇe platn´ych implikac´ı. A = A0 ⇒ A1 ⇒ A2 ⇒ · · · ⇒ An = B D˚ ukaz nepˇr´ım´y spoˇc´ıv´a v pˇr´ım´em d˚ ukazy vˇety ¬B ⇒ ¬A, kter´y m´a stejnou tabulku pravdivostn´ıch hodnot jako p˚ uvodn´ı v´yrok A ⇒ B. ¬B = A0 ⇒ A1 ⇒ A2 ⇒ · · · ⇒ An = ¬A D˚ ukaz sporem je modifikac´ı nepˇr´ım´eho d˚ ukazu, kdy pˇredpokl´ad´ame, ˇze ˇ plat´ı souˇcasnˇe pˇredpoklad A a negace tvrzen´ı ¬B. Radou platn´ych implikac´ı dojdeme k tzv. sporu. Sporem rozum´ıme situaci, kdy by mˇel platit v´yrok V a souˇcasnˇe tak´e jeho negace ¬V , coˇz nen´ı moˇzn´e. A ∧ ¬B ⇒ · · · ⇒ V ∧ ¬V Ke sporu vedla negace tvrzen´ı ¬B, proto plat´ı tvrzen´ı B.

Vˇ eta Mezi kaˇzd´ymi dvˇema vrcholy stromu existuje pr´avˇe jedna cesta. D˚ ukaz Postupujeme sporem. Budeme vych´azet z platnosti pˇredpokladu vˇety (T je strom) a negace tvrzen´ı (mezi nˇekter´ymi vrcholy stromu T neexistuje ˇz´adn´a nebo existuje v´ıce neˇz jedna cesta). Dostaneme spor. Stromu je T souvisl´y graf, proto v´ıme, ˇze mezi kaˇzd´ymi dvˇema vrcholy u, v stromu T vede nˇejak´a cesta. Pro spor pˇredpokl´ad´ame, ˇze mezi nˇekter´ymi vrcholy u, v existuje v´ıce takov´ych cest. Sjednocen´ı tˇechto cest je uzavˇren´y sled ve stromu T , ze kter´eho (vynech´an´ım pˇr´ıpadn´ych opakuj´ıc´ıch se hran a vrchol˚ u) dostaneme cyklus, kter´y je podgrafem ve stromu T . Dost´av´ame spor s pˇredpokladem, ˇze T je strom a neobsahuje cyklus. Negace tvrzen´ı vede ke sporu. Proto mezi vrcholy u a v existuje ve stromu pr´avˇe jedna cesta.  Pozn´ amka Cesty z u do v a “opaˇcnou” cestu z v do u povaˇzujeme za jedinou cestu mezi u, v .

Uˇz v´ıme, ˇze strom s n vrcholy obsahuje n − 1 hran. Pˇrid´an´ım jedn´e hrany neporuˇs´ıme souvislost, ztrat´ıme acykliˇcnost. Strom s pˇridanou hranou mus´ı obsahovat cyklus, uk´aˇzeme ˇze takov´y cyklus bude jedin´y. D˚ usledek Pˇrid´an´ım jedn´e (nov´e) hrany do stromu (s alespoˇ n tˇremi vrcholy) vznikne graf s pr´avˇe jedn´ım cyklem. D˚ ukaz Mˇejme strom T a nˇejak´e dva jeho vrcholy u, v , mezi kter´ymi nen´ı hrana. Pˇrid´an´ım hrany uv vznikne pr´avˇe jeden cyklus spojen´ım uv a jedin´e cesty mezi vrcholy u, v ve stromu T (jedin´e podle pˇredchoz´ı vˇety).  Pozn´ amka Pˇrid´ame-li do stromu alespoˇ n dvˇe hrany, z´avis´ı poˇcet vznikl´ych cykl˚ u na tom, kam hrany pˇrid´ame.

M´ame d´an nˇejak´y souvisl´y graf G . Pˇri urˇcov´an´ı hranov´e souvislosti jsme se ptali, kolik nejm´enˇe staˇc´ı z grafu odstranit hran, aby se G stal nesouvisl´y. M´a smysl se pt´at, kolik nejv´ıce hran m˚ uˇzeme z grafu G odstranit, aby G z˚ ustal souvisl´y, nebo naopak kolik nejm´enˇe hran mus´ı v grafu G z˚ ustat, aby byl souvisl´y. Pr´avˇe stromy jsou grafy, kter´e jsou souvisl´e a uˇz z nich nem˚ uˇzeme odebrat ˇz´adnou hranu, aniˇz by se poruˇsila souvislost. Vˇ eta Strom je minim´aln´ı souvisl´y graf (s dan´ym poˇctem vrchol˚ u). D˚ ukaz Strom je souvisl´y podle definice. Pokud souvisl´y graf obsahuje cyklus, z˚ ustane souvisl´y i po vynech´an´ı nˇekter´e hrany cyklu. Proto je minim´aln´ı souvisl´y graf acyklick´y a je tedy stromem. Naopak, pokud by vynech´an´ım hrany uv ze stromu T vznikl souvisl´y graf, pak by mezi vrcholy u, v v T existovaly dvˇe cesty: cesta z u do v v T \ uv a hrana uv . To by byl spor s pˇredchoz´ı vˇetou. Proto je strom minim´aln´ım souvisl´ym grafem na dan´ych vrcholech. 

Pˇr´ıklad Kolik nejv´ıce hran m˚ uˇzeme odstranit z grafu G na obr´azku, aby v´ysledn´y graf z˚ ustal souvisl´y?

Graf G . Podle pˇredchoz´ı vˇety v´ıme, ˇze v´ysledn´y graf po odeb´ır´an´ı hran bude stromem. Protoˇze graf G m´a 9 vrchol˚ u a 16 hran, tak podle vˇety o poˇctu hran stromu v´ıme, ˇze m˚ uˇzeme odstranit nejv´ıce 8 hran. Z grafu na obr´azku m˚ uˇzeme dokonce odstranit takov´ych 8 hran, ˇze odstranˇen´e hrany tvoˇr´ı spolu s vrcholy grafu G souvisl´y faktor a souˇcasnˇe ponechan´e hrany tvoˇr´ı souvisl´y faktor. Najdete takov´ych 8 hran?

Koˇrenov´ e stromy Nˇekdy je uˇziteˇcn´e pˇri pr´aci se strukturou typu strom“ oznaˇcit v´yznaˇcn´y ” vrchol, tzv. koˇren, ( zaˇc´atek“ uloˇzen´ych dat). Koˇrenov´e stromy maj´ı ” motivaci i v rodokmenech, odtud vych´az´ı i terminologie. Definice Koˇrenov´ym stromem nazveme strom T spolu s vyznaˇcen´ym koˇrenem r ∈ V (T ). Znaˇc´ıme (T , r ), ˇr´ık´ame strom T s koˇrenem r“. ” r

r

r

Nezamˇen ˇovat strom“ a koˇrenov´y strom“, kter´y obsahuje informaci nav´ıc. ” ” Koˇren budeme kreslit nejv´yˇse.

Definice Mˇejme d´an koˇrenov´y strom (T , r ) a v nˇem dvojici vrchol˚ u u, v , kde vrchol u je sousedn´ı s vrcholem v na cestˇe z vrcholu v ke koˇrenu r . Pak u naz´yv´ame rodiˇcem vrcholu v a v naz´yv´ame potomkem vrcholu u. koˇren u v rodiˇc potomci

x

y

z

Nˇekdy pouˇzijeme dalˇs´ı pˇrirozen´e n´azvy prarodiˇc“, sourozenec“, . . . ” ” Vˇsimnˇete si: volbou koˇrene se m˚ uˇze vz´ajemn´y vztah vrchol˚ u zmˇenit.

Definice V netrivi´aln´ıch koˇrenov´ych stromech se vrcholy bez potomk˚ u naz´yvaj´ı koncov´e vrcholy. Vˇsimnˇete si: koncov´e vrcholy jsou listy, ale ne kaˇzd´y list je koncov´ym vrcholem. Definice Centrem stromu T rozum´ıme vrchol nebo hranu v dan´em stromu T , kter´e urˇc´ıme n´asleduj´ıc´ım postupem: 1

2

Jestliˇze m´a strom T jedin´y vrchol v , je v centrum stromu T . Pokud m´a strom T dva vrcholy, je centrem stromu T hrana spojuj´ıc´ı tyto dva vrcholy. Jinak pˇrejdeme k bodu 2. Vytvoˇr´ıme (menˇs´ı) strom T 0 ⊂ T oholen´ım vˇsech list˚ u stromu T a vrac´ıme se na pˇredchoz´ı bod 1.

Rekurz´ı z´ıskan´e centrum stromu T 0 bude z´aroveˇ n centrem stromu T . Procesu, kdy ve stromu oznaˇc´ıme vˇsechny jeho listy a potom je odstran´ıme (i s pˇr´ısluˇsn´ymi hranami), se ˇr´ık´a oholen´ı stromu.

Pˇr´ıklad Urˇcete centrum stromu T1 .

Pˇr´ıklad Urˇcete centrum stromu T2 .

Vˇsimnˇete si: pˇridali jsme nov´y vrchol (a dvˇe hrany m´ısto jedn´e).

Koˇren a centrum strom˚ u Koˇren stromu m˚ uˇze b´yt libovoln´y vrchol stromu; koˇren nemus´ı leˇzet v centru. Budeme-li cht´ıt nˇejak´emu stromu pˇriˇradit koˇren jednoznaˇcnˇe, je nejlepˇs´ı za koˇren zvolit centrum stromu (protoˇze centrum je urˇceno jednoznaˇcnˇe). V pˇr´ıpadˇe, ˇze centrem stromu je hrana uv , pˇrid´ame“ na tuto hranu nov´y ” vrchol a zvol´ıme jej koˇrenem.

Pˇ estovan´ e stromy Dalˇs´ı informac´ı v´azanou ke koˇrenov´ym strom˚ um b´yv´a uspoˇr´ad´an´ı potomk˚ u kaˇzd´eho vrcholu (napˇr´ıklad seˇrazen´ı potomk˚ u jedn´e generace v rodokmenu podle data narozen´ı). Definice Koˇrenov´y strom (T , r ) je uspoˇr´adan´y, jestliˇze pro kaˇzd´y jeho vrchol je jednoznaˇcnˇe d´ano poˇrad´ı jeho potomk˚ u (napˇr´ıklad zleva doprava“). ” Uspoˇr´adan´y koˇrenov´y strom se tak´e naz´yv´a pˇestovan´y strom. 1 1 2

1 2 1

2

3 1

3 1

2

3

Form´alnˇe: pˇestovan´y strom (T , r , f ), kde T je strom a r jeho koˇren. Funkce f : V (T ) → N pˇritom pˇriˇrad´ı kaˇzd´emu vrcholu jeho poˇrad´ı mezi sourozenci 1, 2, . . . , k.

Isomorfismus strom˚ u Pojem isomorfismus strom˚ u je speci´aln´ım pˇr´ıpadem isomorfismu graf˚ u. Dva stromy jsou isomorfn´ı, pokud jsou isomorfn´ı jako grafy. Pˇripomeˇ nme, ˇze pro u ´lohu rozhodnout, zda dva obecn´e grafy jsou isomorfn´ı nen´ı zn´am ˇz´adn´y rychl´y algoritmus. Stromy jsou natolik speci´aln´ı tˇr´ıda graf˚ u, ˇze pro nˇe takov´y algoritmus existuje! Nejprve zavedeme nˇekolik pojm˚ u. Definice Dva koˇrenov´e stromy (T , r ) a (T 0 , r 0 ) jsou isomorfn´ı pokud existuje isomorfismus mezi stromy T a T 0 , kter´y zobraz´ı koˇren r na koˇren r 0 .

T

T0

Isomorfn´ı stromy, kter´e nejsou isomorfn´ı jako koˇrenov´e stromy. Vˇsimnˇete si: liˇs´ı se koˇren strom˚ u T a T 0.

Definice Dva uspoˇr´adan´e koˇrenov´e stromy (pˇestovan´e stromy) jsou isomorfn´ı, jestliˇze pro nˇe existuje isomorfismus koˇrenov´ych strom˚ u, kter´y nav´ıc zachov´a poˇrad´ı potomk˚ u kaˇzd´eho vrcholu.

Isomorfn´ı koˇrenov´e stromy, kter´e nejsou isomorfn´ı jako pˇestovan´e. Vˇsimnˇete si: liˇs´ı se poˇrad´ı potomk˚ u koˇrene. Definice Podstromem vrcholu u dan´eho koˇrenov´eho stromu (T , r ) rozum´ıme kaˇzdou komponentu grafu T − u, kter´a obsahuje nˇekter´eho potomka x vrcholu u. Kaˇzd´y podstrom vrcholu u je opˇet (koˇrenov´ym) stromem.

K´ odov´ an´ı uspoˇr´ adan´ ych koˇrenov´ ych strom˚ u Kaˇzd´emu uspoˇr´adan´emu koˇrenov´emu stromu lze snadno pˇriˇradit ˇretˇezec, kter´y jej jednoznaˇcnˇe popisuje. Vystaˇc´ıme se symboly 0 a 1 (bin´arn´ı k´od). Definice K´ od uspoˇr´adan´eho koˇrenov´eho stromu se sestav´ı rekurzivnˇe z k´od˚ u vˇsech podstrom˚ u koˇrene, seˇrazen´ych ve stejn´em poˇrad´ı jako jsou seˇrazeny koˇreny podstrom˚ u (jeho potomci), a uzavˇren´ych do p´aru 0 a 1 (viz Obr´azek). 0 000101101011 01 0001010111 1 0 001011 01 01 1 01

0 01 01 1 01 01

01

0 00101011 1 0 01 01 01 1

01 01

01

01

K´odov´an´ı uspoˇr´adan´eho koˇrenov´eho (pˇestovan´eho) stromu. Pozn´ amka M´ısto 0“ a 1“ lze pouˇz´ıt jin´e symboly, tˇreba (“ a )“ nebo A“ a B“. ” ” ” ” ” ”

Uspoˇr´ adan´ y koˇrenov´ y strom dan´ y k´ odem Uk´azali jsme, jak kaˇzd´emu uspoˇr´adan´emu stromu pˇriˇradit k´od. Nyn´ı uk´aˇzeme opaˇcn´y postup: jak nakreslit uspoˇr´adan´y koˇrenov´y strom s pˇredepsan´ym k´odem. Lemma M´ame d´an k´od S uspoˇr´adan´eho koˇrenov´eho stromu. Pˇr´ısluˇsn´y strom nakresl´ıme n´asleduj´ıc´ım postupem: pˇri pˇreˇcten´ı prvn´ıho znaku 0“ na zaˇc´atku poloˇz´ıme tuˇzku na pap´ır a ” nakresl´ıme koˇren, pˇri kaˇzd´em dalˇs´ım pˇreˇcten´ı znaku 0“ nakresl´ıme (napravo ” od pˇredchoz´ıch) hranu a nov´eho n´asleduj´ıc´ıho potomka x souˇcasn´eho vrcholu a pˇresuneme se do x, pˇri kaˇzd´em pˇreˇcten´ı znaku 1“ se vr´at´ıme do rodiˇce souˇcasn´eho ” vrcholu, pˇr´ıpadnˇe ukonˇc´ıme kreslen´ı a zvedneme tuˇzku, pokud jsme v koˇrenu. Pozor: ne kaˇzd´a posloupnost 0 a 1 je k´ odem nˇejak´eho stromu (v´ıce na cviˇcen´ı).

Minim´ aln´ı k´ od K´ ody m˚ uˇzeme ch´apat jako ˇretˇezce a ty um´ıme seˇradit jednoznaˇcnˇe, napˇr´ıklad lexikograficky. Pˇredpokl´ad´ame, ˇze znak 0 je ve slovn´ıku pˇred znakem 1. Napˇr´ıklad ˇretˇezec 000111 bude ve slovn´ıku pˇred ˇretˇezci 001011, 0011 i 01. Je nutno rozliˇsovat k´od uspoˇr´adan´eho koˇrenov´eho stromu a minim´aln´ı k´od koˇrenov´eho stromu: nakresl´ıme-li strom, kter´y je urˇcen k´ odem uspoˇr´adan´eho koˇrenov´eho stromu, dostaneme opˇet (T , r ), nakresl´ıme-li strom, kter´y je urˇcen minim´aln´ım k´ odem koˇrenov´eho stromu, m˚ uˇze se poˇrad´ı potomk˚ u oproti v´ychoz´ımu koˇrenov´emu stromu (T , r ) liˇsit. ˇ ık´ame, ˇze jsme koˇrenov´y strom (T , r ) pˇrepˇestovali“. R´ ” Pozn´ amka Horn´ı odhad sloˇzitosti algoritmu pro nalezen´ı minim´aln´ıho k´odu jednoho stromu je O(n3 ).

Pˇr´ıklad 0 001001011011 01 0001010111 1 0 01 001011 01 1

0 00101011 1

0 01 01 1

01

01

01 01 01

0 01 01 01 1

01

01

01

K´od uspoˇr´adan´eho koˇrenov´eho stromu. 0 0001010111 000101101011 01 1 0 001011 01 01 1

0 00101011 1

0 01 01 1

01

01

01 01 01

0 01 01 01 1

01

01

01

Minim´aln´ı k´ od koˇrenov´eho stromu.

Pˇri urˇcov´an´ı isomorfismu obecn´ych strom˚ u: najdeme centrum kaˇzd´eho stromu, v centru vol´ıme koˇren, sestav´ıme minim´aln´ı k´ od (pro kaˇzd´y vrchol seˇrad´ıme k´ody potomk˚ u zleva doprava lexikograficky vzestupnˇe podle jejich k´od˚ u), vyuˇzijeme n´asleduj´ıc´ı Lemma pro jednoznaˇcnou reprezentaci minim´aln´ım k´odem. Lemma Dva uspoˇr´adan´e koˇrenov´e (pˇestovan´e) stromy jsou isomorfn´ı pr´avˇe tehdy, kdyˇz jejich k´ody z´ıskan´e podle pˇredchoz´ıho popisu jsou shodn´e ˇretˇezce. Dostaneme algoritmus, kter´y je pops´an d´ale.

Algoritmus

Urˇ cen´ı isomorfismu strom˚ u

Algoritmus zjiˇst’uje, zda dan´e dva stromy T a U jsou isomorfn´ı (T '? U) // M´ ame dva stromy U, T se stejn´ ym poˇ ctem vrchol˚ u. Vstup < stromy T a U; for (X=T,U) { // urˇ cen´ ı center dan´ ych strom˚ u U, T x = centrum(X); if (x je jeden vrchol) r = x; else do X pˇ ridej vrchol r, nahrad’ hranu uv hranami ru, rv; k[X] = minimalni_kod(X,r); } if ((|V(T)|==|V(U)|) && (k[T]==k[U] jako ˇ retˇ ezce)) vypiˇ s("Stromy T, U jsou isomorfn´ ı."); else vypiˇ s("Stromy T, U nejsou isomorfn´ ı."); exit;

Algoritmus

. . . pokraˇ cov´ an´ı (nalezen´ı minim´ aln´ıho k´ odu)

Funkce minimalni kod(X,r) najde pro strom X s koˇrenem r (lexikograficky) minim´aln´ı k´ od. // na vstupu je koˇ renov´ y strom (pˇ r´ ıpadnˇ e podstrom) vstup < koˇ renov´ y strom (X,r); funkce minimalni_kod(strom X, vrchol r) { if (X m´ a jeden vrchol) return "01"; Y[1...d] = {podstromy po odebr´ an´ ı koˇ rene r}; s[1...d] = {koˇ reny podstrom˚ u Y[] v odpov´ ıdaj´ ıc´ ım poˇ rad´ ı}; // koˇ reny jsou potomci koˇ rene r for (i=1,...,d) k[i] = minimalni_kod(Y[i],s[i]); sort lexikograficky podle kl´ ıˇ ce k[1] <= k[2] <=...<= k[d]; return "0"+k[1]+...+k[d]+"1"; } Funkce hled´a minim´aln´ı k´od rekurzivnˇe.

Pozn´ amka Vˇsimnˇete si, ˇze v Algoritmu kontrolujeme, zda oba stromy maj´ı stejn´y poˇcet vrchol˚ u. Napˇr´ıklad cesty P2n a P2n+1 jistˇe nejsou isomorfn´ı, ale protoˇze centrum cesty P2n je prostˇredn´ı“ hrana, tak pˇri nalezen´ı centra bude na tuto hranu ” pˇrid´an nov´y vrchol a vznikne tak druh´a cesta P2n+1 . Bez porovn´an´ı poˇctu vrchol˚ u by algoritmus mohl v nˇekter´ych pˇr´ıpadech d´at chybnou odpovˇed’. Pˇr´ıklad Je n´asleduj´ıc´ı k´od minim´aln´ı? Proˇc? Jak vypad´a minim´aln´ı k´ od? 0000101101011 01 00010101111 0001011 01 011 001 011 01 01

01

0001010111 01

00101011

01 01

01

01

Kostra grafu Budeme pouˇz´ıvat n´asleduj´ıc´ı pojmy: podgraf, faktor souvisl´y a nesouvisl´y graf v´aˇzen´y graf, ohodnocen´ı grafu Definice Kostrou souvisl´eho grafu G rozum´ıme takov´y faktor grafu G , kter´y je stromem (faktor obsahuje vˇsechny vrcholy grafu G ). V´ahou kostry ohodnocen´eho grafu G rozum´ıme souˇcet ohodnocen´ı vˇsech hran kostry. Budeme ˇr´ıkat ohodnocen´ı hrany“ a v´aha kostry“. ” ” V´yznam koster“ spoˇc´ıv´a v jejich minimalitˇe vzhledem k poˇctu hran, ” pˇriˇcemˇz je zachov´ana souvislost grafu (Vˇeta o minim´aln´ım souvisl´em podgrafu).

V´ahy hran (a tedy v´ahy koster) se mohou liˇsit, dost´av´ame: Probl´ em minim´ aln´ı kostry (MST) Je d´an souvisl´y ohodnocen´y graf G s nez´aporn´ym ohodnocen´ım hran w : E (G ) → R+ em minim´aln´ı kostry znamen´a naj´ıt takovou 0 . Probl´ kostru T v grafu G , kter´a m´a nejmenˇs´ı moˇznou v´ahu. Form´alnˇe   X w (e) . MST = min  kostraT ⊆G

e∈E (T )

MST (z anglick´eho Minimum spanning tree“) je ˇc´ıslo, kter´e ud´av´a v´ahu ” kostry s nejmenˇs´ı moˇznou vahou. Ot´ azky Kolik hran m´a kostra souvisl´eho grafu na n vrcholech? M´a smysl hledat minim´aln´ı kostru v grafu se z´aporn´ym ohodnocen´ım hran? Je kaˇzd´y souvisl´y faktor s minim´aln´ım ohodnocen´ım kostrou grafu?

Uvedeme nˇekolik algoritm˚ u pro nalezen´ı minim´aln´ı kostry dan´eho nez´apornˇe ohodnocen´eho grafu. Algoritmus Hladov´ y pro minim´ aln´ı kostru Mˇejme d´an souvisl´y ohodnocen´y graf G s nez´aporn´ym ohodnocen´ım hran w . Poˇcet hran grafu G oznaˇc´ıme m. Seˇrad´ıme hrany grafu G vzestupnˇe podle jejich ohodnocen´ı: w (e1 ) ≤ w (e2 ) ≤ · · · ≤ w (em ). Zaˇcneme s pr´azdnou mnoˇzinou hran T = ∅ pro kostru. Pro i = 1, 2, . . . , m vezmeme hranu ei a pokud pˇrid´an´ım t´eto hrany nevznikne cyklus (s pˇr´ısluˇsn´ymi vrcholy), tak pˇrid´ame hranu ei do T . Jinak hranu ei zahod´ıme“. ” Po zpracov´an´ı vˇsech hran obsahuje T hrany minim´aln´ı kostry v´aˇzen´eho grafu G s ohodnocen´ım w . Uk´aˇzeme, ˇze algoritmus funguje spr´avnˇe.

Vˇ eta Hladov´y algoritmus najde minim´aln´ı kostru souvisl´eho grafu. D˚ ukaz Sporem. Necht’ T je mnoˇzina hran z´ıskan´a v Hladov´em algoritmu. Pˇredpokl´adejme, ˇze hrany w (e1 ) ≤ w (e2 ) ≤ · · · ≤ w (em ) jsou seˇrazeny podle v´ahy. Vezmˇeme mnoˇzinu hran T0 t´e minim´aln´ı kostry (m˚ uˇze jich b´yt v´ıce se stejnou hodnotou), kter´a se s T shoduje na co nejv´ıce prvn´ıch hran´ach. Pokud T0 = T , algoritmus pracoval spr´avnˇe. Pˇredpokl´adejme ale, ˇze T0 6= T a najdeme spor. Uk´aˇzeme tak, ˇze T0 6= T nem˚ uˇze nastat. Oznaˇcme j > 0 takov´y index, ˇze se mnoˇziny T0 a T shoduj´ı na prvn´ıch j − 1 hran´ach e1 , . . . , ej−1 , ale neshoduj´ı se na hranˇe ej . To znamen´a, ˇze ej ∈ T , ale ej 6∈ T0 . (Podle algoritmu nem˚ uˇze nastat ej 6∈ T a ej ∈ T0 .) V´ıme, ˇze graf T0 ∪ {ej } obsahuje pr´avˇe jeden cyklu C . Cyklus C vˇsak nem˚ uˇze b´yt obsaˇzena v nalezen´e kostˇre T , a proto existuje hrana ek v C , kter´a ek 6∈ T a z´aroveˇ n k > j. Potom vˇsak je w (ek ) ≥ w (e
j ) podle naˇseho seˇrazen´ı hran, a proto kostra na hran´ach T 0 = T0 \ {ek } ∪ {ej } (vznikl´a nahrazen´ım hrany ek hranou ej ) nem´a vyˇsˇs´ı ohodnocen´ı (nen´ı horˇs´ı) neˇz T0 , ale shoduje se s T na v´ıce hran´ach! To je spor s volbou kostry T0 . 

Zm´ınˇen´y hladov´y algoritmus pro hled´an´ı minim´aln´ı kostry grafu byl pops´an poprv´e uˇzit´ım teorie graf˚ u Kruskalem (1956). Je vˇsak zn´amo, ˇze Kruskal vych´azel z pr´ace ˇcesk´eho matematika Otakara Bor˚ uvky. Uˇz v roce 1926 ˇreˇsil ˇcesk´y akademik Bor˚ uvka ot´azku optim´aln´ı stavby elektrick´e s´ıtˇe a popsal velmi podobn´y algoritmus uˇzit´ım matic. Algoritmus

Bor˚ uvk˚ uv algoritmus pro minim´ aln´ı kostru

Mˇejme souvisl´y (kladnˇe) v´aˇzen´y graf G s ohodnocen´ım hran w r˚ uzn´ymi ˇc´ısly. Na zaˇc´atku seˇrad´ıme hrany vzestupnˇe podle jejich ohodnocen´ı w (e1 ) < w (e2 ) < . . . < w (em ). Kostru zaˇcneme sestavovat tak, ˇze pˇrid´ame hranu ei (pro i = 1, 2, . . . , n), pokud pˇrid´an´ım nevznikne cyklus.

Jako reakce na Bor˚ uvkovu pr´aci vypracoval Vojtˇech Jarn´ık v roce 1929 podobn´y algoritmus. Jarn´ık˚ uv algoritmus je ve svˇetˇe zn´am´y jako Prim˚ uv algoritmus z roku 1957. Algoritmus Jarn´ık˚ uv algoritmus pro minim´ aln´ı kostru Mˇejme souvisl´y graf G s n vrcholy a s nez´aporn´ym ohodnocen´ım hran w . Kostru zaˇcneme sestavovat z jednoho (libovoln´eho) vrcholu. V kaˇzd´em kroku algoritmu pˇrid´ame nejmenˇs´ı z hran, kter´e vedou z jiˇz vytvoˇren´eho podstromu do nˇekter´eho ze zb´yvaj´ıc´ıch vrchol˚ u grafu G . Po n − 1 kroc´ıch algoritmus konˇc´ı. Vˇsimnˇete si: v Jarn´ıkovˇe algoritmu hrany na zaˇc´atku neseˇrazujeme, nen´ı tˇreba testovat vznik cyklu (pˇrid´av´ame list), uˇsetˇr´ıme ˇcas. Uk´azky bˇehu hladov´eho (Kruskalova) a Jarn´ıkova (Primova) algoritmu najdete na adrese http://homel.vsb.cz/~kov16/predmety_dm.php

Pomoc´ı algoritm˚ u pro hled´an´ı minim´aln´ı kostry snadno sestavit bludiˇstˇe.

Bludiˇstˇe sestaven´e pomoc´ı Jarn´ıkova algoritmu. ´ Podrobnosti najdete ve skriptech Uvod do teorie graf˚ u“.

Pˇr´ıˇstˇ e

Kapitola Barevnost a kreslen´ı graf˚ u motivace barevnost graf˚ u rovinn´e nakreslen´ı graf˚ u rozpozn´an´ı rovinn´ych graf˚ u barven´ı map a rovinn´ych graf˚ u