Katedra matematiky Fakulta elektrotechniky a...

Katedra matematikyFakulta elektrotechniky a informatiky

Technická univerzita v Ko²iciach

GRAFOVÉ ALGORITMY A FORMÁLNA LOGIKA

Marián Kle²£, Ján Plavka

Ko²ice 2008

RECENZOVALI: RNDr. Vladimír Lacko, PhD.RNDr. �tefan Bereºný, PhD.

Za odbornú stránku u£ebného textu zodpovedajú autori.Rukopis nepre²iel redak£nou ani jazykovou úpravou.

c©Marián Kle²£, Ján Plavka

ISBN 978-80-553-0136-5

Obsah

Úvod 31 Mnoºiny a relácie 5

1.1 Mnoºiny a mnoºinové operácie . . . . . . . . . . . . . . . . . . . . . 51.2 Binárne relácie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Ekvivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Zobrazenia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Boolovská algebra 172.1 £iasto£ne usporiadané mnoºiny . . . . . . . . . . . . . . . . . . . . 172.2 Zväzy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.3 Boolovské funkcie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 Grupy, telesá a polia 293.1 Grupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Cyklické grupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Podgrupy a rozklady grúp . . . . . . . . . . . . . . . . . . . . . . . 333.4 Okruhy, telesá, polia . . . . . . . . . . . . . . . . . . . . . . . . . . 353.5 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Neorientované grafy 394.1 De�nícia a základné typy grafov . . . . . . . . . . . . . . . . . . . . 394.2 Stupne vrcholov, súvislos´ a metrika . . . . . . . . . . . . . . . . . . 424.3 Eulerovskos´, hamiltonovskos´ a planárnos´ . . . . . . . . . . . . . . 454.4 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 Orientované grafy 515.1 De�nícia digrafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.2 Súvislos´ a silná súvislos´ . . . . . . . . . . . . . . . . . . . . . . . . 525.3 Acyklické digrafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

1

2 OBSAH

5.4 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 Grafy a matice 57

6.1 Maticové reprezentácie grafov . . . . . . . . . . . . . . . . . . . . . 576.2 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7 Stromy 637.1 Stromy a ich vlastnosti . . . . . . . . . . . . . . . . . . . . . . . . . 637.2 Kostry a kruºnice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657.3 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

8 Aplikácie grafov a digrafov 718.1 Minimálne cesty a spojenia . . . . . . . . . . . . . . . . . . . . . . . 71

8.1.1 D¨ºka minimálnej cesty . . . . . . . . . . . . . . . . . . . . . 718.1.2 D¨ºka minimálneho spojenia . . . . . . . . . . . . . . . . . . 73

8.2 Minimálna kostra grafu . . . . . . . . . . . . . . . . . . . . . . . . . 758.3 Problém okruºnej cesty . . . . . . . . . . . . . . . . . . . . . . . . . 778.4 Problém obchodného cestujúceho . . . . . . . . . . . . . . . . . . . 788.5 Metóda kritickej cesty . . . . . . . . . . . . . . . . . . . . . . . . . 808.6 Toky v sieách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828.7 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

9 Formalná logika 899.1 Výroková logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899.2 Logické spojky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 909.3 Pravdivostná hodnota . . . . . . . . . . . . . . . . . . . . . . . . . 949.4 Formuly výrokovej logiky . . . . . . . . . . . . . . . . . . . . . . . . 959.5 Ekvivalencia formúl . . . . . . . . . . . . . . . . . . . . . . . . . . . 999.6 Realizácia boolovských funkcií . . . . . . . . . . . . . . . . . . . . . 1029.7 Minimálna realizácia boolovskej formuly . . . . . . . . . . . . . . . 1039.8 Relácia vyplývania . . . . . . . . . . . . . . . . . . . . . . . . . . . 1069.9 Výrokový kalkul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1089.10 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

10 Predikátová logika 11110.1 Predikát . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11110.2 Predikátový kalkúl . . . . . . . . . . . . . . . . . . . . . . . . . . . 11610.3 Úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Literatúra 118

Úvod

Cie©om tejto u£ebnice je ponúknu´ ²tudentom studijných programov Informatikaa Aplikovaná informatika u£ebnú látku zameranú na grafové algoritmy a formál-nu logiku. Publikácia nemá nahradi´ predná²ky z daného predmetu, ale pomôc´²tudentom v systematickom zorientovaní sa v predmete.

U£ebná látka je £lenená do desiatich kapitol, za ktorými sú úlohy na samostat-né precvi£ovanie preberaného u£iva. V prvých dvoch kapitolách sú základné poz-natky o binárnych reláciách, zobrazeniach, £iasto£ne usporiadaných mnoºinách azväzoch, ktoré vyúsújú do boolovskej algebry a pouºitia boolovských funkcií. Tre-tia kapitola je venovaná algebraickým systémom s jednou aj s dvoma binárnymioperáciami. �al²ie kapitoly, ²tvrtá aº ôsma, sú postupne venované neorientovanýmaj orientovaným grafom, stromom, vyuºitiu maticového po£tu pri spracovaní úlohpomocou grafov a aplikácií grafov pri rie²ení konkrétnych úloh. Na záver je ukáºkavyuºitia teórie grafov v transportných sieách pri ur£ovaní maximálnych tokov. De-viata a desiata kapitola je venovaná formálnej logike. V deviatej kapitole sa venu-jeme výrokovej logike, v ktorej základné formuly nemajú ºiadnu vnútornú stavbua jediným ich atribútom je ich pravdivostná hodnota. �al²ia kapitola pojednáva-jú o predikátovej logike, ktorá pracuje so základnými formulami vypovedajúcimio vlastnostiach a vzáhoch medzi predmetmi istého univerza.

Autori vyslovujú po¤akovanie RNDr. Vladimírovi Lackovi, PhD. a RNDr.�tefanovi Bereºnému, PhD., ktorí starostlivo pre£ítali rukopis a cennými radamiprispeli k jeho skvalitneniu.

3

4

Kapitola 1

Mnoºiny a relácie

1.1 Mnoºiny a mnoºinové operácieJedným zo základných pojmov v matematike je pojem mnoºiny. Nebudeme hode�nova´, ale budeme ho chápa´ v intuitívnom zmysle. Pod mnoºinou rozu-mieme súhrn (skupinu, súbor) nejakých navzájom odli²ných objektov, ktoré pod©anejakého kritéria tvoria jeden celok.

Mnoºinu povaºujeme za ur£enú, ak o kaºdom objekte vieme rozhodnú´, £i jealebo nie je prvkom danej mnoºiny. Mnoºiny budeme ozna£ova´ pomocou ve©kýchpísmen:

A, B, . . . , X, Y, . . . , M, N, . . .

a podobne, a prvky mnoºín budeme ozna£ova´ malými písmenami a, b, . . . , x, y, . . . ,m, n, . . . . Skuto£nos´, ºe a je prvkom mnoºiny A zapí²eme

a ∈ A .

Ak a nie je prvkom mnoºiny A, tak zapí²emea /∈ A .

Namiesto a je (nie je) prvkom mnoºiny A zvykneme hovori´ aj a patrí (nepatrí)do mnoºiny A.

Mnoºinu, ktorá neobsahuje ºiadny prvok, nazývame prázdnou mnoºinou aozna£ujeme ju symbolom ∅.

Poznáme rôzne spôsoby ur£enia mnoºín. Ak mnoºina M obsahuje kone£nýpo£et prvkov x1, x2, . . . , xn, vtedy pouºívame zápis

M = {x1, x2, . . . , xn} .

Uvedomme si, ºeD = {0}

5

6 KAPITOLA 1. MNO�INY A RELÁCIE

je neprázdna mnoºina obsahujúca jeden prvok 0, a preto D 6= ∅. Stretávame sa ajs mnoºinami, ktoré sú ur£ené takto: K je mnoºina v²etkých prvkov x ∈ B, ktorémajú vlastnos´ P. V tomto prípade pí²eme:

K = {x ∈ B; P (x)} .

Niektoré mnoºiny, hlavne £íselné, majú v²eobecne zauºívané ozna£enia. Taknapríklad pre mnoºinu v²etkých prirodzených £ísel, t.j. mnoºinu {1, 2, 3, . . . },pouºívame symbol N. Mnoºinu v²etkých celých £ísel ozna£ujeme Z. Racionálne£ísla sú zlomky s celo£íselným £itate©om aj menovate©om. Mnoºinu v²etkýchracionálnych £ísel ozna£ujeme Q. Znak R je symbolom pre mnoºinu v²etkýchreálnych a C pre mnoºinu v²etkých komplexných £ísel.Príklad 1.1.

P = {x ∈ N ; 3 < x2 < 30}je mnoºina v²etkých prirodzených £ísel, ktorých druhá mocnina je vä£²ia neº 3 amen²ia ako 30, teda

P = {2, 3, 4, 5} .

De�nícia 1.1. Mnoºina A je podmnoºinou mnoºiny B práve vtedy, ak kaºdýprvok mnoºiny A patrí aj do mnoºiny B. Zapisujeme

A ⊂ B .

Je zrejme, ºe A = B práve vtedy, ke¤ A ⊂ B a sú£asne aj B ⊂ A. Kaºdáneprázdna mnoºina A obsahuje najmenej dve podmnoºiny a to ∅ a A.De�nícia 1.2. Poten£ná mnoºina mnoºiny A je mnoºina P(A), ktorej prvkamisú v²etky podmnoºiny mnoºiny A.

Napríklad, ak A = {1, 2, 3}, takP(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3, }} .

Predpokladajme, ºe v²etky mnoºiny, s ktorými pracujeme, sú prvkami istejuniverzálnej mnoºiny U .De�nícia 1.3. Zjednotenie mnoºín A a B je mnoºina

A ∪B = {x ∈ U ; x ∈ A alebo x ∈ B}

a prienik mnoºín A a B je mnoºina

A ∩B = {x ∈ U ; x ∈ A a x ∈ B} .

Teda do A∪B patria práve tie prvky, ktoré sú prvkami aspo¬ jednej z mnoºínA a B, a do A∩B patria práve tie prvky, ktoré sú prvkami mnoºiny A aj mnoºinyB.

1.1. MNO�INY A MNO�INOVÉ OPERÁCIE 7De�nícia 1.4. Rozdiel mnoºín A a B je mnoºina

A \B = {x ∈ U ; x ∈ A a x /∈ B} .

�iºe prvkami mnoºiny A \B sú tie prvky mnoºiny A, ktoré nepatria do B.De�nícia 1.5. Komplement (doplnok) mnoºiny A je mnoºina

A = U \ A .

Operáciu zjednotenia a prieniku môºeme roz²íri´ na ©ubovo©ný po£et mnoºín.Nech I je mnoºina, ktorej budeme hovori´ mnoºina indexov a pre kaºdé i ∈ I jede�novaná mnoºina Ai ⊂ U . Hovoríme, ºe je daný systém mnoºín {Ai; i ∈ I}.De�nícia 1.6. Zjednotenie systému mnoºín {Ai; i ∈ I} je mnoºina

⋃i∈I Ai

práve tých prvkov z U , ktoré patria do niektorej z mnoºín Ai.Prienik systému mnoºín {Ai; i ∈ I} je mnoºina⋂

i∈I Ai práve tých prvkov z U ,ktoré patria do v²etkých mnoºín Ai.

Poznámka. Ak I = {1, 2, . . . , k}, tak systém mnoºín je {A1, A2, . . . , Ak}. Ichzjednotenie a prienik ozna£ujeme

k⋃i=1

Ai ak⋂

i=1

Ai .

De�nícia 1.7. Rozklad mnoºiny A 6= ∅ je taký systém {Ai; i ∈ I}, pre ktorýplatí ⋃

i∈I

Ai = A a Ai ∩ Aj = ∅ pre i, j ∈ I, i 6= j .

Veta 1.1. Nech A, B a C sú podmnoºiny mnoºiny U . Potom platí:

1. A ∪B = B ∪ A , A ∩B = B ∩ A ,2. (A ∪B) ∪ C = A ∪ (B ∪ C) , (A ∩B) ∩ C = A ∩ (B ∩ C) ,3. A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) , A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) ,4. A ∪ ∅ = ∅ ∪ A = A , A ∩ U = U ∩ A = A ,5. A ∪ A = A ∪ A = U , A ∩ A = A ∩ A = ∅ ,

6. (A) = A ,7. A ∪ A = A , A ∩ A = A ,8. A ∪ U = U , A ∩ ∅ = ∅ ,9. A ∪ (A ∩B) = A , A ∩ (A ∪B) = A ,

10. (A ∪B) = A ∩B , (A ∩B) = A ∪B .

Tvrdeniam 10 vety 1.1 hovoríme de Morganove pravidlá. Vetu 1.1 nebudemedokazova´, £itate©si jednotlivé vlastnosti môºe overi´ pomocou tzv. Vennovýchdiagramov.


1.2 Binárne relácieJe pozoruhodné, ako ve©a matematických pojmov sa dá vyjadri´ pomocou mnoºína rôznych mnoºinových kon²trukcií. Je to prekvapivé hlavne preto, ºe teóriamnoºín bola do matematiky zavedená pomerne nedávno. Dnes sa v²ak uº sta-la sú£asóu beºného matematického vyjadrovania a je jazykom, ktorý napomáhachápa´ matematiku ako jeden celok so spolo£nými základmi. Ukáºeme si, ako sapomocou jednoduchých mnoºinových prostriedkov môºu de�nova´ ¤al²ie matem-atické pojmy.

Ak x a y sú prvky (nejakej mnoºiny), potom symbol {x, y} ozna£uje mnoºinuobsahujúcu práve prvky x a y a nazýva sa neusporiadaná dvojica prvkov x a y.Pripome¬me, ºe {x, y} je to isté ako {y, x}. Zavedieme tieº ozna£enie (x, y) preusporiadanú dvojicu prvkov x a y. V tomto prípade závisí na poradí prvkovv zátvorkách. Podobne de�nujeme usporiadanú n-ticu prvkov x1, x2, . . . , xn,ktorú budeme ozna£ova´ (x1, x2, . . . , xn). Platí, ºe

(x1, . . . , xn) = (y1, . . . , yn) práve vtedy ak x1 = y1, . . . , xn = yn .

De�nícia 1.8. Karteziánsky sú£in A × B mnoºín A a B je mnoºina v²etkýchusporiadaných dvojíc (a,b), kde a ∈ A a b ∈ B. Formálne zapisujeme

A×B = {(a, b); a ∈ A, b ∈ B} .

Karteziánsky sú£in A×A niekedy zapisujeme ako mocninu, t.j. A2, a podobneA3 = A× A× A at¤.Je zrejmé, ºe C × ∅ = ∅ × C pre ©ubovo©nú mnoºinu C.De�nícia 1.9. Binárna relácia z mnoºiny A do mnoºiny B je ©ubovo©ná podm-noºina R karteziánskeho sú£inu A × B. Ak A = B, hovoríme o binárnej reláciina mnoºine A, £o je ©ubovo©ná podmnoºina R ⊂ A2.

Ak nemôºe dôjs´ k omylu a je jasné, ºe sa jedná o binárnu reláciu, slovo binárnamôºeme vynecha´ a hovori´ iba o relácii.Poznámka Binárna relácia R je mnoºina, a teda by sme mali pouºi´ symbol premnoºinu, t.j. R. Symbol R budeme pouºíva´ preto, aby sme jasne rozlí²ili, ºe sajedná o reláciu.

Ak (a, b) ∈ R, hovoríme, ºe prvok a je v relácii R s prvkom b a zapisujemeaRb. Analogicky namiesto (a, b) /∈ R pí²eme aRb.

Názov karteziánsky sú£in pochádza z geometrickej interpretácie (a pôvodneteda z mena Descartes): Ke¤ napríklad A = B = R, potom A×B môºeme inter-pretova´ ako v²etky body roviny a v tomto prípade x a y sú (karteziánske) súrad-nice bodu (x, y) roviny. Toto znázornenie pouºívame nielen pre £íselné mnoºiny,ale napríklad aj pre karteziánsky sú£in kone£ných mnoºín. Binárnu reláciu potom

1.2. BINÁRNE RELÁCIE 9znázor¬ujeme ako mnoºinu v rovine, ktorá je podmnoºinou mnoºiny znázor¬ujúcejkarteziánsky sú£in. Hovoríme tomu gra�cká interpretácia binárnej relácie.Príklad 1.2. Nech A = {1, 3, 5}, aB = {0, 2}. Nájdite a gra�cky znázor-nite reláciu R, ktorá je de�novaná:aRb ⇔ | a−2 |= | 2b−3 |, a ∈ A, b ∈ B .

Rie²enie. Výpo£tom zistíme, ºe R ={(5, 0), (1, 2), (3, 2)}. Gra�cká interpretá-cia je na obr. 1.1. Plné krúºky súprvkami mnoºiny R, v²etky krúºky (plnéaj prázdne) sú prvkami karteziánskehosú£inu A×B.Príklad 1.3. Majme podmnoºiny reál-nych £ísel X = {x; −3 < x < 2} aY = {y; 1 ≤ y ≤ 4}. Nájdite a gra�ckyznázornite reláciu R, ktorá je de�novaná:xRy ⇔ y ≤ x + 1.Rie²enie. R je £as´ roviny (päúholníkKLMNO) z obr. 1.2 .

Obr. 1.1

Obr. 1.2�al²ími vhodnými interpretáciami binárnej relácie sú maticová a grafová.

Ak R ⊂ A×B, A = {a1, . . . , an}, B = {b1, . . . , bm}, môºeme R zapísa´ pomocoumatice M = (mi,j) typu (n, m), kde

mi,j =

{1 , ak aiRaj ,0 , v ostatných prípadoch.

Pri grafovej interpretácii (presnú de�níciu grafu uvedieme neskôr) prvky mnoºínA a B znázor¬ujeme krúºkami, ktoré budeme nazýva´ vrcholy. Usporiadanúdvojicu (ai, bj) znázorníme ²ípkou v smere od ai k bj, ktorú nazývame oriento-vaná hrana. Tak napríklad pre reláciu R = {(1, 2), (2, 4), (3, 2), (4, 2), (4, 4)} namnoºine {1, 2, 3, 4} máme maticu

MR =

0 1 0 00 0 0 10 1 0 00 1 0 1

Obr. 1.3

a grafová reprezentácia je obr. 1.3.


De�nícia 1.10. Inverzná relácia k binárnej relácii R je binárna relácia R−1 ={(b, a); (a, b) ∈ R}, pri£om a ∈ A a b ∈ B.

Je zrejmé, ºeaRb ⇔ bR−1a a (R−1)

−1= R .

De�nícia 1.11. Nech A, B, C sú mnoºiny, R ⊂ A × B je relácia z A do B, aS ⊂ B × C je relácia z B do C. Sú£inom binárnych relácií (zloºením) R a Snazveme binárnu reláciu R ◦ S ⊂ A×C takú, ºe pre a ∈ A a c ∈ C je a(R ◦ S)cpráve vtedy, ak existuje aspo¬ jedno b ∈ B také, ºe aRb a zárove¬ bSc. Sú£inrelácii R a S tieº niekedy ozna£ujeme RS.

Sú£in relácii sa dá dobre znázorni´ pomocou grafovej reprezentácie. Na obr.1.4 je vidie´, ºe dvojica (a, c) je v relácii R ◦ S vºdy ke¤ z a do c sa dá dosta´ poorientovaných hranách cez nejaké b z mnoºiny B.

Obr. 1.4V²imnime si, ºe sú£in nie je de�novaný pre kaºdé dve binárne relácie. Aby sa

dali relácie sklada´, musia ma´ spolo£nú �prostrednú� mnoºinu (v de�nícii sme juozna£ili B). Ak sú v²ak R aj S relácie na tej istej mnoºine, ich sú£in je vºdydobre de�novaný. V tomto prípade záleºí na poradí skladania, t.j. R ◦ S je vov²eobecnosti iná relácia ako S ◦ R.Veta 1.2. Pre sú£in binárnych relácií platí asociatívny zákon. Ak R ⊂ A × B,S ⊂ B × C a T ⊂ C ×D sú binárne relácie, tak

(R ◦ S) ◦ T = R ◦ (S ◦ T ) .

Dôkaz vety vyplýva z De�nície 1.11 a zo schémy na obr. 1.5.

1.3. EKVIVALENCIA 11Obr. 1.5

Poznámka. Pojem binárnej relácie môºeme zov²eobecni´. Nech A1, A2, . . . , An sú©ubovo©né mnoºiny. Karteziánsky sú£in A1×A2×· · ·×An mnoºín A1, A2, . . . , Anje mnoºina v²etkých usporiadaných n�tíc (a1, a2, . . . , an), kde ai ∈ Ai pre v²etkyi = 1, 2, . . . , n. ²peciálne, ak A1 = A2 = · · · = An, potom A1×A2×· · ·×An = An jemnoºina v²etkých usporiadaných n�tíc prvkov mnoºiny A. Potom n�árna reláciaje ©ubovo©ná podmnoºina karteziánskeho sú£inu A1 × A2 × · · · × An.

1.3 EkvivalenciaV tejto £asti textu sa budeme zaobera´ iba binárnymi reláciami na mnoºine, t.j.ke¤ R ⊂ A× A.De�nícia 1.12. Binárna relácia R na mnoºine A sa nazýva:re�exívna, ak pre v²etky a ∈ A platí aRa;symetrická, ak pre v²etky a, b ∈ A platí, ºe ak aRb, tak aj bRa;antisymetrická, ak pre v²etky a, b ∈ A platí, ºe ak aRb aj bRa, tak a = b ;tranzitívna, ak pre v²etky a, b, c ∈ A platí, ºe ak aRb a bRc, tak aj aRc.

Ak znázor¬ujeme reláciu pomocou matice, tak matica odpovedajúca re�exívnejrelácii má na hlavnej diagonále len jedni£ky. Matica reprezentujúca symetrickúreláciu je symetrická pod©a hlavnej diagonály. Pri grafovej reprezentácii re�exívnejrelácii odpovedá graf s orientovanou slu£kou pri kaºdom vrchole. V grafe reprezen-tujúcom symetrickú reláciu kaºdú dvojicu vrcholov spájajú orientované hranyv oboch smeroch. Aj podmienka tranzitívnosti sa dá dobre vyjadri´ pomocouorientovaných hrán: ak sú v grafe hrany z x do y a z y do z, musí tam by´ aj hranaz a do z.De�nícia 1.13. Hovoríme, ºe relácia R na mnoºine A je ekvivalencia namnoºine A, ak je re�exívna, symetrická a tranzitívna.

Pojem ekvivalencie je zastre²ujúci pojem pre v²etky pojmy vyjadrujúce rov-nakos´, podobnos´, izomor�zmus at¤. £asto sa relácia ekvivalencie zvykne oz-na£ova´ symbolmi =,≡,',≈,∼=, . . . . Príklady ekvivalencie sa vyskytujú napríkladv geometrii: podobnos´ trojuholníkov, rovnobeºnos´ priamok a podobne.

Nech R je ekvivalencia na mnoºine A a nech a je ©ubovo©ný prvok mnoºiny A.Ozna£me symbolom R[a] mnoºinu v²etkých prvkov x, ktoré sú v relácii s prvkoma (teda R[a] = {x; aRx}). R[a] sa nazýva trieda ekvivalencie R ur£ená prvkoma.

Platí nasledujúcaVeta 1.3. Pre kaºdú ekvivalenciu R na mnoºine A platí

(i) R[a] je neprázdna mnoºina pre kaºdý prvok a ∈ A.


(ii) Pre kaºdé dva prvky a, b z mnoºiny A bu¤ R[a] = R[b], alebo R[a]∩R[b] = ∅.

(iii) Triedy ekvivalencie jednozna£ne ur£ujú (popisujú) reláciu R.

Skôr, ako pristúpime k dôkazu, vysvetlime zmysel bodu (iii). Presný významje nasledujúci: Ak sú R a S dve ekvivalencie na mnoºine A a pre kadý prvok az mnoºiny A platí rovnos´ R[a] = S[a], potom R = S.Dôkaz. (i) Mnoºina R[a] vºdy obsahuje aspo¬ prvok a, pretoºe R je re�exívnarelácia.

(ii) Nech a, b sú dané prvky. Ak aRb, ukáºeme najprv ºe R[a] ⊂ R[b]. Jeto tak, pretoºe ak nejaké x ∈ R[a], potom aRx a zo symetrie vyplýva, ºe ajxRa. Ke¤ºe xRa a aRb, z tranzitívnosti vyplýva ºe aj xRb. Ak opä´ pouºijemesymetriu, máme bRx, £o znamená, ºe x ∈ R[b], a teda R[a] ⊂ R[b]. Podobne saukáºe, ºe aj R[b] ⊂ R[a], z £oho vyplýva, ºe R[a] = R[b].Teraz ukáºeme, ºe ak neplatí aRb, tak R[a] ∩ R[b] = ∅. Postupujeme sporom:Nech existuje x ∈ R[a]∩R[b]. Potom aRx a zo symetrie aj xRb. Z tranzitívnostidostávame aRb, £o je spor.

(iii) Táto £as´ tvrdenia vety je zrejmá, pretoºe triedy ekvivalencie R ur£ujú Rvzáhom

aRb práve vtedy, ak {a, b} ⊂ R[a] .

2Obrázok 1.6 znázor¬uje tvrdenia vety 1.3. Podm-noºiny danej mnoºiny A, ktoré sú navzájom dis-junktné a ktoré spolu obsahujú v²etky prvkymnoºiny A, tvoria rozklad mnoºiny A (pozride�níciu 1.7). Tvrdenia vety zaru£ujú, ºe triedyekvivalencie tvoria rozklad mnoºiny a ºe vzáhmedzi v²etkými ekvivalenciami na danej mnoºineA a v²etkými rozkladmi mnoºiny A je vzájomnejednozna£ný.

Obr. 1.6Uvedieme si jednu konkrétnu ekvivalenciu, ktorá rozkladá mnoºinu celých £ísel.

Hovoríme, ºe nenulové celé £íslo b delí celé £íslo a, ak existuje také celé £íslo q, ºea = b · q. Zapisujeme to symbolom b|a.Nech m ∈ N a nech

Rm = {(a, b) ∈ Z× Z; m|(a− b)} .

Ukáºeme si, ºe binárna relácia Rm na mnoºine Z je ekvivalencia. Re�exívnos´platí, pretoºe pre kaºdé a ∈ Z je a − a = 0 a nulu delí kaºdé nenulové £íslo,teda aj na²e dopredu zvolené £íslo m. Je zrejmé, ºe pre ©ubovo©né a, b ∈ Z, akm|(a − b), tak aj m|(b − a) a relácia je symetrická. Uvaºujme teraz ©ubovo©néa, b, c ∈ Z, pre ktoré platí ºe m|(a − b) a tieº m|(b − c). Potom existujú celé

1.4. ZOBRAZENIA 13£ísla q1 a q2 také, ºe a − b = m · q1 a b − c = m · q2. Z toho v²ak vyplýva, ºea− c = (a− b) + (b− c) = m · (q1 + q2), kde q1 + q2 ∈ Z, a teda m|(a− c). Týmsme ukázali, ºe relácia je aj tranzitívna. Ke¤ºe sa jedná o ekvivalenciu, môºemeteraz zostroji´ mnoºinu tried ekvivalencie

Zm = {0, 1, 2, . . . , n− 1} ,

ktoré tvoria rozklad mnoºiny v²etkých celých £ísel Z, pri£om trieda k (0 ≤ k ≤n− 1) má tvar

k = {. . . ,−2m + k,−m + k, k, m + k, 2m + k, . . . } .

Mnoºinu Zm nazývamemnoºinou v²etkých zvy²kových triedmnoºiny Z pod©amodulu m. Napríklad pre m = 5 dostávame:

Z5 = {0, 1, 2, 3, 4} ,

kde0 = {. . . ,−15,−10,−5, 0, 5, 10, 15, . . . } ,1 = {. . . ,−14,−9,−4, 1, 6, 11, 16, . . . } ,2 = {. . . ,−13,−8,−3, 2, 7, 12, 17, . . . } ,3 = {. . . ,−12,−7,−2, 3, 8, 13, 18, . . . } ,4 = {. . . ,−11,−6,−1, 4, 9, 14, 19, . . . } .

1.4 ZobrazeniaPojem zobrazenie sa zhoduje s pojmom funkcie a je jedným zo základných pojmovv matematike. Trvalo dos´ dlho, kým sa dospelo k dne²nému chápaniu zobrazeniaako ²peciálneho typu binárnej relácie. E²te v nedávnej dobe sa uvaºovali ibareálne alebo komplexné funkcie a �poctivá� funkcia musela by´ vyjadrená nejakýmvzorcom alebo sú£tom nekone£ného radu.De�nícia 1.14. Zobrazenie z mnoºiny A do mnoºiny B je binárna relácia f ⊂A×B s vlastnosámi:

a) ku kaºdému a ∈ A existuje b ∈ B tak, ºe (a, b) ∈ f ,b) ak (a, b) ∈ f a (a, c) ∈ f , tak b = c.

Namiesto slova zobrazenie sa v rovnocennom význame £asto pouºíva slovo funk-cia. Teda zobrazenie f z mnoºiny A do mnoºiny B môºeme chápa´ ako pravidlo,ktoré kaºdému prvku a ∈ A priradí práve jeden prvok b z mnoºiny B. To, ºe f jezobrazenie z mnoºiny A do mnoºiny B, zapisujeme takto: f : A → B. Prvok a jevzorom prvku b a prvok b je obrazom prvku a pri zobrazení f . Namiesto

afb alebo (a, b) ∈ f


obvykle pí²emeb = f(a) .

V²etky tri zápisy vyjadrujú to isté: prvok a je v relácii s prvkom b.Poznámka. V²imnime si, ºe aj ke¤ zobrazenie je reláciou, nepouºíva sa na je-ho ozna£enie ve©ké písmeno ako pre reláciu, ale malé. £itate© sa ur£ite £astej²iestretával so zápisom y = f(x), teda s prípadom funkcie (zobrazenia) z mnoºinyX do mnoºiny Y . Je to to isté, ak si uvedomíme, ºe mnoºiny A a B v de�níciizobrazenia boli ©ubovo©né.Príklad 1.4. Nech A = {1, 2, 3}, B = {1, 2, 3, 4}. Potom

f1 = {(1, 2), (2, 2), (3, 4)}

je zobrazenie, alef2 = {(1, 2), (1, 3), (2, 4), (3, 4)}

nie je zobrazenie, lebo nie je splnená vlastnos´ b) de�nície 1.14 a anif3 = {(1, 2), (2, 3)}

nie je zobrazenia, lebo nie je splnená vlastnos´ a) de�nície 1.14.De�nícia 1.15. Zobrazenie f : A → B sa nazýva:surjektívne, ak ku kaºdému b ∈ B existuje aspo¬ jedno a ∈ A tak, ºe b = f(a),injektívne, ak z a1 6= a2, a1, a2 ∈ A vyplýva f(a1) 6= f(a2),bijektívne, ak je surjektívne aj injektívne.

Obr. 1.7Na obr. 1.7 sú znázornené jednotlivé typy zobrazení. Zobrazenie (a) nie je

surjektívne ani injektívne, (b) je surjektívne, ale nie je injektívne, (c) je injektívne,ale nie je surjektívne a (d) je surjektívne aj injektívne, teda bijektívne.

Kaºdé zobrazenie f je binárne relácia z A do B, preto existuje aj binárna reláciaf−1 z B do A, ktorá vo v²eobecnosti nie je zobrazením (funkciou).

1.5. ÚLOHY 15Veta 1.4. Nech f je zobrazenie z A do B. Potom f−1 je zobrazenie z B do Apráve vtedy, ak f je bijektívne zobrazenie.

Dôkaz. Nech f−1 je zobrazenie z B do A. Potom kaºdý prvok b ∈ B má právejeden obraz f−1(b) ∈ A, a teda kaºdý prvok b ∈ B je obrazom práve jedného prvkuz A v zobrazení f , £o je bijektívnos´ zobrazenia f .

Naopak, nech f je bijektívne zobrazenie z A do B. Potom kaºdý prvok b ∈ Bmá práve jeden vzor v mnoºine A, a teda f−1 je zobrazenie, lebo kaºdý prvokb ∈ B má práve jeden obraz f−1(b) ∈ A. 2

De�nícia 1.16. Majme zobrazenia f : A → B a g : B → C. Sú£inom (zloºením)zobrazení f a g je zobrazenie h : A → C de�nované predpisom

h(a) = g(f(a))

pre kaºdé a ∈ A.

Zobrazenie h budeme ozna£ova´ g ◦ f . Platí teda (g ◦ f)(a) = g(f(a)) prekaºdý prvok a ∈ A. Je tu odli²nos´ oproti sú£inu relácií, kde sa skladanie zapisujev poradí �z©ava doprava�. Pri zobrazeniach skladanie zapisujeme �sprava do©ava�.

Pre sú£in zobrazení platí asociatívny zákon, ale nie komutatívny. Ak má f ◦ gzmysel, potom g ◦ f vôbec nemusí by´ de�nované.

1.5 Úlohy1.1. Majme mnoºiny S = {1, 2, 3, 5} a T = {−3, 0, 7}. Utvorte S × T , T × S,

S × S a T × T .1.2. Je daná mnoºina L = {(1, 0), (0, 1), (2, 1), (0, 0), (2, 2), (0, 2), (2, 0)}. Rozhod-

nite, £i existujú také mnoºiny M a P , pre ktoré by platilo L = M × P .1.3. Nájdite bijektívne zobrazenie mnoºiny A × B na mnoºinu B × A pre dve

zvolené mnoºiny A a B.1.4. Zistite, ktoré z vlastností re�exívnos´, symetrickos´, antisymetrickos´, tranz-

itívnos´ platia v nasledujúcich binárnych reláciách:a) R1 = {(x, y) ∈ N2; y = x + 1},b) R2 = {(x, y) ∈ N2; y > x},c) R3 = {(x, y) ∈ Z2; |x− y| = 1},d) R4 = {(x, y) ∈ Z2; |x− y| ≤ m, m ∈ N, (m� pevne zvolené)},e) R5 = {(x, y) ∈ R2; x ≤ y},f) R6 = {(x, y) ∈ A2; x = y}, pri£om A je ©ubovo©ná mnoºina.

1.5. Rozhodnite, ktoré z nasledujúcich binárnych relácií sú ekvivalencie. V prí-pade ekvivalencie nájdite aj triedy ekvivalencií:


a) �Ma´ rovnaký polomer ako� na mnoºine kruºníc v rovine,b) |x− y| ≤ 1, x, y ∈ R,c) |x| = |y|, x, y ∈ C.

1.6. Utvorte mnoºinu Z6 zvy²kových tried mnoºiny Z.1.7. Rozhodnite, ktoré z nasledujúcich zobrazení je injektívne, surjektívne, bijek-

tívne:a) f : N → N, f(n) = 2n pre v²etky n ∈ N,b) f : Z → Z, f(x) = x− 1 pre v²etky x ∈ Z,c) f : 〈−π

2, π

2〉 → 〈−1, 1〉, f(x) = sin x pre v²etky x ∈ 〈−π

2, π

2〉.

Kapitola 2

Boolovská algebra

2.1 £iasto£ne usporiadané mnoºiny�itate© ur£ite pozná usporiadanie mnoºiny prirodzených £ísel alebo iných £íselnýchmnoºín pod©a ve©kosti. Takéto usporiadanie sa v matematike chápe ako ²peciálnytyp relácie, t.j. ako vzáh dvojice £ísel, a relácia sa oby£ajne ozna£uje symbolom�≤� (men²í alebo rovný). Iné binárne relácie nám umoº¬ujú usporiada´ mnoºiny(nielen £íselné) pod©a iných kritérií.De�nícia 2.1. Relácia £iasto£ného usporiadania na nejakej mnoºine A 6= ∅je kaºdá relácia na mnoºine A, ktorá je re�exívna, antisymetrická a tranzitívna.

Príkladmi relácií £iasto£ného usporiadania sú napr.: relácia delite©nosti | namnoºine N, relácia inklúzie ⊂ na systéme mnoºín, usporiadanie £ísel pod©a ve©kosti≤ na R, . . . . Ak nebudeme presne ²peci�kova´, o akú binárnu reláciu sa jedná,budeme na ozna£enie relácie £iasto£ného usporiadania pouºíva´ symbol �. Potommôºeme de�níciu 2.1 sformulova´ takto:De�nícia 2.2. Nech A 6= ∅. Binárna relácia � na mnoºine A je reláciou£iasto£ného usporiadania práve vtedy, ak pre v²etky a, b, c ∈ A platí:

a � a,a � b ∧ b � a ⇒ a = b,a � b ∧ b � c ⇒ a � c.

Usporiadaná dvojica (A;�) sa nazýva £iasto£ne usporiadaná mnoºina.Ak porovnávame £ísla (okrem komplexných) pod©a ve©kosti, tak ©ubovo©né dve

£ísla sa dajú porovna´. Táto vlastnos´ pre mnohé £iasto£ne usporiadané mnoºinynaplatí.De�nícia 2.3. �iasto£ne usporiadaná mnoºina (A;�), v ktorej pre v²etky a, b ∈ Aje a � b alebo b � a sa nazýva lineárne usporiadaná.Príklad 2.1. Nech A = {a, b, c}. Utvorme poten£nú mnoºinu P(A) = {∅, {a},

17

18 KAPITOLA 2. BOOLOVSKÁ ALGEBRA

{b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}. ©ahko overíme, ºe (P(A);⊂) je £iasto£neusporiadaná mnoºina. Nie je v²ak lineárne usporiadaná, lebo napríklad {c} 6⊂{a, b} ani {a, b} 6⊂ {c}.Príklad 2.2. Nech A je neprázdna podmnoºina mnoºiny reálnych £ísel R. Potom(A;≤) je £iasto£ne usporiadaná mnoºina a je aj lineárne usporiadaná.

Kone£né £iasto£ne usporiadané mnoºiny môºeme znázor¬ova´ pomocou grafovpodobne ako ktoréko©vek iné binárne relácie. V takých obrázkoch by v²ak bolove©mi ve©a hrán. Skôr ako si vysvetlime, ktoré hrany netreba zakres©ova´, potre-bujeme pojem pokrývajúci prvok.De�nícia 2.4. Nech (A;�) je £iasto£ne usporiadaná mnoºina a nech a, b ∈ A.Hovoríme, ºe prvok a pokrýva prvok b, ak a 6= b a platí:

1. a � b,2. neexistuje x ∈ A, x 6= a, x 6= b taký, ºe a � x � b.

�iasto£ne usporiadané mnoºiny (A;�) budeme znázor¬ova´ pomocou tzv. Has-seho diagramov. Vrcholy odpovedajúce prvkom mnoºiny A umiestnime v rovinetak, ºe ak a � b, tak vrchol a umiestnime niº²ie ako vrchol b. Vrcholy a, b spo-jíme £iarou (hranou) práve vtedy, ak prvok b pokrýva prvok a. Tým si u²etrímekreslenie ²ípky, pretoºe orientácia hrany je uvaºovaná zdola nahor, a nekreslimeani hrany medzi dvojicami prvkov, ktorých rela£ný vzáh vyplýva z tranzitívnosti.Re�exívnos´ relácie dovo©uje nekresli´ ani slu£ky pri vrcholoch. Hasseho diagram£iasto£ne usporiadanej mnoºiny z príkladu 2.1 je na obr. 2.1(a).

Obr. 2.1Príklad 2.3. Nech A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. (A; |) je £iasto£ne usporiadanámnoºina, pretoºe relácia delite©nosti | je re�exívna, antisymetrická a tranzitívna.Hasseho diagram je na obr. 2.1(b).De�nícia 2.5. Nech (A;�) je £iasto£ne usporiadaná mnoºina. Prvok a ∈ A sanazýva najmen²í (najvä£²í) prvok v (A;�), ak pre kaºdý prvok x ∈ A platí a � x(x � a).

2.2. ZVÄZY 19Prvok a ∈ A sa nazýva minimálny (maximálny) prvok v (A;�), ak neexistujeprvok x ∈ A, x 6= a taký, ºe x � a (a � x).

Najmen²í (najvä£²í) prvok je zárove¬ aj minimálnym (maximálnym) prvkom£iasto£ne usporiadanej mnoºiny, ale naopak to neplatí. Ak £iasto£ne usporiadanámnoºina má najmen²í, resp. najvä£²í prvok, je jediným a je zárove¬ aj jej jedinýmminimálnym, resp. maximálnym prvkom. Napríklad v (A;�) z príkladu 2.3 £íslo 1je najmen²ím prvkom a je zárove¬ aj jediným minimálnym, maximálnymi prvkamisú £ísla 6, 7, 8, 9 a 10 a najvä£²í prvok neexistuje. V (P(A);⊂) z príkladu 2.1 je ∅jediným minimálnym a sú£asne aj najmen²ím prvkom a prvok {1, 2, 3} je jedinýmmaximálnym a zárove¬ aj najvä£²ím prvkom.

Nech M je neprázdna podmnoºina mnoºiny A. Ak (A;�) je £iasto£ne uspo-riadaná mnoºina, tak aj (M ;�) je £iasto£ne usporiadaná mnoºina. Hovoríme, ºed je najvä£²í (najmen²í, maximálny, minimálny) prvok mnoºiny M ⊂ A, akje najvä£²ím (najmen²ím, maximálnym, minimálnym) prvkom £iasto£ne uspori-adanej mnoºiny (M ;�).De�nícia 2.6. Nech (A;�) je £iasto£ne usporiadaná mnoºina a ∅ 6= M ⊂ A.Mnoºina

h(M) = {x ∈ A; (∀a ∈ M : a � x)}

je mnoºina v²etkých horných ohrani£ení mnoºiny M a mnoºina

d(M) = {x ∈ A; (∀a ∈ M : x � a)}

je mnoºina v²etkých dolných ohrani£ení mnoºiny M . Najmen²í (najvä£²í) prvok mnoºiny h(M) (d(M)), ak existuje, sa nazýva supremum (in�mum)mnoºiny M a zapisuje sa sup M (inf M).

Príklad 2.4. H©adajme supremum a in�mum niektorých podmnoºín mnoºiny Az príkladu 2.3. Napríklad:

sup{2, 3, 6} = 6, inf{2, 3, 6} = 1,sup{2, 3, 5, 6} neexistuje, inf{2, 3, 5, 6} = 1,sup{2, 5} = 10, inf{2, 5} = 1,sup{2, 10} = 10, inf{2, 10} = 2.

2.2 ZväzyTeória zväzov sa vyuºíva v teórii kon²trukcie po£íta£ov a pri dokazovaní správnos-ti programov. Jej výsledky a metódy sa pouºívajú aj pri ²túdiu grúp a inýchalgebraických ²truktúr. My sa zameriame na pouºitie teórie zväzov v Boolovskejalgebre.


Nech (A;�) je £iasto£ne usporiadaná mnoºina a nech x, y ∈ A. Pre inf {x, y}a sup {x, y}, ak existujú, zavedieme tieto ozna£enia:

inf {x, y} = x∧̇y

a £ítame priesek prvkov x a y. ¤alejsup {x, y} = x∨̇y

a £ítame spojenie prvkov x a y.V príklade 2.4 sme videli, ºe nie pre kaºdú dvojicu prvkov £iasto£ne uspori-

adanej mnoºiny existuje spojenie (nie kaºdá dvojica prvkov má spojenie). Podob-ne je to aj s priesekom. V lineárne usporiadanej mnoºine majú kaºdé dva prvkypriesek aj spojenie, je nim men²í, resp. vä£²í z nich.De�nícia 2.7. Zväz je £iasto£ne usporiadaná mnoºina, v ktorej kaºdé dva prvkymajú spojenie aj priesek.

Príklad 2.5. Nech A = {1, 2, 3, 4, 5} a nechB = {∅, {1}, {1, 2}, {1, 3}, {1, 2, 3, 4}, {1, 2, 3, 5},{1, 2, 3, 4, 5}} je jej podmnoºina. ©ahko sapresved£íme, ºe (B;⊂) je £iasto£ne usporiadanámnoºina. Jej Hasseho diagram je na obr. 2.2. Nieje to v²ak zväz, lebo prvky {1, 2} a {1, 3} nemajúspojenie (mnoºina ich horných ohrani£ení nemánajmen²í prvok) a prvky {1, 2, 3, 4} a {1, 2, 3, 5}nemajú priesek (mnoºina ich dolných ohrani£enínemá najvä£²í prvok).�iasto£ne usporiadaná mnoºina (A;⊂) z príkladu2.1 je zväz a v jej Hasseho diagrame na obr. 2.1sa ©ahko presved£íme, ºe kaºdá dvojica prvkov mápriesek aj spojenie. Obr. 2.2Veta 2.1. Nech (L;�) je zväz. Potom pre ©ubovo©né x, y, z ∈ L platí:

x∨̇x = x, x∧̇x = x, idempotentnos´,x∨̇y = y∨̇x, x∧̇y = y∧̇x, komutatívnos´,x∨̇(y∨̇z) = (x∨̇y)∨̇z, x∧̇(y∧̇z) = (x∧̇y)∧̇z, asociatívnos´,x∨̇(y∧̇x) = x, x∧̇(y∨̇x) = x, absorbcia.

Poznámka. Vo zväze priesek a spojenie môºeme chápa´ ako zobrazenia:∧̇ : A× A → A, ∧̇ : A× A → A,

£o sú binárne operácie. Binárna operácia teda priradí dvom prvkom mnoºinyjeden prvok z tej istej mnoºiny. Podobne unárna operácia priradí len jedné-mu prvku jeden prvok z tej istej mnoºiny. Rovnocennou de�níciou zväzu je ajnasledujúca:

2.2. ZVÄZY 21De�nícia 2.8. Zväz je algebraický systém (L; ∨̇, ∧̇), kde L 6= ∅ a pre operácieprieseku ∧̇ a spojenia ∨̇ platia vlastnosti: idempotentnos´, komutatívnos´, asoci-atívnos´ a absorbcia.

Príklad 2.6. Na zväz (A;⊂) z príkladu 2.5, ktorého Hasseho diagram je na obr.2.1, sa môºeme pozera´ aj ako na mnoºinu s de�novanými binárnymi operáciamizjednotenia a prieniku. £itate©si ©ahko preverí, ºe algebraický systém (P(A);∪,∩)vyhovuje de�nícii 2.8.Algebraický systém (Z; +, ·) zväzom nie je, lebo hne¤ prvá vlastnos´ � idempo-tentnos´ neplatí.De�nícia 2.9. Zväz (L; ∨̇, ∧̇) sa nazýva distributívny, ak pre v²etky x, y, z ∈ Lplatí:

x∧̇(y∨̇z) = (x∧̇y)∨̇(x∧̇z),x∨̇(y∧̇z) = (x∨̇y)∧̇(x∨̇z).

Príklad 2.7. Na obr. 2.3 sú Hasseho di-agramy zväzov N5 a M5 (tieto ozna£enia súzauºívané v literatúre). Nie sú distributívne,lebo v kaºdom sa dá nájs´ trojica prvkov,pre ktorú neplatí aspo¬ jedna z rovnostív de�nícii 2.9. Napr. v N5 je u∧̇(v∨̇y) =u∧̇z = u, ale (u∧̇v)∨̇(u∧̇y) = v∨̇x = v.Podobne v M5 je s∧̇(t∨̇q) = s∧̇r = s, ale(s∧̇t)∨̇(s∧̇q) = p∨̇p = p. Obr. 2.3

V kaºdom kone£nom zväze existuje jediný najvä£²í prvok I (horné univerzálneohrani£enie) a jediný najmen²í prvok 0 (dolné univerzálne ohrani£enie). Ti-eto prvky môºeme ozna£i´ aj v symbolickom zápise zväzu takto: (L; ∨̇, ∧̇, 0, I).

De�nícia 2.10. Nech (L; ∨̇, ∧̇, 0, I) je zväz. Prvok x′ ∈ L nazývame komple-mentom prvku x ∈ L práve vtedy, ak

x∧̇x′ = 0 a x∨̇x′ = I .

Príklad 2.8. Pre prvky zväzu z príkladu 2.6, ktorého Hasseho diagram je na obr.2.1(a), platí 0 = ∅ a I = {a, b, c}. ¤alej je 0′ = I, I ′ = 0, {a}′ = {b, c}, {b}′ ={a, c}, {c}′ = {a, b}, {a, b}′ = {c}, {a, c}′ = {b}, {b, c}′ = {a}. Ku kaºdému prvkuteda existuje práve jeden kompliment.Pre zväz M5 na obr. 2.3 platí 0 = p a I = r. ¤alej 0′ = I, I ′ = 0, s′ = t, s′ =q, t′ = s, t′ = q, q′ = s, q′ = t,teda prvky s, t, q majú po dva komplementy. Existujú zväzy, v ktorých niektoréprvky majú viac komplementov.


De�nícia 2.11. Zväz (L; ∨̇, ∧̇, 0, I) sa nazýva komplementárny práve vtedy, akkaºdý jeho prvok má komplement. Distributívny a komplementárny zväz nazývameboolovským zväzom.

Veta 2.2. V boloovskom zväze (L; ∨̇, ∧̇, 0, I) má kaºdý prvok práve jeden komple-ment.

Poznámka. Dá sa ukáza´, ºe ak je zväz kone£ný a kaºdý jeho prvok má právejeden komplement, tak je aj distributívny. Uº sme si ukázali, ºe (P(A);⊂), kdeA = {a, b, c}, je zväz, ºe je distributívny aj komplementárny, teda boolovský. Platíaj to pre kaºdú inú kone£nú mnoºinu, t.j ke¤ |A| = n. Taký zväz má 2n prvkova môºeme ho zapisova´ aj (P(A);∪,∩). Dá sa tieº ukáza´, ºe kaºdý kone£nýboolovský zväz má 2n prvkov pre nejaké nezáporné celé £íslo n, a ºe jeho Hassehodiagram je zhodný s Hasseho diagramom zväzu (P(A);∪,∩) pre to isté n.

Komplement v boolovskom zväze (L; ∨̇, ∧̇, 0, I) môºeme chápa´ ako unárnu op-eráciu z mnoºiny L do mnoºiny L. Potom sa na boolovský zväz môºeme pozeraáko na algebraický systém (L; ∨̇, ∧̇,′ , 0, I), kde L 6= ∅, operácie ∨̇, ∧̇ sú binárneoperácie a ′ je unárna operácia na L. Takému vyjadreniu zväzu budeme hov-ori´ boolovská algebra. Okrem uº uvedených vlastností idempotentnos´, komu-tatívnos´, asociatívnos´, absorbcia, distributívnos´ a existencia komplementu kukaºdému prvku platí v boolovskej algebre aj mnoho ¤al²ích vlastností. Uvediemelen najhlavnej²ie z nich, ktoré budeme neskôr pouºíva´ pri úprave boolovskýchfunkcií:

(1) x∨̇0 = x, (2) x∧̇I = x,(3) x∨̇x′ = I, (4) x∧̇x′ = 0,(5) x∧̇0 = 0, (6) x∨̇I = I,(7) (x∨̇y)′ = x′∧̇y′, (8) (x∧̇y)′ = x′∨̇y′,(9) x∨̇(x′∧̇y) = x∨̇y, (10) x∧̇(x′∨̇y) = x∧̇y.

Poznámka. Vlastnosti (7) a (8) sú známe pod názvom de Morganové pravidlá.Doporu£ujeme £itate©ovi v²imnú´ si podobnos´ mnoºinových vlastností z vety 1.1a vlastností boolovskej algebry.Príklad 2.9. Majme dvojprvkovú mnoºinu D = {0, 1}. Nech pre prvky mnoºinyD sú de�nované binárne operácie priesek a spojenie a unárna operácia ′ pomocoutabuliek:

∧̇ 0 10 0 01 0 1

∨̇ 0 10 0 11 1 1

'0 11 0

V tomto prípade dolné univerzálne ohrani£enie je 0 a horné univerzálne ohrani£enieje 1 (musíme si uvedomi´, ºe nie sú to £ísla 0 a 1). Bez vä£²ích áºkosti si môºemeoveri´, ºe algebraický systém (D; ∨̇, ∧̇,′ , 0, 1) je boolovská algebra.

2.3. BOOLOVSKÉ FUNKCIE 232.3 Boolovské funkcieV tejto £asti poukáºeme na aplikácie boolovských algebier v elektrotechnike av logike.De�nícia 2.12 Nech (D; ∨̇, ∧̇,′ , 0, 1) je boolovská algebra, kde D = {0, 1}. Zo-brazenie f : Dn → D sa nazýva boolovská funkcia s n premennými. Zapisujemeju

y = f(x1, x2, . . . , xn) ,

kde y, xi ∈ D pre v²etky i = 1, 2, . . . , n.Z uvedeného vyplýva, ºe boolovská funkcia s n premennými kaºdej usporiadanej

n�tici núl a jedni£iek z mnoºiny Dn priradí hodnotu 0 alebo 1.Veta 2.3. Existuje práve 22n

rôznych boolovských funkcií s n premennými.Príklad 2.10. Z vety 2.3 vyplýva, ºe existuje práve 16 rôznych boolovskýchfunkcií s 2 premennými. Kaºdej zo ²tyroch usporiadaných dvojíc (x1, x2) funkciafi, i = 1, 2, . . . , 16, priradí hodnotu 0 alebo 1. V²etkých 16 funkcií je vypísanýchv nasledujúcej tabu©ke.(x1, x2) f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16

(0,0) 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1

(0,1) 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0

* (1,0) 1 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0

(1,1) 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 1

De�nícia 2.13. Nech x∗i ozna£uje hodnotu xi ∈ D alebo hodnotu jeho komple-mentu x′i pre v²etky i = 1, 2, . . . , n. Boolovskú funkciu

k(x1, x2, . . . , xn) = x∗1∧̇x∗2∧̇ . . . ∧̇x∗n

nazývame elementárna konjunkcia a boolovskú funkciu

d(x1, x2, . . . , xn) = x∗1∨̇x∗2∨̇ . . . ∨̇x∗n

nazývame elementárna disjunkcia.Nech k1, k2, . . . , kj, kde 0 ≤ j ≤ 2n, sú rôzne elementárne konjunkcie. Funkcia

f = 0∨̇k1∨̇k2∨̇ . . . ∨̇kj

je boolovská funkcia s n premennými v normálnom disjunktívnom tvare (NDT).Nech d1, d2, . . . , dr, kde 0 ≤ r ≤ 2n, sú rôzne elementárne disjunkcie. Funkcia

f = 1∧̇d1∧̇d2∧̇ . . . ∧̇dr

je boolovská funkcia v normálnom konjunktívnom tvare (NKT).


Vzniká prirodzene otázka, £i sa dá kaºdá boolovská funkcia napísa´ v niektoromz týchto tvarov.Veta 2.4. Kaºdá boolovská funkcia sa dá zapísa´ v normálnom disjunktívnomtvare aj v normálnom konjunktívnom tvare.

Príklad 2.11. Upravme na normálny disjunktívny tvar boolovskú funkciu f =(x′1∧̇x′3)∨̇(x′2∧̇x′3). Vyuºijeme vlastnosti boolovskej algebry a robíme postupnéúpravy tak, aby sme neporu²ili rovnos´.

f = (x′1∧̇x′3)∨̇(x2∧̇x3) = [(x′1∧̇x′3)∧̇(x′2∨̇x2)]∨̇[(x2∧̇x3)∧̇(x′1∨̇x1)] =

(x′1∧̇x′2∧̇x′3)∨̇(x′1∧̇x2∧̇x′3)∨̇(x′1∧̇x2∧̇x3)∨̇(x1∧̇x2∧̇x3).

Vyuºili sme , ºe (x′1∨̇x1) = (x′2∨̇x2) = 1 pod©a vlastnosti (3) predchádzajúcehoparagrafu. Pouºili sme aj vlastnos´ (6), z ktorej sme dostali (x′1∧̇x′3)∧̇(x′2∨̇x2) =(x′1∧̇x′3) a (x2∧̇x3)∧̇(x′1∨̇x1) = (x2∧̇x3). Okrem toho sme pouºili vlastnos´ dis-tributívnos´ v opa£nom poradí, tzv. vyberanie pred zátvorku ako aj komutatívnosá asociatívnos´.

Uvedieme aj iný spôsob ako boolovskú funkciu previes´ na normálny disjunk-tívny, resp. konjunktívny tvar. Pre porovnanie pracujme s tou istou funkciou fako v predchádzajúcom príklade. Vyrobíme si tabu©ku, v ktorej v prvých trochst¨pcoch sú v²etky trojice hodnôt premenných x1, x2 a x3. V st¨pci f budú hod-noty boolovskej funkcie pre príslu²né usporiadané trojice núl a jedni£iek. V st¨pciki vytvoríme v kaºdom riadku, v ktorom hodnota funkcie je 1, elementárnu kon-junkciu tak, aby jej hodnota pre príslu²nú trojicu premenných bola tieº 1. Podobnev st¨pci di v kaºdom riadku s hodnotou funkcie rovnou 0 vytvoríme elementárnudisjunkciu dávajúcu hodnotu 0 pre príslu²nú trojicu premenných.

x1 x2 x3 f ki di0 0 0 1 x′1∧̇x′2∧̇x′30 0 1 0 x1∨̇x2∨̇x′30 1 0 1 x′1∧̇x2∧̇x′30 1 1 1 x′1∧̇x2∧̇x31 0 0 0 x′1∨̇x2∨̇x31 0 1 0 x′1∨̇x2∨̇x′31 1 0 0 x′1∨̇x′2∨̇x31 1 1 1 x1∧̇x2∧̇x3

Ak vytvoríme disjunkciu elementárnych konjunkcií zo st¨pca ki a konjunkciu ele-mentárnych disjunkcií zo st¨pca di, tak dostaneme:

f = (x′1∧̇x′2∧̇x′3)∨̇(x′1∧̇x2∧̇x′3)∨̇(x′1∧̇x2∧̇x3)∨̇(x1∧̇x2∧̇x3),

f = (x1∨̇x2∨̇x′3)∧̇(x′1∨̇x2∨̇x3)∧̇(x′1∨̇x2∨̇x′3)∧̇(x′1∨̇x′2∨̇x3).

2.3. BOOLOVSKÉ FUNKCIE 25Poznámka. V de�nícii 2.13 na za£iatku NKT je jedni£ka a na za£iatku NDTje nula. Tieto kon²tanty vo vä£²ine prípadov nemusíme písa´, ale dôleºitú úlohuzohrávajú, ak sa jedná o funkciu, ktorá pre v²etky hodnoty premenných nadobúdahodnotu 1, resp. 0.

Vo výrokovej logike pod výrokom rozumieme ©ubovo©né tvrdenie, o ktorommá zmysel hovori´, £i je pravdivé alebo nepravdivé. Kaºdému výroku môºemepriradi´ jeho pravdivostnú hodnotu t.j. pravda (ozna£ujeme symbolom 1), resp.nepravda (pouºívame symbol 0). Rozoznávame elementárne výroky, alebo výrokyzloºené z elementárnych pomocou logických operácií. Zloºeným výrokom hovorímeaj výrokové formuly. Základnými logickými operáciami sú: negácia ′ , konjunkcia∧, disjunkcia ∨, implikácia⇒ a ekvivalencia ⇔. �itate© sa s nimi uº ur£ite stretolna strednej ²kole, preto ich nebudeme bliº²ie popisova´.

Kaºdá formula výrokovej logiky sa dá zapísa´ (realizova´) pomocou boolovskejfunkcie. Je tým daná jednozna£ná kore²pondencia medzi ∧ a ∨ (a a alebo) na jednejstrane a ∧̇ a ∨̇ na strane druhej. Preto v ¤al²om texte pri boolovských funkciáchnemusíme pouºíva´ symboly prieseku a spojenia ∧̇ a ∨̇ �zdedené� zo zväzov, alebudeme písa´ symboly logickej konjunkcie a disjunkcie, t.j. ∧ a ∨. Samozrejmev zápise výrokovej formuly pomocou boolovskej funkcie sa nevyskytuje implikáciaani ekvivalencia.Príklad 2.12. Zapí²me pomocou boolovskej funkcie výrokovú formulu

(p ⇔ q) ⇔ [(p ⇒ q) ∧ (q ⇒ p)].

Zostrojíme si pravdivostnú tabu©ku pre túto výrokovú formulu a st¨pec s prav-divostnými hodnotami celej formuly je zárove¬ st¨pcom hodnôt boolovskej funkciepre príslu²né hodnoty premenných (pravdivostných hodnôt elementárnych výrokov)p a q. ¤alej postupujeme pod©a uº opísaného postupu pri zapisovaní boolovskejfunkcie v NDT alebo NKT. Takto získané zápisy sa £asto dajú pomocou vlast-ností boolovskej algebry zna£ne zjednodu²i´. Uvedený postup ukazuje nasledujúcatabu©ka a potom zápis získaných funkcií v NDT a NKT. Je vidie´, ºe sa jednáo tzv. tautológiu, t.j. vºdy pravdivý výrok.

p q p ⇔ q p ⇒ q q ⇒ p (p ⇒ q) ∧ (q ⇒ p) f1 1 1 1 1 1 11 0 0 0 1 0 10 1 0 1 0 0 10 0 1 1 1 1 1

Potom v normálnom disjunktívnom tvare jef = (p ∧ q) ∨ (p ∧ q′) ∨ (p′ ∧ q) ∨ (p′ ∧ q′)

a v normálnom konjunktívnom tvare jef = 1 ,


pretoºe po£et príslu²ných elementárnych disjunkcií je nula.Boolovskú algebru moºno s výhodou vyuºi´ pri navrhovaní kontaktných sietí.

Kontaktné siete v praxi vyuºívame pri kontrole práce nejakých zloºitých sústav,pri£om poruchu sústavy oby£ajne signalizuje rozsvietená signaliza£ná ºiarovka.Ukáºeme, ako moºno navrhnú´ kontaktnú sie´ na kontrolu takého systému.Príklad 2.13. Pre sústavu troch strojov navrhnite kontaktnú sie´ tak, aby sig-nalizovala, ºe nastala niektorá z uvedených porúch:

a) prvý stroj nepracuje, druhý pracuje,b) prvý a druhý stroj pracujú, ale tretí nepracuje.

Rie²enie. Sta£ia nám tri základné kontakty, pri£om sa dohovoríme, ºe kontak-tom p prechádza prúd práve vtedy, ke¤ pracuje prvý stroj, kontaktom q právevtedy, ke¤ pracuje druhý stroj a kontaktom r práve vtedy, ke¤ pracuje tretí stroj.Celou sieóu bude prechádza´ prúd práve vtedy, ke¤ nastane niektorá z uvedenýchporúch. To znamená, ºe v na²om prípade bude sieóu prechádza´ prúd práve vt-edy, ak nastane niektorá z nasledujúcich moºnosti:

1. prvý stroj nepracuje, druhý pracuje a tretí pracuje,2. prvý stroj nepracuje, druhý pracuje a tretí nepracuje,3. prvý a druhý stroj pracujú, tretí nepracuje.

Túto situáciu môºeme realizova´ napríklad kontaktnou sieóu na obr. 2.4(a) a sie´môºeme �boolovsky� charakterizova´ pomocou funkcie

f = (p′ ∧ q ∧ r) ∨ (p′ ∧ q ∧ r′) ∨ (p ∧ q ∧ r′)

Obr. 2.4Mohli sme si pomôc´ aj tabu©kou na výrobu elementárnych konjunkcií a el-

ementárnych disjunkcií. Funkcia f je teraz zapísaná v NDT. Kontaktná sie´ naobr. 2.4(a) je zbyto£ne zloºitá. Ak vyuºijeme vlastnosti boolovskej algebry, dá safunkcia zna£ne zjednodu²i´:

f = (p′ ∧ q ∧ r) ∨ (p′ ∧ q ∧ r′) ∨ (p ∧ q ∧ r′) =

[(p′ ∧ q) ∧ (r ∨ r′)] ∨ (p ∧ q ∧ r′) =

(p′ ∧ q) ∨ (p ∧ q ∧ r′) = q ∧ [p′ ∨ (p ∧ r′)] =

2.4. ÚLOHY 27q ∧ [(p′ ∨ p) ∧ (p′ ∨ r′)] = q ∧ (q′ ∨ r′).

Tomuto výrazu zodpovedá kontaktná sie´ na obr. 2.4(b), ktorá je podstatnejednoduch²ia (je dokonca minimálna).

2.4 Úlohy2.1. Ukáºte, ºe relácia rovnosti na mnoºine je sú£asne £iasto£ným usporiadaním

aj ekvivalenciou. Je to jediná relácia, pre ktorú to platí.2.2. Ukáºte, ºe kaºdá kone£ná lineárne usporiadaná mnoºina má sú£asne naj-

men²í aj najvä£²í prvok.2.3. Nech F je mnoºina v²etkých reálnych funkcií fi jednej reálnej premennej,

ktorých de�ni£ný obor je D ⊂ R. Reláciu R de�nujme takto: Pre v²etkyf1, f2 ∈ F je f1Rf2 práve vtedy, ak pre v²etky x ∈ D je f1(x) ≤ f2(x).Ukáºte, ºe (F ;R) je £iasto£ne usporiadaná mnoºina.

2.4. Nakreslite Hasseho diagram £iasto£ne usporiadanej mnoºiny (M ; |) (ak to je£iasto£ne usporiadaná mnoºina), kde M = {1, 2, 3, 4, 5, 6, 7, 10, 11, 12} a |je relácia delite©nosti celých £ísel.

2.5. Rozhodnite, £i (A;R) je £iasto£ne usporiadaná mnoºina, ak A = R × R arelácia R je de�novaná:

a) (a, b)R(c, d) ⇔ a + b ≤ c ∧ b ≤ d pre v²etky (a, b), (c, d) ∈ A,b) (a, b)R(c, d) ⇔ a ≤ c ∧ b ≤ d pre v²etky (a, b), (c, d) ∈ A.

2.6. Ukáºte, ºe kaºdá lineárne usporiadaná mnoºina je zväzom.2.7. Presved£íte sa, ºe (S; |), kde S = {1, 2, 3, 4, 5, 6, 10, 12, 15, 30, 60} a | je

relácia delite©nosti celých £ísel, je zväz. Nakreslite jeho Hasseho diagram.Zistite, £i tento zväz je distributívny a £i kaºdý jeho prvok má komplement.

2.8. Ukáºte, ºe v kaºdom distributívnom zväze pre ©ubovo©né tri prvky x, y, zplatí rovnos´

(x∧̇y)∨̇(y∧̇z)∨̇(z∧̇x) = (x∨̇y)∧̇(y∨̇z)∧̇(z∨̇x).

2.9. Nech x, y sú ©ubovo©né prvky boolovskej algebry. Dokáºte, ºe x = y právevtedy, ak (x∧̇y′)∨̇(x′∧̇y) = 0.

2.10. Upravte boolovskú funkciu f = x1∧̇[(x′2∧̇x4)∨̇x′3] na normálny konjunktívnytvar aj na normálny disjunktívny tvar.


2.11. Zistite, £i boolovské funkcief = [(x∧̇y)∨̇(x∨̇z)]′ ∨̇x a g = [x′∧̇(z∨̇(y′∧̇z))] ∨̇x

sa rovnajú.2.12. Svetlo v chodbe je ovládané z troch vypína£ov a v kaºdom momente môºe

by´ zapnuté aj vypnuté ktorýmko©vek z nich. Navrhnite kontaktnú sie´ pretakéto zapojenie.

2.13. Výrobná linka pozostáva z troch strojov. Navrhnite minimálnu kontaktnúsie´, ktorá signalizuje, ºe nastal niektorý z uvedených stavov:

a) prvý stroj pracuje a z ostatných jeden pracuje a jeden nie,b) prvý stroj nepracuje a z ostatných jeden pracuje a jeden nie.

2.14. Zapí²te pomocou boolovskej funkcie v normálnom konjunktívnom aj v nor-málnom disjunktívnom tvare výrokovú formulu

(((A ⇒ B) ⇒ (A ⇒ C)) ⇒ (B ⇒ C)) ⇒ A

a minimalizujte získanú boolovskú funkciu.

Kapitola 3

Grupy, telesá a polia

3.1 GrupyTeória grúp patrí medzi mladé matematické disciplíny. Jej za£iatky siahajú doprvej polovice minulého storo£ia, ke¤ v roku 1826 nórsky matematik Henrik Abelpodal dôkaz nerie²ite©nosti algebraickej rovnice 5. stup¬a pomocou odmocnín.Grupy na²li ²iroké uplatnenie v matematických i nematematických disciplínách aich význam s rozvojom informatiky rastie.

Vieme, ºe usporiadanej dvojici celých £ísel (a, b) môºeme priradi´ celé £ísloc = a + b. S£ítavanie je vlastne zobrazenie f , v tomto prípade f : Z×Z → Z, kdef(a, b) = a + b. Zobrazenie takého typu sa nazýva binárnou operáciou.Príklad 3.1. Rie²me rovnicu 3x = 4. Oby£ajný postup si rozpí²eme podrobnej²ie(pozri pravý st¨pec):Pritom vyuºívame, ºe 1

3je vzh©adom na

násobenie inverzný prvok k £íslu 3, prizmene poradia zátvoriek vyuºívame aso-ciatívnos´ násobenia, potom to, ºe £ís-lo 1 je vzh©adom na násobenie neutrál-ny prvok a v neposlednom rade to, ºesú£in dvoch reálnych £ísel je opä´ reálne£íslo, t.j. uzavretos´ mnoºiny reálnych£ísel vzh©adom na operáciu násobenia.Práve vymenované ²tyri vlastnosti námumoº¬ujú zavies´ pojem grupy.

3x = 4 /1

3

1

3(3x) =

1

3· 4

(1

3· 3)x =

4

3

1 · x =4

3

x =4

3

De�nícia 3.1. Nech G 6= ∅ je mnoºina. Grupa je algebraický systém (G; ∗),prektorý platí:

1. Pre v²etky x, y ∈ G aj x ∗ y ∈ G.2. Pre v²etky x, y, z ∈ G je x ∗ (y ∗ z) = (x ∗ y) ∗ z.3. V G existuje prvok e taký, ºe pre kaºdé x ∈ G je x ∗ e = e ∗ x = x.

29

30 KAPITOLA 3. GRUPY, TELESÁ A POLIA

4. Ku kaºdému x ∈ G existuje taký prvok x′ ∈ G, ºe x ∗ x′ = x′ ∗ x = e.Ak G je kone£ná mnoºina a |G| = n, tak £íslo n je rád grupy (G; ∗).

Poznámka. Vlastnos´ 1. z de�nície vyjadruje uzavretos´ mnoºiny vzh©adom naoperáciu ∗. Vlastnos´ 2. poznáme pod názvom asociatívnos´. Prvok e z vlastnos-ti 3. sa nazýva neutrálny prvok vzh©adom na operáciu ∗ a prvok x′ z vlastnosti4. je inverzný prvok k prvku x vzh©adom na operáciu ∗.Ak pre (G; ∗) platí vlastnos´ 1. (uzavretos´) a vlastnos´ 2. (asociatívnos´), alge-braický systém (G; ∗) nazývame pologrupa.Veta 3.1. V kaºdej grupe (G; ∗) existuje práve jeden neutrálny prvok e a kukaºdému prvku x existuje práve jeden inverzný prvok x′.

De�nícia 3.2. Grupa (G; ∗) sa nazýva komutatívna alebo abelovská, ak prev²etky x, y ∈ G platí

x ∗ y = y ∗ x.

Príklad 3.2. Algebraický systém (N;−) nie je grupa, pretoºe existujú prirodzené£ísla m, n také, ºe m− n je záporné £íslo, a teda neplatí uzavretos´.Pre algebraický systém (P(A);∩) platí, ºe pre kaºdé Ai, Aj ∈ P(A) aj Ai ∩ Aj ∈P(A), platí asociatívnos´ prieniku mnoºín, a tieº existuje neutrálny prvok e = Ataký, ºe pre kaºdú mnoºinu Ai ∈ P(A), teda Ai ⊂ A, je Ai ∩ e = e ∩ Ai = Ai.Nie je to v²ak grupa, lebo v P(A) ºiadna vlastná podmnoºina mnoºiny A nemáinverzný prvok.�ahko sa preverí, ºe (Z; +) je grupa a tieº (R \ {0}; ·) je grupa.Algebraický systém (R; ·) grupou nie je, lebo k £íslu 0 neexistuje inverzný prvok.

Vlastnosti grupy sú zov²eobecnením s£ítavania a násobenia reálnych £ísel. Aksa jedná o grupu s binárnou operáciou s£ítavania (G; +), hovoríme o aditívnejgrupe. Podobne multiplikatívna grupa je grupa (G; ·) s operáciou násobenia.Veta 3.2. Nech (G; ∗) je grupa a nech a, b ∈ G. Potom rovnica

a ∗ x = b (x ∗ a = b)

má práve jedno rie²enie

x = a′ ∗ b (x = b ∗ a′).

Z vety 3.2 vyplýva pravidlo o krátení z©ava (sprava): Pre v²etky a, x1, x2 ∈ Gplatí:

a ∗ x1 = a ∗ x2 ⇔ x1 = x2

(x1 ∗ a = x2 ∗ a ⇔ x1 = x2).

3.1. GRUPY 31V abelovskej grupe teda rovnice x1 ∗ a = b a a ∗ x2 = b majú rovnaké rie²enie

x1 = x1 = b ∗ a′.

Táto veta nám vraví kedy rovnice toho typu majú pre operácie s£ítavania anásobenia £ísel jednozna£né rie²enie a kedy nie. Vä£²inou rie²ime takéto rovniceuº na základných a stredných ²kolách a ani si neuvedomujeme, ºe pracujeme napr.na grupách (Z; +), (R \ {0}; ·) a podobne. O £íselných mnoºinách a operáciáchs£ítavania a násobenia £ísel vieme ve©a. Ve©kou prednosóu grúp je, ºe vlastnostígrúp �rovnakého typu� sa zhodujú bez oh©adu na to, o akú mnoºinu a akú binárnuoperáciu sa jedná. Potom sta£í ukáza´, ºe sa jedná o ur£itý typ grupy a môºemevyuºíva´ v²etky vlastnosti dokázané na inej grupe rovnakého typu. £o rozumiemepod grupami rovnakého typu nám vystihuje pojem izomor�zmus.De�nícia 3.3. Dve grupy (A; 2) a (B;4) sú izomorfné práve vtedy, ak existujebijektívne zobrazenie ϕ : A → B také, ºe pre v²etky a1, a2 ∈ A je

ϕ(a12a2) = ϕ(a1)4(a2).

Príklad 3.3. Na mnoºine zvy²kových tried modulo m (pozri paragraf 1.3) side�nujeme operácie ⊕ a � takto:

a⊕ b = a + b a a� b = a · b.

Nech K = {1,−1, i,−i} je podmnoºina komplexných £ísel. Zistite, £i algebraickésystémy (Z4;⊕) a (K; ·) sú izomorfné grupy.Rie²enie. V²etky výsledky binárnych operácií ⊕ a · na uvedených mnoºináchmôºeme zapísa´ do Cayleyho tabuliek:

⊕ 0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

· 1 −1 i −i

1 1 −1 i −i

−1 −1 1 −i i

i i −i −1 1

−i −i i 1 −1

Obe mnoºiny sú uzavreté vzh©adom na operáciu, lebo v poli tabu©ky sú iba prvkypríslu²nej mnoºiny. Neutrálnym prvkom v prvom prípade je 0 a v druhom 1.V tabu©ke to vidíme tak, ºe sa v riadku (st¨pci) odpovedajúcemu neutrálnemuprvku zopakuje riadok (st¨pec) zo záhlavia. Inverzný prvok k nejakému prvkunájdeme tak, ºe v riadku, ktorý tomu prvku odpovedá, nájdeme neutrálny prvoka nad ním v záhlaví tabu©ky je inverzný. Platí to aj pre st¨pce. V prvom prípadeje 0 ′ = 0, 1 ′ = 3, 2 ′ = 2 a 3 ′ = 1, v druhom 1′ = 1, −1′ = −1, i ′ = −i a −i ′ = i.Iba asociatívnos´ sa nedá zisti´ priamo z tabu©ky. Pre (K; ·) asociatívnos´ platí,


pretoºe platí pre násobenie ©ubovo©ných troch komplexných £ísel. Pri s£ítavanízvy²kových tried modulo m pre ©ubovo©né x, y, z ∈ Zm je

x⊕ (y ⊕ z) = x⊕ (y + z) = x + (y + z)

(x⊕ y)⊕ z = x + y ⊕ z = (x + y) + z.

Ke¤ºe x + (y + z) = (x + y) + z, asociatívnos´ s£ítavania v Zm platí, a teda platíaj v Z4. (Podobne sa ukáºe asociatívnos´ násobenia � zvy²kových tried.)Algebraické systémy (Z4;⊕) a (K; ·) sú teda grupy. Uvaºujme teraz bijektívnezobrazenie ϕ : Z4 → K de�nované

ϕ =

(0 1 2 31 i −1 −i

).

Dá sa bez áºkostí preveri´, ºe pre kaºdú dvojicu prvkov x, y ∈ Z4 jeϕ(x⊕ y) = ϕ(x) · ϕ(y).

Ide teda o izomorfné grupy.Poznámka. Ak máme dve izomorfné grupy s malým po£tom prvkov, potom sa ichCayleyho tabu©ky dajú zostroji´ tak, ºe po poloºení na seba sa prekrývajú presnepod©a zvoleného izomorfného zobrazenia ϕ. Doporu£ujeme £itate©ovi zmeni´ po-radie prvkov v záhlaví jednej tabu©ky tak aby sa prekrývali 0 s 1, 1 s i, 2 s −1 a3 s −i.

3.2 Cyklické grupyGrupy uvedené v predchádzajúcom príklade majú aj �al²iu vlastnos´, sú cyklické.Pred de�novaním pojmu cyklickos´ potrebujeme pojem mocniny prvku.De�nícia 3.4. Nech (G; ∗) je grupa a nech n ∈ Z. Potom n�tou mocninouprvku x ∈ G nazývame taký prvok xn ∈ G, pre ktorý platí:

xn =

n︷︸︸︷x ∗ x ∗ · · · ∗ x, ak n > 0,

xn = 1, ak n = 0,xn = (x′)−n, ak n < 0.

De�nícia 3.5. Nech (G; ∗) je grupa a nech x ∈ G. Ak existuje také prirodzené£íslo n, ºe xn = 1, hovoríme, ºe prvok x má kone£ný rád. Najmen²ie prirodzené£íslo n, pre ktoré je xn = 1, nazývame rád prvku x. Ak neexistuje také n, prvokx má nekone£ný rád.

De�nícia 3.6. Nech (G; ∗) je grupa. Ak existuje taký prvok x ∈ G, ºe kaºdý prvokmnoºiny G je jeho mocninou, tak (G; ∗) nazývame cyklickou grupou a prvok xje generátorom tejto grupy.

3.3. PODGRUPY A ROZKLADY GRÚP 33Príklad 3.4. Pre grupu (Z4;⊕) z príkladu 3.3 dostávame:

11

= 1, 12

= 1⊕ 1 = 2, 13

= 2⊕ 1 = 3, 14

= 3⊕ 1 = 0 = e,

teda prvok 1 je generátorom grupy a grupa je cyklická. Rád prvku 1 je 4. Grupamá aj druhý generátor, a to prvok 3. Overte, ºe prvok 0 má rád 1 a 2 má rád 2.Ke¤ºe grupa (K; ·) je izomorfná s grupou (Z4;⊕). Prvky, ktoré sa v izomor�zmenavzájom na seba zobrazujú, majú rovnaký rád. Teda grupa (K; ·) má tieº dvagenerátory a je cyklická. Overte to!Poznámka. Ak sú dve grupy izomorfné, tak sa zhodujú vo v²etkých vlastnostiach.Ak sa grupy lí²ia £o len v jednej vlastnosti, izomorfné nie sú.Veta 3.3. Nech (G; ∗) je cyklická grupa s generátorom a. Ak existujú také celé£ísla r < s, ºe ar = as, tak grupa (G; ∗) je kone£ná. Ak |G| = n, tak

G = {a0, a1, a2, . . . , an−1},

kde a0 je neutrálny prvok.

Príklad 3.5. Nech A = {2n; n ∈ Z}. Potom (A; ·) je nekone£ná cyklická grupas generátorom 2n.Veta 3.4. Kaºdé dve cyklické grupy rovnakého rádu sú izomorfné.

3.3 Podgrupy a rozklady grúpDe�nícia 3.7. Nech (G; ∗) je grupa a ∅ 6= H ⊂ G. Ak (H; ∗) je grupa, tak sanazýva podgrupou grupy (G; ∗).Veta 3.5. Nech ∅ 6= H ⊂ G a nech (G; ∗) je grupa. Algebraický systém (H; ∗) jepodgrupou grupy (G; ∗) práve vtedy, ak platia podmienky:

1. pre kaºdé a, b ∈ H aj a ∗ b ∈ H,2. pre kaºdé a ∈ H aj a′ ∈ H.

Príklad 3.6. Nech A = {1, 2, 3}. Potom mnoºina v²etkých permutácií na mnoºineA je mnoºina S3 = {P1, P2, P3, P4, P5, P6}, kde

P1 =

(1 2 31 2 3

), P2 =

(1 2 31 3 2

), P3 =

(1 2 32 1 3

),

P4 =

(1 2 32 3 1

), P5 =

(1 2 33 1 2

), P6 =

(1 2 33 2 1

).

Tieto permutácie sú zobrazeniami a môºeme ich sklada´. Napr.P2 ◦ P3 =

(1 2 31 3 2

)◦

(1 2 32 1 3

)=

(1 2 32 3 1

)= P4,


P3 ◦ P2 =

(1 2 32 1 3

)◦

(1 2 31 3 2

)=

(1 2 33 1 2

)= P5.

Výsledky v²etkých sú£inov (zloºení) sa dajú preh©adne zapísa´ do tabu©ky:◦ P1 PP P3 P4 P5 P6

P1 P1 P2 P3 P4 P5 P6

P2 P2 P1 P4 P3 P6 P5

P3 P3 P5 P1 P6 P2 P4

P4 P4 P6 P2 P5 P1 P3

P5 P5 P3 P6 P1 P4 P2

P6 P6 P4 P5 P2 P3 P1

Ke¤ºe z prvej kapitoly vieme, ºe pre skladanie zobrazení platí asociatívnyzákon, z tabu©ky je zrejmé, ºe (S3; ◦) je nekomutatívna grupa. Nech H1 ={P1, P4, P5} ⊂ S3. Ak sa obmedzíme iba na £as´ tabu©ky s prvkami P1, P4 a P5v záhlaví, vidíme, ºe (H1; ◦) je tieº grapa, a teda podgrupa grupy (S3; ◦). Naviac©ahko sa dá zisti´, ºe grupa (S3; ◦) nie je cyklická, ale jej podgrupa (H1; ◦) cyklickáje. Jej generátormi sú prvky P4 a P5. Podobne aj prvky P1, P2, P3 a P6 námgenerujú podmnoºiny

H2 = {P1}, H3 = {P1, P2}, H4 = {P1, P3}, H5 = {P1, P6},

pri£om kaºdý algebraický systém (Hi; ◦) pre i = 2, 3, 4, 5 je cyklickou podgrupougrupy (S3; ◦), aj ke¤ grupa (S3; ◦) cyklická nie je.

Pre podgrupy cyklickej grupy platí nasledujúca veta.Veta 3.6. Kaºdá podgrupa cyklickej grupy je cyklická.

Zavedieme si nasledujúce ozna£enia. Nech (G; ∗) je grupa a (H; ∗) je jej pod-grupa. Symbolom xH ozna£íme mnoºinu v²etkých prvkov x ∗ h, kde x ∈ G ah ∈ H. Teda pre prvok x ∈ G je

xH = {x ∗ h; h ∈ H}.

Je zrejmé, ºe pre abelovskú grupu (G; ∗) je xH = Hx.Veta 3.7. Nech (H; ∗) je podgrupou grupy (G; ∗). Potom mnoºina

G/H = {xH; x ∈ G}

tvorí rozklad mnoºiny G.Poznámka. Mnoºina G/H sa nazýva pravým rozkladom grupy (G; ∗) pod©ajej podgrupy (H; ∗). Jeho prvky xH nazývame pravými triedami rozkladu.Mohutnos´ mnoºiny G/H nazývame indexom podgrupy (H; ∗) v grupe (G; ∗).Príklad 3.7. Urobme rozklad grupy (S3; ◦) z príkladu 3.6 pod©a jej podgrupy(H1; ◦), kde H1 = {P1, P4, P5}.

3.4. OKRUHY, TELESÁ, POLIA 35Rie²enie. Pre kaºdé x ∈ G utvorme mnoºinu xH1:pre x = P1 je xH1 = {P1 ◦ P1, P1 ◦ P4, P1 ◦ P5} = {P1, P4, P5}pre x = P2 je xH1 = {P2 ◦ P1, P2 ◦ P4, P2 ◦ P5} = {P2, P3, P6}pre x = P3 je xH1 = {P3 ◦ P1, P3 ◦ P4, P3 ◦ P5} = {P3, P6, P2}pre x = P4 je xH1 = {P4 ◦ P1, P4 ◦ P4, P4 ◦ P5} = {P4, P5, P1}pre x = P5 je xH1 = {P5 ◦ P1, P5 ◦ P4, P5 ◦ P5} = {P5, P1, P4}pre x = P6 je xH1 = {P6 ◦ P1, P6 ◦ P4, P6 ◦ P5} = {P6, P2, P3}.Takºe

S3/H1 = {{P1, P4, P5}{P2, P3, P6}}

a index podgrupy (H1; ◦) v grupe (S3; ◦) je 2. Je vidie´, ºe v tomto prípade je|S3/H1| =

|S3||H1|

.

O tom, ºe to platí v²eobecne, nás informuje nasledujúca veta.Veta 3.8. (Lagrangeova veta.) Rád kone£nej grupy je celo£íselným násobkomrádu kaºdej jej podgrupy.

Veta 3.9. Kaºdá grupa prvo£íselného rádu je cyklická a kaºdý jej prvok, okremneutrálneho, je jej generátorom.

Poznámka. Z preh©adu o grupách vyplýva, ºe existuje (aº na izomor�zmus)práve jedna grupa rádu 1, 2, 3, 5, 7, a to cyklická grupa. Rád 4 majú dve grupy(neizomorfné): cyklická grupa, ktorá sa objavovala v na²ich príkladoch, a grupanecyklická. Najmen²ou neabelovskou grupou je grupa (S3; ◦). Existujú cyklickégrupy ©ubovo©ného rádu.

3.4 Okruhy, telesá, poliaV ¤al²om texte budeme pracova´ s mnoºinami, na ktorých sú de�nované dvebinárne operácie. Napríklad na mnoºine Z v²etkých celých £ísel sú de�nované dvebinárne operácie, a to s£ítavanie + a násobenie · . Vieme, ºe algebraický systém(Z; +) je komutatívna (abelovská) grupa a algebraický systém (Z; ·) je pologrupa(platí uzavretos´ mnoºiny Z vzh©adom na operáciu · a tieº asociatívnos´). Okremtoho pre v²etky x, y, z ∈ Z je

x(y + z) = xy + xz .

Hovoríme, ºe násobenie je distributívne vzh©adom na operáciu s£ítavania.De�nícia 3.8. Nech na mnoºine A 6= ∅ sú de�nované dve binárne operácie 2 a∗. Algebraický systém (A; 2, ∗) sa nazýva okruh, práve vtedy, ak:

1. (A; 2) je komutatívna grupa,


2. (A; ∗) je pologrupa,3. Operácia ∗ je distributívna vzh©adom na operáciu 2, to znamená, ºe pre

v²etky x, y, z ∈ A platí

x ∗ (y2z) = (x ∗ y)2(x ∗ z) a (x2y) ∗ z = (x ∗ z)2(y ∗ z) .

Poznámky.1. V algebraickom systéme (A; 2, ∗) je dôleºité poradie operácií, nemôºeme ich

poradie vymeni´. Napr. algebraický systém (Z; ·, +, ·) nie je okruh, pretoºe (Z; ·)nie je grupa, ale (Z; +) okruhom je.

2. Neutrálny prvok operácie 2 budeme ozna£ova´ e(2) ( £asto sa nazýva nu-la). Neutrálny prvok operácie ∗ (ak existuje) ozna£íme symbolom e(∗) (zvykne sanazýva´ jednotka). V okruhu (A; +, ·) je to 0, resp. 1.

3. Ak operácia ∗ je komutatívna, okruh nazývame komutatívny.4. Pod triviálnym okruhom rozumieme okruh, ktorý obsahuje iba prvok e(2).

V ostatných prípadoch hovoríme o netriviálnom okruhu.Príkladmi okruhov sú napríklad £íselné (Z; +, ·), (R; +, ·), (C; +, ·). Skúmanie

okruhov za£alo práve na £íselných mnoºinách s operáciami + a · , ale ich vlastnostisa ©ahko dajú prenies´ a na iné okruhy.Príklad 3.8. Nech Mn je mnoºina v²etkých ²tvorcových matíc rádu n (n je pevnezvolené), n ≥ 2, ktorých prvky sú reálne £ísla. �ahko sa preverí, ºe (Mn; +, ·),kde + a · je s£ítavanie a násobenie matíc, je okruh. Nech a 6= 0 je reálne £íslo.Utvorme

a 0 . . . 00 0 . . . 0... ... . . . ...0 0 . . . 0

·

0 0 . . . 00 0 . . . 0... ... . . . ...0 0 . . . a

=

0 0 . . . 00 0 . . . 0... ... . . . ...0 0 . . . 0

.

Matice na ©avej strane majú práve po jednom nenulovom prvku a, teda sú nenulové.Sú£in matíc stru£ne zapí²eme

K ·M = 0,

kde K,M,0 sú uvaºované matice z mnoºiny Mn. Zistili sme, ºe sú£in dvochnenulových matíc je nulová matica, £iºe sú£in dvoch nenulových prvkov (rôznychod e(+)) K a M je nulový prvok 0 (neutrálny prvok vzh©adom na operáciu +).Obdoba toho v £íselných okruhoch (Z; +, ·), (R; +, ·) a (C; +, ·) neexistuje.De�nícia 3.9. Hovoríme, ºe prvok a ∈ A, a 6= e(2), v okruhu (A; 2, ∗) jenetriviálnym delite©om nuly práve vtedy, ak existuje prvok b ∈ A, b 6= e(2), taký,ºe

a ∗ b = e(2) alebo b ∗ a = e(2).

3.5. ÚLOHY 37V príklade 3.8 maticeK aM sú netriviálnymi delite©mi nuly v okruhu (Mn; +, ·).

De�nícia 3.10. Okruh, ktorý má aspo¬ dva prvky a nemá netriviálne delitelenuly, nazývame obor integrity.Príklad 3.9. Presved£íte sa, ºe algebraické systémy (Z5;⊕,�) a (Z6;⊕,�) súokruhy. Z Cayleyho tabuliek pre príslu²né operácie ©ahko zistite, ºe (Z5;⊕,�) jeobor integrity. (Z6;⊕,�) oborom integrity nie je, pretoºe napr. 3� 2 = 0.Veta 3.10. Okruh (Zn;⊕,�) je oborom integrity práve vtedy, ak n je prvo£íslo.

De�nícia 3.11. Okruh (A; 2, ∗) nazývame telesom práve vtedy, ak (A\{e(2)}; 2, ∗)je grupa.

Veta 3.11. Kaºdé teleso je oborom integrity.

De�nícia 3.12. Teleso (A; 2, ∗), v ktorom (A\{e(2)}; ∗) je komutatívna (abelovská)grupa nazývame pole.Poznámka. Dá sa dokáza´, ºe okruh (Zn;⊕,�) je pole práve vtedy, ak n jeprvo£íslo.

3.5 Úlohy3.1. Na mnoºine v²etkých nepárnych prirodzených £ísel sú de�nované operácie 2

a ∗ takto:x2y = x + y + 1,x ∗ y = 0, 5(x + 1)(y + 1)− 1.

Dokáºte, ºe operácia ∗ je distributívna vzh©adom na operáciu 2.3.2. Nech pre ©ubovo©né x, y ∈ N je x � y = yx. Nájdite v²etky x ∈ N, pre ktoré

platí x � 2 = 2 � x. �alej nájdite aspo¬ jednu trojicu x, y, z ∈ N, pre ktorúplatí

(x � y) � z = x � (y � z) .

3.3. Ozna£me pZ (nZ) mnoºinu v²etkých párnych (nepárnych) celých £ísel. Zis-tite, ktoré z nasledujúcich algebraických systémov sú uzavreté vzh©adom naoperáciu:a) (pZ; +), b) (pZ; ·), c) (nZ; ·).

3.4. Zistite, ktoré z nasledujúcich algebraických systémov sú grupy:a) (A; ·), kde A = {z ∈ C; z6 − 1 = 0},b) (B; ·), kde B = {z ∈ C; z6 + 1 = 0},c) (Z; �), kde a � b = a + b− 5 pre v²etky a, b ∈ Z,d) (Z; 2), kde a2b = a + b + a · b pre v²etky a, b ∈ Z.


3.5. Zistite, ktoré z nasledujúcich podmnoºín mnoºiny v²etkých komplexných£ísel C s operáciou + sú podgrupami grapy (C; +):a) mnoºina v²etkých rýdzo imaginárnych £ísel,b) mnoºina v²etkých komplexných £ísel a + ib, kde a, b ∈ Z,c) mnoºina v²etkých komplexných £ísel s absolútnou hodnotou rovnou 1.

3.6. Zistite, £i (A; ◦) je grupa, ak A = {f1, f2, . . . , f6}, kde pre i = 1, 2, . . . , 6 súfi zobrazenia z mnoºiny R \ {0, 1} do mnoºiny R \ {0, 1} de�nované:

f1(x) = x, f2(x) = 1x, f3(x) = 1− x,

f4(x) = 11−x

, f5(x) = 1− 1x, f6 = x

x−1.

3.7. Nájdite v²etky generátory cyklickej grupy (Z10;⊕).3.8. Zistite, £i algebraický systém (A; +, ·) je okruh, ak:

a) A = {a + b 3√

2; a, b ∈ Q},b) A = {2, 4, 6, 8, . . . },c) A = {. . . ,−6,−4,−2, 0, 2, 4, 6, . . . },d) A = {z ∈ C; |z| = 1},e) A = {a + ib; a, b ∈ Q}.

3.9. Zistite, £i (H; ·) je podgrupou grupy (R \ {0}; ·), ak H = {−1, 1}.3.10. Overte, £i algebraický systém (A; +, ·) je okruh, teleso alebo pole, ak:

a) A = {a + b√

7; a, b ∈ Q},b) A = {a + b

√7; a, b ∈ Z}.

Kapitola 4

Neorientované grafy

4.1 De�nícia a základné typy grafovV predchádzajúcich kapitolách sme viackrát vyuºili moºnos´ vyjadri´ ur£ité vzáhypomocou grafov. Boli to napríklad diagramy binárnych relácií, zobrazení, alebo£iasto£ných usporiadaní. Ne²lo pritom o grafy funkcií, ktoré vyjadrujú vzáhymedzi veli£inami (premennými), ktoré poznáme z matematickej analýzy.

Teória grafov je pomerne mladá matematická disciplína, aj ke¤ prvá prácaz teórie grafov, Eulerovo pojednanie o mostoch mesta Krá©ovca (dne²ný Kalin-ingrad), je z roku 1736. Prudký rozvoj teórie grafov nastal aº v druhej polovici20. storo£ia v súvislosti s rozvojom po£íta£ov a ve©kými poºiadavkami na algo-ritmizáciu rôznych úloh. V tomto u£ebnom texte sa oboznámime so stru£nýmizákladmi neorientovaných a orientovaných grafov a s niektorými ich aplikáciamiv elektrotechnike ako aj pri algoritmickom rie²ení rôznych úloh z praxe.De�nícia 4.1. Graf G je usporiadaná dvojica (V, H), kde V je nejaká neprázdnamnoºina a H je mnoºina dvojprvkových podmnoºín mnoºiny V . Prvky mnoºiny Vnazývame vrcholy grafu G a prvky mnoºiny H nazývame hrany grafu G.

V na²om texte budeme uvaºova´ grafy s kone£nou mnoºinou vrcholov (v nieko©kýchprípadoch, ke¤ budeme uvaºova´ nekone£né grafy, to zvlá²´ zdôraznime).

Ak chceme zdôrazni´, ºe graf má mnoºinu vrcholov V a mnoºinu hrán H,pí²eme G = (V, H). Ak hovoríme o nejakom známom grafe G, jeho mnoºinuvrcholov ozna£ujeme V (G), podobne mnoºinu hrán grafu G ozna£ujeme H(G).

Graf je teda rýdzo kombinatorický objekt, ktorý dáva do vzájomných vzáhovprvky dvoch mnoºín. Zdôraz¬ujeme to preto, ºe postupne sa budeme vyjadrova´dos´ obrazne a grafy znázor¬ova´ kreslením do roviny. Vrcholom grafu sa priradiabody roviny (vyzna£ené krúºkami) a hrany sa vyjadrujú spojením príslu²ných dvo-jíc bodov rovnými alebo zakrivenými £iarami. Takému znázorneniu grafu budemehovori´ diagram grafu. Pozor, dva rôzne grafy môºu ma´ rovnaký diagram anaopak, ten istý graf sa dá znázorni´ pomocou dos´ nepodobných �obrázkov�.

39

40 KAPITOLA 4. NEORIENTOVANÉ GRAFY

Príklad 4.1. Na obr. 4.1 sú dva rôzne diagramy grafu G1 = (V1, H1), kdeV1 = {1, 2, 3, 4, 5} a H1 = {{1, 2}{2, 3}{3, 4}{4, 5}{1, 5}} a diagram grafu G2 =(V2, H2), kde V2 = {a, b, c, d, e} a H2 = {{a, b}{b, c}{c, d}{d, e}{e, a}}.

Obr. 4.1Budeme hovori´, ºe hrana {u, v} inciduje s vrcholmi u a v (v diagrame sú

vrcholy u a v spojené £iarou). Tieº sa dá poveda´, ºe vrchol inciduje s hranou.Dva vrcholy sa nazývajú susedné, ak incidujú s tou istou hranou, dve hranynazývame susedné, ak incidujú s tým istým vrcholom.Poznámka. Niekedy sa na rie²enie problémov z praxe vyuºívajú aj grafy s viac-násobnými hranami (v diagrame je dvojica vrcholov spojená viacerými £iarami),tzv. multigrafy, alebo grafy, v ktorých hrana (tzv. slu£ka) inciduje dvakráts tým istým vrcholom. Ak graf môºe obsahova´ slu£ky aj násobné hrany, hovorímeo pseudografe.

Uvedieme si nieko©ko typov grafov, ktoré sa £asto vyuºívajú, a preto dostali²peciálne pomenovania:Kompletný graf na n ≥ 1 vrcholoch je graf Kn = (V, H), kde |V | = n a H ob-sahuje v²etky dvojprvkové podmnoºiny vrcholovej mnoºiny (v diagrame je spojenáhranou kaºdá dvojica vrcholov).Kompletný bipartitný graf Km,n = (V, H), kde m, n ≥ 1, je graf, v ktoromV = {u1, . . . , um} ∪ {v1, . . . , vn}, H = {{ui, vj}; i = 1, 2, . . . ,m, j = 1, 2, . . . , n}.

Kruºnica d¨ºky n ≥ 1 je graf Cn = (V, H), kdeV = {1, 2, . . . , n}, H = {{i, i + 1}; i = 1, . . . , n− 1} ∪ {{1, n}}.

Cesta d¨ºky n ≥ 0 je graf Pn = (V, H), kdeV = {0, 1, . . . , n}, H = {{i− 1, i}; i = 1, . . . , n}.

Komplement grafu G = (V, H) je graf G = (V, H ′), kde H ′ obsahuje v²etky hranychýbajúce v grafe G k tomu, aby bol kompletným grafom, pri£om H ∪H ′ = ∅.

Kruºnica C5 je na obr. 4.1. Na obr. 4.2 sú postupne grafy: K3, K5, P5, K2,3 aK3,3.

4.1. DEFINÍCIA A ZÁKLADNÉ TYPY GRAFOV 41

Obr. 4.2Dva grafy G a G′ povaºujeme za rovnaké, ak majú totoºné mnoºiny vrcholov

a hrán, teda G = G′ znamená, ºe V (G) = V (G′) a E(G) = E(G′). Mnohografov sa v²ak lí²i iba ozna£ením svojich vrcholov a hrán. Toto vystihuje pojemizomor�zmus.De�nícia 4.2. Dva grafy G = (V, E) a G′ = (V ′, E ′) sa nazývajú izomorfné, akexistuje bijektívne zobrazenie f : V → V ′ také ºe pre v²etky u, v ∈ V :

{u, v} ∈ V práve ke¤ {f(u), f(v)} ∈ E ′, .

Zobrazenie f nazývame izomor�zmus grafov G a G′. Fakt, ºe grafy G a G′ súizomorfné zapisujeme G ∼= G′.

Príklad 4.2. Na obr. 4.3 sú diagramy troch izomorfných grafov. Nájdite príslu²néizomor�zmy.

Obr. 4.3Rie²enie. Jeden z izomor�zmov medzi prvým a druhým grafom je napríklad

f =

(1 2 3 4 5 6a d b e c f

).

Existuje viac moºností. Zvy²ok ponecháme na £itate©a. V²etky tri grafy súizomorfné s grafom K3,3.Z de�nície 4.2 vyplýva, ºe pre dva izomomorfné grafy G1 = (V1, H1) a G2 =(V2, H2) platí

|V1| = |V2|, |H1| = |H2| .

Je zrejmé, ºe splnenie týchto dvoch podmienok e²te nezaru£uje, ºe nejaké dva grafysú izomorfné.


De�nícia 4.3. Hovoríme, ºe graf G1 je podgrafom grafu G, ak V (G1) ⊂ V (G)a H(G1) ⊂ H(G). Zapisujeme to: G1 ⊂ G.

De�nícia 4.4. Podgraf G′ = (V, H ′) grafu G = (V, H) nazývame faktor grafu G.

Faktor grafu je teda taký podgraf, ktorý obsahuje v²etky vrcholy daného grafu.Rôzne faktory sa môºu lí²i´ nielen po£tom hrán, ale aj rôznym zloºením hranovýchmnoºín.

Obr. 4.4Na obr. 4.4 sú diagramy v²etkých faktorov grafu K3. Je ich 6 (vrcholy na tej

istej pozícii môºeme uvaºova´ za rovnako ozna£ené), ale ak by sme za rôzne po-vaºovali iba neizomorfné faktory, tak by boli iba 4 rôzne. Je vidie´, ºe v niektorýchfaktoroch (grafoch) sú aj vrcholy, ktoré neincidujú so ºiadnou hranou.

4.2 Stupne vrcholov, súvislos´ a metrikaDe�nícia 4.5. Nech G je graf a v jeho vrchol. Symbolom δG(v) ozna£me po£ethrán incidujúcich s vrcholom v. £íslo δG(v) nazývame stupe¬ vrcholu v v grafeG. Ak δG(v) = 0, vrchol v nazývame izolovaný vrchol.

Ak nemôºe dôjs´ k zámene, tak index G v δG(v) vynechávame. Graf nemôºema´ úplne ©ubovo©né stupne vrcholov. Maximálny stupe¬ (ozna£uje sa symbolom∆(G)) v grafe s n vrcholmi je n− 1 a minimálny 0.Veta 4.1. Pre kaºdý graf G = (V, H) platí∑

v∈V

δG(v) = 2|H|.

Je to zrejmé, pretoºe kaºdá hrana inciduje s dvoma vrcholmi a ke¤ spo£ítavamestupne vrcholov, tak kaºdú hranu zarátame dvakrát. Z tejto vety vyplýva dôleºitýdôsledok.Dôsledok 4.1. Po£et vrcholov s nepárnym stup¬om je v kaºdom grafe £íslo párne.

Ak má graf v²etky vrcholy rovnakého stup¬a k, nazývame ho pravidelnýmgrafom stup¬a k. Je zrejmé, ºe kompletný graf Kn je pravidelným grafom stup¬a

4.2. STUPNE VRCHOLOV, SÚVISLOS� A METRIKA 43n − 1. Z dôsledku je zrejmé, ºe pravidelný graf nepárneho stup¬a nemôºe mańepárny po£et vrcholov.

Nech pre danú dvojicu vrcholov u a v v grafe G = (V, H) existuje postupnos´vrcholov a hrán

v0, h1, v1, h2, v2, . . . , vn−1, hn, vn ,

kde vi ∈ V pre i = 0, 1, 2, . . . , n, pri£om v0 = u, vn = v a hi+1 = {vi, vi+1} prei = 0, 1, . . . , n− 1. Takúto postupnos´ nazývame sledom d¨ºky n medzi vrcholmiu a v. Ak u = v (u 6= v), tak sled je uzavretý (otvorený). Obvykle na ur£eniesledu zapisujeme iba postupnos´ vrcholov, teda v0v1v2 . . . vn.V²imnime si, ºe pre sled sme nepoºadovali aby vrcholy (hrany) boli rôzne.Preto medzi dvojicou vrcholov grafu bu¤ existuje nekone£ne ve©a sledov, aleboneexistuje ºiadny. Sledy môºeme rozdeli´ na nasledujúce typy:áh je sled, v ktorom sú v²etky hrany rôzne.Cesta je áh, v ktorom sú v²etky vrcholy (a tým aj hrany) rôzne. Cestu d¨ºky n(po£et jej hrán) ozna£ujeme Pn.Kruºnica je uzavretá cesta d¨ºky aspo¬ 3. Kruºnica Cn d¨ºky n má práve nvrcholov. (V²imnite si, ºe uº skôr sme zaviedli ten istý pojem iným spôsobom.)

Je zrejmé, ºe z kaºdého sledu S medzi vrcholmi u a v grafu G môºeme vybraćestu, ktorá spája tieto vrcholy.De�nícia 4.6. Hovoríme, ºe graf G je súvislý, ak pre kaºdé dva jeho vrcholyu a v existuje v ¬om sled (cesta) z u do v. Graf, ktorý nie je súvislý, sa nazývanesúvislý.

Ak v nejakom grafe G zvolíme vrchol v, môºeme sa zaujíma´ o v²etky vrcholy,do ktorých sa dá dosta´ po sledoch za£ínajúcich vo vrchole v. Tieto vrcholy a hrany,ktoré s nimi incidujú, tvoria súvislý podgraf grafu G, ktorý nazývame komponentgrafu obsahujúci vrchol v. Presnej²ia de�nícia je:De�nícia 4.7. Komponent grafu je kaºdý jeho maximálny súvislý podgraf (t.j.taký súvislý podgraf, ktorý nie je vlastným podgrafom iného súvislého podgrafu grafuG).

Obr. 4.5Na obr. 4.5(a) je príklad súvislého grafu, zatia©£o na obr. 4.5(b) je príklad

nesúvislého grafu. Na obr. 4.5(c) je nesúvislý graf s tromi komponentmi. Jeho


podgraf pozostávajúci z troch vrcholov a, b, d a z dvoch hrán {a, b} a {b, d} nieje komponentom, hoci jeho diagram vyzerá rovnako ako diagram komponentus vrcholmi e, f, g. Je totiº vlastným podgrafom komponentu so ²tyrmi vrcholmia, b, c, d.

Súvislý graf má iba jeden komponent. Rozhodnú´, £i graf je súvislý, poprípadenájs´ v²etky jeho komponenty, nie je áºké, hoci z diagramu to nemusí by´ vºdy naprvý poh©ad zrejmé. Súvislos´ grafu je typická globálna vlastnos´ grafu. Niekedysa v²ak o nej dá rozhodnú´ na základe lokálnych vlastností grafu, teda z vlastnostíbezprostredného okolia jednotlivých vrcholov a hrán.Veta 4.2. Nech G = (V, H), |V | = n, je graf, v ktorom sú£et stup¬ov ©ubovo©nejdvojice nesusedných vrcholov je aspo¬ n− 1. Potom graf G je súvislý.

Veta 4.3. Nech G = (V, H), |V | ≥ 2, je súvislý graf. Potom v grafe G existujúaspo¬ dva vrcholy také, ºe vynechaním ©ubovo©ného z nich sa súvislos´ neporu²í.

Artikulácia je vrchol grafu, ktorý ak z grafu vynecháme (aj hrany, ktoré s nímincidujú), poru²í sa súvislos´ grafu (v nesúvislom grafe sa zvä£²í po£et komponen-tov). Hranu s tou istou vlastnosóu nazývame most.Veta 4.4. Nech G = (V, H) je kone£ný súvislý graf s n vrcholmi. Potom platí

n− 1 ≤ |H| ≤ n(n− 1)

2.

Predstavme si cestnú sie´ mesta vyjadrenú grafom. Je namieste pýta´ sa nanajkrat²iu dopravnú trasu pre jazdu autom z miesta A do miesta B. Takéto apodobné úvahy vedú k zavedeniu pojmu vzdialenosti v grafe.De�nícia 4.8. Nech G = (V, H) je súvislý graf. Vzdialenos´ d(u, v) vrcholovu, v grafu G je d¨ºka najkrat²ej cesty spájajúcej vrcholy u a v.

Na vzdialenos´ v grafe sa môºeme pozera´ ako na zobrazenie d : V × V →N ∪ {0}, ktoré má nasledujúce vlastnosti:

1. d(u, v) ≥ 0; d(u, v) = 0 ⇔ u = v,2. d(u, v) = d(v, u),3. d(u, v) ≤ d(u, z) + d(z, v) pre v²etky z ∈ V .

Tieto vlastnosti sú axiómy metriky, preto usporiadaná dvojica (V, d) je metrickýpriestor. Pritom V je vrcholová mnoºina grafu a d je metrika � vzdialenos´ vrcholovv grafe. Uvedené vlastnosti sa pri izomor�zme zachovávajú, preto sú uºito£néaj pojmy, ktoré sú de�nované pomocou metriky. Nasledujúca de�nícia uvádzaniektoré u nich.De�nícia 4.9. Nech G = (V, H) je súvislý graf.Exentricita vrcholu u ∈ V je £íslo

e(u, G) = maxv∈V

d(u, v).

4.3. EULEROVSKOS�, HAMILTONOVSKOS� A PLANÁRNOS� 45Priemer grafu G je £íslo

P (G) = maxv∈V

e(v, G).

Polomer grafu G je £íslo

r(G) = minv∈V

e(v, G).

Stred grafu G je mnoºina vrcholov, ktorých exentricita je rovná polomeru.

Poznámka. Priemer grafu G môºeme de�nova´ aj vzáhomP (G) = max

u,v∈Vd(u, v).

Pre grafy neplatí obdoba vzáhu medzipriemerom a polomerom z geometrickejkruºnice. Napríklad pre graf, ktorého dia-gram je na obr. 4.6 je P (G) = r(G) = 2a stred je celá vrcholová mnoºina. V²imnimesi podrobnej²ie vzájomný vzáh priemeru apolomeru toho istého grafu. Obr. 4.6Veta 4.5. Nech G = (V, H) je súvislý graf. Potom platí

r(G) ≤ P (G) ≤ 2r(G).

4.3 Eulerovskos´, hamiltonovskos´ a planárnos´Pojmy a vlastnosti, ktoré si uvedieme v tomto paragrafe, sa vyuºívajú pri rie²eniachpraktických úloh za pomoci teórie grafov.

Jednou zo základných (a najstar²ích) úloh týkajúcich sa grafov je nasledujúcaotázka: Dá sa nakresli´ diagram daného grafu G = (V, H) jedným uzavretým á-hom bez zdvihnutia ceruzky z papiera tak, aby sme po ºiadnej hrane neprechádzaliviackrát?Matematicky môºeme úlohu sformulova´ takto: Dá sa v grafe nájs´ uzavretý sled,v ktorom sa kaºdá hrana vyskytuje práve raz? Taký sled nazývame uzavretýmeulerovským áhom. Graf je eulerovský práve vtedy, ke¤ obsahuje aspo¬ jedenuzavretý eulerovský áh. Hovoríme tieº, ºe graf sa dá pokry´ uzavretým áhom.Dá sa ukáza´, ºe eulerovské grafy môºeme jednozna£ne charakterizova´ bez toho,aby sme hovorili o áhoch. Platí nasledujúca veta.Veta 4.6. (Charakteristika eulerovských grafov.) Graf je eulerovský právevtedy, ak je súvislý a kaºdý jeho vrchol má párny stupe¬.


Ak graf nie je eulerovský, £asto nás zaujíma minimálny po£et hranovo disjunk-tných otvorených áhov, ktorými sa dá pokry´. Pre súvislý graf môºeme nájs´minimálne pokrytie p otvorenými áhmi práve vtedy, ak obsahuje 2p (p ≥ 1)vrcholov nepárneho stup¬a. Tieto otvorené áhy za£ínajú a kon£ia vºdy vo vr-choloch nepárnych stup¬ov. Ak je graf nesúvislý, uvaºujeme kaºdý komponentzvlá²´. (Nakreslite si známy �dom£ek� s piatimi vrcholmi a ôsmimi hranami jed-ným áhom.)

Jedna vec je vedie´, ºe graf je eulerovský, to sa dá ©ahko zisti´, iné je uzavretýeulerovský áh nájs´. Pri h©adaní uzavretého áhu za£neme v ©ubovo©nom vrcholea po hrane s ním incidentnej prejdeme do nejakého susedného vrcholu. Pouºitúhranu z grafu odoberieme a postupujeme rovnakým spôsobom ¤alej aº sa nakoniecvrátime do vrcholu, v ktorom sme za£ínali. Výber hrany je viazaný iba podmienk-ou, aby jej vypustením nevznikol nesúvislý graf (izolované vrcholy pripú²áme, ale²tartovací vrchol sa stane izolovaným aº v poslednom kroku).

Hamiltonovská kruºnica v grafe G je kruºnica obsahujúca v²etky vrcholygrafu G. Graf nazývame hamiltonovský, ak obsahuje aspo¬ jednu hamiltonovskúkruºnicu. Aby bol graf hamiltonovský, musí by´ kone£ný, súvislý, musí obsahovaáspo¬ jeden vrchol a nesmie obsahova´ mosty ani artikulácie. Av²ak ani splnenieuvedených podmienok nezaru£uje existenciu hamiltonovskej kruºnice. NapríkladPetersenov graf na obr. 4.7 nie je hamiltonovský.

Pojem hamiltonovskej kruºnice je na prvýpoh©ad podobný uzavretému eulerovskému áhu:Hamiltonovská kruºnica má prechádza´ bez opakova-nia v²etky vrcholy a uzavretý eulerovský áh v²etkyhrany. Napriek tomu je matematická obtiaºnosóboch problémov ve©mi rozdielna. Zatia©£o uza-vreté eulerovské áhy sú ©ahko zvládnute©né, prob-lém existencie hamiltonovskej kruºnice je mimoriadnenáro£ný a doteraz nepoznáme ºiadnu jednoduchúcharakteristiku hamiltonovských grafov. Tejto prob-lematike sa venuje ve©ké mnoºstvo matematikov adosiahli obrovské mnoºstvo £iasto£ných výsledkov,nie

Obr. 4.7

v²ak nutnú a posta£ujúcu podmienku existencie hamiltonovskej kruºnice. My siuvedieme dve posta£ujúce podmienky.Veta 4.7. Nech G = (V, H) je graf, |V | = n, n ≥ 3. Ak stupe¬ kaºdého vrcholugrafu je aspo¬ n

2, tak G je hamiltonovský graf.

Veta 4.8. Ak pre ©ubovo©né dva nesusedné vrcholy u, v grafu G = (V, H), |V | = n,n ≥ 3, platí

δ(u) + δ(v) ≥ n ,

4.3. EULEROVSKOS�, HAMILTONOVSKOS� A PLANÁRNOS� 47tak graf G je hamiltonovský.

S hamiltonovskými grafmi sa moºno stretnú´ v rôznych súvislostiach aj mimomatematiky. Napríklad americký vedec J. Lederberg, nosite©Nobelovej ceny zamedicínu, pouºil hamiltonovské grafy v chémii pri klasi�kácií organických zlú£enín.My sa s niektorými aplikáciami stretneme neskôr.

V diagrame Petersenovho grafu na obr. 4.7 sa niektoré hrany pretínajú. Môºemesi postavi´ otázku, £i je to nutné. Skúste tento diagram prekresli´. Ak neurobítechybu, tak sa vám to bez pretínania hrán nepodarí.De�nícia 4.10. Graf G = (V, H) je planárny (rovinný), ak jeho diagram v rovinemôºeme zostroji´ tak, ºe dve rôzne hrany majú spolo£né nanajvý² krajné vrcholy.Ak G nie je planárny, tak ho nazývame neplanárny.

V prípade planárneho grafu ide teda o moºnosńakresli´ jeho diagram poºadovaným spôsobom.Planárny je napríklad graf K4, ktorého dva diagramysú na obr. 4.8, hoci v jednom z nich sa hrany pretína-jú. Diagram bez pretínania hrán rozde©uje rovinu nadisjunktné oblasti (ak obsahuje aspo¬ jednu kruºnicu)a tie budeme nazýva´ oblasámi planárneho grafu.Neohrani£enú oblas´ nazývame vonkaj²ia a vhodnýmprekreslením diagramu sa dá dosiahnu´, ºe vonka-j²ou oblasóu bude hociktorá z nich. O oblastiachnemá zmysel hovori´, ak máme diagram s priese£ník-mi. Môºeme sa v²ak pýta´, ko©ko oblastí má diagramplanárneho grafu, ak ho znázornime bez pretínaniahrán.

Obr. 4.8Veta 4.9. (Eulerova veta o planárnych grafoch.) Nech G = (V, H) je súvislýplanárny graf. Nech r je po£et oblastí grafu G. Potom platí

|H| − |V |+ 2 = r .

Z tejto ve©mi dôleºitej vety môºeme odvodi´ nasledujúce závery.Dôsledky.

1. Ak G = (V, H) je súvislý planárny graf, tak |H| ≤ 3|V | − 6.2. Ak G = (V, H) je súvislý planárny graf bez trojuholníkov, tak |H| ≤ 2|V |−4.3. Kaºdý planárny graf obsahuje aspo¬ jeden vrchol, ktorého stupe¬ je men²í

ako ²es´.4. Grafy K5 a K3,3 sú neplanárne.Uvedené grafy K5 a K3,3 predstavujú najmen²ie neplanárne grafy. K5 má

najmen²í po£et vrcholov a K3,3 najmen²í po£et hrán zo v²etkých neplanárnych


grafov. Tieto dva grafy hrajú ve©mi dôleºitú úlohu pri charakterizácii planárnychgrafov. Uvaºujme graf G = (V, H) s aspo¬ jednou hranou. Ak z neho vynechámehranu {u, v} a nahradíme ju dvoma novými hranami {u, z} a {z, v}, povieme, ºenový graf vznikol rozpolením hrany. Dva grafy nazveme homeomorfné, ak súizomorfné, alebo vznikli postupným rozpo©ovaním hrán (aspo¬ u jedného z nich)z toho istého grafu.

Problematiku planárnosti grafov s vyuºitím výhradne kombinatorických vlast-ností, teda bez odvolávania sa na kreslenie diagramov, rie²i nasledujúca elegantnáveta.Veta 4.10. (Kuratowského veta.) Graf G je planárny práve vtedy, ak neob-sahuje podgraf homeomorfný s grafom K5 ani s grafom K3,3.

Príklad 4.3. V Petersenovom grafe na obr. 4.7 nájdite podgraf homeomorfnýs grafom K3,3. Tým ukáºete, ºe nie je planárny. Môºe obsahova´ aj podgrafhomeomorfný s K5?

Problematika kreslenia diagramov grafov nie je jednoduchá, a to ani pre grafyplanárne. Ak sú grafy neplanárne, ich diagramy sa dajú znázorni´ len tak, ºeniektoré hrany sa pretínajú v nekoncových bodoch. To vedie k skúmaniu rôznychmier neplanárnosti grafov. Typickými príkladmi z praxe, kde sa tieto výsledkyintenzívne vyuºívajú sú tzv. VLSI obvody, £o sú ve©mi husto integrované elek-tronické prvky pospájané mikrovodi£mi. Rovinné siete sa pritom skladajú na sebaa prepojenia, ktoré sa nedajú urobi´ v rovine bez pretínania, musia sa realizo-va´ medzi jednotlivými vrstvami. Ide pritom o minimalizáciu takých prepojení ao nahustenie £o najviac prvkov do jednej vrstvy.

4.4 Úlohy4.1. Zistite, £i existuje kone£ný graf, v ktorom ºiadne dva rôzne vrcholy nemajú

rovnaký stupe¬.4.2. Je daný graf, ktorý má aspo¬ dva vrcholy a menej hrán ako vrcholov. Môºe

ma´ kaºdý vrchol grafu stupe¬ aspo¬ dva?4.3. Nech G je komplementárny graf ku grafu G a nech G má aspo¬ dva kompo-

nenty.a) Aký je maximálny po£et komponentov grafu G?b) Aký je priemer grafu G?

4.4. Nech G1 je súvislý faktor grafu G2. Musí by´ graf G2 súvislý?4.5. Majme graf K4 s ozna£enými vrcholmi. Nájdite:

a) po£et rôznych kruºníc v grafe K4,b) po£et rôznych faktorov grafu K4.

4.4. ÚLOHY 494.6. Zistite priemer, polomer a stred Petersenovho grafu.4.6. Akým najmen²ím po£tom áhov sa dá nakresli´ ²achovnica?


Kapitola 5

Orientované grafy

5.1 De�nícia digrafu�itate© si uº ur£ite v²imol dôleºitý rozdiel medzi grafmi z predchádzajúcej kapi-toly a grafmi, ktorými sme znázor¬ovali binárne relácie, zobrazenia alebo £ias-to£ne usporiadané mnoºiny. V spomínaných grafoch sa vyskytovali ²ípky, ktoréreprezentovali usporiadané dvojice prvkov. V tejto kapitole sa budeme zaobera´práve týmito orientovanými grafmi, ktoré budeme skrátene nazýva´ digrafmi. Jeto skrátka z anglického názvu directed graph.De�nícia 5.1. Nech V = {v1, v2, . . . , vn} a nech H ⊂ (V ×V )\{{v1, v1}, {v2, v2},. . . , {vn, vn}}. Digraf −→G je usporiadaná dvojica mnoºín

−→G = (V, H).

Podobne ako pri neorientovaných grafoch, V je mnoºina vrcholov a H je mnoºi-na (orientovaných) hrán. Ak hrana h = (u, v) ∈ H, nazývame vrchol u za£ia-to£ným a vrchol v koncovým vrcholom orientovanej hrany h. Hrany h1 = (u, v)a h2 = (v, u) nazývame opa£ne orientovanými hranami. Pojmy incidencia asusednos´ pre vrcholy aj hrany sa pouºívajú v tom istom význame ako pri (neori-entovaných) grafoch. Podobne v rovnakých významoch sa pouºívajú aj pojmy akopodgraf (aj ke¤ správne by sme mali hovori´ poddigraf) a faktor.

De�nícia digrafu predpokladá orientáciu v²etkých hrán. Je moºné si v²ak ve©-mi dobre predstavi´ aj taký �graf�, v ktorom sú orientované iba niektoré hranya ostatné sú neorientované (napríklad pri znázor¬ovaní dopravnej situácie v ne-jakom meste, kde sú jednosmerné aj obojsmerné ulice). My budeme v tomto texteuvaºova´ iba digrafy so v²etkými orientovanými hranami.

Zru²ením orientácie digrafu môºeme dosta´ graf alebo multigraf. Opa£ný pre-chod je jednozna£ný � orientáciou hrán grafu vºdy dostaneme digraf. Niekedy savyuºíva tzv. symetrická orientácia grafu: Pre kaºdú hranu h = {u, v} grafuG = (V, H) vytvoríme dve opa£ne orientované hrany h′ = (u, v) a h′′ = (v, u)

v digrafe −→G = (V, H ′).51

52 KAPITOLA 5. ORIENTOVANÉ GRAFY

De�nícia 5.2. Dva digrafy −→G 1 = (V1, H1) a−→G 2 = (V2, H2) sa nazývajú izomorfné,

ak existuje bijektívne zobrazenie f : V1 → V2 také ºe pre v²etky u, v ∈ V :

(u, v) ∈ H1 ⇔ (f(u), f(v)) ∈ H2 .

Zobrazenie f nazývame izomor�zmom digrafov−→G 1 a

−→G 2. Zapisujeme

−→G 1

∼=−→G 2.

De�nícia 5.3. Nech−→G = (V, H) je digraf. Ozna£me δ+(v), resp δ−(v) po£et

hrán, ktorých vrchol v je za£iato£ným, resp. koncovým vrcholom. £íslo δ+(v),resp. δ−(v) nazývame vonkaj²í, resp. vnútorný stupe¬ vrcholu v.

Nech G = (V, H) vznikne z −→G = (V, H) zru²ením orientácie. Potom pre kaºdývrchol v ∈ V platí

δ+(v) + δ−(v) = δ(v) .

Dá sa dokáza´, ºe pre vrcholy a hrany digrafu −→G = (V, H) platí (pozri vetu 4.1)∑v∈V

δ+(v) =∑v∈V

δ−(v) = |H| .

V mnohých prípadoch sa ukazuje výhodné zavies´ ²peciálne názvy pre vrcholydigrafu −→G = (V, H). Nech v ∈ V , potom ak:

δ+(v) = δ−(v), tak v je rovnováºny vrchol,δ+(v) > 0, δ−(v) = 0, tak v je prame¬,δ+(v) = 0, δ−(v) > 0, tak v je ústie,δ+(v) > δ−(v) > 0, tak v je zosil¬ova£,0 < δ+(v) < δ−(v), tak v je zoslabova£.

5.2 Súvislos´ a silná súvislos´Moºnos´ prechodu od digrafu ku grafu prostredníctvom zru²enia orientácie hránvyuºijeme na de�novanie nasledujúcich pojmov:Sled v digrafe −→G je postupnos´ vrcholov a hrán v −→G , ktorá po zru²ení orientácieje sledom v G. D¨ºka sledu je po£et jeho hrán.Spojenie v −→G je taký sled v −→G , v ktorom je zachovaná orientácia hrán od za£ia-to£ného vrcholu ku koncovému.Orientovaný áh v −→G je také spojenie v −→G , ktoré po zru²ení orientácie je áhomv G (neopakujú sa hrany).Dráha v −→

G je také spojenie v −→G , ktoré po zru²ení orientácie je cestou v G

(neopakujú sa vrcholy). D¨ºka dráhy je rovná po£tu jej hrán.Cyklus v −→G je uzavretá dráha. Po£et jej vrcholov (hrán) je d¨ºka cyklu.

5.2. SÚVISLOS� A SILNÁ SÚVISLOS� 53Poznámka. V digrafe −→G môºeme tieº hovori´ o pojmoch áh, cesta, kruºnica. Súto také sledy v digrafe −→G , z ktorých po zru²ení orientácie dostaneme áh, cestu,kruºnicu v grafe G. Nezáleºí teda v nich na orientácií hrán.

Pozrime sa teraz na pojem súvislosti digrafu −→G . Budeme rozli²ova´ dva druhy,a to: súvislos´ a silnú súvislos´. De�nícia súvislosti je totoºná s de�níciou súvis-losti v (neorientovanom) grafe. Digraf je teda súvislý, ak medzi jeho ©ubovo©noudvojicou vrcholov existuje sled. Môºeme to vyjadri´ aj takto: Digraf −→G je súvislý,ak je súvislý graf G, ktorý vznikol zru²ením orientácie v −→G .

Nech −→G = (V, H) je súvislý digraf. Pod vzdialenosóu −→d (u, v) z vrcholu udo vrcholu v rozumieme d¨ºku nminimálnej dráhy z u do v. Ak neexistuje dráhaz u do v, tak −→d (u, v) = ∞.De�nícia 5.4. Digraf −→G = (V, H) je silne súvislý, ak pre ©ubovo©né dva vrcholyu, v ∈ V existuje spojenie z u do v aj spojenie z v do u . Silným komponen-tom digrafu

−→G nazývame kaºdý jeho maximálny silne súvislý poddigraf.

Príklad 5.1. Na obr. 5.1 je diagram digrafu, ktorý je súvislý, ale nie je silnesúvislý. Neexistuje spojenie napríklad z vrcholu d do vrcholu b. Digraf obsahujetri silné komponenty, a to: −→G 1 = (V1, H1), −→G 2 = (V2, H2) a −→G 3 = (V3, H3), pri£omV1 = {a, f}, H1 = {(a, f), (f, a)}, V2 = {b, c, g, h}, H2 = {(b, c), (c, h), (h, b), (g, h),(b, g)}, V3 = {d, e, j} a H3 = {(d, e), (e, j), (j, d)}. Ak by sme pridali k tomutodigrafu hranu so za£iato£ným vrcholom v mnoºine V3 a koncovým v mnoºine V1,takt získaný digraf by bol silne súvislý.

Obr. 5.1Veta 5.1. Pre digraf

−→G = (V, H) sú nasledujúce tri tvrdenia ekvivalentné:

a)−→G je silne súvislý.

b)−→G je súvislý a kaºdá jeho hrana sa vyskytuje aspo¬ v jednom cykle.

c) Pre ©ubovo©ný rozklad {V1, V2} vrcholovej mnoºiny V existujú hrany h1, h2

také, ºe h1 má za£iato£ný vrchol vo V1 a koncový vo V2 a h2 má za£iato£ný vrcholvo V2 a koncový vo V1.

Poznámka. Výraz, ºe tvrdenia a), b) a c) sú ekvivalentné znamená: a) platí právevtedy, ak platí b), b) platí práve vtedy, ak platí c) a a) platí práve vtedy, akplatí c). Ak by sme chceli urobi´ dôkaz vety, sta£í nám dokazova´ tri implikácie, ato: a) ⇒ b), b) ⇒ c) a c) ⇒ a).


Veta 5.2. Nech −→G = (V, H) je súvislý digraf, v ktorom pre kaºdý vrchol v ∈ V platíδ+(v) = 1. Potom

−→G obsahuje jediný cyklus.

Ak v Digrafe −→G zmeníme orientáciu kaºdej hrany na opa£nú, získame opa£neorientovaný digraf −→G−. Zrejme v −→G− sa oproti −→G navzájom vymenia vonkaj²iea vnútorné stupne v²etkých vrcholov, v²etky spojenia a cykly zmenia svoju orien-táciu. Z toho vyplýva, ºe tvrdenie vety 5.2 bude plati´ aj v prípade, ºe pre kaºdývrchol v ∈ V predpokladáme δ−(v) = 1.

V predchádzajúcej kapitole sme sa zoznámili s eulerovskými a hamiltonovskýmigrafmi. Vä£²ina vlastností týchto grafov sa dá preformulova´ aj pre digrafy. Digrafnazveme eulerovský, ak sa dá hranovo pokry´ uzavretým orientovaným áhom. Dása ukáza´, ºe digraf je eulerovský práve vtedy, ak je súvislý a kaºdý jeho vrcholje rovnováºny. Podobne môºeme hovori´ o hamiltonovských cykloch, sú to cykly,ktoré obsahujú v²etky vrcholy digrafu. Digraf je hamiltonovský, ak obsahuje aspo¬jeden hamiltonovský cyklus.

5.3 Acyklické digrafyZ doteraz uvedených vlastností digrafov je vidie´, ºe cykly hrajú v digrafoch ve©midôleºitú úlohu. Ovplyv¬ujú silnú súvislos´, rozklad na silné komponenty a majúzásadný vplyv na moºnosti vytvárania rôznych spojení s digrafe. Je napríkladzrejmé, ºe pri zisóvaní povahy v²etkých moºných výpo£tov, ktoré môºu prebieha´pod©a zadaného vývojového diagramu, bude situácia ove©a jednoduch²ia, ak nepri-pustíme cykly. Teraz preberieme iba základné vlastností, ktoré budeme potrebova´pri aplika£nom vyuºití digrafov.De�nícia 5.5. Digraf −→G = (V, H), ktorý neobsahuje cyklus, nazývame acyklickýdigraf.

Na obr. 5.2 sú diagramy troch acyklických digrafov −→G 1, −→G 2 a −→G 3.

Obr. 5.2Ak −→G = (V, H) je acyklický digraf, je zrejmé, ºe aj kaºdý jeho poddigraf je

acyklický. Otázku existencie prame¬a a ústia rie²i nasledujúca veta.

5.4. ÚLOHY 55Veta 5.3. Nech −→G = (V, H), kde H 6= ∅, je kone£ný acyklický digraf. Potom v

−→G

existuje aspo¬ jeden vrchol v ∈ V , pre ktorý je δ+(v) > 0 a δ−(v) = 0.

Nasledujúca veta je nutnou a posta£ujúcou podmienkou pre to, aby digrafbol acyklický. Vyuºíva sa napríklad pri ozna£ovaní vrcholov tzv. sieóvých grafov,ktorými sa rie²ia ve©ké projekty pozostávajúce z mnohých rôzne navzájom súvisiaci-ch úloh.Veta 5.4. Digraf

−→G = (V, H) je acyklickým digrafom práve vtedy, ak môºeme

jeho vrcholy ozna£i´ £íslami 1, 2, . . . , |V | tak, ºe kaºdá hrana (i, j)sp¨¬a podmienkui < j.

Veta 5.3 nám vraví, ºe v kaºdom kone£nom acyklickom digrafe −→G ktorý ob-sahuje aspo¬ jednu hranu, existuje aspo¬ jeden prame¬. Vzh©adom na to, ºeopa£ne orientovaný digraf −→G− k acyklickému digrafu −→G je tieº acyklický, môºemetieº tvrdi´, ºe kaºdý kone£ný digraf s aspo¬ jednou hranou obsahuje vrchol ktorýje ústím. Táto skuto£nos´ nám umoº¬uje zostavi´ postup na zisóvanie, £i danýdigraf je acyklický. Sta£í v danom digrafe nájs´ nejaký prame¬ (alebo ústie) avynecha´ hrany, ktoré sú s nim incidentné. Na vzniknutom digrafe tento postupopakujeme, aº dospejeme ku grafu bez hrán (vrcholy zostávajú) alebo k digrafu,ktorý uº nemá ºiadny prame¬ ani ústie. V prvom prípade bol pôvodný digrafacyklický, v druhom obsahoval aspo¬ jeden cyklus. Z takto popísaného postupu jemoºné odvodi´ aj spôsob orientácie hrán grafu G = (V, H), ktorý zaru£ene povediek acyklickému digrafu.

5.4 Úlohy5.1. Ko©ko cyklov obsahuje digraf na obrázku 5.1?5.2. Majme kruºnicu d¨ºky d, d ≥ 3. Ko©ko je moºností zvoli´ orientácie v²etkých

hrán tak, aby vznikol acyklický digraf?5.3. Uvaºujme kone£ný digraf, v ktorom platí δ+(v) ≥ 1 a δ−(v) ≥ 1 pre v²etky

jeho vrcholy. Je moºné tvrdi´, ºe kaºdý vrchol digrafu je obsiahnutý v ne-jakom cykle?

5.4. Existuje digraf s uzavretým spojením obsahujúcim kaºdú hranu práve raz,ktorý nie je silne súvislý?

5.5 Aký musí by´ graf, aby sa jeho hrany dali orientova´ tak, ºe vznikne silnesúvislý digraf?

5.6. Nech pre kaºdý vrchol v súvislého digrafu −→G = (V, H) je δ+(v) = 1. Aký jemaximálny a aký je minimálny po£et cyklov v −→G?


5.7. Nech −→G je kone£ný, súvislý, acyklický digraf s jediným ústím q a jedinýmprame¬om p. Zostrojme digraf −→G′ tak, ºe ku −→

G pridáme hranu (q, p).Dokáºte, ºe −→G′ je silne súvislý.

5.8. Ukáºte, ºe ak −→G = (V, H) je silne súvislý digraf s aspo¬ dvoma vrcholmi,tak |H| ≥ |V |.

5.9. Ukáºte, ºe je moºné na hranách trojrozmernej kocky zvoli´ orientácie tak, ºevznikne silne súvislý digraf, ktorý neobsahuje hamiltonovský cyklus.

Kapitola 6

Grafy a matice

6.1 Maticové reprezentácie grafov�truktúru grafov v uvaºovaných príkladoch vyjadrovali geometrickým modelom �diagramom. Vhodne zvolený diagram poskytuje na prvý poh©ad ve©a cenných in-formácií o samotnom grafe, av²ak ne²ikovne nakreslený diagram nás môºe zvádza´k nesprávnym záverom, najmä ak ide o izomorfné grafy. Pri po£íta£ovom spra-covaní úloh rie²ených pomocou grafov je reprezentácia grafu diagramom ve©minevýhodná. V tomto prípade je vhodné zvoli´ diskrétny (presnej²ie £íslicový) popisgrafu a na tento ú£el nám výhodne poslúºia matice.De�nícia 6.1. Nech G = (V, H) je graf, V = {v1, v2, . . . , vn} a H = {h1, h2, . . . ,hm}. Maticou incidencie grafu G nazývame maticu A = (aij) typu (n,m), akpre jej prvky platí

aij =

{1 , ak hrana hj je incidentná s vrcholom vi ,0 , v ostatných prípadoch.

Po£et riadkov matice A je rovný po£tu vrcholov grafu G a po£et st¨pcovodpovedá po£tu hrán grafu G. Kaºdý st¨pec matice A obsahuje práve dve jed-ni£ky, pretoºe kaºdá hrana grafu G inciduje práve s dvoma vrcholmi. Riadokodpovedajúci i�tému vrcholu vi obsahuje práve δ(vi) jedni£iek, £o odpovedá po£tuhrán incidentných s vrcholom vi. Tvar matice je ur£ený poradím, v akom smeo£íslovali vrcholy a hrany grafu, je teda závislý na ozna£ení prvkov vrcholovej ahranovej mnoºiny daného grafu. Zmena o£íslovania prvkov aspo¬ jednej z týchtomnoºín má za následok permutáciu riadkov, resp. st¨pcov (prípadne aj riadkovaj st¨pcov) matice incidencie. Z toho vyplýva kritérium pre izomor�zmus dvochgrafov.Veta 6.1. Dva grafy sú izomorfné práve vtedy, ak ich matice incidencie sa stotoº-nia po kone£nom po£te permutácií riadkov a st¨pcov jednej z nich.

57

58 KAPITOLA 6. GRAFY A MATICE

Toto kritérium sa v praxi osved£uje iba s dodato£nými obmedzeniami, pre-toºe pri ve©kých grafoch by bolo potrebné preverova´ v²etkých m!n! permutácií nriadkov a m st¨pcov.Príklad 6.1. Matica incidencie A grafu, ktorého diagram je na obr. 6.1 má tvar

A =

1 0 1 0 1 01 1 0 1 0 00 0 0 1 1 10 1 1 0 0 1

.

Obr. 6.1V matici incidencie sme uvaºovali vrcholy aj hrany grafu a ich vzájomnú in-

cidenciu. Vo v²eobecnosti to bude obd¨ºniková matica. V matici, ktorú terazbudeme de�nova´, uvaºujeme iba vrcholy a existenciu hrany medzi dvoma vrchol-mi. Operácie uskuto£¬ované s týmito maticami nám dokáºu poveda´ o grafochove©a viac.De�nícia 6.2. Nech G = (V, H) je graf s vrcholovou mnoºinou V = {v1, v2, . . . ,vn}. Matica susednosti grafu G je ²tvorcová matica B = (bij) rádu n, ak pre jejprvky platí

bij =

{1 , ak {vi, vj} ∈ H,0 , v ostatných prípadoch.

Napríklad pre graf, ktorého diagram je na obr. 6.1 máme

B =

0 1 1 11 0 1 11 1 0 11 1 1 0

.

Pretoºe {vi, vj} = {vj, vi}, je matica B symetrická. Na jej hlavnej diagonále súnuly, pretoºe v G neexistujú slu£ky. Pri zisóvaní izomor�zmu dvoch grafov po-mocou matíc susednosti musíme v týchto maticiach uvaºova´ rovnaké permutáciemnoºiny ich riadkov aj st¨pcov, takºe celkový po£et moºností je n!.

Matice susednosti sa dajú výhodne vyuºi´ pri overovaní súvislosti grafov akoaj pri ur£ovaní vzdialenosti v danom grafe. K tomu potrebujeme zavies´ ²peciálnenásobenie matíc, ktorých prvky sú iba nuly a jednotky. Nech B je matica sused-nosti grafu G = (V, H), |V | = n. Ozna£me B(1) maticu, ktorú dostaneme z matice

6.1. MATICOVÉ REPREZENTÁCIE GRAFOV 59B pridaním jednotiek na hlavnú diagonálu. Uvaºujme maticu B(2) = (b

(2)ij ) takú,

ºe B(2) = B(1) ·B(1). Z násobenia matíc je zrejmé, ºe

b(2)ij =

n∑k=1

b(1)ik · b(1)

kj ,

pri£om ale v tomto sú£ine matíc budeme pouºíva´ tzv. boolovské s£ítavanie anásobenie (1·1 = 1, 0·1 = 1·0 = 0·0 = 0, 1+0 = 0+1 = 1+1 = 1, 0+0 = 0).V²eobecne môºeme uvaºova´ maticu

B(m) = B(m−1) ·B(1) .

Veta 6.2. Majme maticu susednosti B súvislého grafu G = (V, H), |V | = n.Potom pre ©ubovo©né k, k = 1, 2, . . . , n, je prvok b

(k)ij matice B(k) rovný jednej

práve vtedy, ak d(vi, vj) ≤ k.

Dôsledok 6.1. Graf G = (V, H), |V | = n, je súvislý práve vtedy, ke¤ prvky maticeB(n−1) sú iba jednotky.

Dôsledok 6.2. Pre kaºdé dva rôzne vrcholy grafu G = (V, H) platí

d(vi, vj) = min{k; b(k)ij = 1} .

Nakoniec uvedieme vetu, ktorá dáva do vzáhu maticu incidencie a maticusúvislosti daného grafu.Veta 6.3. Nech A je matica incidencie, AT je k nej transponovaná matica aB je matica susednosti grafu G = (V, H). Nech D = (dij) je diagonálna maticas prvkami dii = δ(vi). Potom

A ·AT = B + D .

Príklad 6.2. Nájdite v²etky dvojice vrcholov, ktorých vzdialenos´ je presne 3 av²etky dvojice vrcholov, ktorých vzdialenos´ je viac ako 3 v grafe zadanom maticoususednosti

B =

0 0 0 1 0 00 0 0 1 1 10 0 0 0 1 11 1 0 0 0 00 1 1 0 0 10 1 1 0 1 0

.

Rie²enie. Pridaním jednotiek na hlavnú diagonálu dostaneme maticuB(1). MaticuB(2) získame násobením B(1) ·B(1) a maticu B(3) násobením B(2) ·B(1). Postupne


teda dostávame:

B(1) =

1 0 0 1 0 00 1 0 1 1 10 0 1 0 1 11 1 0 1 0 00 1 1 0 1 10 1 1 0 1 1

,

B(2) =

1 1 0 1 0 01 1 1 1 1 10 1 1 0 1 11 1 0 1 1 10 1 1 1 1 10 1 1 1 1 1

,

B(3) =

1 1 0 1 1 11 1 1 1 1 10 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 1

.

Vzh©adom na symetrickos´ matíc pod©a hlavnej diagonály si budeme v²íma´ ibaprvky nad diagonálou. V matici B(3) je iba jedna nula v prvom riadku a treómst¨pci, £o pod©a dôsledku 6.2 znamená, ºe vzdialenos´ vrcholov v1 a v3 je viac ako3. V matici B(2) sú rovné nule aj prvky b

(2)1,5, b

(2)1,6 a b

(2)3,4, pri£om v B(3) sú rovné

jednej. To pod©a dôsledku 6.2 znamená, ºe d(v1, v5) = d(v1, v6) = d(v3, v4) = 3.Aj pri digrafoch, podobne ako pri grafoch, patria matice k základným prostried-

kom ich vyjadrenia, hlavne pri strojovom spracovaní.De�nícia 6.3. Nech −→G = (V, H) je digraf, V = {v1, v2, . . . , vn}, H = {h1, h2, . . . ,

hm}. Maticou incidencie digrafu−→G nazývame maticu A = (aij) typu (n, m),

ak pre jej prvky platí

aij =

1 , ak hj = (vi, vk) pre nejaké vk ∈ V ,

−1 , ak hj = (vk, vi) pre nejaké vk ∈ V ,0 , v ostatných prípadoch.

Uvedieme základné vlastnosti matice A:a) v kaºdom st¨pci sa £ísla 1 a −1 vyskytujú práve raz, ostatné prvky sú nuly,b) po£et jednotiek v i�tom riadku je rovný δ+(vi),c) po£et £ísel −1 v i�tom riadku je rovný δ−(vi).Z matice incidencie A digrafu −→G ©ahko dostaneme maticu incidencie grafu G,

ktorý vznikne zru²ením orientácie, a to tak, ºe namiesto aij zoberieme |aij|.

6.2. ÚLOHY 61De�nícia 6.4. Nech −→G = (V, H) je digraf s vrcholovou mnoºinou V = {v1, v2, . . . ,

vn}. Matica susednosti digrafu −→G je ²tvorcová matica B = (bij) rádu n, ak prejej prvky platí

bij =

{1 , ak (vi, vj) ∈ H,0 , v ostatných prípadoch.

Veta 6.4. Nech B je matica susednostidigrafu

−→G = (V, H). Potom pre kaºdé

n ∈ N prvok b(n)ij matice Bn udáva po£et

spojení d¨ºky n z vrcholu vi do vrcholu vj.

Pre maticu incidencie A a maticu sused-nosti B digrafu, ktorého diagram je naobr. 6.2 máme Obr. 6.2

A =

1 −1 1 0 1 00 0 0 −1 −1 0

−1 1 0 0 0 −10 0 −1 1 0 1

,

B =

0 1 1 10 0 0 01 0 0 00 1 1 0

.

6.2 Úlohy6.1. Bez kreslenia diagramu zistite, £i matice

A1 =

1 0 1 0 00 1 0 0 00 1 0 1 00 0 1 1 11 0 0 0 1

, A2 =

0 0 0 1 01 0 1 0 11 1 0 0 00 1 0 0 10 0 1 1 0

sú maticami incidencie toho istého grafu.

6.2. Zistite, £i graf G je súvislý, ak jeho matica susednosti je

B =

0 0 1 0 00 0 1 0 01 1 0 1 00 0 1 0 10 0 0 1 0

.


6.3. Zistite v²etky dvojice vrcholov vi, vj, ktorých vzdialenos´ je vä£²ia ako 3, akgraf je zadaný maticou susednosti

B =

0 1 0 0 0 0 01 0 1 0 0 0 00 1 0 1 0 0 00 0 1 0 1 1 00 0 0 1 0 0 00 0 0 1 0 0 10 0 0 0 0 1 0

.

6.4. Zistite, £i je graf G súvislý, ak je zadaný maticou susednosti

B =

0 1 1 0 0 0 01 0 1 1 0 0 01 1 0 0 0 0 00 1 0 0 0 0 00 0 0 0 0 1 00 0 0 0 1 0 10 0 0 0 0 1 0

.

6.5. Napí²te maticu susednosti digrafu, ktorého diagram je na obr. 5.1.6.6. Ako sa môºeme pomocou maticovej reprezentácie presved£i´, £i digraf je

alebo nie je silne súvislý?

Kapitola 7

Stromy

7.1 Stromy a ich vlastnostiDe�nícia 7.1. Strom je neprázdny súvislý graf, ktorý neobsahuje kruºnice. Lesje graf, ktorého komponenty sú stromy.

Z aplika£ného h©adiska patria stromy k najpopulárnej²ím pojmom teórie grafov.So stromami sa stretávame pri vyjadrovaní ²truktúrnych vlastností rôznych systé-mov. Poznáme napríklad genealogické stromy, ktoré zachytávajú rozvetvenie po-tomstva vo významných rodoch, stromom môºeme vyjadri´ priebeh vyra¤ovacieho(napríklad tenisového) turnaja, rozhodovacím stromom sa dajú ve©mi preh©adnezachyti´ v²etky moºné odpovede na nejakú skupinu otázok s dopredu vymedzený-mi vo©bami odpovedí na jednotlivé otázky, pomocou stromov vyjadrujeme ²truk-túrne vzorce v chémii a podobne. V programovaní sú stromy povaºované za ve©midôleºitý druh dátových ²truktúr a môºu by´ vyuºité napríklad pri preklade z pro-gramovacích jazykov (syntaktické stromy), pri operáciách zora¤ovania súborov dát,pri realizácii tabuliek údajov s potrebou ve©mi rýchlej lokalizácie jednotlivýchpoloºiek (vyh©adávacie stromy).

Na ozna£enie stromov, ako ²peciálnych grafov, budeme pouºíva´ ozna£enie T =(V, H). Písmeno T je z anglickej terminológie, a to zo slova tree.

Dá sa dokáza´, ºe kaºdý súvislý podgraf stromu je tieº strom. Takejto vlast-nosti, ktorá sa prená²a na v²etky podgrafy, hovoríme dedi£ná vlastnos´.Veta 7.1. Nech T = (V, H) je strom a |H| ≥ 1. Potom v T existujú aspo¬ dvarôzne vrcholy, ktoré majú stupe¬ rovný £íslu 1.

Na obr. 7.1 sú diagramy troch stromov. Prvý z nich má práve dva vrcholystup¬a 1 a v²etky ostatné vrcholy majú stupe¬ 2. Taký strom sa nazýva had.Druhý zo stromov je hviezda. Hviezda je strom, ktorý má práve jeden vrcholstup¬a aspo¬ 3 a v²etky ostatné vrcholy majú stupe¬ 1. Tretí zo stromov na obr.7.1 je typ rozhodovacieho stromu (prípadne genealogického stromu).

63

64 KAPITOLA 7. STROMY

Obr. 7.1Nasledujúce vety nám popisujú niektoré zo základných vlastností stromov.

Veta 7.2. Nech T = (V, H) je strom. Potom

|H| = |V | − 1 .

Veta 7.3. Graf G = (V, H) je stromom práve vtedy, ak medzi kaºdou dvojicoujeho vrcholov existuje práve jedna cesta.

V de�nícii 4.8 sme zaviedli pojem priemer P (G), polomer r(G) a stred grafuG = (V, H). Stromy majú ²peciálne vlastnosti vzh©adom na priemer, polomer astred grafu.Veta 7.4. Nech T = (V, H) je strom. Ak jeho priemer je £íslo párne, tak stredomstromu je jediný vrchol a P (T ) = 2r(T ). Ak jeho priemer je £íslo nepárne, takstredom sú dva susedné vrcholy a P (T ) = 2r(T )− 1.

Stru£ne si opí²eme, ako h©ada´ stred (priemer, polomer) v danom grafe. Akmáme daný strom, tak z neho vynecháme v²etky vrcholy stup¬a 1 (aj s hranami,ktoré s nimi incidujú). Dostaneme opä´ strom a proces opakujeme. Nakoniecdostaneme jedinú hranu � stred pozostáva z dvoch vrcholov, alebo dostanemejediný vrchol, ktorý je stredom. Ak stredom je jeden vrchol, polomer je rovnýpo£tu iterácií (ko©kokrát sme vykonali proces odoberania vrcholov stup¬a 1). Akstred pozostáva z dvoch vrcholov, polomer je o jednotku vä£²í ako po£et iterácií.Na obr. 7.2 je znázornený uvedený postup na dvoch stromoch.

Obr. 7.2

7.2. KOSTRY A KRU�NICE 657.2 Kostry a kruºniceDe�nícia 7.2. Kostra grafu G = (V, H) je taký jeho faktor, ktorý je stromom.

Ke¤ si uvedomíme význam slov faktor a strom, tak môºeme kostru charakter-izova´ aj ako súvislý podgraf daného grafu, ktorý obsahuje v²etky jeho vrcholy aneobsahuje kruºnicu. Je zrejmé, ºe v grafe G existuje kostra práve vtedy, ak jegraf G súvislý. Ak je graf G strom, potom v ¬om existuje jediná kostra, ktorouje práve graf G. Na obr. 7.3 sú hrubými £iarami vyzna£ené tri rôzne kostry tohoistého grafu. Je vidie´, ºe graf môºe ma´ viac kostier. K ur£eniu po£tu rôznychkostier grafu sa vrátime neskôr.

Obr. 7.3Veta 7.5. Nech G = (V, H) je súvislý graf a T je jeho podgraf v |V | − 1 hranamineobsahujúci kruºnice. Potom T je kostra grafu G.

Ak sa zamyslíme nad tvrdením vety 7.5 a de�níciou stromu, tak zistíme, ºe©ubovo©né tri z nasledujúcich ²tyroch vlastností implikujú ²tvrtú vlastnos´:

(a) T je súvislý graf,(b) T neobsahuje kruºnice,(c) T má |V | = n vrcholov,(d) T má n− 1 hrán.Napríklad: Nech T je súvislý graf neobsahujúci kruºnice a má n vrcholov,

potom T má n− 1 hrán.Cayley v roku 1889 dokázal, ºe po£et v²etkých rôznych kostier (v²imnite si, ºe

1. a 3. kostra na obr. 7.3 sú rôzne) kompletného grafu Kn pre n ≥ 2 je rovný £íslunn−2. Teraz si uvedieme, ako je moºné ur£i´ po£et rôznych kostier grafu pomocouvhodného determinantu.

Nech G = (V, H), |V | = n, je súvislý graf. Nech B je matica susednosti a D jediagonálna matica s prvkami dii = δ(vi) grafu G. Ozna£me Di −Bi maticu rádun − 1, ktorú sme vytvorili z matice D − B vynechaním i�tého riadku a i�téhost¨pca pre ©ubovo©né i ∈ {1, 2, . . . , n}. Potom pre po£et p(T ) v²etkých rôznychkostier grafu G platí

p(T ) = det(Di −Bi) .


Príklad 7.1. Vypo£ítajte po£et rôznych kostier grafu, ktorého diagram je na obr.7.3.Rie²enie. Najprv napí²eme matice

B =

0 1 1 1 01 0 1 1 01 1 0 1 11 1 1 0 10 0 1 1 0

,

D =

3 0 0 0 00 3 0 0 00 0 4 0 00 0 0 4 00 0 0 0 2

,

D−B =

3 −1 −1 −1 0

−1 3 −1 −1 0−1 −1 4 −1 −1−1 −1 −1 4 −1

0 0 −1 −1 2

.

Vzh©adom na výpo£et determinantu pomocou rozvoja pod©a riadku alebo st¨pcaje výhodné vynecha´ i�tý riadok a i�tý st¨pec tak, aby v matici ostalo £o najviacnúl (nie je to v²ak nutné). Pre i = 3 v na²om prípade dostávame

Di −Bi =

3 −1 −1 0

−1 3 −1 0−1 −1 4 −1

0 0 −1 2

a det(Di −Bi) = 40. Je vidie´, ºe aj v prípade malého grafu je po£et kostier dos´ve©ký.De�nícia 7.3. Nech T = (V, H) je strom. Ak kaºdej hrane stromu T priradímepráve jednu z dvoch moºných orientácií, tak dostaneme orientovaný strom −→

T .

Je zrejmé, ºe k stromu T = (V, H) môºeme zostroji´ práve 2|H| orientovanýchstromov −→T (niektoré z nich budú navzájom izomorfné).De�nícia 7.4. Nech

−→Tv je orientovaný strom s aspo¬ dvoma vrcholmi, v ktorom

z vrcholu v existuje dráha do v²etkých ostatných vrcholov. Potom−→Tv nazývame

kore¬ový strom a vrchol v je kore¬om stromu.Poznámka. V terminológii digrafov kore¬ stromu je vlastne (jediným) prame¬omdigrafu, ktorý je kore¬ovým stromom. Vrcholom, ktoré v digrafe nazývame ústia,

7.2. KOSTRY A KRU�NICE 67budeme v kore¬ových stromoch hovori´ listy (názornej²ie to odpovedá predstavestromu).

V niektorých prípadoch je výhodné uvaºova´ ku kore¬ovému stromu −→Tv opa£neorientovaný strom −→

T−v (v²etky hrany sú opa£ne orientované).

Nako©ko v kore¬ovom strome môºe medzi dvoma rôznymi vrcholmi existovańajviac jedna dráha, orientácia kaºdej hrany v kore¬ovom strome je jednozna£neur£ená výberom kore¬a. Kore¬ový strom −→

Tv môºeme potom v rovine reprezento-va´ aj diagramom neorientovaného stromu Tv, pri£om kore¬ stromu v umiestnimenajvy²²ie.De�nícia 7.5. Nech

−→G je digraf, ktorý vznikol orientáciou grafu (multigrafu)

G. Nech K je kostra grafu (multigrafu) G. Potom digraf−→K , ktorý vznikol z K

rovnakou orientáciou hrán, sa nazýva orientovanou kostrou digrafu−→G . Kostra

súvislého digrafu−→G , ktorá je kore¬ovým stromom, sa nazýva kore¬ová kostra

digrafu−→G .

Ak po zru²ení orientácie v²etkých hrán v digrafe −→G = (V, H) získame graf,tak po£et rôznych orientovaných kostier digrafu −→G je rovný po£tu rôznych kostierv grafe G. Iná situácia je, ak v digrafe −→G sú opa£ne orientované hrany a po zru²eníorientácie získame multigraf.

Nech −→G = (V, H), |V | = n, je súvislý digraf. Nech A je jeho matica incidencie.Potom pre po£et p(

−→T ) v²etkých rôznych orientovaných kostier digrafu −→G platí

p(−→T ) = det( (A ·AT)i )

pre ©ubovo©né i ∈ {1, 2, . . . , n}, pri£om (A · AT)i je matica utvorená z maticeA ·AT vynechaním i�tého riadku a i�tého st¨pca.Príklad 7.2. Vypo£ítajte po£et v²etkých rôznych kostier digrafu −→

G , ktoréhodiagram je na obr. 6.2.Rie²enie. Kmatici incidencie digrafu−→G uverejnenej v kapitole 6 urobíme transpono-vanú maticu a vypo£ítame sú£in A ·AT. Potom pre i = 1 (alebo ©ubovo©né iné)dostávame:

A ·AT =

4 −1 −2 −1

−1 2 0 −1−2 0 3 −1−1 −1 −1 3

a

det( (A ·AT)i ) =

∣∣∣∣∣∣2 0 −10 3 −1

−1 −1 3

∣∣∣∣∣∣ = 13.


Nakoniec sa pozrieme na spôsob ur£ovania po£tu p(−→Tvs) v²etkých rôznych ko-

re¬ových kostier digrafu −→G = (V, H) s kore¬om vo vrchole vs. Na tento ú£el

vytvoríme maticu K = (kij) rádu |V | digrafu −→G , kdekii = δ−(vi), pre i = 1, 2, . . . , |V |,kij = −bij, pre i 6= j, i, j = 1, 2, . . . |V |,

pri£om bij sú prvky matice susednostiB digrafu−→G . Utvorme maticuKs vynechaníms�tého riadku a s�tého st¨pca matice K. Potom platí

p(−→Tvs) = det Ks .

Príklad 7.3. Majme digraf −→G ,ktorého diagram je na obr. 7.4.Zistite po£et p(

−→Tv3) jeho kore¬ových

kostier s kore¬om vo vrchole v3.Rie²enie. Ur£íme matice K a K3takto: Obr. 7.4

K =

1 0 0 0 0 0

−1 1 0 0 −1 −10 −1 0 −1 0 00 0 0 2 −1 00 0 0 0 3 00 0 0 −1 −1 1

,

K3 =

1 0 0 0 0

−1 1 0 −1 −10 0 2 −1 00 0 0 3 00 0 −1 −1 1

.

Potom p(−→Tv3) = det K3 = 6.

7.3 Úlohy7.1. Je moºné, aby v súvislom (kone£nom) grafe existovali dve rôzne kostry, ktoré

nemajú spolo£nú hranu?7.2. Nájdite v²etky neizomorfné stromy s nie viac ako 5 hranami.7.3. Ko©ko hrán treba odstráni´ z Petersenovho grafu, aby vznikla kostra?

7.3. ÚLOHY 697.4. Vypo£ítajte po£et rôznych kostier grafu, ktorý vznikne zru²ením orientácií

hrán digrafu na obrázku 7.4.7.5. V digrafe, ktorého diagram je na obrázku 5.1 vypo£ítajte:

a) po£et rôznych orientovaných kostier,b) po£et rôznych kore¬ových kostier s kore¬om vo vrchole b,c) po£et rôznych kore¬ových kostier s kore¬om vo vrchole a.


Kapitola 8

Aplikácie grafov a digrafov

8.1 Minimálne cesty a spojeniaV tejto kapitole uvedieme niektoré typické úlohy z praxe, pri rie²ení ktorých savýznamne vyuºíva teória grafov. Zárove¬ v niektorých prípadoch uvedieme ajznáme algoritmy na ich rie²enie alebo aspo¬ vhodné heuristicke postupy. Algo-ritmy budeme povaºova´ za rýchly, ak je moºné po£et krokov, ktoré algoritmuspri výpo£te vykoná, ohrani£i´ kon²tantným násobkom polynomiálnej funkcie. Akje algoritmus rýchly, tak so zvä£²ovaním vstupu algoritmu je nárast £asu na je-ho úspe²né ukon£enie �zvládnute©ný� rýchlej²ím po£íta£om. V opa£nom prípadehovoríme, ºe algoritmus nie je efektívny. Záujemcov o presnej²iu charakteristikurýchlosti práce algoritmov odkazujeme na knihy: J. Plesník, Grafové algoritmy,resp. L. Ku£era, Kombinatorické algoritmy zo zoznamu literatúry v závere.

Jednou zo základných úloh v teórii grafov je nájs´ najkrat²iu cestu medzi dvomavrcholmi grafu. Taká poºiadavka sa vyskytuje v mnohých praktických aplikáciách(napríklad pri h©adaní najkrat²ieho dopravného spojenia). V takých grafoch sahrany ozna£ujú £íslami, ktorých význam je rôzny a záleºí od toho, aká úloha sadaným grafom rie²i.

Majme graf G = (V, H), |V | = n. Nech R+ je mnoºina kladných reálnych £ísel.Zobrazenie f : H → R+ nazývame hranovým ohodnotením grafu G. Pre kaºdúhranu {vi, vj} ∈ H £íslo wij = f({vi, vj}) ∈ R+ nazývame ohodnotením hrany{vi, vj}.Podobne de�nujeme hranové ohodnotenie aj pre digrafy, iba namiesto neoriento-vaných hrán {vi, vj} uvaºujeme orientované hrany (vi, vj).

8.1.1 D¨ºka minimálnej cestyPredstavme si, ºe súvislý hranovo ohodnotený graf predstavuje nejakú cestnú sie´,v ktorej vrcholy odpovedajú mestám a kriºovatkám a hodnoty hrán odpovedajú vz-dialenostiam medzi bodmi reprezentovanými vrcholmi. V závislosti od typu úlohy

71

72 KAPITOLA 8. APLIKÁCIE GRAFOV A DIGRAFOV

ohodnotenia hrán môºu predstavova´ aj £as alebo náklady na prepravu z jednéhomiesta na druhé. V takom grafe chceme nájs´ najvýhodnej²ie �spojenia�.

Nech S je cesta z vrcholu vi do vrcholu vj v ohodnotenom grafe G. Sú£etohodnotení hrán cesty S nazveme d¨ºkou cesty S. Pre dva vrcholy vi a vj potomminimálnu z d¨ºok ciest medzi vi a vj nazveme d¨ºkou minimálnej cesty aozna£íme symbolom dw(vi, vj).Pri rie²ení úloh súvisiacich so vzdialenosóu sa naj£astej²ie stretávame s nasle-dujúcimi variantmi:

1. pre dané dva vrcholy u, v ohodnoteného grafu ur£i´ vzdialenos´ medzi u a v,2. pre daný vrchol u ur£i´ vzdialenosti z u do kaºdého vrcholu ohodnoteného

grafu,3. ur£i´ vzdialenosti medzi v²etkými dvojicami vrcholov ohodnoteného grafu.Vzh©adom na to, ºe úloha £íslo 1 je obsiahnutá v 2. a 3. úlohe, obmedzíme

sa na algoritmické rie²enia 2. a 3. úlohy. Pre tento prípad (neorientovaný graf)uvedieme Dijkstrov algoritmus, ktorý rie²i 2. úlohu. Rie²enie 3. úlohy siukáºeme neskôr pre digraf.

Vstupom Dijkstrovho algoritmu je hranovo ohodnotený graf G = (V, H) aza£iato£ný vrchol a, od ktorého sa ur£uje d¨ºka minimálnej cesty (vzdialenos´)dw(a, v) k vrcholu v pre v²etky v ∈ V . Pre kaºdý vrchol v ∈ V sa zavádzapremenná L(v). Je to £íslo, ktoré udáva momentálny �odhad� d¨ºky minimálnejcesty z a do v. Presnej²ie, v kaºdom momente je dw(a, v) ≤ L(v), £o znamená,ºe v priebehu práce algoritmu sa pre niektoré vrcholy môºe L(v) zmen²ova´, preiné sa hodnota L(v) uº stáva pevnou a vtedy je presne rovná dw(a, v). Algoritmuspracuje e²te s premennou A, £o je mnoºina �aktívnych� vrcholov, teda vrcholovs premennou hodnotou L(v). Na za£iatku je A = V .

V hlavnom kroku algoritmu vyberieme z mnoºiny vrcholov s pevnými hodno-tami L vrchol v, ktorý má hodnotu L(v) minimálnu, t.j. do ktorého je z vrcholu anajkrat²ia vzdialenos´ zo v²etkých uº známych vzdialeností. Potom zisújeme, £isa cez tento vrchol v môºu skráti´ doteraz známe nie pevné vzdialenosti do jehosusedov (vrcholov s e²te nie pevnou hodnotou L(x)) cez hrany, ktoré ich spájajú.Ak áno, príslu²né vrcholy dostanú men²iu hodnotu L(x).Algoritmus ur£enia minimálnej cesty (Dijkstra)Vstup: Hranovo ohodnotený graf G = (V, H), po£iato£ný vrchol a.Výstup: L(x) = dw(a, x) pre kaºdý vrchol x ∈ V .

1. Poloº L(a) := 0; L(x) := ∞ pre kaºdé x ∈ V \ {a}; A := V .2. Ak A = ∅, STOP.3. Poloº v := {y ∈ A; L(y) ≤ L(z), z ∈ A} (ak je viac moºností, zvo©©ubovo©nú).

Poloº A := A \ {v}.

8.1. MINIMÁLNE CESTY A SPOJENIA 734. Pre v²etky x ∈ A také, ºe {v, x} ∈ H poloº

L(x) := min{L(x), L(v) + f({v, x})}.Skok na krok 2.

Poznámka. Pri praktickom programovaní nahradíme symbol ∞ nejakou ve©kouhodnotou, o ktorej máme zaru£ené, ºe bude vä£²ia ako d¨ºka maximálnej cestyv G, napr. M = 105 +

∑{u,v}∈H f({u, v}).

Poznamenajme e²te, ºe algoritmus môºeme (len nahradením neorientovanýchhrán {u, v} orientovanými (u, v)) pouºi´ aj pre digrafy.

Poºiadavka, ºe ohodnotenia v²etkých hrán sú kladné, je ve©mi dôleºitá. Preúlohu h©adania d¨ºky minimálnej cesty v grafe, kde niektoré hrany môºu ma´ ajzáporné ohodnotenia (za ich pridanie do cesty dostaneme �prémiu�), nie je známyºiadny efektívny algoritmus, a asi ani ºiadny neexistuje.Príklad 8.1. Zistite d¨ºky minimálnychciest z vrcholu a do v²etkých vrcholovohodnoteného grafu, ktorého diagram jena obr. 8.1.Rie²enie. Získané hodnoty L(x) prijednotlivých prechodoch cyklami (2�3�4) algoritmu sú zapísané v nasledujúcejtabu©ke. Pod£iarknuté hodnoty sú pri vr-choloch, ktoré sme v 3. kroku zvolili zavrchol v. Sú to vlastne de�nitívne hod-noty L(v) = dw(a, v) pre v²etky v ∈ V . Obr. 8.1Poznámka. Nájs´ konkrétnu pos-tupnos´ vrcholov a hrán cesty s min-imálnou d¨ºkou z vrcholu a do zv-oleného vrcholu je moºné �spätným�chodom, na ktorý je práve tabu©kovýzápis priebehu výpo£tu ve©mi výhod-ný. Doporu£ujeme £itate©ovi premys-lie´ si tento postup. Ide pritom vºdyo nájdenie predchádzajúceho vrcholuminimálnej cesty, ak postupujeme odjej konca.

a b c d e f g h0 ∞ ∞ ∞ ∞ ∞ ∞ ∞

4 ∞ 9 ∞ ∞ 7 ∞12 6 ∞ ∞ 7 ∞11 7 ∞ 7 ∞11 7 ∞ 1510 15 910 13

13

8.1.2 D¨ºka minimálneho spojeniaUvaºujme súvislý hranovo ohodnotený digraf −→G = (V, H), to znamená, ºe kaºdejhrane (vi, vj) je priradené kladné reálne £íslo f((vi, vj)) = wij. Nech −→S je spojeniez vrcholu vi do vrcholu vj. Sú£et ohodnotení hrán spojenia −→S nazývame d¨ºkou


spojenia −→S . Pre dva vrcholy vi a vj potom minimálnu z d¨ºok spojení z vi do vj

nazveme d¨ºkou minimálneho spojenia a ozna£íme symbolom −→d w(vi, vj). Aknedôjde k nedorozumeniu, budeme skrátene hovori´ o vzdialenosti z vi do vj.

Na ohodnotenom digrafe si ukáºeme rie²enie 3. úlohy z predchádzajúcej strany,t.j. ako ur£i´ vzdialenosti medzi v²etkými dvojicami vrcholov ohodnoteného grafu.K tomu potrebujeme pojmy cenová a di²tan£ná matica.De�nícia 8.1. Nech

−→G = (V, H), |V | = n, je hranovo ohodnotený digraf. ²tvor-

covú maticu C = (cij) rádu n nazývame cenovou maticou, ak pre jej prvky platí

cij =

wij , ak (vi, vj) ∈ H,∞ , ak (vi, vj) /∈ H,0 , ak i = j .

De�nícia 8.2. Nech−→G = (V, H), |V | = n, je hranovo ohodnotený digraf. ²tvor-

covú maticu D = (dij) rádu n nazývame di²tan£nou maticou, ak pre jej prvkyplatí

dij =

−→d w(vi, vj) , ak existuje spojenie z vi do vj,∞ , ak neexistuje spojenie z vi do vj,0 , ak i = j .

Cenová matica sa zo zadaného ohodnoteného digrafu získa ©ahko a slúºi námna výpo£et di²tan£nej matice (matice vzdialeností), v ktorej sú preh©adne zapísanéd¨ºky minimálnych spojení medzi v²etkými dvojicami vrcholov. Na²im cie©om jeteda vypo£íta´ di²tan£nú maticu. Jedným z moºných postupov na jej ur£enie jetzv. Floydov algoritmus, v ktorom ²tartujeme z cenovej matice a postupným�umoc¬ovaním� získame di²tan£nú maticu.Algoritmus ur£enia minimálneho spojenia (Floyd)Vstup: Hranovo ohodnotený digraf −→G = (V, H) s vrcholmi v1, v2, . . . , vn.Výstup: Di²tan£ná matica D = (dij).

1. Poloº D(0) := C, kde C je cenová matica digrafu −→G , teda d(0)ij = cij pre

v²etky i, j = 1, 2, . . . , n.Poloº k := 1.

2. Vytvor maticu D(k) = d(k)ij tak, ºe

d(k)ij := min{d(k−1)

ij , d(k−1)ik + d

(k−1)kj }.

3. Ak k = n, STOP (D(k) = D), inak poloº k := k + 1.Skok na krok 2.

8.2. MINIMÁLNA KOSTRA GRAFU 75Príklad 8.2. Zostrojte di²tan£nú maticu digrafu−→G , ktorého diagram je na obr. 8.2.Rie²enie. Najprv napí²eme cenovú maticu C apoloºíme ju rovnú matici D(0). Pre k = 1 súv matici D(0) prvý riadok a prvý st¨pec �pracov-né�, a pre prvok d

(1)ij zostrojovanej matice D(1)

platí, ºe je rovný men²iemu z dvojice £ísel: pr-vok na tej istej pozícii v matici D(0), resp. sú£etprvku v prvom riadku a j�tom st¨pci a prvku v pr-vom st¨pci a i�tom riadku. Podobne kon²truu-jeme D(2), . . . ,D(5) = D. Obr. 8.2

C =

0 1 6 ∞ ∞8 0 2 ∞ 9∞ ∞ 0 9 43 5 ∞ 0 ∞∞ ∞ ∞ 3 0

= D(0), D(1) =

0 1 6 ∞ ∞8 0 2 ∞ 9∞ ∞ 0 9 43 4 9 0 ∞∞ ∞ ∞ 3 0

,

D(2) =

0 1 3 ∞ 108 0 2 ∞ 9∞ ∞ 0 9 43 4 6 0 13∞ ∞ ∞ 3 0

, D(3) =

0 1 3 12 78 0 2 11 6∞ ∞ 0 9 43 4 6 0 10∞ ∞ ∞ 3 0

,

D(4) =

0 1 3 12 78 0 2 11 612 13 0 9 43 4 6 0 106 7 9 3 0

, D(5) = D =

0 1 3 10 78 0 2 9 610 11 0 7 43 4 6 0 106 7 9 3 0

.

Poznámka. Floydov algoritmus sa dá bez problémov pouºi´ aj na h©adanie d¨ºkyminimálnych ciest v neorientovanom grafe. Ak ho nechceme ve©mi modi�kova´,sta£í v grafe G nahradi´ kaºdú hranu dvojicou opa£ne orientovaných hrán s rov-nakým ohodnotením.

8.2 Minimálna kostra grafuAº doteraz boli pre nás rôzne kostry daného grafu v zásade rovnocenné, pretoºev²etky obsahovali rovnaký po£et hrán. Iná situácia nastane v hranovo ohod-notenom grafe. V takom prípade má zmysel h©ada´ kostry grafu, ktoré majúextremálny (t.j. najmen²í alebo najvä£²í) sú£et ohodnotení hrán.


Majme súvislý hranovo ohodnotený graf G = (V, H). Zo v²etkých kostier grafuG h©adajme takú, ktorá má minimálny sú£et ohodnotení v²etkých jej hrán. Je zre-jmé, ºe existuje aspo¬ jedna kostra T = (V, H ′) s minimálnym sú£tom ohodnoteníhrán a nazveme ju minimálnou kostrou grafu G = (V, H).

Problém ur£enia minimálnej kostry grafu má svoju motiváciu v praxi. Z na²ichmatematikov sa ním ako prvý úspe²ne zaoberal O. Bor·vka za£iatkom 20. rokovminulého storo£ia v súvislosti s návrhom siete pre rozvod elektriny. ¤al²iu metódurie²enia navrhol v roku 1930 V. Jarník, ale základné my²lienky ich algoritmovsa v²eobecne roz²írili aº po zavedení po£íta£ov. My si uvedieme dva jednoduchéalgoritmy a to Primov a Kruskalov. Primov je výhodnej²í pri strojovom spracovaníproblému, Kruskalov viac vyuºijeme pri rie²ení malých úloh na cvi£eniach, akbudeme rie²i´ úlohy, ktoré nejakým spôsobom potrebujú minimálnu kostru alebojej modi�káciu.I. Algoritmus ur£enia minimálnej kostry (Kruskal)Vstup: Hranovo ohodnotený graf G = (V, H).Výstup: Minimálna kostra T = (V, H ′).

1. Zostroj diskrétny faktor T = (V, ∅).2. Zora¤ hrany grafu G do neklesajúcej postupnosti vzh©adom na ich ohod-

notenia.3. Do T pridaj z neklesajúcej postupnosti prvú hranu, ktorá v T nevytvorí

kruºnicu, a z postupnosti hrán ju odober.4. Ak |H ′| = |V | − 1, STOP (T = (V, H ′) je minimálna kostra), inak skok na

krok 3.Z popísaného algoritmu vyplýva, ºe ak ohodnotenia v²etkých hrán sú navzájom

rôzne, tak existuje jediná minimálna kostra grafu G.II. Algoritmus ur£enia minimálnej kostry (Prim)Vstup: Hranovo ohodnotený graf G = (V, H), V = {v1, v2, . . . , vn}.Výstup: Minimálna kostra T = (V (T ), H ′(T )).

1. Poloº T := (V (T ), H ′(T )), V (T ) := {v1}, H ′(T ) := ∅.2. Ak |V (T )| = n, STOP (T je minimálna kostra).3. Pre vi ∈ V (T ) a vj ∈ V (G) \ V (T ) zvo©hranu {vi, vj} s minimálnym ohod-

notením.Poloº V (T ) := V (T ) ∪ {vj}, H ′(T ) := H ′(T ) ∪ {vi, vj}.(Ak je viac hrán {vi, vj} s rovnakým minimálnym ohodnotením, z nich majúnajprv prednos´ hrany s najmen²ím i a potom s najmen²ím j).Skok na krok 2.

8.3. PROBLÉM OKRU�NEJ CESTY 77Poznámka. V prípade existencie viacerých minimálnych kostier grafu pri pos-tupe pod©a Kruskalovho algoritmu môºeme získa´ ktorúko©vek z nich. Primovalgoritmus produkuje vºdy jedinú kostru, ktorá je ur£ená o£íslovaním vrcholov.Príklad 8.3. Predpokladajme, ºe máme plán okresu, v ktorom existuje ur£itásie´ ciest prvej triedy. Je potrebné v zimnom období zabezpe£i´ dopravu tak, aby:

a) ©ubovo©né dve obce boli spojené zjazdnou cestou,b) náklady na údrºbu ciest boli minimálne.

Majme graf, ktorého diagram je modelom tejto situácie. Hranám priradíme hod-noty nákladov na údrºbu ciest (napr. v tisíckach korún). Rie²ením je kostra grafu(silnej²ie vyzna£ená) na obr. 8.3, ktorej sú£et ohodnotení hrán je 21.

Obr. 8.3

8.3 Problém okruºnej cestyPredstavme si, ºe v ur£itom meste má vyjs´ z po²ty po²tový doru£ovate©, obís´v²etky ulice svojho obvodu a má sa vráti´ naspä´ na po²tu. Cestu si má naplánova´tak, aby bola najkrat²ia.

S touto situáciou úzko súvisí problém okruºnej cesty, ktorý ºiada nájs´v súvislom hranovo ohodnotenom grafe uzavretý sled, ktorý obsahuje kaºdú hranuaspo¬ raz, a pritom sú£et ohodnotení hrán toho sledu je minimálny. Poºadujeteda také hranové pokrytie grafu, ktorého sú£et ohodnotení hrán je minimálny.Uvaºujme nasledujúce prípady.

A. Graf G = (V, H) je hranovo ohodnotený, a pritom eulerovský. V tomtoprípade sa graf dá pokry´ jedným uzavretým áhom, v ktorom sa kaºdá hranagrafu vyskytuje práve raz. Sú£et ohodnotení hrán toho áhu je rie²ením na²ejúlohy.

B. Graf G = (V, H) je súvislý a má práve dva vrcholy nepárneho stup¬a, nechsú to vrcholy u a v. Potom existuje pokrytie grafu jedným otvoreným áhoms koncovými vrcholmi u a v, ktorý uº obsahuje v²etky hrany grafu G. Cestamusí by´ okruºná, a preto z u do v (alebo naopak) musíme prejs´ po niektorýchhranách, ktoré sa uº vyskytli v otvorenom áhu. Pre túto cestu vyberieme zov²etkých moºností takú, ktorá dáva minimálny sú£et ohodnotení hrán. Je zrejmé,


ºe ak k sú£tu ohodnotení hrán otvoreného áhu (v²etkých hrán grafu) pridámesú£et ohodnotení hrán minimálnej cesty z u do v, dostaneme okruºnú cestu v grafeG s minimálnym sú£tom ohodnotení hrán.

C. Prípad B môºeme zov²eobecni´. Nech súvislý graf G = (V, H) obsahujepráve 2m (m > 1) vrcholov nepárneho stup¬a. Potom sa dá pokry´ práve motvorenými áhmi. Kaºdý z otvorených áhov v jednom vrchole nepárneho stup¬aza£ína a v inom kon£í. Preto pri rie²ení problému vyh©adáme v²etky vrcholys nepárnymi stup¬ami a snaºíme sa ich po dvoch pospája´ cestami tak, aby sú£ethodnotení hrán týchto m ciest bol minimálny. K tomuto £íslu pripo£ítame sú£etohodnotení v²etkých hrán grafu.Poznámka. Problémom vo vä£²om grafe môºe by´ ve©ký po£et vrcholov nepárnychstup¬ov. Nájs´ minimálne cesty medzi v²etkými vrcholmi nepárnych stup¬ov gra-fu G môºeme napríklad Dijkstrovým algoritmom, ale výhodnej²ia je modi�káciaFloydovho algoritmu pre neorientované grafy.Príklad 8.4. Majme hranovo ohodnotený grafG, ktorého diagram je na obr. 8.4. VrcholyB, C, D,E majú nepárne stupne. Potrebujemeteda nájs´ dve cesty spájajúce do dvojíc tieto ²tyrivrcholy tak, ºe sú£et ohodnotení ich hrán je min-imálny zo v²etkých moºností. Máme tri moºnosti:

ED + BC = 9 + 8 = 17,EB + DC = 11 + 10 = 21,EC + BD = 10 + 12 = 22.

Najvýhodnej²í je sú£et ciest ED + BC = 17.Ak k tomu £íslu pripo£ítame sú£et ohodnotenív²etkých hrán grafu 67, dostaneme hodnotu min-imálnej okruºnej cesty 84. Obr. 8.4

8.4 Problém obchodného cestujúcehoMajme hranovo ohodnotený súvislý graf, v ktorom vrcholy predstavujú nejakémestá a hrany cestné spojenia medzi týmito mestami, pri£om ohodnotenie hranypredstavuje d¨ºku príslu²ného cestného spojenia. Obchodný cestujúci má vyjs´z jedného pevne zvoleného mesta, prejs´ v²etkými mestami práve raz a vráti´ sado pôvodného mesta, pri£om má cestu voli´ tak, aby bola najkrat²ia.

Ak pouºijeme terminológiu teórie grafov, tak v hranovo ohodnotenom súvislomgrafe G = (V, H) máme nájs´ hamiltonovskú kruºnicu, ktorá má minimálny sú£etohodnotení hrán.

Je zrejmé, ºe v ©ubovo©nom súvislom grafe nemusí hamiltonovská kruºnicavôbec existova´. V tom prípade úloha nemá rie²enie. Uº vieme, ºe nepoznámeefektívne algoritmy ani na zistenie existencie hamiltonovskej kruºnice v danom

8.4. PROBLÉM OBCHODNÉHO CESTUJÚCEHO 79grafe, tobôº na nájdenie minimálnej. My si uvedieme metódu, ktorá spo©ahlivorie²i problém obchodného cestujúceho, av²ak iba v grafoch s malým po£tom hrán.Metódu popí²eme na konkrétnom príklade.Príklad 8.5. Rie²te problém obchodného cestujúceho v grafe, ktorého diagram jena obr. 8.4.Rie²enie. Ke¤ºe v hamiltonovskej kruºnici nezáleºí na po£iato£nom vrchole,predpokladajme, ºe obchodný cestujúci vyjde z mesta A, má prejs´ cez v²etkymestá B, C, D,E a F práve raz a vráti´ sa do mesta A. Sú£et ohodnotení prej-dených hrán má by´ minimálny.

Na rie²enie problému pouºijeme tzv. rozhodovací strom. Z vrcholu A môºemeís´ do B alebo do E. Tejto situácii budú v strome odpoveda´ dve orientovanéhrany, a to hrana (A, B) a hrana (A, E). Ak si zvolíme cestu do B, máme opä´ dvemoºnosti: bu¤ pôjdeme do C alebo do F . V rozhodovacom strome potom budúhrany (B, C) a (B, F ). Takto pokra£ujeme ¤alej v snahe prejs´ v²etky vrcholypráve raz a vráti´ sa do vrcholu A. Získame teda rozhodovací strom s kore¬om vovrchole A. Ohodnotenia hrán grafu z obr. 8.4 môºeme prenies´ aj do kore¬ovéhostromu, my ich v²ak kvôli preh©adnosti na obrázok 8.5 nebudeme zapisova´. Naobr. 8.5 je rozhodovací strom, z ktorého je vidie´, ºe v grafe existuje práve 6hamiltonovských kruºníc, a to:

A B C F D E A (1) A E F D C B A (4)

A B C D F E A (2) A E D C F B A (5)

A B F C D E A (3) A E D F C B A (4)

Obr. 8.5Hamiltonovské kruºnice (1) a (6), (3) a (5), a tieº (2) a (4) sú rovnaké, lí²ia sa

iba smerom �obehu�. Preto ¤alej uvaºujeme iba kruºnice (1), (2) a (3) a vypo£í-tame sú£ty ohodnotení ich hrán. Kruºnica (2) je minimálna so sú£tom 42 ((1) má


sú£et 46 a (3) má sú£et 50). Rie²ením na²ej úlohy sú hamiltonovské kruºnice (2)a (4).Poznámka. Táto metóda rozhodovacieho stromu uº nie je pouºite©ná pri hranovohustých grafoch s viac ako 20 vrcholmi ani ak nasadíme rýchle po£íta£e. Bolivyvinuté niektoré heuristicke metódy, t.j. metódy ktoré nie vºdy sú úspe²né,ale dos´ £asto úspe²né sú aj na grafoch aº do 100 vrcholov. Napríklad metódupenalizácie vrcholov môºe £itate© nájs´ vo viacerých knihách zo zoznamu literatúryv závere.

8.5 Metóda kritickej cestyUvaºujme ur£itú sie´ projektu nejakého výrobného procesu. Sieóvý graf jegrafová reprezentácia nejakého projektu pozostávajúceho z navzájom súvisiacichúloh, ktoré sa musia vykona´ v ur£itom poradí. Je to teda hranovo ohodnotenýsúvislý acyklický digraf −→G = (V, H) s jediným prame¬om a jediným ústím. Ori-entovaná hrana v digrafe −→G sa pouºíva na znázornenie £innosti, ²ípka na hraneznázor¬uje smer pokra£ovania v projekte a ohodnotenie kaºdej hrany je plánovaný£as trvania príslu²nej £innosti. Vrchol v −→G ozna£uje stav, kedy sú ukon£ené £in-nosti, ktoré do¬ho vstupujú a môºu za£a´ £innosti z neho vychádzajúce. Predpok-ladajme, ºe sa nevyskytujú £asové straty. Chceme nájs´ optimálne £asové trvaniecelého projektu.

Kritickou £innosóu nazývame takú £innos´, pred¨ºenie trvania ktorej (zapredpokladu, ºe v ostatných £innostiach je plánovaná doba trvania dodrºaná) spô-sobí pred¨ºenie celého procesu. Dráha medzi prame¬om a ústím v −→G , ktorej kaºdáhrana vyjadruje kritickú £innos´, sa nazýva kritická cesta.

Vrcholy sieóvého grafu budeme ozna£ova´ trojicou £ísel: i, T (i) a T ′(i) (pozriobr. 8.6).

�íslo i znamená poradové £íslo pri o£íslovaní vrcholov £íslami od 1 do |V | tak,ºe kaºdá hrana smeruje z £ísla men²ieho do vä£²ieho.

�íslo T (i) vyjadruje minimálnu dobu, za ktorú sa dá od za£iatku procesu dopríslu²ného stavu dosta´ � je to minimálne £asové ohodnotenie.

�íslo T ′(i) udáva posledný moºný £as, v ktorom musia za£a´ v²etky £innostiodpovedajúce hranám vychádzajúcim z vrcholu i, aby nedo²lo k pred¨ºeniu trvaniacelého procesu � je to maximálne £asové ohodnotenie.

Stru£ne si popí²eme £innos´ algoritmu na h©adanie minimálneho £asového ohod-notenia vrcholov digrafu. Nech sú uº o£íslované vrcholy digrafu. Za£iatok procesu,t.j. vrchol 1 má minimálne £asové ohodnotenie 0 (T (1) = 0). Nech i je ©ubovo©nývrchol skúmaného digrafu −→G . Preberieme v²etky vrcholy j, j < i, také, ºe existujehrana (j, i). Ak ozna£íme f(j, i) ohodnotenie hrany (j, i), tak vrchol i ohodnotímenajvä£²ím z £ísel T (j) + f(j, i), t.j. ozna£ením £asu, v ktorom budú ukon£ené

8.5. METÓDA KRITICKEJ CESTY 81v²etky £innosti kon£iace vo vrchole i. Aby sme mohli vrchol i ohodnoti´, musiaby´ ohodnotené v²etky vrcholy s men²ími poradovými £íslami.Algoritmus minimálneho £asového ohodnoteniaVstup: Hranovo ohodnotený, súvislý, acyklický digraf −→G = (V, H) s jedinýmprame¬om, jediným ústím a s o£íslovanými vrcholmi od 1 do n = |V | tak, ºepre kaºdú hranu (i, j) je i < j.Výstup: Minimálne £asové ohodnotenie T (i) pre kaºdý vrchol i.

1. Poloº T (1) := 0.2. Poloº i := 2.3. Poloº T (i) := max{T (j)+f(j, i)} pre v²etky vrcholy j < i, pre ktoré existuje

hrana (j, i).4. Ak i = n, STOP, inak poloº i := i + 1.

Skok na krok 3.Algoritmus maximálneho £asového ohodnoteniaVstup: Hranovo ohodnotený, súvislý, acyklický digraf −→G = (V, H) s jedinýmprame¬om, jediným ústím a s o£íslovanými vrcholmi od 1 do n = |V | tak, ºepre kaºdú hranu (i, j) je i < j. Hodnoty T (i) pre kaºdý vrchol.Výstup: Maximálne £asové ohodnotenie T ′(i) pre kaºdý vrchol i.

1. Poloº T ′(n) := T (n).2. Poloº i := n− 1.3. Poloº T ′(i) := min{T ′(j)−f(i, j)} pre v²etky vrcholy j > i, pre ktoré existuje

hrana (i, j).4. Ak i = 1, STOP, inak poloº i := i− 1.

Skok na krok 3.Kaºdý vrchol, ktorého minimálne a maximálne £asové ohodnotenia sú rovnaké

(T (i) = T ′(i)), leºí na nejakej kritickej ceste, iné vrcholy na kritickej ceste neleºia.K tomu, aby hrana (i, j) leºala na kritickej ceste, musí sp¨¬a´ podmienky:

1. Vrcholy i, j leºia na kritickej ceste, teda T (i) = T ′(i) a T (j) = T ′(j).2. Pre ohodnotenie f(i, j) hrany (i, j) platí f(i, j) = T (j) − T (i) (f(i, j) =

T ′(j)− T ′(i)).Príklad 8.6. Nájdite kritickú cestu výrobného procesu, ktorý je znázornenýgrafom získaným z grafu na obr. 8.6, ak v ¬om vrcholy �stiahneme� do malýchkrúºkov a neuvaºujeme £ísla vo vrcholoch.


Rie²enie. Najskôr prekreslíme diagram tak, ºe vä£²ie krúºky odpovedajúce vr-cholom rozdelíme na tri £asti (pozri obr. 8.6). Do horných £astí o£íslujeme vrcholytak, aby kaºdá hrana smerovala z vrcholu s men²ím £íslom do vrcholu s vä£²ím.Potom do ©avých £astí zapisujeme hodnoty T (i), t.j. minimálne £asové ohodnote-nia. Vo vrchole 1 je T (1) = 0. Vo vrchole 2 je to T (1) + f(1, 2) = 0 + 8 = 8, tedaT (2) = 8. Vo vrchole 3 je: T (2)+f(2, 3) = 8+10 = 18, T (1)+f(1, 3) = 0+20 =20, preto je T (3) = 20, at¤.

Potom vyplníme hodnoty T ′(i), t.j. nájdeme maximálne £asové ohodnotenia.Za£neme vo vrchole 8, tu je T ′(8) = 40. Prejdeme k vrcholu 7, kde T ′(8) −f(7, 8) = 40−4 = 36, teda T ′(7) = 36. Takto pokra£ujeme vºdy k vrcholu s £íslomo jednotku men²ím a napríklad pre vrchol 3 je: T ′(7) − f(3, 7) = 36 − 5 = 31,T ′(6)−f(3, 6) = 27−7 = 20, teda vo vrchole 3 je T ′(3) = 20, at¤. Hrany kritickejcesty sú na obr. 8.6 vyzna£ené silnej²ie.

Obr. 8.6

8.6 Toky v sieáchZa£neme príkladom. Je daná sie´ potrubia, pri£om potrubie môºe ma´ rôznepriemery a niektoré jeho £asti môºu by´ aj jednosmerné. Sie´ potrubia je uza-vretá okrem dvoch miest, za£iatku a a konca z, kde tekutina do potrubia vteká,resp. z neho vyteká. Máme ur£i´, aké maximálne mnoºstvo tekutiny môºe sieóuza ur£itú dobu pretiec´ z a do z. Je logické sa zaujíma´ o maximálny tok (mnoºstvokvapaliny za jednotku £asu). Potrubie a tekutinu sme uviedli iba pre názornos´, alemôºe sa jedna´ o rôzne prenosové siete a prená²ané médium môºe by´ tieº rôzne.Jedným z takých príkladov môºu by´ aj siete na prenos informácií medzi jed-notlivými po£íta£mi. Pravidlá, ktoré uvedieme v ¤al²ej £asti, platia pre v²etkytakéto tzv. transportné siete. Teóriu uvedieme iba pre orientované grafy. Ak niek-toré potrubia sú obojsmerné, sta£í nahradi´ neorientované hrany dvojicami opa£neorientovaných hrán s rovnakými ohodnoteniami.

8.6. TOKY V SIE�ACH 83De�nícia 8.3. Transportná sie´ (alebo skrátene sie´) je súvislý, orientovaný,hranovo ohodnotený graf

−→G = (V, H) sp¨¬ajúci nasledujúce podmienky:

1. v−→G existuje jediný prame¬ a,

2. v−→G existuje jediné ústie z,

3. kaºdá hrana (i, j) je ohodnotená nezáporným £íslom Cij, ktoré nazývamekapacita hrany (i, j).

Poznámka. V praxi sa iba zriedkavo stáva, ºe transportná sie´ má jediný preme¬a jediné ústie. Napríklad vodovodné potrubie rozvádza vodu z viacerých zdrojova ústia sú v kaºdej domácnosti. Aby sme mohli takúto situáciu matematickyspracova´, pridáme hrany orientované z jedného �ktívneho prame¬a do v²etkýchskuto£ných, a tieº hrany zo skuto£ných ústí do �ktívneho ústia. Kapacity novýchhrán uvaºujeme nekone£ne ve©ké.De�nícia 8.4. Nech −→G je transportná sie´. Tok transportnou sieóu je zobrazenieT : R+ ∪ {0} → H, ktoré kaºdej hrane (i, j) priradí nezáporné £íslo Tij tak, ºe:

1. pre kaºdú hranu (i, j) je Tij ≤ Cij,2. pre kaºdý vrchol j rôzny od prame¬a a ústia platí zákon zachovania toku

cez tento vrchol, teda ∑i

Tij =∑

i

Tji .

Veta 8.1. Nech T je tok v transportnej sieti−→G . Potom tok z prame¬a je rovný

toku do ústia, t.j. ∑i

Tai =∑

i

Tiz .

De�nícia 8.5. Nech T je tok v transportnej sieti−→G . £íslo∑

i

Tai =∑

i

Tiz

nazývame ve©kosóu toku v sieti−→G . Tok T je maximálny, ak pre kaºdý iný

tok T ′ platí, ºe jeho ve©kos´ nie je vä£²ia ako ve©kos´ toku T .

Príklad 8.7. Na obr. 8.7 je transportná sie´s vyzna£enými kapacitami hrán Cij (prvé £íslo nakaºdej hrane) a s tokmi cez hrany Tij (druhé £ís-lo). Ve©kos´ toku je Tab + Tad = Tcz + Tez = 5.Je vidie´, ºe pre kaºdý vrchol okrem a a z platízákon zachovania toku, teda ko©ko do¬ho vte£ie,to©ko z neho vyte£ie. Ak by sme ale zmenili tokhranou (d, e) na hodnotu 1, uº by neplatil zákonzachovania toku pre vrcholy d a e a ohodnoteniahrán £íslami Tij by sa nemohli nazýva´ tokom. Obr. 8.7


V tejto jednoduchej transportnej sieti ©ahko zistime, ºe ak na hranách (a, d),(d, c) a (c, z) zvä£²íme tok o jednotku, zostanú v platnosti podmienky kladené natok a ve©kos´ toku bude Tab +Tad = 6, teda tieº vä£²ia o jednotku. Je to spôsobenézvä£²ením toku pozd¨º cesty P : adcz. Znamená to, ºe pôvodný tok v sieti nebolmaximálny a bolo moºné ho zvä£²i´. Nás bude zaujíma´ práve maximálny tokv sieti, ako získa´ jeho hodnotu a ako zisti´, ºe uº ho nemoºno zvä£²i´.

Zistili sme, ºe ak sa nám podarí nájs´ cestu z prame¬a do ústia, pozd¨º ktorejje moºné zvä£²i´ tok, tak sa zvä£²í tok celou sieóu. V na²om prípade v²ak v²etkyhrany cesty P : adcz boli orientované od prame¬a k ústiu, teda zhodne s cestouP . V niektorých sieách je moºné zvä£²ova´ tok aj pozd¨º ciest, ktoré obsahujúaj hrany opa£ne orientované vzh©adom na cestu. O moºnosti zvä£²enia tokucelou sieóu nás informuje nasledujúca veta.Veta 8.2. Nech P je cesta v transportnej sieti

−→G sp¨¬ajúca podmienky:

1. pre kaºdú zhodne orientovanú hranu (i, j) cesty P je Tij < Cij,2. pre kaºdú opa£ne orientovanú hranu (i, j) cesty P je 0 < Tij.

Nech X je mnoºina obsahujúca £ísla Cij − Tij pre zhodne orientované hrany cestyP a £ísla Tij pre opa£ne orientované hrany cesty P .Ak ∆ = min X a T ∗ je tok transportnou sieóu de�novaný

T ∗ij =

Tij , ak (i, j) /∈ P ,Tij + ∆ , ak (i, j) je zhodne orientovaná s P ,Tij −∆ , ak (i, j) je opa£ne orientovaná vzh©adom na P ,

tak ve©kos´ toku T ∗ je o ∆ vä£²ia ako ve©kos´ pôvodného toku T .

Na základe tejto vety môºeme zostroji´ algoritmus na h©adanie maximálnehotoku v transportnej sieti. Princíp jeho £innosti spo£íva v tom, ºe v transportnejsieti so zadanými kapacitami hrán za£neme nejakým tokom (môºe to by´ nulovýtok kaºdou hranou) a h©adáme cestu z prame¬a do ústia, pozd¨º ktorej je moºnétok zvä£²i´. Ak ju nájdeme, tok zvä£²íme, a opakujeme tento proces znovu. Akopomôcku pri h©adaní cesty z a do z pouºijeme ozna£ovanie vrcholov usporiadanoudvojicou znakov, kde prvý znak znamená predchádzajúci vrchol práve ozna£o-vaného vrcholu na h©adanej ceste P a druhý znak je rovný hodnote, o ktorú jemoºné zvä£²i´ tok na ceste P od prame¬a po práve ozna£ovaný vrchol. Za pre-verený vrchol povaºujeme taký, z ktorého sme uº ozna£ovali jeho neozna£enýchsusedov. Algoritmus ukon£í svoju £innos´ aº ke¤ tok sieóu je maximálny. Pre£oje to tak, si uvedieme neskôr.Algoritmus maximálneho toku (Ford � Fulkerson)Vstup: Transportná sie´ −→G = (V, H), prame¬ a, ústie z, kapacity hrán Ci,j prekaºdú hranu (i, j) a vrcholy o£íslované a = v0, v1, . . . , vn = z.Výstup: Maximálny tok T .

8.6. TOKY V SIE�ACH 851. Poloº Tij := 0 pre kaºdú hranu (i, j).2. Ozna£ vrchol a usporiadanou dvojicou ( ,∞).3. Ak je vrchol z ozna£ený, skok na krok 6.4. Zvo©ozna£ený, ale nepreverený vrchol vi s najmen²ím indexom i. Ak taký

neexistuje, STOP (tok je maximálny), inak poloº v := vi .

5. Nech (α, ∆) je ozna£enie vrcholu v. Prever kaºdú hranu (v, w) a (w, v)(v poradí (v, v0), (v0, v), (v, v1), (v1, v), . . . ), kde w je neozna£ený vrchol. Akpre hranu (v, w) je Tvw < Cvw, ozna£ vrchol w usporiadanou dvojicou

(v; min{∆, Cvw − Tvw}) ,

inak hranu (v, w) neozna£uj. Ak pre hranu (w, v) je Twv > 0, ozna£ vrcholw usporiadanou dvojicou

(v; min{∆, Twv}) ,

inak hranu (w, v) neozna£uj.Skok na krok 3.

6. Nech (γ, ∆) je ozna£enie vrcholu z. Nech w0 = z, w1 = γ. Ak ozna£enievrcholu wi je (γ′, ∆′), poloº wi+1 := γ′. Pokra£uj aº do wk = a. Teraz

P : a = wkwk−1 . . . w1w0 = z

je h©adaná cesta z a do z.Zme¬ tok pozd¨º cesty P takto: Ak hrana h je zhodne orientovaná s P ,zvý² jej tok o ∆, ak je opa£ne orientovaná, zníº jej tok o ∆. Zru² ozna£eniav²etkých vrcholov.Skok na krok 2.

Príklad 8.8. Nájdite maximálny tokv transportnej sieti z obr. 8.8.Rie²enie. Kaºdej hrane priradíme tokTij = 0. Ozna£íme vrchol a znakom( ,∞). Teraz ozna£ujeme jeho susedov,pri£om zachovávame ich poradie. Vrcholv1 ozna£íme znakom (a, 10) a vrchol v3znakom (a, 8). Tým sa vrchol a stáva pre-vereným. Z ozna£ených a nepreverenýchvrcholov má minimálny index vrchol v1,takºe teraz sa zaujímame o jeho neoz-na£ených susedov. Je to jediný vrcholv2 a dostane ozna£enie (v2, 5). ¤al²í pre-verovaný vrchol je v2.

Obr. 8.8


Jeho neozna£ené susedné vrcholy v4 a v6 ozna£íme rovnako (v2, 5). Teraz z oz-na£ených a nepreverených vrcholov má najmen²í index vrchol v3. Nemá neoz-na£ených susedov a tým sa stáva prevereným. Nasleduje vrchol v4. Jeho jedinýneozna£ený sused v5 dostane ozna£enie (v4, 5). Teraz preverujeme v5 a z neho oz-na£íme iba vrchol z znakom (v5, 5). Ke¤ºe vrchol z je uº ozna£ený, pokra£ujemekrokom 6, kde získame cestu P : av1v2v4v5z, pozd¨º ktorej môºeme zvä£²i´ toko hodnotu 5. Urobíme to a za£neme celý proces h©adania novej cesty z prame¬ado ústia odznova. ¤al²ie pokra£ovania sa dajú sledova´ na postupnosti diagramovna obr. 8.9.

Obr. 8.9Na vysvetlenie, ºe v momente ukon£enia práce algoritmu je uº dosiahnutý tok

maximálny, potrebujeme nasledujúce pojmy.De�nícia 8.6. Rez (P, P ) v transportnej sieti

−→G = (V, H) je rozklad jej vrcholovej

mnoºiny na mnoºinu P obsahujúcu prame¬ a jej komplement P , ktorý obsahujeústie.Kapacita rezu (P, P ) je £íslo

C(P, P ) =∑i∈P

∑j∈P

Cij .

8.7. ÚLOHY 87Rez v sieti je teda ©ubovo©né rozdelenie vrcholovej mnoºiny V na mnoºiny P a

P , pri£om a ∈ P , z ∈ P , P ∪ P = V a P ∩ P = ∅. Kapacita rezu je sú£et kapacítv²etkých hrán, ktoré za£ínajú v P a kon£ia v P . Hrany z P do P nás pri kapaciterezu nezaujímajú.Veta 8.3. Nech T je tok v transportnej sieti

−→G = (V, H) a nech (P, P ) je rez v

−→G .

Potom kapacita rezu (P, P ) je vä£²ia alebo rovná ako ve©kos´ toku T , t.j.

C(P, P ) =∑i∈P

∑j∈P

Cij ≥∑

i

Tai .

Veta 8.4. Nech T je tok v transportnej sieti−→G = (V, H) a nech (P, P ) je rez

v−→G . Ak ve©kos´ toku T je rovná kapacite rezu (P, P ), tak tok T je maximálny a

rez (P, P ) je minimálny. Naviac∑i∈P

∑j∈P

Cij =∑

i

Tai

práve vtedy, aka) Tij = Cij pre v²etky i ∈ P a j ∈ P

a zárove¬b) Tij = 0 pre v²etky i ∈ P a j ∈ P .

To znamená, ºe ak sa nám v transportnej sieti podarí nájs´ taký rez (P, P ), ºepre kaºdú hranu smerujúcu z P do P je tok cez ¬u rovný jej kapacite a tok kaºdouhranou z P do P je nulový, tak máme minimálny rez a jeho kapacita je zárove¬rovná maximálnemu toku sieóu. Ak si v²imneme, ºe algoritmus na h©adaniemaximálneho toku kon£í práve vtedy, ke¤ uº nemôºeme ozna£ova´ ¤al²ie vrcholy,t.j. ke¤ hrany smerujúce z ozna£ených vrcholov do neozna£ených sú uº nasýtené azárove¬ hrany z neozna£ených vrcholov do ozna£ených majú nulové hodnoty toku,tak môºeme vyslovi´ nasledujúcu vetu.Veta 8.5. V momente skon£enia £innosti algoritmus (Ford � Fulkerson) dáva navýstupe maximálny tok. Naviac, ak P (P ) je mnoºina ozna£ených (neozna£ených)vrcholov v okamihu ukon£enia £innosti algoritmu, tak rez (P, P ) je minimálny.

8.7 Úlohy8.1. V grafe, ktorého diagram je na obr. 8.10(a):

a) Nájdite minimálnu kostru.b) Nájdite maximálnu kostru.c) Vypo£ítajte d¨ºky minimálnych ciest z vrcholu a do ostatných vrcholov.d) Rie²te problém okruºnej cesty.


Obr. 8.108.2. Vypo£ítajte d¨ºky minimálnych spojení medzi v²etkými dvojicami vrcholov

v digrafe na obr. 8.10(b).8.3. V grafe získanom zru²ením orientácií hrán digrafu na obr. 8.10(b) rie²te

problém obchodného cestujúceho.8.4. Nájdite kritickú cestu v sieóvom grafe, ktorého diagram je na obr. 8.11.

Obr. 8.118.5. Vypo£ítajte maximálny tok transportnou sieóu, ktorá je na obr. 8.12.

Obr. 8.12

Kapitola 9

Formalná logika

9.1 Výroková logikaJednou z hlavných úloh modernej logiky je h©adanie vhodného formálneho jazy-ka, ktorý dovolí vyjadrova´ tvrdenia o nejakej oblasti, a pritom sa vyhne rozporom.

Preto budeme h©ada´ odpovede na tieto otázky:a) £i platia alebo neplatia niektoré tvrdenia sformulovane v uvaºovanom jazyku,b) kedy nejaké tvrdenie vyplýva z iných tvrdení,c) ako skon²truova´ dôkaz tvrdenia.Najskôr popí²eme axiómy a odvodzovacie pravidlá, ktoré ur£ujú vlastností

logických spojok, a to vo formálnom systéme, ktorý nazývame výroková logika(výrokový po£et).Ak k výrokovej logike pridáme axiómy a odvodzovacie pravidlá pre kvanti�kátory,vznikne predikátová logika (predikátový po£et).V prvých troch paragrafoch výrokovej logiky sa oboznámime so základnými po-jmami ako sú výrok, pravdivostná hodnota výroku a logické spojky. Budeme sav prevaºnej miere opiera´ o intuíciu, aº neskôr, v ¤al²ích paragrafoch tieto pojmypo formálnej stránke upresníme.

Majme nejaký jazyk ako dorozumievaci prostriedok. Niektoré gramatické vety,okrem toho, ºe môºu vytvára´ zloºené vety - súvetia, obsahujú v sebe ur£itú infor-máciu, o ktorej má zmysel rozhodova´, £i je pravdivá alebo nepravdivá.Napr.: �Sú£et vnútorných uhlov v kaºdom trojuholníku je 180 stup¬ov� alebo�Ko²ice sú najvä£²ím mestom na svete�. Prisúdenie pravdivosti alebo nepravdi-vosti týchto viet nie je problém jazykovedcov, ale odborníkov.

89

90 KAPITOLA 9. FORMALNÁ LOGIKA

Taká istá situácia je aj v prípade symbolických jazykov, ako sú napr. pro-gramovací jazyk alebo jazyk matematických disciplín. Existujú gramaticke vety,o pravdivosti alebo nepravdivosti ktorých nemá zmysel hovori´. Sú to v²etky opy-tovacie, rozkazovacie a zvolacie vety, napr.: �Nehovor a pí²!�

Uvaºujme nejaký jazyk J , v ktorom je daná istá mnoºina V0 výrazov ktorémajú tieto vlastností:

1. O kaºdom výraze jazyka J vieme rozhodnu´, £i patrí alebo nepatrí do V0.2. Kaºdé dva výrazy z V0 vieme navzájom rozlí²i´.3. Kazdý výraz z V0 je pravdivý alebo nepravdivý.Výrazom z mnoºiny V0 budeme hovori´ elementárne výroky a ozna£ova´

písmenamip, q, r, . . . ,

alebo písmenom p s indexomp1, p2, . . . .

Ak elementárny výrok p je pravdivý, potom pí²emev(p) = 1

a £ítame �pravdivostná hodnota výroku p sa rovná jednej�.Analogicky, ak elementárny výrok p je neprávdivý, tak pí²eme v(p) = 0 £ítame

�pravdivostná hodnota výroku p je nula�.

9.2 Logické spojkyV prirodzenom jazyku z daných viet vytvárame zloºené vety � súvetia� pomocouspojok. Vo formálnej logike sa vyskytujú tieto typy �zloºených viet�:

1. �Nie je pravda, ºe A�.2. �A alebo B�.3. �A a B�.

9.2. LOGICKÉ SPOJKY 914. �Ak A, tak B�.5. �A práve vtedy, ak B�.Písmena A a B tu zastupujú nejaké vety (také, o pravdivosti ktorých má zmy-

sel hovori´). Slovám, pomocou ktorých sú v 1 aº 5 vytvorené zloºené vety, budemehovori´ logické spojky. Teda, logickými spojkami sú:

�nie je pravda, ºe ...��... alebo . . .��ak ...., tak ...��... práve vtedy, ak ...�.Pomocou uvedených logických spojok môºeme z elementárnych formúl jazyka

J vytvára´ nové výrazy, napr.:�ak p, tak q��p práve vtedy, ak r��ak p alebo q, tak nie je pravda, ºe r�Pre jednotlivé logické spojky budeme pouºíva´ tieto znaky:1. �nie je pravda, ze� : ¬2. �alebo� : ∨3. �a� : ∧4. �ak, tak� : ⇒5. �práve vtedy, ak� : ⇔a budeme ich (v uvedenom poradí) nazýva´: negácia, disjunkcia, konjunk-

cia, implikácia, ekvivalencia.Okrem týchto znakov pre zapis výrazov budeme pouºíva´ zátvorky, a to:


©avú zátvorku (a pravú zátvorku ).Zátvorky budú vyjadrova´ prioritu jednotlivých logických spojok pri vytváraní

výrazov. Potom nasledujúce výrazy môºeme pomocou zavedených symbolov vy-jadri´ takto:

�ak p, tak q� má symbolický zápis: p ⇒ q,�p práve vtedy, ak r� má symbolický zápis: p ⇔ r,�ak p alebo q, tak nie je pravda, ºe r� má symbolický zápis: (p ∨ q) ⇒ (¬r).

Majme mnoºinu V0 elementárnych výrokov. Potom:1. Elementárne výroky sú výroky.2. Ak A a B sú výroky, tak aj ¬A, A ∨B, A ∧B, A ⇒ B, A ⇔ B sú výroky.3. Výroky sú práve tie výrazy z V0, ktoré sa dajú utvori´ pod©a 1 a 2.

Príklad 9.1 Výraz((p ∧ q) ⇒ (p ∨ q))

je výrok, pretoºe ho môºeme vytvori´ pomocou 1 aº 3 takto:

p, q pod©a 1.,

p ∧ q pod©a 2.,

p ∨ q pod©a 2.,

((p ∧ q) ⇒ (p ∨ q)) pod©a 3.

9.2. LOGICKÉ SPOJKY 93Konvencia o zátvorkách.Pri dôslednom pouºívaní zátvoriek sa výraz môºe sta´ malo preh©adným. Pre

zjednodu²enie zápisu sa preto dohodneme dodrºiava´ nasledujúcu dohodu:1. Namiesto (p) budeme písa´: p.2. Namiesto (¬(B)) budeme písa´ ¬B.3. Nech 4 a ∇ sú dve spojky vybrané zo spojok:

∧,∨,⇒,⇔ .

Potom:a) namiesto (¬(A))4(B) budeme písa´ ¬A4B,

b) namiesto (B)4(¬(A)) budeme písa´ B4¬A,

c) namiesto((A)4(B))∇(C) a (C)∇((A)4(B))

budeme písa´(A4B)∇C a C∇(A4B).

Príklad 9.2 Výrok(p) ⇒ ((q) ∨ (r))

budeme zapisova´p ⇒ (q ∨ r).

Výrazp ⇒ q ⇒ r

nie je výrok, pretoºe pod©a pravidiel 1., 2. a konvencie o zátvorkách nemôºemejednozna£ne rozhodnú´, £i ide o výrok

p ⇒ (q ⇒ r)

alebo o výrok(p ⇒ q) ⇒ r.


9.3 Pravdivostná hodnotaKaºdému elementárnemu výroku p ∈ V0 sme priradili pravdivostnú hodnotu v(p).Na tomto mieste pripomíname pravdivostné tabu©ky.

Negácia:A ¬A1 00 1

Disjunkcia:A B A ∨B0 0 00 1 11 0 11 1 1

Konjunkcia:A B A ∧B0 0 00 1 01 0 01 1 1

Implikácia:A B A ⇒ B0 0 10 1 11 0 01 1 1

Ekvivalencia:A B A ⇔ B0 0 10 1 01 0 01 1 1

Vhodným pouºitím tabuliek môºeme ur£i´ pravdivostnú hodnotu zloºitej²íchvýrokov.Príklad 9.3 Vy²etríme pravdivostnú hodnotu výroku

B = (((p ∧ q) ⇒ r) ∧ (¬r ⇒ q)) ⇒ (p ⇒ r).

Ozna£meK = ((p ∧ q) ⇒ r) ∧ (¬r ⇒ q), T = p ⇒ r

potomB = (K ⇒ T ).

V záhlaví tabu©ky vypí²eme v²etky výroky, z ktorých je daný výrok vytvorenýpod©a bodov 1., 2. a do st¨pcov ozna£ujúcich elementárne výroky napíseme v²etkymoºné kombinácie symbolov 0 a 1.Ostatné st¨pce doplníme pouºítim príslu²nej tabu©ky de�nujúcej pravdivostnú hod-notu výroku A4B.

9.4. FORMULY VÝROKOVEJ LOGIKY 95p q r ¬r p ∧ q p ∧ q ⇒ r ¬r ⇒ q K p ⇒ r B0 0 0 1 0 1 0 0 1 10 0 1 0 0 1 1 1 1 10 1 0 1 0 1 1 1 1 10 1 1 0 0 1 1 1 1 11 0 0 1 0 1 0 0 0 11 0 1 0 0 1 1 1 1 11 1 0 1 1 0 1 0 0 11 1 1 0 1 1 1 1 1 1Výrok B je pravdivý vºdy, bez oh©adu na to, £i elementárne výroky p, q, r sú

pravdivé alebo nepravdivé.

9.4 Formuly výrokovej logikyV posledných dvoch £astiach sme sa zoznamili s intuitívnym chápaním pojmovvýroku a pravdivostnej hodnoty výroku. Pokúsme sa tieto pojmy vymedzi´ pres-nej²ie.

De�nícia 9.1 Pod abecedou rozumieme kone£nú alebo spo£ítate©nú mnoºinu A.�ubovo©nú postupnos´ prvkov mnoºiny A nazývame slovom.

Niektoré slová v poslednej de�nícii nemajú zmysel. Je zrejmé, ºe je ú£elnérozli²ova´ medzi slovami utvorenými �správne� (napr. mur) a slovami, ktoré sú ibanáhodným zoskupením prvkov mnoºiny A (napr. umr).De�nícia 9.2 Abecedu výrokovej logiky (AVL) tvoria výrokové premenné:

p, q, r, . . . , p, p1, p2, ...,

logické spojky:¬,∨,∧,⇒,⇔,

zátvorky: (, ).

Ozna£me V0 = {p, q, . . . } mnoºinu výrokových premenných, S = {¬,∨,∧,⇒,⇔}mnoºinu logických spojok. Je zrejmé, ºe mnoºina V0 je nekone£ná a mnoºina S jekone£ná.De�nícia 9.3 Pravdivostné ohodnotenie v (valuácia) je zobrazenie mnoziny V domnoºiny {0, 1}. Pí²eme v : V0 → {0, 1}.


De�nícia 9.4 Postupnos´ slov

A1, A2, . . . , An

je vytvárajúcou postupnosóu formuly (VPF) práve vtedy, ak pre kaºdé i, 1 ≤i ≤ n je splnená práve jedna z týchto podmienok:

1. Ai je výroková premenná.

2. Ai je negácia niektorého prvku mnoºiny {A1, A2, . . . , Ai−1}.

3. Ai vznikla z nejakých dvoch prvkov mnoºiny {A1, A2, . . . , Ai−1} aplikáciou

niektorej z logických spojok ¬,∨,∧,⇒,⇔.

Poslednú de�níciu môºeme formulova´ aj takto:De�nícia 9.5 Postupnos´ slov

A1, A2, . . . , An

je vytvárajúcou postupnosóu formuly (VPF) práve vtedy, ak pre kaºdé i, 1 ≤i ≤ n je splnená práve jedna z týchto podmienok:

1'. Ai je výroková premenná.

2'. Existuje j < i také, ºe Ai je práve ¬Aj.

3'. Existujú j, k < i a 4 ∈ S také, ºe Ai je Aj4Ak.

De�nícia 9.6 Slovo A v abecede výrokovej logiky je formula výrokovej logikypráve vtedy, ak existuje taká vytvárajúca postupnos´ formuly, ºe A je jej posledným£lenom.

Jednotlivé formuly budeme ozna£ova´ ve©kými písmenami. Mnoºinu vsetkých for-múl ozna£me F . Abecedu výrokovej logiky spolu s formulami výrokovej logikybudeme nazýva´ jazykom výrokovej logiky (JVL).Príklad 9.4 Slovo

p ⇒ (q ∨ ¬r)

je formula s vytvárajúcou postupnosóup, q, r,¬r, q ∨ ¬r, p ⇒ (q ∨ ¬r).

9.4. FORMULY VÝROKOVEJ LOGIKY 97Kaºdá formula (slovo) má ur£itú zloºitos´, ktorá je daná po£tom logických

spojok s(A). Z toho je zrejmé, ºe v²etky výrokové premenné majú zloºitos´ rovnúnule, to znamená, ºe patria do mnoºiny V0.Zápis A(p1, p2, . . . , pn) znamená, ºe formula A neobsahuje iné výrokové premennéako p1, p2, . . . , pn.

Príklad 9.5 Ak A = p ∧ r ∧ q, tak môºeme písa´ A(p, q, r) = p ∧ r ∧ q.Okrem vytvárania nových formúl pomocou logických spojok, môºeme ich tvori´

aj postupom, ktorý nazývame substitúcia.Ak A(p1, p2, . . . , pn) je formula a B1, B2, . . . , Bn sú slová z abecedy výrokovej

logiky, takA(p1/B1, p2/B2, . . . , pn/Bn)

budeme ozna£ova´ slovo v abecede výrokovej logiky, ktoré dostaneme zA(p1, p2, . . . , pn)

tak, ºe v²ade v A, kde sa vyskytuje písmeno pi (i ∈ {1, 2, . . . , n}) namiesto nehodosadíme slovo Bi. Potom hovoríme, ºe slovo

A(p1/B1, p2/B2, . . . , pn/Bn)

vzniklo substitúciou (dosadením) B1, B2, . . . , Bn za p1, p2, . . . , pn.Dá sa dokáza´, ºe ak A(p1, p2, . . . , pn), B1, B2, . . . , Bn sú formuly, tak aj

A(p1/B1, p2/B2, . . . , pn/Bn)

je formula.Príklad 9.6 Nech A = p ⇒ (q ⇒ r), B = ¬p, C = r ⇒ q. Potom

A(p/B, q/C, r/r) = ¬p ⇒ ((r ⇒ q) ⇒ r).

Boolovskú algebru sme de�novali ako usporiadanú ²esticu B2 = (D, ∨̇, ∧̇,′ , 0, 1),D = {0, 1}, pri£om pre a, b ∈ {0, 1} platí:

a b a′ b′ a∨̇b a∧̇b0 0 1 1 0 00 1 1 0 1 01 0 0 1 1 01 1 0 0 1 1


Porovnaním s tabu©kami pravdivostných hodnôt pre jednotlivé logické spojkyzistíme, ºe

v(¬A) = (v(A))′,

v(A ∨B) = v(A)∨̇v(B),

v(A ∧B) = v(A)∧̇v(B),

v(A ⇒ B) = v(A)′∨̇v(B),

v(A ⇔ B) = (v(A)∧̇v(B))∨̇(v(A)′∧̇(v(B)′).

Aby sme posledné zápisy mohli zjednodu²i´, de�nujme v boolovskej algebre B2okrem operácií ∧̇ a ∨̇ e²te ¤al²ie dve binárne operácie, ktoré ozna£íme: →, ↔.Je rozumné ich de�nova´ v súlade s pravdivostnými tabu©kami pre logické spojky:⇒,⇔.

0 → 0 = 1, 0 ↔ 0 = 1,

0 → 1 = 1, 0 ↔ 1 = 0,

1 → 0 = 0, 1 ↔ 0 = 0,

1 → 1 = 1, 1 ↔ 1 = 1.

Je zrejmé, ºe pre a, b ∈ B2 platía → b = a′∨̇b, a ↔ b = (a′∨̇b)∧̇(a′∨̇b).

De�nícia 9.7 Interpretácia jazyka výrokovej logiky v boolovskej algebre B2 je zo-brazenie v : F → {0, 1} také, ºe platí:

v(¬A) = (v(A))′,

v(A ∨B) = v(A)∨̇v(B),

v(A ∧B) = v(A)∧̇v(B),

v(A ⇒ B) = v(A)′∨̇v(B),

v(A ⇔ B) = (v(A)∧̇v(B))∨̇(v(A)′∧̇(v(B)′).

v(A) nazývame pravdivostnou hodnotou formuly A.

9.5. EKVIVALENCIA FORMÚL 999.5 Ekvivalencia formúlVo v²eobecnosti pod syntaxom rozumieme ²túdium vnútornej stránky ²truktúrysystémov znakov (symbolov) nezávisle na tom, akú funkciu vykonávajú.Sémantika zahr¬uje ²túdium systémov znakov ako prostriedok vyjadrovania zmyslu(významu, obsahu).De�nícia 9.8 Formula A je sémanticky ekvivalentná s formulou B, pí²eme

A ≡ B,

práve vtedy, ak v kaºdej interpretácii v jazyka výrokovej logiky (JVL) v boolovskejalgebre B2 platí v(A) = v(B).

Iná formulácia:Formula A je sémanticky ekvivalentná s formulou B práve vtedy, ak má rov-

nakú pravdivostnú hodnotu ako formula B, nezávislé od pravdivostných hodnôtvýrokových premenných. �iºe formuly A a B sa lí²ia iba syntakticky, t.j. svojouformou (ako slová jazyka výrokovej logiky).De�nícia 9.9 Formula A je tautológia (kontradikcia) práve vtedy, ak pre kaºdúinterpcetáciu v jazyka výrokovej logiky v boolovskej algebre B2 platí:

v(A) = 1 (v(A) = 0).

Zmysel poslednej de�nície je v tom, ºe tautológia je vºdy pravdivá (bez oh©aduna pravdivostné hodnoty výrokových premenných, z ktorých je vytvorená). For-mula je kontradikcia, ak je vºdy nepravdivá.

Ak A je tautológia, tak pí²eme|= A.

Veta 9.1 Formula A je sémanticky ekvivalentná s formulou B práve vtedy, akformula A ⇔ B je tautológia.

Dôkaz. Máme dokáza´, ºe A ≡ B práve vtedy, ak |= (A ⇔ B).1. Nech A ≡ B, t.j. v(A) = v(B). Pod©a de�nície interpretácie jazyka výrokovejlogiky v boolovskej algebre B2 jev(A ⇔ B) = v(A) ↔ v(B) = (v(A)∧̇v(B))∨̇(v(A)′∧̇(v(B)′) = v(A)∨̇(v(A))′ = 1.

2. Nech |= (A ⇔ B), t.j. v(A ⇔ B) = 1. Potomv(A ⇔ B) = v(A) ↔ v(B) = (v(A)∧̇v(B))∨̇(v(A)′∧̇(v(B)′) = v(A)∨̇v(A)′ = 1.


Z toho v(A)∧̇v(B) = 1 alebo v(A)′∧̇v(B)′ = 1. V prvom prípade jev(A) = v(B) = 1,

v druhom prípade mámev(A)′ = v(B)′ = 1,

a tedav(A) = v(B) = 0.

�

Veta 9.2 Relácia ≡ je reláciou ekvivalencie na mnoºine F .

Dôkaz. Bez áºkostí sa dá overi´, ºe relácia sémantickej ekvivalencie≡ je re�exívna,symetrická a tranzitívna.�Z de�nície interpretácie jazyka výrokovej logiky a de�nície semantickej ekvivalencievyplýva, ºe v²etky tautológie sú ekvivalentné s tautológiou

p ∨ ¬p = 1

a v²etky kontradikcie sú ekvivalentné s formuloup ∧ ¬p = 0.

Na logické spojky ∨,∧ môºeme pozera´ aj ako na binárne operácie na mnoºine F :kaºdým dvom formulám A, B ∈ F je jednozna£ne priradená formula A∨B a formu-la A∧B. Analogicky logickú spojku ¬môzeme povaºova´ za unárnu operáciu na F .

Utvorme rozklad mnoºiny F na základe relácie ekvivalencie ≡ na triedy amnoºinu týchto tried oznacme Fe. Platí nasledujúca veta:Veta 9.3 Algebraický systém (Fe,∨,∧,¬, 0, 1) je boolovská algebra.

Z toho, ºe platí posledná veta vyplýva rad dôleºitých tvrdení o sémantickej ekvi-valencii formúl. Niektoré z nich uvádzame:

A ∨B ≡ B ∨ A A ∧B ≡ B ∧ AA ∨ (B ∨ C) ≡ (A ∨B) ∨ C A ∧ (B ∧ C) ≡ (A ∧B) ∧ C

A ∨ A ≡ A A ∧ A ≡ AA ∨ (A ∧B) ≡ A A ∧ (A ∨B) ≡ A

A ∨ I ≡ I A ∧ I ≡ AA ∨O ≡ A A ∧O ≡ OA ∨ ¬A ≡ I A ∧ ¬A ≡ O

¬(A ∨B) ≡ ¬A ∧ ¬B ¬(A ∧B ≡ ¬A ∧ ¬B¬(¬A) ≡ A

9.5. EKVIVALENCIA FORMÚL 101�al²ie sémantické ekvivalentnosti:

A ⇒ B ≡ B ∨ ¬A, A ⇔ B ≡ (A ∧B) ∨ (¬A ∧ ¬B),

A ⇒ B ≡ ¬B ⇒ ¬A, A ∧B ≡ ¬(A ⇒ ¬B),

A ⇔ B ≡ (A ⇒ B) ∧ (B ⇒ A), A ∨B ≡ ¬A ⇒ B.

V mnohých prípadoch k formule A je výhodné nájs´ formulu, ktorá je s ¬ousémanticky ekvivalentná a ktorá má nejakým spôsobom "normalizovaný" tvar.Zo v²etkých normálnych tvarov vyberieme dva, ktoré majú najvä£²í praktickývýznam.Z asociativných zákonov

A ∨ (B ∨ C) = (A ∨B) ∨ C, A ∧ (B ∧ C) = (A ∧B) ∧ C

vyplýva, ºe ak formula A je vytvorená z formúl A1, . . . , An iba pomocou symbolov∨, (, ),

prípadne∧, (, ),

tak pri kaºdom rozloºení zátvoriek dostaneme formulu ekvivalentnú s formulou A.Ozna£me ju

A1 ∨ A2 ∨ · · · ∨ An =n∨

i=1

Ai,

A1 ∧ A2 ∧ · · · ∧ An =n∧

i=1

Ai.

V ¤alsom budeme potrebova´ nasledujúce ozna£enia:Nech A je formula, c je jeden zo symbolov 0 alebo 1, potom

Ac =

{A, ak c = 1,

¬A, ak c = 0.

De�nícia 9.10 Nech p1, p2, . . . , pn sú výrokové premenné. Elementárna kon-junkcia je formula, ktorá má tvar

pc11 ∧ pc2

2 ∧ · · · ∧ pcnn

a elementárna disjunkcia je formula tvaru

pc11 ∨ pc2

2 ∨ · · · ∨ pcnn .


De�nícia 9.11 Formula A má disjunktívny normálny tvar práve vtedy, ak

A = A1 ∨ A2 ∨ · · · ∨ Am

a konjunktívny normálny tvar práve vtedy, ak

A = B1 ∧B2 ∧ · · · ∧Bm,

kde Ai (i = 1, 2, . . . ,m) je elementárna konjunkcia a Bi je elementárna disjunkcia.

Veta 9.4 Ku kaºdej formule výrokovej logiky A existujú formuly tvaru

A1 ∨ A2 ∨ · · · ∨ Am, B1 ∧B2 ∧ · · · ∧Bm,

ktoré sú s ¬ou sémanticky ekvivalentné.

9.6 Realizácia boolovských funkciíMajme formulu A(p1, p2, . . . , pn) = a1 . . . am. Formula B je podformulou danejformuly A práve vtedy, ak existujú prírodzené £ísla i, j; 1 ≤ i ≤ j ≤ n také, ºe Bje slovo aiai+1 . . . aj alebo menej formálne:

Formulu výrokovej logiky, ktorá sa vyskytuje vo v²etkých vytvárajúcich pos-tupnostiach formuly A, nazývame podformulou formuly A.Príklad 9.7 Podformulami formuly

(p ⇒ (q ∧ r)) ∨ (q ⇔ r)

súp, q ∧ r, q ⇔ r, p ⇒ (q ∧ r).

Kaºdej formule A(p1, p2, . . . , pn) výrokovej logiky prislúcha tabu©ka pravdivost-ných hodnôt. Av²ak tá istá tabu©ka hodnôt jednozna£ne ur£uje istú boolovskúfunkciu n premenných, ktorú ozna£íme fA a budeme ju nazýva´ pravdivostnoufunkciou formuly A.Rie²me nasledujúcu úlohu. K danej funkcii f ∈ BF (n) máme nájs´ takú formuluA, ºe f = fA.De�nícia 9.12 Formula A realizuje boolovskú funkciu f práve vtedy, ak f =fA.

Veta 9.5 Ku kaºdej boolovskej funkcii existuje formula, ktorá ju realizuje.

9.7. MINIMÁLNA REALIZÁCIA BOOLOVSKEJ FORMULY 103Dôkaz.1. Nech f(x1, . . . , xn) = 0. Potom zrejme

f(x1, . . . , xn) = x1 ∧ x1.

2. Nech f(x1, . . . , xn) 6= 0. Potom ju moºno vyjadri´ v disjunktívnom normálnomtvare

f(x1, . . . , xn) =∨

(σ1,...,σn), f(σ1,...,σn)=1

xσ11 ∧ · · · ∧ xσn

n .

Znamená to, ºe ©ubovolnú funkciu moºno vyjadri´ formulou pozostavajúcou z trochfunkcií a to negácie, konjunkcie a disjunkcie.�

9.7 Minimálna realizácia boolovskej formulyV istých prípadoch je vhodné nájs´ £o najkrat²í normálny tvar formuly. Na tentoú£el bolo vyvinutých nieko©ko metód. K najob©úbenej²ím patrí Karnaughovamapa, ktorú môºeme de�nova´ nasledujúco:

Nech je daná formula A(a1, . . . , an) výrokovej logiky, pri£om a1, . . . , an sú rôznélogické premenné. Naviac predpokladajme, ºe máme zostavenú pravdivostnú tabu©kuformuly A, ktorá má 2n riadkov.

Predpokladajme, ºe s ∈ N, s > 1. V prípade, ºe s = 1 Karnaughovu mapunie je moºné zostavi´.

Nech s = 2k (s je párne).Zoznam premenných rozdelíme na dve podmnoºiny rovnakej mohutnosti:

{a1, . . . , a`} a {a`+1, . . . , as},

kde ` = s/2.Skon²truujme dvojrozmernú tabu©ku KM , ktorá má 2` riadkov a 2` st¨pcov.Kaºdý riadok bude ozna£ený `-ticou núl a jednotiek, pri£om ozna£enia riadkov,

ako `-tice núl a jednotiek sa lí²ia práve v jednej poloºke.Kaºdý st¨pec bude ozna£ený `-ticou núl a jednotiek, pri£om ozna£enia st¨pcov,

ako `-tice núl a jednotiek sa lí²ia práve v jednej poloºke.


Ak (r1, . . . , r`) je ozna£enie riadku a (s1, . . . , s`) je ozna£enie st¨pca potomtabu©ka KM bude ma´ na danej pozícii hodnotu z riadku (r1, . . . , r`, s1, . . . , s`)pravdivostnej tabu©ky formuly A.

Nech s = 2k + 1, s > 1 (s je nepárne).Zoznam premenných rozdelíme na dve podmnoºiny mohutnosti ` a ` + 1 :

{a1, . . . , a`} a {a`+1, . . . , as},

kde ` = (s− 1)/2.Skon²truujme dvojrozmernú tabu©ku KM , ktorá má 2` riadkov a 2`+1 st¨pcov.Kaºdý riadok bude ozna£ený `-ticou núl a jednotiek, pri£om ozna£enia riadkov,ako `-tice núl a jednotiek sa lí²ia práve v jednej poloºke.Kaºdý st¨pec bude ozna£ený `-ticou núl a jednotiek, pri£om ozna£enia st¨pcov, ako`-tice núl a jednotiek sa lí²ia práve v jednej poloºke.Ak (r1, . . . , r`) je ozna£enie riadku a (s1, . . . , s`+1) je ozna£enie st¨pca potom tabu©-ka KM bude ma´ na danej pozícii hodnotu z riadku (r1, . . . , r`, s1, . . . , s`+1) prav-divostnej tabu©ky formuly A.

Takejto dvojrozmernej tabu©ke KM budeme hovori´Karnaughova mapa for-muly A.Karnaughova mapa je zaloºená na preorganizovaní pravdivostnej tabu©ky boolovskejformuly do tvaru, z ktorého sa dajú ©ahko identi�kova´ £asti vyjadrite©né ako kon-junkcie £o najmen²ieho po£tu literálov. V prípade dvoch premenných je to oby£a-jná ²tvorcová tabu©ka 2×2. Ak sú premenné tri, tabu©ka je typu 2×4, ak sú ²tyri,je typu 4× 4. St¨pce, resp. riadky, v posledných dvoch prípadoch sú ²peci�kovanéohodnoteniami dvojíc výrokových premenných, pri£om susedné sú práve tie, ktorésa lí²ia v jednej zloºke. Teda za susedné sú povaºované aj oba krajné st¨pce, resp.riadky. Napríklad v Karnaughovej mape

pq/rs 00 01 11 1000 1 1 0 101 0 1 0 011 0 0 1 010 0 0 0 0

pq/rs 00 01 11 1000 1 1 0 101 0 1 0 011 0 0 1 010 0 0 0 0

tu£ne vyzna£ené st¨pce a riadky sú susedné.Karnaughovu mapu si teda môºeme predstavi´ ako objekt nakreslený na povrchuanuloidu (torus), £o je priestorové teleso, tvarom pripominajúce pneumatiku.De�nícia 9.13 Bázickou maticou jedni£iek (núl) nazývame £as´ Karnaughovejmapy zo samých jedni£iek (resp. núl) vytvárajúcu obd¨ºnik susedných polí£ok.Rozmery tohto obd¨ºnika musia by´ celo£íselné mocniny £ísla dva.

9.7. MINIMÁLNA REALIZÁCIA BOOLOVSKEJ FORMULY 105Kaºdá bázická matica jedni£iek (resp. núl) odpovedá elementárnej konjunkcii

(resp. klauzule). �ím vä£²ia matica, tým menej literálov treba na jej vyjadrenie.

Príklad 9.8 Karnaughova mapapq/rs 00 01 11 1000 1 0 0 101 0 0 0 011 0 0 0 010 0 0 0 0

obsahuje bázickú maticu jedni£iek s rozmermi obdlºníka 1× 2.Príklad 9.9 Karnaughova mapa

pq/rs 00 01 11 1000 1 0 0 101 0 0 0 011 0 0 0 010 1 0 0 1

obsahuje bázickú maticu jedni£iek s rozmermi obdlºníka 2× 2.Príklad 9.10 Karnaughova mapa

pq/rs 00 01 11 1000 1 1 1 001 0 0 0 011 0 0 0 010 0 0 0 0

nie je bázická matica. Rozmer obd¨ºníka jedni£iek je 1× 3.Príklad 9.11 Nájdime minimálne normálne realizácie boolovskej formuly ur£enejnasledujúcou tabu©kou.

p 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1q 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1r 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1s 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1f 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0

Najprv identi�kujeme minimálny po£et £o najvä£²ích bázických matíc jedni£iekpokrývajúcich v²etky jedni£ky v tele Karnaughovej mapy na obrázku.


pq/rs 00 01 11 1000 0 0 1 101 1 0 1 111 0 0 0 010 1 1 0 0

Potom dostávame nasledujúce bázické matice s vyzna£enými obd¨ºníkmi jednotiek:

K1=pq/rs 00 01 11 1000 0 0 1 101 0 0 1 111 0 0 0 010 0 0 0 0

ktorá odpovedá klauzule ¬p ∧ q ∧ ¬s,

K2=pq/rs 00 01 11 1000 0 0 0 001 1 0 0 111 0 0 0 010 0 0 0 0

ktorá odpovedá klauzule ¬p ∧ ¬r,

K3=pq/rs 00 01 11 1000 0 0 0 001 0 0 0 011 0 0 0 010 1 1 0 0

ktorá odpovedá klauzule p ∧ ¬q ∧ ¬r.Potom minimálny disjunktívny normálny tvar formuly je nasledujúci:

(¬p ∧ q ∧ ¬s) ∨ (¬p ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r).

9.8 Relácia vyplývaniaDe�nícia 9.14 Formula A vyplýva z kone£nej mnoºiny formúl

Γ = {G1, . . . , Gn}

práve vtedy, ak v(A) = 1 pre kaºdú interpretáciu v, pre ktorú v(Gi) = 1, Gi ∈ Γ.

9.8. RELÁCIA VYPLÝVANIA 107Z uvedenej de�nície je evidentné, ºe A vyplýva z Γ práve vtedy, ke¤ pre jej prav-divostnú tabu©ku (funkciu) platí

fA(c1, c2, . . . , cn) = 1,

a pre kaºdu formulu GfG(c1, c2, . . . , cn) = 1.

Ak A vyplýva z Γ, tak zapí²emeΓ |= A.

Vzh©adom na to, ºe Γ = {G1, . . . , Gn}, budeme písa´ ajG1, . . . , Gn |= A.

Príklad 9.12 Zistite, £i platí:p ⇒ q, (p ∨ r) |= (q ∨ r).

Zostrojme pravdivostnú tabu©ku:p q r p ⇒ q p ∨ r q ∨ r0 0 0 1 0 00 0 1 1 1 10 1 0 1 0 10 1 1 1 1 11 0 0 0 1 01 0 1 0 1 11 1 0 1 1 11 1 1 1 1 1

V tomto prípadeΓ = {p ⇒ q, p ∨ r}.

Vidíme, ºe pravdivostná hodnota obidvoch formúl z Γ je 1 v riadkoch 2, 4, 7 a 8.Ke¤ºe v týchto riadkoch je rovná 1 aj pravdivostná hodnota formuly

A = q ∨ r,

platí, ºeΓ |= A

alebop ⇒ q, p ∨ r |= q ∨ r.

Veta 9.6 Formula B vyplýva z A1, A2, . . . , An práve vtedy, ak B vyplýva z A1 ∧A2 ∧ · · · ∧ An.


Dôkaz. Sta£í uvaºi´, ºev(A1 ∧ A2 ∧ · · · ∧ An) = 1

práve vtedy, ke¤v(A1) = v(A2) = · · · = v(An) = 1.

�Nasledujúce tvrdenia uvádzame bez dôkazov:

1. A1, A2, . . . , An |= B práve vtedy, ak A1, A2, . . . , An−1 |= An ⇒ B.2. A1, A2, . . . , An |= B práve vtedy, ak |= A1 ∧ A2 ∧ · · · ∧ An ⇒ B.3. Pravidlo modus ponens: A, A ⇒ B |= B.

9.9 Výrokový kalkulPojem vyplývania je sémantický: Γ |= A práve vtedy, ak z pravdivosti formúl z Γvyplýva pravdivos´ formuly A.Teraz zavedieme pojem dokázate©nosti z Γ , ktorý je syntaktickou analógiou pojmuvyplývania.De�nícia 9.15 Hovoríme, ºe formula A vyplýva z formúl B a C pod©a pravidlamodus ponens (MP) práve vtedy, ak

C = B ⇒ A.

Poznamka. Akonáhle tri formuly majú tvarB, B ⇒ A, A,

tak prehlásime o formule A, ºe vyplýva z prvých dvoch pod©a pravidla modusponens (MP).Pravidlo modus ponens (MP) nazývame deduk£ným pravidlom výrokovej logiky.De�nícia 9.16 Axiómami výrokovej logiky nazývame nasledujúce formuly:

1. A ⇒ (B ⇒ A),

2. (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)),

3. (A ⇔ B) ⇒ (B ⇒ A),

4. (A ⇔ B) ⇒ (A ⇒ B),

9.9. VÝROKOVÝ KALKUL 1095. (A ⇒ B) ⇒ ((B ⇒ A) ⇒ (A ⇔ B)),

6. A ∨B ⇒ B ∨ A,

7. A ∧B ⇒ B ∧ A,

8. A ⇒ A ∨B

9. A ∧B ⇒ A

10. A ⇒ (B ⇒ A ∧B),

11. ((A ⇒ C) ∧ (B ⇒ C)) ⇒ (A ∨B ⇒ C),

12. (A ⇒ B ∧ ¬B) ⇒ ¬A,

13. A ∧ ¬A ⇒ B,

14. A ∨ ¬A.

Dá sa overi´, ºe kaºdá z formúl 1 aº 14 je tautológia.De�nícia 9.17 Dôkaz z mnoºiny formúl Γ je postupnos´ formúl

A1, A2, . . . , An

taká, ºe kazdý jej £len Ai sp¨na práve jednu z podmienok:

1. Ai je axióma výrokovej logiky.

2. Ai ∈ Γ.

3. Existuje j, k < i také, ºe Ai vyplýva z Aj a Ak pod©a pravida modus ponens.

Poznámka. Pojem de�novaný v poslednej de�nícii sa niekedy nazýva aj �formálnydôkaz�.De�nícia 9.18 Formula A je dokázate©ná z Γ práve vtedy, ak existuje dôkaz z Γtaký, ºe

A1, A2, . . . , An = A.

Ak A je dokázate©ná z Γ budeme zapisova´ ` A a formuly z Γ nazývame predpok-lady.Výrokový kalkul je tvorený formulami výrokovej logiky, axiómami 1 aº 14 a pravid-lom modus ponens spolu s popísanou procedúrou dôkazu.Veta 9.7 Formula A je dokázate©ná práve vtedy, ak je tautológia.

Poslednú vetu môºeme ekvivalentne zapísa´ nasledujúco.Veta 9.8 ` A práve vtedy, ak |= A.


9.10 Úlohy9.1. Overte, £i

((p) ∨ (q)) ⇒ ¬r.

je výrok.9.1. Vy²etrite pravdivostnú hodnotu výroku

A = (p ⇒ q) ⇔ (q ∨ ¬p).

9.1. Vy²etrite pravdivostnú hodnotu výrokuB = (p ∨ q) ⇔ ¬(¬p ∧ ¬q).

9.1. Presved£te sa, ºe nasledujúce formuly sú tautológie:(A ∧B) ⇔ ¬(¬A ∨ ¬B),

¬(A ∧B) ⇔ (¬A ∨ ¬B),

(A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)).

9.1. Overte, ºe platí:p ∨ q, p ⇒ q |= q,

p ∨ q ∨ r, q ⇒ r |= p ∨ r,

p ⇒ q, p ⇒ r |= p ⇒ (q ∨ r).

Kapitola 10

Predikátová logika

10.1 PredikátOznamovacia veta �x + y je nepárne £íslo� nie je výrok, pretoºe o jej pravdivostimôºeme rozhodnu´ aº vtedy, ke¤ za x a y dosadíme konkrétne £ísla. Ozna£me

G(x, y) = x + y

pre v²etky (x, y) ∈ R×R. Zrejmé, ºe G je funkciou dvoch premenných. HodnotaG(2, 5) je rovná 7 a veta: �7 je nepárne £íslo� je pravdivý výrok; hodnota G(2, 2)sa rovná 4 a veta: �4 je nepárne £íslo� je nepravdivý výrok.Funkciu G(x, y) nazveme výrokovou funkciou dvoch premennych x a y. Namiestoterminu �výroková funkcia� budeme pouºíva´ aj termín �predikát�.De�nícia 10.1 Nech je daná M ©ubovolná mnoºina a M1, . . . ,Mn je systém jejpodmnoºiny. Funkciu de�novanú na karteziánskom sú£ine M1 ×M2 × · · · ×Mn,ktorej oborom hodnôt sú výroky, nazývame n-miestny predikát.Výrok môzeme povazova´ za 0-miestny predikát. Predikáty budeme ozna£ova´ve©kými písmenami: P, Q, . . . , alebo s indexmi: P1, P2, . . . , Q1, Q2, . . . . Ak budemeuvaºova´ n-miestny predikát P , vtedy pí²eme P n, alebo P (x1, x2, . . . , xn).De�nícia 10.2 Obor pravdivosti predikátu P n de�novaného na M1 ×M2 ×· · · × Mn je mnoºina v²etkých usporiadaných n-tíc (a1, a2, . . . , an) ∈ M1 × M2 ×· · · ×Mn, pre ktoré P (a1, a2, . . . , an) je pravdivý výrok.

Príklad 10.1 Nech R je mnoºina v²etkých reálnych £ísel. Na karteziánskomsú£ine R nech je de�novaný predikát Q(x, y, z) vzáhom

x2 + y2 + z2 = 14.

Výroky Q(1, 2, 3), Q(3, 1, 2) sú pravdivé výroky a Q(0, 2,−1), Q(−1, 2, 7) sú neprav-divé výroky.

111

112 KAPITOLA 10. PREDIKÁTOVÁ LOGIKA

Preto body (1, 2, 3), (3, 1, 2) patria do oboru pravdivosti Q(x, y, z) a body (0, 2,−1),(−1, 2, 7) do neho nepatria.V²eobecne (a, b, c) ∈ R3 patrí do oboru pravdivosti Q(x, y, z) práve vtedy, ak

a2 + b2 + c2 = 14

a z geometrického h©adiska bod (a, b, c) leºí na gu©ovej plochea2 + b2 + c2 = 14.

U predikátov niekedy nebudeme uvádza´ de�ni£ný obor. V tomto prípade predpok-ladáme, ºe jeho �obor de�nície� je mnoºina v²etkých objektov, ktoré ke¤ dosadímeza premenné, tak dostaneme výrok.

Nech P je n-miestny predikát de�novaný na karteziánskom sú£íne X1 ×X2 ×· · · × Xn = J a Q je m-miestny predikát de�novaný na Y1 × Y2 × · · · × Yn = K.Potom pre (a1, a2, . . . , an) ∈ J a (b1, b2, . . . , bm) ∈ K sú výrokmi:

¬P (a1, a2, . . . , an),

P (a1, a2, . . . , an) ∨Q(b1, b2, . . . , bm),

P (a1, a2, . . . , an) ∧Q(b1, b2, . . . , bm),

P (a1, a2, . . . , an) ⇒ Q(b1, b2, . . . , bm),

P (a1, a2, . . . , an) ⇔ Q(b1, b2, . . . , bm).

Pomocou P a Q môºeme de�nova´ nové predikáty:¬P, P ∨Q, P ∧Q, P ⇒ Q, P ⇔ Q.

Príklad 10.2 Majme dvojmiestny predikát de�novaný na R2 vzáhomP (x, y) = 9x2 + 4y2 ≤ 36

a Q je jednomiestny predikát0 ≤ x ≤ 1.

Potom obor pravdivosti predikátu ¬P je mnoºina v²etkych bodov roviny R2, ktoréleºia mimo elipsy 9x2+4y2 = 36. Obor pravdivosti predikátu P∧D sú body leºiacev elipse 9x2 + 4y2 = 36, pre ktoré platí 0 ≤ x ≤ 1.Obor pravdivosti predikatu P ∨ Q sú body leºiace v elipse 9x2 + 4y2 = 36 alebopre ktoré platí 0 ≤ x ≤ 1.

10.1. PREDIKÁT 113V ¤alsom zavedieme pojem kvanti�kátorov:

1. Existen£ný (malý) kvanti�kátor ∃ (∃x £ítame: �existuje aspo¬ jedno x�).2. V²eobecný (velký) kvantifkátor ∀ (symbol ∀x £ítame: �pre v²etky x�).Vymedzíme význam pouºítia kvanti�kátorov na predikát.

De�nícia 10.3 Nech 1 ≤ i ≤ n a P (x1, x2, . . . , xn) je predikát. Potom

(∀xi)P (x1, x2, . . . , xn)

je (n − 1)-miestny predikát závislý na premenných x1, x2, . . . , xi−1, xi+1, . . . , xn,ktorého hodnota pre a1, a2, . . . , ai−1, ai+1, . . . , an je pravdivý výrok práve vtedy, ak 1-miestny predikát P (a1, a2, . . . , ai−1, xi, ai+1, . . . , an) je pravdivý pre v²etky xi ∈ Mi.

Príklad 10.3 Majme dvojmiestny predikát S(x, y) tvarux2 ≥ y.

Utvorme(∀x)(x2 ≥ y),

a to je uº jednomiestny predikát závislý na jednej premennej y. Výrok(∀x)(x2 ≥ b),

je pravdivý pre v²etky b ∈ (−∞, 0). Teda obor pravdivosti predikátu(∀x)(x2 ≥ y),

je interval (−∞, 0).De�nícia 10.4 Nech 1 ≤ i ≤ n a P (x1, x2, . . . , xn) je predikát. Potom

(∃xi)P (x1, x2, . . . , xn)

je (n − 1)-miestny predikát závislý na premenných x1, x2, . . . , xi−1, xi+1, . . . , xn,ktorého hodnota pre a1, a2, . . . , ai−1, ai+1, . . . , an je pravdivý výrok práve vtedy, ak1-miestny predikát P (a1, a2, . . . , ai−1, xi, ai+1, . . . , an) je pravdivý pre aspo¬ jednuhodnotu premennej xi ∈ Mi.


Táto £as´ je venovaná abstraktnej²iemu prístupu k predikátovej logike.Abecedu predikátovej logiky tvoria:premenné: x1, x2, . . . , xn, y, z, . . .

predikátové symboly: P 11 , P 1

2 , . . . , Q11, Q

12, . . . , P

1, P 2, . . .

funkcionálne symboly: f 11 , f1

2 , . . . , q11, q

12, . . . , f

1, f2, . . .

individuálne kon²tanty: a1, a2, . . . , a, b, . . .

logické spojky: ¬,∨∧ ⇒,⇔,kvanti�kátory: ∃,∀,zátvorky: (, ).Horný index predikátoveho symbolu P k

i a funkcionálneho symbolu fki ozna£uje

k-miestny predikátový symbol, respektíve k-árnu operáciu. V ¤alsom budeme ajo k-miestnom predikáte hovori´ ako o k-árnom predikáte.De�nícia 10.5 Termy sú:

1. Premenné a individuálne kon²tanty.

2. Ak t1, t2, . . . , tn sú termy a fn je n-árny funkcionálny symbol, tak aj

fn(t1, t2, . . . , tn) je term.

3. Kaºdý term môºeme zostroji´ pod©a bodov 1. a 2.

De�nícia 10.6 Formulu de�nujeme:

1. Ak P n je n-árny predikátovy symbol a t1, t2, . . . , tn sú termy, tak

P n(t1, t2, . . . , tn) je formula.

2. Ak F a G sú formuly, tak aj

¬F, F ∨G, F ∧G, F ⇒ G, F ⇔ G sú formuly.

3. Ak F je formula a x je premenná, tak (∀x)F a (∃x)F sú formuly.

4. Kazdá formula vznikne pod©a 1. aº 3. bodu.

10.1. PREDIKÁT 115Formuly vytvorene pod©a bodu 1. nazývame atomické formuly.

Posledné de�nície sú �gramatikou� predikátovej logiky.Jazykom predikátovej logiky (JPL) nazývame abecedu predikátovej logiky

spolu s formulami predikátovej logiky.Niekedy nepotrebujeme kompletný jazyk predikátovej logiky, ale vysta£íme aj

s jeho ur£itými £asámi.Formula v jazyku L je formula predikátovej logiky vytvorená len zo symbolovjazyka L. Pí²eme L = (P ,F ,K), kde P je mnoºina predikátovych symbolov, Fmnoºina funkcionálnych premenných a K mnoºina individuálnych kon²tant.De�nícia 10.7 Interpretácia jazyka L = (P ,F ,K) v mnoºine M je zobrazenieVM , ktoré kaºdému P n ∈ P prira¤uje n-árnu reláciu P n ⊂ Mn, kaºdej funkcionál-nej premennej fn ∈ F prira¤uje n-árnu operáciu f

nna M a kaºdej individuálnej

kon²tante a ∈ K prira¤uje prvok a ∈ M .

Nech t je term jazyka L a c1, c2, . . . , cn ∈ M . De�nujme induktívne "hodnotu"termu t(c1, c2, . . . , cn):

1. Ak t je ai, tak t(c1, c2, . . . , cn) = ai,2. Ak t je xi, tak t(c1, c2, . . . , cn) = ci,3. Ak t je f(t1, t2, . . . , tn), tak

t(c1, c2, . . . , cn) = f(t1(c1, c2, . . . , cn), . . . , tn(c1, c2, . . . , cn)).

Z 1-3 vidíme, ºe hodnota t(c1, c2, . . . , cn) termu t je prvok z mnoºiny M . Ana-logicky hodnota F (c1, c2, . . . , cn) formuly F pre c1, c2, . . . , cn ∈ M je výrok

1. P (t1(c1, c2, . . . , cn), . . . , tn(c1, c2, . . . , cn)), ak F je P (t1, . . . , tn),2. ¬G(c1, c2, . . . , cn), ak F je ¬G,3. G(c1, c2, . . . , cn) ∨H(c1, c2, . . . , cn), ak F je G ∨H,4. G(c1, c2, . . . , cn) ∧H(c1, c2, . . . , cn), ak F je G ∧H,5. G(c1, c2, . . . , cn) ⇒ H(c1, c2, . . . , cn), ak F je G ⇒ H,


6. G(c1, c2, . . . , cn) ⇔ H(c1, c2, . . . , cn), ak F je G ⇔ H,7. (∀x)G(c1, c2, . . . , cn), ak F je (∀x)G(x),8. (∃x)G(c1, c2, . . . , cn), ak F je (∃x)G(x).Formula jazyka L je vºdy pravdivá (tautológia) práve vtedy, ak je pravdivá

v kaºdej interpretácii VM.Premenná x sa v danej formule môºe vyskytnú´ viackrát. Daný výskyt pre-

mennej x je viazaný, ak sa nachádza bezprostredne za kvanti�kátorom alebo jev jeho rozsahu. Inak je výskyt premennej x vo©ný.

Poznámka. Vo výrokovej logike poznáme algoritmus (tabu©kovú metódu), nazáklade ktorého o kaºdej formule vieme rozhodnú´, £i je alebo nie je tautológia.V predikátovej logike takáto metóda neexistuje. Prí£ina je v tom, ºe pre výrokovúlogiku existuje interpretácia v boolovskej algebre B2, kým formula predikátovejlogiky je tautológiou len vtedy, ke¤ je pravdivá v kaºdej interpretácii a v kaºdejmnoºine, teda aj v nekone£nej. Druhy spôsob ako zisti´, £i formula výrokovejlogiky je tautológia, dáva veta o úplnosti výrokovej logiky. Túto druhú moºnos´vyuºijeme aj v predikátovej logike.

10.2 Predikátový kalkúlTak, ako výrokovy kalkúl, aj predikátový kalkúl je tvorený mnoºinou formúl prediká-tovej logiky, ktoré sa nazývajú axiómy predikátovej logiky a deduk£nými pravid-lami, ktoré slúºia na odvodzovanie dokázate©ných formúl.

Ak A(p1, p2, . . . , pn) je formula predikátovej logiky a B1, B2, . . . , Bn sú formulypredikátovej logiky, tak

A(p1/B1, p2/B2, . . . , pn/Bn)

znamená výraz, ktorý dostaneme z A, ak v²ade v A za pi dosadíme formulu Bi,i = 1, 2, . . . , n. Je zrejmé, ºe tento výraz bude formulou predikátovej logiky.De�nícia 10.8 Axiómy predikátovej logiky sú tieto formuly:

1. A(p1/B1, p2/B2, . . . , pn/Bn), kde B1, B2, . . . , Bn sú formuly predikátovejlogiky a A(p1, p2, . . . , pn) je tautológia výrokovej logiky.

2 . (∀x)F (x) ⇒ F (t) , kde t = t(xα1 , xα2 , . . . , xαn) je term a xα1 , xα2 , . . . , xαn

sú vo©né pre x vo formule F .

10.3. ÚLOHY 1173 . F (t) ⇒ (∃x)F (x) , kde t = t(xα1 , xα2 , . . . , xαn) je term a xα1 , xα2 , . . . , xαn

sú vo©né pre x vo formule F .

De�nícia 10.9 Deduk£nými pravidlami predikátovej logiky sú schémy:

1. F,F⇒GG ,

2. F⇒G(x)F⇒(∀x)G(x) , x nie je vo©ná v F .

3. G(x)⇒F(∃x)G(x)⇒F , x nie je vo©ná v F .

Schema 1. je pravidlo modus ponens. Schému 2. nazveme A pravidlom aschému 3. nazveme E pravidlom. O formule, ktorá sa v deduk£nom pravidlenachádza pod £iarou, hovoríme, ºe vyplýva z formuly (formúl) nad £iarou pod©aprí²lusného deduk£ného pravidla.De�nícia 10.10 Dôkaz v predikátovej logike je taká postupnos´ formúl

A1, A2, . . . , An,

ºe pre kaºdé i = 1, 2, . . . , n nastáva práve jedna z moºností:

1. Ai je axióma predikátovej logiky.

2. Existuje j, k < i také, ºe Ai vyplýva z Aj a Ak pod©a pravidla modus ponens.

3. Existuje j < i také, ºe Ai vyplýva z Aj pod©a A alebo E pravidla.

Formula F predikátovej logiky je dokázate©ná práve vtedy, ak existuje dôkazv predikátovej logike, ktorého posledný £len je F .Ak formula F je dokázate©ná, budeme písa´ ` F.

Veta 10.1 (Veta o úplnosti.) Formula predikátovej logiky je dokázate©ná právevtedy, ak je tautológia.

10.3 Úlohy10.1. Nájdite obor pravdivosti predikátu

x2 + y2 = z2.


pre x, y, z ∈ {1, 2, 3, . . . , 20}.10.2. Nájdite obory pravdivosti predikátov:

Q = y ≥ 2x2, x, y ∈ R,

S = x2 + y2 ≤ 1, x, y ∈ R.

10.3. Nájdite obory pravdivosti predikátov Q∧S, Q∨S, kde Q a S sú predikátyz predchádzajúceho príkladu.

Literatúra

[1] M. Bieliková,P. Návrat, Funkcionálne a logické programovanie, STU, Bratisla-va 1997.

[2] G. Birkhof, S. MacLane: Preh©ad modernej algebry, ALFA, Bratislava 1979.[3] G. Birkhof, T. O. Bartee: Aplikovaná algebra, ALFA, Bratislava 1981.[4] J. Bosák: Grafy a ich aplikácie, ALFA, Bratislava 1980.[5] M. Bu£ko: Grafy, ALFA, Bratislava 1985.[6] M. Bu£ko, M. Kle²£: Diskrétna matematika, Academic Press elfa, s.r.o.,

Ko²ice 1999.[7] L. Bukovský, Úvod do matematickej logiky, ÚMV PF UPJ², Ko²ice 2006.[8] M. Demlová, B. Pond¥lí£ek: Matematická logika, FEL £VUT, Praha 1997.[9] J. Galanová, J. Bosák, J. Gatia©: Algebry a grafy, ES SV²T, Bratislava 1987.[10] F. Harary: Graph Theory, Addison�Wesley, Reading, MA, 1969.[11] J. Johnsonbaugh: Discrete Mathematics, Macmillan Publishing Company,

New York 1990.[12] T. Katri¬ák a kol.: Algebra a teoretická aritmetika (1), ALFA, Bratislava

1985.[13] O. Kolá°, O. �tepánková, M. Chytil: Logika, algebry a grafy, SNTL, Praha

1989.[14] L. Ku£era: Kombinatorické algoritmy, SNTL, Praha 1983.[15] V. Kvasni£ka, Pospíchal J., Matematická logika, Slovenská technická univerzi-

ta, Bratislava 2006.[16] A. Legé¬: Grupy, okruhy a zväzy, ALFA, Bratislava 1980.

119

[17] Z. Manna, Matematická teórie program·, SNTL, Praha 1981.[18] Z. Manna, Waldinger R., The Logical Basis for Computer Programming, Vol-

ume 2: Deductive Systems, Addison-Wesley 1990.[19] E. Mendelson , Introduction to Mathematical Logic, Princeton Univ. Press

1964.[20] J. Matou²ek, J. Ne²et°il: Kapitoly z diskrétní matematiky, Nakladatelství

Karolinum, Praha 2000.[21] J. Ne£as: Grafy a ich pouºití, SNTL, Praha 1978.[22] J. Ne²et°il: Teorie graf·, SNTL, Praha 1979.[23] J. Plesník: Grafové algoritmy, VEDA, Bratislava 1983.[24] F. P. Preparata, R. T. Yeh: Úvod do diskrétnych matematických ²truktúr,

ALFA, Bratislava 1982.[25] K. H. Rosen: Discrete Mathematics and Its Applications, AT&T Information

Systems, New York 1988.[26] J. Sedlá£ek: Úvod do teorie graf·, Academie, Praha 1981.[27] J.R. Shoen�eld , Mathematical Logic, Adison-Wesley 1967.[28] R. Smullyan , Nav¥ky nerozhodnuto, Academia, Praha 2003.[29] A. Sochor , Klasická matematická logika, Karolinum, Praha 2001.[30] T. �alát a kol: Algebra a teoretická aritmetika (2), ALFA, Bratislava 1986.[31] V. ²vejdar, Logika, Academia, Praha 2002.

LITERATÚRA 121

Titul: Grafové algoritmy a formálna logikaU£ebnicaAutori: Marián Kle²£, Ján PlavkaPublikované: FEI TUKE, Ko²ice 2008, Ko²iceISBN 978-80-553-0136-5

Date post:	15-May-2019
Category:	Documents
Upload:	dinhcong
View:	216 times
Download:	0 times

Katedra matematiky Fakulta elektrotechniky a...

Documents