Diskrétní matematika DISKRÉTNÍ MATEMATIKA. RNDr. Ivan Havlíček, CSc., ::

Diskrétní matematika

DISKRÉTNÍ MATEMATIKA

pro obor aplikovaná informatika

1. RNDr. Ivan Havlíček, CSc., [email protected] ::


diskrétní 1. ohleduplný, taktní 2. zachovávající tajemství 3. nespojitý, přetržitý

Akademický slovník cizích slov (1998):


Diskrétní matematika Literatura Berka, M., Teorie grafů a úlohy na grafech, (http://home.eunet.cz/berka/o/grafy.htm) . Demel, J., Grafy a jejich aplikace, Academia, Praha 2002. Duží, M., Matematická logika, FEI VŠB, TU Ostrava, skripta. Fábry, J., Matematické modelování, Nakladatelství Oeconomica, VŠE FIS, Praha 2007. Hliněný, P., Diskrétní matematika, FEI VŠB, TU Ostrava 2005, (http://cs.vsb.cz/hlineny/vyuka/DIMslides/DIM-text05.pdf). Konopík, M., Abstraktní datový typ graf – Úvod do teorie grafů, KIV, ZČU. (http://www.kiv.zcu.cz/~konopik/sem/cech/index.html). Kovár, M., Diskrétní matematika, FIT VUT, Brno 2002. (http://www.umat.feec.vutbr.cz/~kovar/webs/vyuka/fit/2006/ida/soubory/IDM.pdf). Kovár, M., Cvičení z diskrétní matematiky, FIT VUT, Brno 2003, (http://www.umat.feec.vutbr.cz/~kovar/webs/vyuka/fit/2006/ida/soubory/IDMCV.pdf). Kovář, P., Diskrétní matematika, FAM VŠB, TU Ostrava (http://homel.vsb.cz/~kov16/predmety_dm.php). Křemen, J.,Modely a systémy,Academia a ČMT, Praha 2007. Matoušek, J. a Nešetřil,J., Kapitoly z diskrétní matematiky, Karolinum, Praha 2002. Muhamma, R., Algorithmic Graph Theory, (http://www.personal.kent.edu/~rmuhamma/GraphTheory/graphTheory.htm). Raclavský, J., Logika, MU Brno, (http://www.phil.muni.cz/fil/logika/). Roberts, F.S., Discrete Mathematical Models with Applications to Social, Biological and Environmentals Problems, Prentice-Hall,Inc., New Jersey 1976. Ryjáček, Z., Teorie grafů a diskrétní optimalizace, KMA ZCU 2005, (http://www.kma.zcu.cz/TGD1). 3. RNDr. Ivan Havlíček, CSc., [email protected] ::


1 Matematická logika 1.1 Výroky a úsudky 1.2 Výroková logika 1.3 Predikátová logika


Diskrétní matematika 1. Matematická logika 1.1 Úsudky a výroky 1/4

Definice. Výrokem je jakékoli tvrzení, o kterém lze říci, že je pravdivé nebo, že je nepravdivé. Úsudkem nazýváme duševní postup, při němž usuzujeme na pravdivost výroku A na základě pravdivosti výroků B1, B2,…, Bn. Výroky B1, B2,…, Bn nazýváme předpoklady neboli premisy a výrok A nazýváme závěr. Píšeme B1, B2,…, Bn→ A. Definice. Úsudek B1, B2,…, Bn → A je platný, jestliže závěr A logicky vyplývá z předpokladů B1, B2,…, Bn. Platný úsudek značíme B1, B2,…, Bn |= A. 5. RNDr. Ivan Havlíček, CSc., [email protected] ::


Několik platných úsudků. Všichni psi štěkají. Pudl je pes. → Pudl štěká. V seznamu novodobých římských císařů není žádná žena. Marie Terezie byla žena. → Marie Terezie nebyla římská císařovna. Je doma nebo odešel do kavárny. Je-li doma, pak nás očekává. → Jestliže nás neočekává, pak odešel do kavárny. Je-li tento kurz dobrý, pak je užitečný. Buď je přednášející shovívavý, nebo je tento kurz neužitečný. Ale přednášející není shovívavý. → Tento kurz je špatný. 6. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Jestliže je výrok A pravdivý za všech okolností, říkáme, že je platný, nebo že je tautologií a značíme |= A. Jestliže předpoklady v množině {B1 ,B2 ,..., Bn} nemohou být současně všechny splněny, říkáme, že množina {B1 ,B2 ,..., Bn} je kontradiktorická (sporná, nesplnitelná). Kontradikci značíme {B1 ,B2 ,..., Bn} |=.

Z kontradiktorické množiny premis plyne jakýkoli závěr. 7. RNDr. Ivan Havlíček, CSc., [email protected] ::


Vlastnosti deduktivních úsudků. Logicky správný úsudek může mít nepravdivý závěr (např.: Všechny kobry jsou jedovaté. Tato hůl je kobra. → Tato hůl je jedovatá.) V takovém případě však musí být některý z předpokladů nepravdivý. Jestliže platí B1, B2,…, Bn |= A, platí i B1, B2,…, Bn, Bn+1 |= A pro libovolný další předpoklad Bn+1. Tato vlastnost závěru se nazývá monotónnost. Jestliže platí B1, B2,…, Bn |= A a C1, C2,…, Cn |= A′ , pak platí B1, B2,…, Bn, C1, C2,…,Cn |= A a zároveň B1, B2,…, Bn, C1, C2,…, Cn |= A′ . Tato vlastnost se nazývá tranzitivita. Jestliže je A rovno jedné z premis B1, B2,…, Bn, pak platí B1, B2,…, Bn |= A. Tato vlastnost se nazývá reflexivita. 8. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 1. Matematická logika 1.2 Výroková logika 1/7

Definice jazyka výrokové logiky Abeceda jazyka výrokové logiky je množina následujících symbolů: Výrokové symboly p, q, r,…A, B,…. Symboly logických spojek (funktorů) ￢, , ,⇒, ⇔. Pomocné symboly (závorky) ( ),[ ],{ },.... Symboly ￢, , , ⇒, ⇔ nazýváme po řadě funktory negace, konjunkce, disjunkce, implikace, ekvivalence. 9. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice jazyka výrokové logiky - pokračování Gramatika jazyka výrokové logiky rekurzivně definuje formule: 1. Výrokové symboly jsou formule. 2. Jsou-li A, B formule, pak jsou formulemi i výrazy (￢A), (A (A B), (A ⇒B), (A ⇔ B).

B),

3. Jiných formulí výrokové logiky než těch, které vzniknou aplikací podle bodů 1. a 2., není. Jazyk výrokové logiky je množina všech formulí výrokové logiky. 10. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice logických funktorů Negace výroku A se značí ￢A a znamená „není pravda, že“. Konjunkce výroků A a B se značí A B a znamená, že „platí zároveň A a zároveň B“. Disjunkce (alternativa) výroků A a B se značí A B a znamená, že „platí buď A nebo B“ (nebo obojí). Implikace: Vyplývá-li z výroku A výrok B, říkáme, že „z A plyne B“ nebo že „A implikuje B“ nebo „jestliže A, pak B“ nebo „když A, tak B“, … a píšeme A ⇒ B. Ekvivalence nastane, platí-li zároveň A ⇒ B a B ⇒ A a říkáme, že výroky A a B jsou ekvivalentní, a značíme A ⇔ B . Ekvivalenci čteme také: „B platí právě, když platí A“ nebo „B platí tehdy a jen tehdy, platí-li A“. 11. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice sémantiky výrokové logiky Interpretace – pravdivostní ohodnocení (valuace) J přiřazuje každé formuli pravdivostní hodnotu z množiny {1,0}, která kóduje množinu {pravda, nepravda}. Tautologie je formule, která nabývá hodnoty pravda při každé interpretaci. Kontradikce je formule, která nabývá hodnoty nepravda při každé interpretaci. Pravdivostní tabulka A B A ∧ B A ∨ B A⇒B A⇔B 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1

12.

RNDr. Ivan Havlíček, CSc., [email protected] ::


Zjistěme, zda množina formulí M ={p ⇒ r, q ⇒ r, p ∨ q} je splnitelná, tj zda platí p ⇒ r, q ⇒r, p ∨ q |= r

p 1 1 1 1 0 0 0 0

q 1 1 0 0 1 1 0 0

r 1 0 1 0 1 0 1 0

p⇒r 1 0 1 0 1 1 1 1

q⇒r 1 0 1 1 1 0 1 1

p∨q 1 1 1 1 1 1 0 0 13. RNDr. Ivan Havlíček, CSc., [email protected] ::


Seznam některých tautologií A) Tautologie s jediným výrokovým symbolem: ￢( p ∧ ￢p) zákon sporu ( p ∨ ￢p) zákon vyloučeného třetího p⇒p zákon totožnosti p ⇔￢￢p zákon dvojí negace p ⇔ ( p ∨ p) zákon idempotence p ⇔ ( p ∧ p) zákon idempotence B) ( p ∧ ￢p)⇒ p)⇒ q zákon Dunse Scota p ⇒ (q ⇒ p) zákon simplifikace ( p ⇒ q)⇔(￢q ⇔ ⇒ ￢p) zákon kontrapozice C) De Morganovy zákony: ￢( p ∨ q) ⇔ (￢p ∧ ￢q) ￢( p ∧ q) ⇔ (￢p ∨ ￢q)

14.



Převod z přirozeného jazyka do jazyka výrokové logiky Je doma (p) nebo odešel do kavárny (￢p). Je-li doma, pak nás očekává (q). → Jestliže nás neočekává, pak odešel do kavárny. ( p ⇒ q) ⇔ (￢q ⇒￢p) Převod z přirozeného do symbolického jazyka nemusí být vždy zcela jednoznačný. „Jestliže má člověk vysoký tlak (p) a špatně se mu dýchá (q) nebo má zvýšenou teplotu (r), pak je nemocen (s).“ Můžeme převádět jako 1. možnost: [(p ∧ q)∨ r]⇒ s 2. možnost: [p ∧(q ∨ r)]⇒ s. Obě formule jsou různé, obě vyhovují zadání, ale ze zadání nepoznáme, jak bylo tvrzení myšleno. 15. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 1. Matematická logika 1.3 Predikátová logika 1/6

Definice jazyka predikátové logiky I) Abeceda predikátové logiky (následující symboly): a. Logické symboly i. individuové proměnné x,y,z, individuové konstanty a,b,c,… . ii. symboly pro spojky ￢,∧,∨,⇒,⇔, ∧∨⇒⇔ iii. symboly pro kvantifikátory ∀, , iv. případně binární predikátový symbol = (predikátová logika s rovností). b. Speciální symboly i. predikátové symboly p,q,r,…, ii. funkční symboly f,g,h,…. c. Pomocné symboly – závorky.

16.



Definice jazyka predikátové logiky - pokračování II) Gramatika, která udává, jak tvořit a. termy: jsou proměnné nebo konstanty b. atomické formule: i. je-li p n-ární predikátový symbol a jsou-li t1,…,tn termy, pak výraz p(t1,…,tn) je atomická formule, ii. jsou-li t1 a t2 termy, pak výraz (t1 = t2) je atomická formule. c. formule: i. každá atomická formule je formule, ii. je-li výraz A formule, pak ￢A je formule, iii. jsou-li A a B formule, pak výrazy (A ∧ B),(A ∨ B),(A ⇒ B) , (A ⇔ B) jsou formule, iv. je-li x proměnná a A formule, pak výrazy ∀xA a xA jsou formule, v. jen výrazy dle i. – iv. jsou formule.

17.



Kvantifikátory. Kvantifikátor ∀ nazýváme obecným (velkým) kvantifikátorem a vyjadřuje „každý; žádný; všechna; kterýkoli; libovolný;…“ Kvantifikátor je existenčním (malým) kvantifikátorem a vyjadřuje „existuje; některé; lze nalézt; alespoň jeden;…“. Někdy se používá ! pro vyjádření „existuje právě jeden“



Univerzum. Univerzum je množina individuí, která spadají do našeho uvažování. Máme- li na mysli např. tři dívky, Annu, Báru a Gabrielu, pak tyto tři dívky tvoří naše univerzum U. Dívky po řadě označíme α ,β ,γ , tedy U ={α ,β ,γ}. Predikát. Predikátový symbol je výraz označující predikát, tedy vlastnost nebo vztah, který lze vypovědět (predikovat) o individuu. Vlastnost „být dívka“ je predikovatelná o třech individuích námi uvažovaného univerza a píšeme P(x).



Příklady převodu z přirozeného jazyka do symbolického jazyka predikátové logiky 1) Nikdo, kdo není zapracován (P), nepracuje samostatně (S). ∀x[￢P(x) ⇒￢S(x)] 2) Ne každý talentovaný (T) spisovatel (Sp) je slavný (Sl). ￢∀x{[T(x) ∀x{[T(x) ∧ Sp(x)]⇒ Sl(x)} 3) Pouze zaměstnanci (Z) používají výtah (V). ∀ ∀x[V (x)⇒Z(x)] ⇒ 20. RNDr. Ivan Havlíček, CSc., [email protected] ::


Příklady převodu z přirozeného jazyka do symbolického jazyka predikátové logiky - pokračování 4) Ne každý člověk (C), který hodně mluví (M), nemá co říci (R). ￢∀x{[C(x) ∧ M(x)]⇒ ￢R(x)} 5) Někdo je spokojen (Sn) a někdo není spokojen. xSn(x) ∧ y￢Sn( y) 6) Někteří chytří lidé (Ch) jsou líní (L). x[Ch(x) ∧ L(x)] 7) Všichni zaměstnanci (Z) používají výtah (V). ∀x[Z(x)⇒V(x)] 21. RNDr. Ivan Havlíček, CSc., [email protected] ::


2 Dokazování v diskrétní matematice 2.1 Stavba matematiky 2.2 Matematické důkazy


Diskrétní matematika 2 Dokazování v diskrétní matematice 2.1 Stavba matematiky

Ucelenou matematickou teorii tvoří: - axiomy, - definice, - věty neboli tvrzení, - lemmata, - matematické důkazy.



Axiomy množiny přirozených čísel Giuseppe Peano 1891

P1. Existuje přirozené číslo, které není následníkem žádného přirozeného čísla. Nazveme ho 1. P2. Každé přirozené číslo má právě jednoho následníka. P3. Každé přirozené číslo je následníkem nejvýše jednoho přirozeného čísla. P4. Každá množina, která obsahuje přirozené číslo 1 a s každým přirozeným číslem obsahuje i jeho následníka, je množinou přirozených čísel. 24. RNDr. Ivan Havlíček, CSc., [email protected] ::


Eukleidovy axiomy Konec 4. stol. před n.l.

E1. Od každého bodu ke každému lze vést přímou spojnici. E2. Ohraničenou spojnici lze libovolně prodloužit. E3. Z každého středu a poloměru lze narýsovat kružnici. E4. Všechny pravé úhly jsou navzájem shodné. E5. Daným bodem lze s danou přímkou vést právě jednu rovnoběžku. 25. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 2 Dokazování v diskrétní matematice 2.2 Matematické důkazy 1/5

Důkaz je posloupnost ověřitelných elementárních kroků, které pomocí již dokázaných faktů (popř. axiomů) podle logických pravidel dospějí k požadovanému tvrzení (větě). Rozlišujeme: a) důkaz převedením na známé (již dokázané) tvrzení, b) nepřímý důkaz, c) důkaz sporem, d) důkaz matematickou (tzv. úplnou) indukcí, e) důkaz konstrukcí nebo počítáním. 26. RNDr. Ivan Havlíček, CSc., [email protected] ::


Důkaz převedením na známé tvrzení provádíme postupnými implikacemi z předpokladu A (jednoho nebo více) A ⇒ B , B ⇒ C ,… ,Y ⇒ Z až dojdeme k žádanému tvrzení Z. Tvrzení: Úhlopříčky v kosočtverci se navzájem půlí a jsou k sobě kolmé. Důkaz: Z definice kosočtverce plyne, že strany jsou stejně dlouhé a po dvou rovnoběžné. Úhlopříčky vytvoří se stranami čtyři trojúhelníky. Dva protilehlé trojúhelníky vytvoří mezi úhlopříčkami a stranami kosočtverce dvě dvojice stejných střídavých úhlů. Podle věty úsú jsou tyto trojúhelníky shodné. Pak podle věty sss jsou s nimi shodné i zbývající trojúhelníky. Z toho plyne, že se úhlopříčky půlí. V průsečíku úhlopříček se stýkají čtyři shodné úhly, musí tedy být pravé. □

27.



Důkaz sporem. Místo implikace A⇒B dokazujeme (A ∧ ￢B)⇒C B)⇒C , kde C je jasně nepravdivý výrok nebo je ve sporu s předpokladem. Tím jsme došli ke sporu a tudíž A⇒B ⇒ . Tvrzení: Mezi přirozenými čísly menšími než 8 je nejvýš 5 prvočísel. Důkaz: Předpokládejme pro spor, že je jich 6. Pak mezi nimi musí být nejméně dvě čísla sudá, jedno rovné dvěma a druhé tedy různé od dvou, které tudíž není prvočíslo, a to je spor s předpokladem o šesti prvočíslech. Tím je tvrzení dokázáno. □ 28. RNDr. Ivan Havlíček, CSc., [email protected] ::


Matematická indukce. Mějme tvrzení P(n) s přirozeným (nebo celočíselným) parametrem n. Nechť platí: 1) Tvrzení P(n) je pravdivé pro nejmenší přípustné n. Toto tvrzení nazýváme základ indukce. 2) Pro libovolné přirozené (či celé) n0 plyne z platnosti P(n0) také platnost tvrzení P(n0 + 1). Pak P(n) platí pro všechna přirozená (či celá) n.

29.



Tvrzení: Vztah n(n + 1) 1 + 2 + ... + n = ∑i = 2 i =1 n

platí pro libovolné n. Důkaz: Nejprve ukážeme dosazením, že vztah platí pro nejmenší uvažované n, v našem případě n = 1. V druhém kroku vyjdeme z platnosti vztahu pro nějaké n0 a dokážeme, že platí i pro n = n0 + 1. Tedy

n0 (n0 + 1) (n0 + 1)(n0 + 2) + (n0 + 1) = 2 2 což je původní výraz pro n0 + 1 a tvrzení je dokázáno.

□

30.



3 Množiny 3.1 Základní množinové operace 3.2 Čísla a číselné množiny 3.3 Princip inkluze a exkluze 3.4 Kartézský součin


Diskrétní matematika 3. Množiny 3.1 Základní množinové operace 1/7

Definice Označíme X = {x} množinu X obsahující prvky x; také píšeme x∈ X . Množinu, která nemá žádný prvek, nazýváme prázdnou množinou a značíme ji Ø. Podmnožina X množiny Y je její částí: X ⊆ Y ⇔ (∀x∈X ⇒ x∈Y) Rovnost množin X a Y nastane, mají-li stejné prvky: X = Y ⇔ X ⊆ Y ∧Y ⊆ X Sjednocení množin je množina Z obsahující prvky, které jsou buď X X X nebo prvky Y (nebo obou): prvky X ∪Y ={∀(x∈X ∨ y∈Y)}



Definice - pokračování Průnik množin X a Y je množina Z obsahující prvky, které jsou prvky X a zároveň prvky Y: X ∩Y ={ a (a X

a Y)}

Množiny, jejichž průnik je prázdná množina, nazýváme disjunktní. Rozdíl množin X a Y je množina Z obsahující prvky, které jsou prvky X a nejsou prvky Y : X \Y ={∀a ∈ X ∧ a Y} Jestliže je Y ⊆ X , pak Y = X \Y nazýváme doplňkem množiny Y v množině X.

33.



Vennův diagram: a) b) c) d)

A∪ ∪B A∩ ∩B A\B doplněk B v A



Vlastnosti množinových operací. Nechť A, B, C jsou množiny. Pak platí: 1. A∪ B = B ∪ A

komutativní zákony

2. A∩B = B ∩A 3. (A∪ B)∪C = A∪(B ∪C)

asociativní zákony

4. (A∩ B)∩C = A∩(B ∩C) 5. (A∪ B)∩C =(A∩C)∪(B ∩C) 6. (A∩ B)∪C =(A∪C)∩(B ∪C)

distributivní zákony 35. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pro konečnou množinu X budeme symbolem |X| označovat její mohutnost neboli počet prvků. Je-li mohutnost |X| sudá, říkáme, že množina X je sudé velikosti, je-li lichá, říkáme, že X je liché velikosti.



Počet podmnožin - 1 Tvrzení: Nechť množina X má n prvků. Pak X má 2n podmnožin . Důkaz: 1. Pro n = 0 tvrzení platí, neboť prázdná množina má jedinou, opět prázdnou, podmnožinu. 2. Nechť platí dokazované tvrzení pro n ≥ 0 . Vezmeme libovolný prvek a ∈ X , kde |X| = n +1. Utvoříme množinu X ′ = X \{a}, takže |X ′| = n , pro níž podle předpokladu tvrzení platí. Uvažujme libovolnou, pevně zvolenou podmnožinu P ⊆ X a máme dvě možnosti: buď je a P nebo je a∈ P . Není-li a∈ P , je P podmnožinou X ′ a takových P je podle indukčního předpokladu 2n . Je-li a∈ P , je P′ = P \{a} podmnožinou Xá takových P′ je opět 2n . Dohromady je tedy 2n+1 možností volby P ⊆ X. □ 37. RNDr. Ivan Havlíček, CSc., [email protected] ::


Počet podmnožin - 2 Tvrzení: Každá n-prvková ( n ≥ 1) množina má právě 2n-1 podmnožin sudé velikosti a 2n-1 podmnožin liché velikosti. Důkaz: Opět pomocí matematické indukce. 1. Pro n = 1 tvrzení platí, neboť jednoprvková množina má jednu podmnožinu liché velikosti (prázdnou) a jednu sudé velikosti (prázdnou a s jedním prvkem). 2. Nechť množina X má libovolně zvolený počet prvků n a platí pro ni dokazované tvrzení. předchozí tvrzení. …


Diskrétní matematika 3. Množiny 3.2 Čísla a číselné množiny 1/5

Množina přirozených čísel je {1,2,3,4,5,...} a značíme ji ℕ. Interval přirozených čísel a < b značíme [a,b] = {a,a +1,...,b −1,b}. Celá část čísla x se značí takto: ⌊x⌋. Znamená to, že např. ⌊3,14159 = 3. Množina celých čísel se značí ℤ = {…,-3,-2,-1,0,1,2,3,…} V diskrétní matematice se pracuje s přirozenými čísly rozšířenými o nulu, tj. {0,1,2,3,4,5,...} 39. RNDr. Ivan Havlíček, CSc., [email protected] ::


Racionální čísla ℚ jsou čísla, která vzniknou podílem dvou celých čísel (kromě dělení nulou). Jejich desetinné vyjádření má konečný počet nenulových desetinných míst nebo je ukončeno opakující se skupinou číslic - periodou. Iracionální čísla jsou ta čísla, která nelze vyjádřit jako podíl dvou celých čísel. Mají nekonečně mnoho číslic za desetinou čárkou, jež se neopakují. Iracionální je většina odmocnin, hodnot goniometrických funkcí, logaritmů apod. Racionální a iracionální čísla dohromady tvoří reálná čísla ℝ.



Spočetná množina je množina, jejíž prvky dokážeme seřadit do pořadí očíslovaného přirozenými čísly. Množiny, které nejsou spočetné, označujeme jako nespočetné. Množina přirozených čísel, ač nekonečná, je spočetná. Její mohutnost označujeme prvním kardinálním číslem 0 (alef nula). Tvrzení: Racionálních čísel je spočetně mnoho. Důkaz: Racionální čísla seřadíme takto: 0, 1/1, -1/1, 1/2,-1/2, 2/1,2/1, 1/3, -1/3, 2/3,-3/2, 3/1,-3/1,… . Tato seřazená racionální čísla se dají očíslovat. □ 41. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Reálných čísel je nespočetně mnoho. Důkaz: Dokážeme, že i v intervalu (0,1) je nespočetně mnoho reálných čísel. K důkazu sporem vyjdeme z předpokladu, že reálných čísel v (0,1) je spočetně mnoho. Pak existuje způsob, jak je seřadit za sebou jako přirozená čísla. Nechť je to toto uspořádání a1 = 0, a11 , a12 ,..., a1k ,...

a 2 = 0, a 21 , a 22 ,..., a 2 k ,... ... al = 0, al1 , al 2 ,..., alk ,... ..., kde aij jsou čísla 0, 1, 2,…,9 a k,l jsou přirozená čísla. 42. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pokračování důkazu: Budeme uvažovat následující číslo b = 0,b1 ,b2 ,… podle pravidla: Je-li na m-tém desetinném místě čísla am číslo 5, bude bm = 4, není-li na m-tém desetinném místě čísla am číslo 5, bude bm = 5. Takto utvořené číslo b se nutně liší od čísla am na m-tém desetinném místě pro libovolné m. Liší se tedy od všech čísel, které jsou v předpokládaném uspořádání, to znamená že předpoklad o spočetnosti reálných čísel intervalu (0,1) byl nesprávný. Správné je tedy dokazované tvrzení tj., že reálných čísel je nespočetně mnoho. □ 43. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 3 Množiny 3.3 Princip inkluze a exkluze

Tvrzení (Princip inkluze a exkluze). Mějme množiny Ai , i = 1,…,n a uvažujme všechny neprázdné podmnožiny I ⊆ {1,…,n}. Pak pro mohutnost sjednocení množin platí |A1 ∪ A2| = |A1| + |A2| - |A1 ∩ A2|

|A1

A2

A3| = |A1| + |A2| + |A3| - |A1 ∩ A2| - |A1 ∩ A3| - |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|

……………………………………………………..atd.


Diskrétní matematika 3. Množiny 3.4 Kartézský součin

Uspořádaná dvojice, je dvojice prvků (x,y), u níž záleží na pořadí x a y. Kartézský součin množin X a Y , X×Y, × je množina všech uspořádaných dvojic (x,y), kde x∈X ∈ a y∈Y. ∈



4 Relace 4.1 Binární relace 4.2 Ekvivalence 4.3 Zobrazení 4.4 Skládání zobrazení 4.5 Relace uspořádání


Diskrétní matematika 4 Relace 4.1 Binární relace

Definice. Binární relace R mezi dvěma množinami X a Y je množina uspořádaných dvojic (x,y), kde x X a y Y. R je tedy podmnožinou kartézského součinu. Vznikne-li dvojice (x,y) relací R, říkáme, že (x,y) náleží R a píšeme (x,y) R nebo jednoduše xRy. Definice. Relace na množině X je množina dvojic prvků X. Matice sousednosti relace R na množině X o n prvcích je n × n matice A = (aij) , kde aij = 1 aij = 0

jestliže (xi,yj) jestliže (xi,yj)

R, R.



4 Relace 4.2 Ekvivalence 1/2

Definice. Relace R na množině X je reflexivní, jestliže pro každé x X platí xRx, je symetrická, jestliže kdykoliv platí xRy, platí i yRx, je transitivní, jestliže ze vztahů xRy a yRz plyne xRz. Relace R na X, která je reflexivní, symetrická a transitivní se nazývá ekvivalence na X. Nechť R je ekvivalence na množině X, nechť x je libovolný prvek X. Označme symbolem R[x] množinu všech prvků y, které jsou ekvivalentní s x. R[x] se nazývá třída ekvivalence R určená prvkem x.


Diskrétní matematika 4 Relace 4.2 Ekvivalence 2/2

Tvrzení. Pro každou ekvivalenci R na množině X platí: 1) R[x] je neprázdná množina pro každý prvek x

X.

2) Pro každé dva prvky x,y množiny X je buď R[x] = R[y] nebo je R[x] ∩ R[y] = (prázdná množina). 3) Třídy ekvivalence jednoznačně určují R. Důkaz: Plyne z definice ekvivalence.


Diskrétní matematika 4 Relace 4.3 Zobrazení

Definice. Zobrazení f množiny X do množiny Y je relace f X × Y, pro kterou platí, že pro každý prvek x ∈ X existuje právě jediný prvek y ∈ Y tak, že xfy; píšeme y = f(x), nebo také f : X → Y.

Definice. Zobrazení nazýváme a) prosté (neboli injektivní), jestliže pro x ≠ y je f(x) ≠ f(y), b) zobrazení na (neboli surjektivní), jestliže pro každé y X splňující rovnost f(x) = y a

Y existuje x

c) vzájemně jednoznačné zobrazení (neboli bijektivní), jestliže f je prosté a na a píšeme f : X ↔ Y. 50. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 4 Relace 4.4 Skládání zobrazení

Definice. Jsou-li f : X → Y a g : Y → Z zobrazení, pak lze pro všechna x ∈ X definovat zobrazení h : X → Z takto h(x) = g(f(x)). Zobrazení h nazýváme složením zobrazení f a g a budeme ho značit g ◦ f. Tvrzení. Nechť f : X → Y a g : Y → Z jsou zobrazení. Pak platí: 1. Jsou-li f, g prostá zobrazení, je rovněž g ◦ f prosté zobrazení. 2. Jsou-li f, g zobrazení na, je rovněž g ◦ f zobrazení na. 3. Jsou-li f, g zobrazení vzájemně jednoznačná, je rovněž g ◦ f zobrazení vzájemně jednoznačné. 4. Pro každé zobrazení f : X → Y existují množina Z, prosté zobrazení h : Z → Y a zobrazení na g : X → Z tak, že f = h ◦ g. 51. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 4 Relace 4.5 Relace uspořádání 1/4

Definice. Relace R na množině X se nazývá slabě antisymetrická, jestliže pro každé x, y ∈ X platí, že pokud xRy a zároveň yRx, potom musí být x = y. Relace R na množině X se nazývá (silně) antisymetrická, jestliže pro každé platí, že pokud xRy, pak musí být ¬(yRx). Relace R na množině X se nazývá antireflexivní, jestliže pro každé je ¬(xRx). Definice. Uspořádání (slabé) na nějaké množině X je každá relace na X, která je reflexivní, slabě antisymetrická a tranzitivní. Upořádaná množina je dvojice (X,R), kde X je množina a R je uspořádání na X. Ostré uspořádání je relace, která je antireflexivní, tranzitivní a antisymetrická. 52. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pro relace uspořádání se používají symboly <,≤,⋞,… , popřípadě ostré nebo obrácené. Dobře známé uspořádané množiny: (ℕ ℕ, ≤), (ℝ,≤). Definice. Pokud můžeme každé dva prvky z uspořádané množiny porovnat, tj. pro každé dva prvky x a y platí např. buď x⋞y nebo y⋞x, mluvíme o lineárním nebo úplném uspořádání. Nemůžeme-li porovnat každé dva prvky, mluvíme o částečném uspořádání a částečně uspořádané množině. Úplně uspořádané množiny jsou podmnožinou částečně uspořádaných množin. 53. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Říkáme, že prvky a, b v částečném uspořádání jsou neporovnatelné, pokud neplatí ani jedno z a ⋞ b a b ⋞ a. Říkáme, že posloupnost tvoří řetězec v částečném uspořádání pokud . Říkáme, že prvek m je nejmenší v částečném uspořádání množiny A, pokud každý jiný prvek je větší než m, tj. . Největší prvek v částečném uspořádání definujeme analogicky k nejmenšímu prvku. Definice. Nechť (X,⋞) je uspořádaná množina. Řekneme, že prvek x je bezprostředním předchůdcem prvku y a budeme značit x⊲y, jestliže a neexistuje žádný prvek z ∈ X takový, že x⊲z⊲y.



Tvrzení. Nechť (X, ⋞) je konečná uspořádaná množina a ⊲ je příslušná relace bezprostředního předchůdce. Potom pro libovolné dva prvky x,y ∈ X a k∈ℕ platí, že x ⋞ y právě, když existují prvky x1,…xk ∈ X takové, že x ⊲ x1⊲…⊲ xk ⊲ y Je-li k = 0, je přímo x ⊲ y. Důkaz: Jedna implikace je zřejmá: máme-li x ⊲ x1⊲…⊲ xk⊲ y, pak podle definice je i x⋞x1⋞…⋞xk⋞y. Opačnou implikaci dokážeme indukcí podle k. □



5 Kombinatorické počítání 5.1 Podmnožiny 5.2 Permutace 5.3 Kombinační čísla 5.4 Binomická věta


Diskrétní matematika 5 Kombinatorické počítání 5.1 Podmnožiny 1/2

Tvrzení. Nechť N je nějaká n-prvková množina n ≥ 0 a M je mprvková množina m ≥ 1. Pak počet všech zobrazení f : N → M je mn. Důkaz: Provedeme jej indukcí podle n. Pro n = 0 se jedná o zobrazení (relaci) prázdné množiny. Taková relace je jedna, totiž prázdná. Tvrzení tedy platí pro n = 0. Předpokládejme, že tvrzení platí pro všechna n ≤ n0 a pro každé m. Mějme nyní n = n0 + 1-prvkovou množinu N a m-prvkovou množinu M. Zvolíme libovolně jeden prvek a ∈ N. Zadat zobrazení f : N → M znamená zadat hodnotu f(a) ∈ M a f´: N\{a} → M zobrazení zbývajících prvků. Hodnotu f(a) můžeme zvolit m způsoby a pro volbu f´ máme podle indukčního předpokladu mn-1 možností. Každou volbu f(a) můžeme kombinovat s f´, takže máme celkem m. mn-1 - mn možností pro f. □ 57. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 5 Kombinatorické počítání 5.1 Podmnožiny 2/2

Tvrzení. Pro m,n ≥ 0 existuje právě n−1

m×(m−1) ×(m− 2) ×...×(m− n +1) = ∏(m− i) i=0 =

prostých zobrazení n-prvkové množiny do m-prvkové množiny. Důkaz: Tvrzení se jednoduše dokáže indukcí. Zkusme n = 0: prázdné zobrazení je prosté. Mějme nyní n-prvkovou množinu N, n ≥ 0 a mprvkovou množinu M, m ≥ n. Vybereme prvek a ∈ N a zvolíme jeho funkční hodnotu f(a) ∈ M libovolně, jedním z m způsobů. Zbývá zobrazit prostým zobrazením prvky množiny N\{a} do množiny M\{f(a)}. Takových prostých zobrazení je podle indukčního předpokladu (m −1)(m − 2)...(m − n +1) . Celkem tedy je m prostých zobrazení m (m −1)(m − 2)...(m − n +1) . □

58.


Diskrétní matematika 5 Kombinatorické počítání 5.2 Permutace

Definice. Prostá zobrazení konečné množiny X do sebe se nazývají permutace množiny X.

p : {a,b,c,d,e,f} → {d,f,e,b,a,c}

Tvrzení. Zobrazení podle předchozí definice jsou zároveň na. 59. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 5 Kombinatorické počítání 5.3 Kombinační čísla 1/5

Definice. Nechť n a k jsou nezáporná čísla. Binomický koeficient neboli kombinační číslo je funkce proměnných n, k definovaná vzorcem  n  n(n − 1)(n − 2)...(n − k + 1)   = = 1 × 2 × ... × k k 

. Takové kombinační číslo čteme „n nad k“.

∏

k −1

i =0

(n − i)

k!

n! = k!(n − k )!

Definice. Nechť X je množina a k celé nezáporné číslo. Symbolem X    budeme značit množinu všech k-prvkových podmnožin množiny X. k X  Specielně  2  budeme označovat množinu všech dvouprvkových  

podmnožin množiny X.



Tvrzení. Pro každou konečnou množinu X je počet jejích kX X  X  n       prvkových podmnožin roven  k  . Čili   =  , anebo   je počet   k  k  k  všech k-prvkových podmnožin n-prvkové množiny. Důkaz: Označme n = |X|. Budeme dvěma způsoby počítat všechny uspořádané k-tice, které lze utvořit z prvků množiny X (bez opakování). Na jedné straně tento počet podle tvrzení je n(n -1)… (n – k + 1). Na

X druhé straně z jedné k-prvkové podmnožiny M ⊆   můžeme vytvořit k! k různých uspořádaných k-tic a každou uspořádanou k-tici dostaneme z nějaké podmnožiny právě jednou. Takže

X n(n − 1)...(n − k + 1) = k!   k

□

61.



Definice. O permutacích s opakováním mluvíme v případě, že seřazujeme dané prvky do posloupnosti, ve které prvky mají předepsaný nenulový počet identických kopií (tzn. prvky se „opakují“).

Tvrzení. Počet všech permutací s opakováním z k prvků, kde se i-tý prvek opakuje mi-krát pro i = 1,…,k, je

(m 1 + m 2

+ ... + m k )! m 1 ! m 2 !... m k !



Příklad. Kolika různými způsoby můžeme seřadit do posloupnosti písmena sousloví DISKRETNIMATEMATIKA? Řešení: Použijeme metodu dvojího počítání. Počet všech seřazení bez ohledu na to zda se některá písmena opakují (jako bychom si je očíslovali): Označme x výsledný počet různých seřazení daných písmen, (v tomto počtu se nesmí odrazit skutečnost, že se některá písmena vyskytují více než jednou). Abychom tedy dostali hledaný počet seřazení, vynásobíme číslo x ještě 3! za permutace písmen „A“, 33! . ! za permutace písmen „I“, atd. Zároveň však stejný počet dostaneme jako počet permutací 19-ti čísel. Máme tedy

x(3!) (2!) = 19! 3

3

z toho

19! x= (3! ) 3 ( 2! ) 3 63. RNDr. Ivan Havlíček, CSc., [email protected] ::


Z kombinačních čísel můžeme tvořit Pascalův trojúhelník ¨ 0   = 1 0

1   = 1 1

1   =1 0  2   = 1  0  3   = 1  0

3   = 3 1

 2   = 2  1

 3   = 3  2

 2   = 1  2  3   = 1  3

………………………………………………


Diskrétní matematika 5 Kombinatorické počítání 5.4 Binomická věta

Tvrzení (Binomická věta) Binomická věta (ve specielním tvaru) říká, že pro n ≥ 0 platí

 n k (1 + x) = ∑  x k =0  k  n

n

. Důkaz: Při algebraickém součinu binomů využíváme pravidlo násobit každý člen s každým. To znamená, že v rozvoji

(1 + x )(1 + x )...(1 + x ) 14 4424 4 43 n

nám člen xk vyjde tolikrát, kolikrát lze vybrat (neuspořádanou) kn tici z n členů. To je právě  k  krát .

□

65.



6 Diskrétní pravděpodobnost 6.1 Konečné pravděpodobnostní prostory 6.2 Nezávislé jevy 6.3 Náhodné výběry 6.4 Střední hodnoty


Diskrétní matematika 6 Diskrétní pravděpodobnost 6.1 Konečné pravděpodobnostní prostory 1/2

Definice. Pod pojmem konečný pravděpodobnostní prostor rozumíme dvojici (Ω,P), kde Ω je konečná množina a P je zobrazení přiřazující každé podmnožině množiny Ω číslo z intervalu <0,1> , takové, že

1. P(Ø) = 0, 2. P(Ω) = 1, 3. P(A∪B) = P(A) + P(B) pro libovolné množiny A, B ⊆ Ω a A∩B = ∅. Prvky množiny Ω se nazývají elementární jevy a P se nazývá funkce pravděpodobnosti. 67. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 6 Diskrétní pravděpodobnost 6.1 Konečné pravděpodobnostní prostory 2/2

Tvrzení. Pro libovolné množiny A, B ⊆ Ω má funkce pravděpodobnosti tyto další vlastnosti:

( )

1. P A = 1 − P( A) 2. je-li A⊆ B pak je P( A) ≤ P(B), 3. P( A∪B) = P( A) + P(B) − P( A∩B) .


Diskrétní matematika 6 Diskrétní pravděpodobnost 6.2 Nezávislé jevy 1/2

Definice. Podmíněná pravděpodobnost, že nastane jev A za předpokladu, že jev B nastal je (předpokládáme, že ) P(A ∩ B) P (A B ) = P(B)

Definice. Nechť P(B) ≠ 0. Potom jevy A a B jsou nezávislé tehdy a jen tehdy, když

P(A|B) = P(A),

tj. pravděpodobnost jevu A není ovlivněna tím, že jev B nastal. 69. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 6 Diskrétní pravděpodobnost 6.2 Nezávislé jevy 2/2

Tvrzení. Jevy A, B jsou nezávislé právě tehdy, když platí

P ( A ∩ B ) = P ( A).P ( B )

. . Jev B je nezávislý na jevu A, pokud je pravděpodobnost P(B) při nastalém jevu A stejná, jako pravděpodobnost P(B) jevu B samotného. Tedy

P( A ∩ B) P( B) = P( A) Ω 70. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 6 Diskrétní pravděpodobnost 6.3 Náhodné výběry

Náhodná podmnožina. Z dané n-prvkové množiny vybíráme libovolnou z 2n jejích podmnožin, každou s pravděpodobností 2-n. Náhodná permutace. Ze všech n! permutací n-prvkové množiny vybíráme libovolnou jednu s pravděpodobností 1/n!. Náhodná kombinace. Ze všech k-prvkových kombinací dané n n-prvkové množiny vybíráme jednu s pravděpodobností 1/  k  .  

Náhodná posloupnost bitů. Vybíráme libovolně dlouhou posloupnost z 0 a 1 tak, že každý další bit je vybírán s pravděpodobností ½ zcela nezávisle na všech předchozích bitech. Tzn. každá vybraná podposloupnost této náhodné posloupnosti má stejnou šanci se objevit. 71. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 6 Diskrétní pravděpodobnost 6.4 Střední hodnota 1/2

Definice. Nechť náhodná proměnná X nabývá k možných hodnot z číselné množiny X ∈ {h1,…,hk} , kde jev [X=hi] , tj. X nabývá hodnoty hi nastává s pravděpodobností pi a p1 + p2 +…+pk = 1. Střední hodnotou proměnné X je pak číslo

E(X) = p1.h1 + p2.h2 +…+ pkhk .

Definice. Dvě náhodné proměnné X = {x1,…,xk} a Y = {y1,…,yl} jsou nezávislé, jestliže jevy [X=xi] a [Y=yj] jsou nezávislé pro každé i = 1,…,k a každé j = 1,…,l.


Diskrétní matematika 6 Diskrétní pravděpodobnost 6.4 Střední hodnota 2/2

Tvrzení. Pro libovolné dvě náhodné proměnné X, Y platí

E(X + Y) = E(X) + E(Y) . Tvrzení. Pro libovolné dvě nezávislé náhodné proměnné X, Y platí

E(X.Y) = E(X).E(Y) .

Střední hodnota čísel padlých na hrací kostce je E(X) = (1/6)(1 + 2 + 3 + 4 + 5 + 6 ) = 3,5 . Střední hodnota součinu čísel padlých na dvou hracích kostkách je E(X1.X2) = E(X1).E(X2) = 3,5.3,5 = 12,25.

73.



7 Neorientovaný graf 7.1 Pojem grafu 7.2 Důležité grafy 7.3 Isomorfismus grafů 7.4 Podgrafy 7.5 Souvislost, komponenty 7.6 Matice sousednosti


Diskrétní matematika 7 Neorientovaný graf 7.1 Pojem grafu 1/2

Graf je útvar, který se skládá z bodů, které nazýváme vrcholy nebo uzly, a čar, které tyto body spojují, ty nazýváme hrany nebo oblouky.


Diskrétní matematika 7 Neorientovaný graf 7.1 Pojem grafu 2/2

Definice. Říkáme, že graf G je uspořádaná dvojice (V,E), kde V je neprázdná množina vrcholů a E množina dvoubodových podmnožin množiny V, tzn. množina hran. Abychom vyznačili, že se jedná o množiny V a E příslušející grafu G, značíme také V(G) nebo E(G). Graf G zapíšeme G = (V,E). Hranu, kterou je připojen vrchol v nazýváme incidentní hranou s vrcholem v. Počet incidentních hran s vrcholem v nazýváme stupeň vrcholu v.


Diskrétní matematika 7 Neorientovaný graf 7.2 Důležité grafy 1/4

Úplný graf. Úplný graf je graf, v němž každé dva různé vrcholy jsou spojeny právě jednou hranou. Úplný graf o n V  vrcholech značíme Kn. Pro n ≥ 1 platí E ( K n ) =    2 .

K3

K4

K5

K6 77. RNDr. Ivan Havlíček, CSc., [email protected] ::


Cesta. Cesta je graf, jenž je posloupností navzájem různých vrcholů, které jsou spojeny hranami. Tedy pro Pn , (n ≥ 0) má hrany E = {{i – 1, i}, i = 1,…,n}. .

E = {{i − 1, i }; i = 1,..., n

}



Kružnice. Kružnice je cesta, jejíž oba konce splynuly. Tedy Cn , (n ≥ 3) má hrany E = {{i, i + 1 }; i = 1,..., n − 1 } ∪ {1, n } .

C3

C4

C5

C6



Úplný bipartitní graf. Úplný bipartitní graf je graf, jehož vrcholy jsou rozděleny do dvou množin a hrany vždy vedou „přes hranici“ těchto množin. Tedy Kn,m, (n,m ≥ 1) má vrcholy V = U∪W = {u1,…,un}∪{w1,…wm} a hrany E = {{ui,wj}, i = 1,…,n, j = 1,…,m} a U∩W = ∅.

K1,1

K1,2

K1,3

K2,3

K3,3 80. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 7 Neorientovaný graf 7.3 Izomorfismus grafů 1/2

Definice. Dva grafy G = (V,E) a G´ = (V´,E´) nazveme isomorfní, jestliže existuje vzájemně jednoznačné zobrazení f :V ↔V ′ tak, že platí

{x, y }∈ E ⇔ { f (x), f ( y) }∈ E′ Zobrazení f se nazývá isomorfismus a značíme G ≅ G´

Označíme-li na dvou grafech vrcholy čísly 1,…,n, jsou tyto grafy isomorfní tehdy a jen tehdy, jestliže můžeme převést vrcholy na sebe tak, že zůstanou zachována spojení hranami mezi příslušnými vrcholy. Jinak řečeno, jestliže můžeme posouváním vrcholů a prodlužováním, zkracováním a ohýbáním hran převést druhý graf na tvar stejný s prvním grafem.

81.


Diskrétní matematika 7 Neorientovaný graf 7.3 Izomorfismus grafů 2/2

Tvrzení. Relace „být isomorfní“ na množině všech grafů je ekvivalencí. 82. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 7 Neorientovaný graf 7.4 Podgrafy 1/3

Definice. Graf H je podgrafem grafu G jestliže množiny vrcholů a hran grafu H jsou podmnožinami množin vrcholů a hran grafu G.



Cesta Pt v grafu G je podgraf grafu G tvořený posloupností (v0,e1,v1.e2,…,et-1,et,vt), kde vi jsou navzájem různé vrcholy grafu G a ei = {vi-1,vi} jsou hrany grafu G. Říkáme, že cesta z v0 do vt má délku t.

Kružnice Ct (t ≥ 3) v grafu G je podgraf grafu G tvořený posloupností (v0,e1,v1.e2,…,et-1,et,v0), kde v0,v1,…,vt-1 jsou navzájem různé vrcholy grafu G. 84. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Graf G´ nazýváme faktorem grafu G, vznikne-li z grafu G pouhým vynecháním některých hran a přitom množina vrcholů zůstává zachována, tedy V(G) = V(G´). .

Definice. Graf G´ nazýváme podgrafem indukovaným množinou vrcholů, A ⊆ V(G), jestliže podgraf G´má množinu vrcholů A a obsahuje všechny hrany grafu G, jejichž oba vrcholy jsou z množiny A.

Podgraf indukovaný množinou {a,c,d,e,f} 85. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 7 Neorientovaný graf 7.5 Souvislost, komponenty grafu

Definice. Graf G je souvislý, jestliže pro každé dva jeho vrcholy x a y v něm existuje cesta z x do y. Definice. Relaci ~ (cesta) na množině vrcholů grafu G definujeme vztahem: x ~ y právě, když v grafu G existuje cesta z x do y. Tvrzení. Relace ~ je ekvivalence. Důkaz: Relace ~ je reflexivní, protože z x do x vede nulová cesta. Je symetrická, protože existuje-li cesta z x do y, lze jít i opačně z y do x. Tranzitivitu dokážeme následujícím způsobem: Nechť posloupnost (x=v0,e1,v1,…,er,vr=y) je cesta z x do y a posloupnost ( y = v 0′ , e1′ , v1′ ,..., e ′s , v ′s = z ) je cesta z y do z. Označme t maximální index, pro který je vt′ ∈ {v0 ,..., v r } a označme ještě vt′ = vi Potom hledaná posloupnost z x do z je ( x = v0 , e1 , v1 ,..,ei = vt′ , et′+1 , vt′+1 ,...,e′s , v′s = z ) □ 86. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 7 Neorientovaný graf 7.6 Matice sousednosti v grafu

Definice. Nechť G = (V,E) je graf bez smyček s n vrcholy. Označme v nějakém libovolném pořadí vrcholy v1,...,vn. Matice sousednosti grafu G je čtvercová n × n matice AG = (aij)ni,j=1 definovaná předpisem

aij = 1

pro

{v i , v j }∈ E

aij = 0 jinak.



8 Sledy a délky cest 8.1 Sled 8.2 Ohodnocený graf a vzdálenosti v grafu 8.3 Hledání nejkratší cesty 8.4 Párování


Diskrétní matematika 8 Sledy a délky cest 8.1 Sled v grafu

Definice. Sled délky n v grafu G = (V,E) je posloupnost

(v0,e1,v1,e2,…,en,vn), kde pro i = 1,…,n jsou ei = {vi-1,vi} ∈ E a v0,…,vn ∈ V.

Tvrzení. Nechť G = (V,E) je graf s množinou vrcholů V = {v1,…,vn} a maticí sousednosti A. Označme Ak k-tou mocninu matice A a a(k)ij prvek matice Ak v pozici (i,j). Pak a(k)ij je počet sledů délky k z vrcholu vi do vrcholu vj.


Diskrétní matematika 8 Sledy a délky cest 8.2 Ohodnocený graf a vzdálenost v grafu 1/2

Definice. Grafem s ohodnocenými hranami rozumíme graf G = (V,E), jehož každé hraně e ∈ E(G) je přiřazeno reálné číslo w(e), které můžeme chápat např. jako délku hrany e. Délka cesty v ohodnoceném grafu je rovna součtu délek jejích hran. Nejkratší vzdálenost vrcholů u a v označíme dG,w(u,v) a ta je rovna nejkratší z délek všech cest spojujících u a v.

Grafem s ohodnocenými vrcholy rozumíme graf G = (V,E), jehož každému vrcholu v ∈ V(G) je přiřazeno reálné číslo w(v), které můžeme chápat např. jako prostupnost vrcholu.


Diskrétní matematika 8 Sledy a délky cest 8.2 Ohodnocený graf a vzdálenost v grafu 2/2

Definice (vzdálenost v grafu). Nechť G = (V,E) je souvislý graf. Pro vrcholy v, v´ definujeme číslo dG(v,v´) jako délku nejkratší cesty z v do v´ v grafu G. Číslo dG(v,v´) se nazývá vzdálenost vrcholů v a v´ v grafu G. Tvrzení („trojúhelníková nerovnost“). Zobrazení dG : V × V → ℝ, které nazýváme metrika grafu G má tyto vlastnosti:

1. dG(v,v´) ≥ 0 a dG(v,v´) = 0 právě, když v = v´, 2. (symetrie) dG(v,v´) = dG(v´,v) pro každou dvojici vrcholů v, v´, 3. (trojúhelníková nerovnost) dG(v,v´´) ≤ dG(v,v´) + dG(v´,v´´) pro každou trojici v, v´,v´´ vrcholů z V.

91.


Diskrétní matematika 8 Sledy a délky cest 8.3 Hledání nejkratší cesty 1/2

Dijkstrův (Dijkstra) algoritmus. Je dán graf G = (V,E), ohodnocení jeho hran w : E → (0, ∞) a počáteční vrchol s ∈ V. Pro každý vrchol v ∈ V se vypočítá číslo dG,w(s,v), čili nejkratší vzdálenost z s do v:

Pro každý vrchol v zavedeme proměnnou d(v) jako momentální odhad k dG,w(s,v). Počáteční odhady jsou d(v) = 0 pro v = s a d(v) = ∞ pro v ≠ s. Množina A (A ⊆ V) je na začátku A = V\{s}, tj. všechny vrcholy, které budeme teprve zkoumat patří do A. Vrcholy, pro které je d(v) nejmenší, utvoří množinu N a vyjmou se z množiny A. Přepočtou se hodnoty d(x) pro sousedy vrcholů z N. Pro každou hranu {v,y}, kde v ∈ N a y ∈ A se porovnají d(y) a d(v) + w({v,y}). Pokud je d(v) + w({v,y}) < d(y), znamená to, že z s do y vede přes v kratší cesta a dosavadní d(y) se nahradí hodnotou d(v) + w({v,y}). Algoritmus končí, jestliže A je buď prázdná množina, nebo obsahuje jen vrcholy nedosažitelné z vrcholu s. 92. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 8 Sledy a délky cest 8.3 Hledání nejkratší cesty 2/2

krok a b c d e f

N

A

δ

0.

0 ∞ ∞ ∞ ∞ ∞ ∅ a,b,c,d,e,f 0

1.

0 1 ∞ ∞ ∞ ∞ b

b,c,d,e,f

1

2.

0 1 4 ∞ ∞ ∞ c

c,d,e,f

4

3.

0 1 4 5 ∞ ∞ d

d,e,f

5

4.

0 1 4 5 6 ∞ e

e,f

6

5.

0 1 4 5 6 8 f

f

8

6.

0 1 4 5 6 7 f

∅

7

93.


Diskrétní matematika 8 Sledy a délky cest 8.4 Párování 1/9

Definice. Buď dán graf G = (V,E). Párování v grafu G je taková množina hran P ⊆ E(G) že žádné dvě hrany z množiny P nemají společný vrchol. O vrcholech, které jsou incidentní s některou hranou párování P říkáme, že jsou párováním P nasyceny nebo též pokryty. O ostatních vrcholech říkáme, že jsou volné. Párování, které nasycuje všechny vrcholy grafu, nazýváme perfektním párováním.



Úlohy o párování. Praktické úlohy vedoucí na párování lze zpravidla zařadit do některé z následujících kategorií: 1. V daném grafu najít maximální párování, tj. párování, které obsahuje největší počet hran. 2. V grafu, jehož hrany jsou ohodnoceny cenami, najít nejlevnější maximální párování, tj. nejlevnější párování ze všech, která jsou maximální. 3. V ohodnoceném grafu najít nejdražší párování, tj. párování s největším součtem cen.



Definice. Buď dán graf G a v něm párování P. Střídavá cesta vzhledem k párování P je taková neorientovaná cesta, že její hrany střídavě leží a neleží v P a je-li krajní vrchol cesty nasycen v párování P, pak hrana, která jej nasycuje, je částí cesty.

Střídavá kružnice vzhledem k párování P je kružnice, jejíž hrany střídavě leží a neleží v párování P.



Definice (změna podél střídavé cesty/kružnice). Pomocí střídavých cest a kružnic lze párování snadno měnit tím, že u hran, které leží na cestě nebo kružnici, změníme příslušnost k párování. Je-li H množina hran tvořících střídavou cestu nebo kružnici vzhledem k párování P, vytvoříme nové párování P´ takto:

jestliže e ∈ H, pak e ∈ P´ ⇔ e ∉ P jestliže e ∉ H, pak e ∈ P´ ⇔ e ∈ P. .

Takovou změnu párování budeme nazývat změnou podél střídavé cesty nebo kružnice.



Tvrzení. Buď dán prostý graf G a v něm libovolné párování P1. Pak pro každé párování P2 v grafu G existuje soustava vrcholově disjunktních střídavých cest a střídavých kružnic taková, že změnami podél všech těchto cest a kružnic lze z párování P1 získat párování P2. Důkaz: Uvažujme faktor G´grafu G s množinou hran (P1\P2)∪(P2\P1). Graf Góbsahuje právě ty hrany, které leží přesně v jednom párování. Pro každý vrchol x ∈ V(G´) = V(G) nastane jedna ze čtyř možností: 1. Není-li vrchol x nasycen v ani P1 ani v P2, je izolovaným v G´. 2. Je-li x nasycen v jednom z P1 a P2, má v grafu G´stupeň 1. 3. Je-li x nasycen v P1 i v P2 touž hranou, pak tato hrana neleží v G´ a vrchol x je v G´ izolovaným vrcholem. 4. Je-li x nasycen v P1 i v P2 různými hranami e1 ∈ P1, e2 ∈ P2, pak obě tyto hrany leží v Gá stupeň vrcholu x je 2. 98. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pokračování důkazu Každý vrchol má tedy v grafu G´ stupeň nejvýše 2. Z toho plyne, že graf G´ má komponenty souvislosti tří typů: 1. izolovaný vrchol, 2. kružnice sudé délky, jejíž hrany leží střídavě v P1 a P2, 3. cesta, jejíž hrany střídavě leží v P1 a P2 a jejíž krajní vrcholy jsou různé, přičemž každý z nich je nasycen v jednom z obou párování P1, P2. Komponenty souvislosti grafu G´ přímo určují střídavé cesty a kružnice. Provedením změn párování P1 podél všech těchto cest a kružnic dostaneme párování P2. 99. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Párování P v grafu G je maximální právě tehdy, když v grafu G vzhledem k párování P neexistuje střídavá cesta spojující dva volné vrcholy. Důkaz: Je-li párování maximální, pak vzhledem k němu nemůže existovat střídavá cesta spojující dva volné vrcholy. Kdyby existovala, mohli bychom podél ní párování zvětšit. Není-li naopak párování P maximální, vezmeme nějaké maximální párování P1. Podle předchozího tvrzení existuje soustava střídavých cest a kružnic taková, že změnami podél nich dostaneme párování P1 z párování P. Poněvadž je |P|<|P1| , musí některá z těchto změn zvětšovat párování, musí tedy být změnou podél střídavé cesty s volnými krajními vrcholy (jiné změny nezvětšují počet hran v párování). 100. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Buď graf G, jehož hrany jsou ohodnoceny cenami c : E(G) → ℝ . Dále buď v grafu G párování P a vzhledem k němu střídavá cesta, popř. kružnice. Množinu hran této cesty, popř. kružnice označme H. Cenu střídavé cesty, popř. kružnice stanovíme jako

C =

∑ c (e) − ∑ c (e)

e∈ H O P

e∈ H ∩ P

Tvrzení. Má-li střídavá cesta, popř. kružnice cenu C a provedeme-li podél ní změnu, pak cena párování vzroste o hodnotu C. Tvrzení. Párování P v grafu G je nejdražší právě tehdy, když v grafu G vzhledem k párování P neexistuje ani střídavá cesta, ani střídavá kružnice s kladnou cenou.

101.



Střídavá cesta a změna párování



9 Eulerovské grafy a k-souvislost 9.1 Skóre grafu 9.2 Eulerovské tahy a grafy a hamiltonovské kružnice a cesty 9.3 Algoritmus kreslení grafu jedním tahem 9.4 Stupně souvislosti 9.5 Grafové operace


Diskrétní matematika 9 Eulerovské grafy a k-souvislost 9.1 Skóre grafu 1/3

Definice. Nechť v ∈ V je vrchol grafu G = (V,E). Počet hran obsahujících v označíme degG(v) a nazveme stupněm vrcholu v v grafu G. Nechť v1,…,vn jsou vrcholy grafu G v libovolném pořadí. Posloupnost (degG(v1),…,degG(vn)) se nazývá skóre grafu G.



Tvrzení (princip sudosti v grafech bez smyček). Pro každý graf G = (V,E) bez smyček platí ∑ deg G (v) = 2 E v∈V

Důkaz: Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát za každý její konec.

Důsledek. Každý graf bez smyček má sudý počet vrcholů lichého stupně



Tvrzení. Nechť D = d1,…,dn je posloupnost přirozených čísel. Předpokládejme, že d1 ≤ d2 ≤…≤ dn, a označme symbolem D´ posloupnost (d1´,…,dn´), kde

di´= di di´= di – 1

pro pro

i < n – d n, i ≥ n – dn.

Potom D je skóre grafu právě když D´ je skóre grafu.

Příklad. Existuje graf se stupni vrcholů (1,1,1,1,2,3,4,6,7)? Řešení: Upravíme na (1,0,0,0,1,2,3,5) a uspořádáme (0,0,0,1,1,2,3,5), znovu upravíme (0,0,-1,0,0,1,2) a to už není skóre grafu, protože stupeň vrcholu nemůže být záporný. 106. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 9 Eulerovské grafy a k-souvislost 9.1 Eulerovské tahy a grafy a hamiltonovské kružnice a cesty 1/7

Definice. Uzavřeným) eulerovským tahem rozumíme takový uzavřený sled (v0,e1,v1,…,em-1,vm-1,em,v0), v němž se každá hrana vyskytuje právě jednou a každý vrchol alespoň jednou.

Definice. Eulerovský graf je takový, který má alespoň jeden (uzavřený) eulerovský tah.

Tvrzení. Graf G je eulerovský tehdy a jen tehdy, když je souvislý a každý jeho vrchol má sudý stupeň. 107. RNDr. Ivan Havlíček, CSc., [email protected] ::


Předchozí tvrzení představuje nutnou a postačující podmínku pro existenci eulerovského tahu a představuje silné kritérium. Nutná podmínka: je-li G eulerovský, pak každý vrchol G má sudý stupeň . Postačující podmínka je: Jestliže každý vrchol má sudý stupeň, pak G je eulerovský.



Definice. Hamiltonovská cesta v grafu G je cesta obsahující všechny vrcholy grafu G. Hamiltonovská kružnice v grafu G je kružnice obsahující všechny vrcholy grafu G. Graf obsahující hamiltonovskou kružnici se nazývá hamiltonovský graf.

Nutná podmínka pro existenci hamiltonovské kružnice nebyla zatím nalezena. Jsou nalezeny pouze některé postačující podmínky.



Úloha čínského pošťáka. Pošťák má projít všechny ulice města a vrátit se do výchozího místa a přitom ujít co nejméně kilometrů. Jinými slovy: je dán neorientovaný souvislý graf, jehož hrany jsou ohodnoceny kladnými čísly a úkolem je najít nejkratší uzavřený sled, který obsahuje všechny hrany grafu. Řešení: Je-li graf eulerovský, tj. existuje-li v něm uzavřený eulerovský graf. je úloha tímto tahem již vyřešena. Pokud v grafu eulerovský tah neexistuje, pak sled, který obsahuje všechny hrany, musí projít některými hranami dvakrát nebo vícekrát. Lze však dokázat, že nejkratší sled prochází každou hranou pouze jedenkrát nebo nejvýše dvakrát. V nejkratším sledu, který obsahuje všechny hrany grafu, tvoří opakovaně procházené hrany soustavu cest spojujících vždy dva vrcholy lichého stupně. Lze ukázat, že takové cesty jsou disjunktní 110. (žádná hrana grafu neleží ve dvou takových cestách). RNDr. Ivan Havlíček, CSc., [email protected] ::


Řešení úlohy čínského pošťáka - pokračování Při řešení úlohy čínského pošťáka je možné postupovat takto: 1. V daném grafu G najdeme množinu L vrcholů s lichým stupněm. 2. Pro všechny dvojice (x,y) vrcholů množiny L vypočteme délku d(x,y) nejkratší cesty z x do y. 3. Na množině vrcholů L definujeme úplný graf K, jehož hrany jsou ohodnoceny délkami nejkratších cest d(x,y). 4. V grafu K najdeme nejlevnější perfektní párování P. 5. Pro každou hranu (x,y) grafu K, která leží v párování P, vezmeme všechny hrany původního grafu G, které tvoří nejkratší cestu z x do y a ke grafu G přidáme kopie těchto hran (dostaneme násobné hrany). V grafu G´, který takto získáme, mají všechny hrany sudý stupeň. 6. V grafu G´ sestrojíme eulerovský tah. Tento tah prochází také všemi přidanými hranami, což odpovídá opakovaným průchodům hranami původního grafu. 7. V eulerovském tahu nahradíme všechny přidané hrany jim odpovídajícími hranami grafu původního. Tak získáme hledaný nejkratší sled, který prochází všemi hranami grafu G. 111. RNDr. Ivan Havlíček, CSc., [email protected] ::




Problém obchodního cestujícího. Obchodní cestující má povinnost navštívit n měst v libovolném pořadí a vrátit se do výchozího bodu tak, aby jeho cesta byla co nejkratší. Přitom předpokládáme, že jsou známy vzdálenosti mezi všemi jednotlivými městy – ohodnocení grafu.

Řešení spočívá v nalezení nejkratší hamiltonovské kružnice v úplném ohodnoceném grafu.


Diskrétní matematika 9 Eulerovské grafy a k-souvislost 9.3 Algoritmus kreslení grafu jedním tahem 1/3

Definice. Hranu e ∈ E v grafu G = (V,E) nazveme mostem, jestliže graf G´ = (V,E\{e}) má větší počet komponent než graf G.



Tvrzení. Nechť G = (V,E) je graf, jehož stupně všech vrcholů jsou sudé. Potom graf G neobsahuje most. Důkaz provedeme sporem: Nechť hrana {v,v´} = e je most grafu G. Nechť V1,…,Vn jsou všechny komponenty grafu G označené tak, že

{v,v´}⊆V1. Uvažujme graf G1 = (V1,E1) =

 V1 V1, E∩    2   

Graf G1 je souvislou komponentou grafu G, má tedy všechny stupně sudé a hrana e je mostem grafu G1. Zřejmě graf (V1,E1\{e}) je nesouvislý a má dvě komponenty. Jedna obsahuje vrchol v a druhá vrchol v´ a tyto dva vrcholy jsou lichého stupně. To je spor s předpokladem sudosti. 115. RNDr. Ivan Havlíček, CSc., [email protected] ::


Algoritmus pro nakreslení grafu jedním tahem. Nechť G = (V,E) je graf, jehož všechny vrcholy mají sudý stupeň, nechť |E| = m.

1. krok: Zvol v0 ∈ V libovolně. Polož T0 = v0, 2. krok: Opakuj následující 3. krok pro i = 0, 1, 2,…, dokud je to možné. Pokud už 3. krok nelze provést, potom i = m a Tm je hledaný tah. 3. krok: (prodloužení tahu): Nechť Ti = (v0,e1,…,ei,vi) je již definovaný tah. Zvol hranu ei+1 = E\{e1,…,ei} obsahující vrchol vi. Pokud je to možné, zvol ei+1navíc tak, aby grafy (V,E\{e1,…,ei} a (V,E\{e1,…,ei,ei+1} měly stejný počet komponent. 116. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 9 Eulerovské grafy a k-souvislost 9.4 Stupně souvislosti 1/6

Definice (Hranový stupeň souvislosti). Graf G nazveme hranově k souvislým, má-li alespoň 3 vrcholy a vynecháním libovolných k – 1 hran zůstane G souvislým grafem, ale odebráním libovolné k-té hrany již bude nesouvislý.

Tvrzení. Graf je hranově 2-souvislý neobsahuje-li žádný most.

Tvrzení. Graf G je vrcholově 2-souvislý tehdy a jen tehdy, když pro každé dva jeho vrcholy existuje v grafu G kružnice, která je obsahuje (tj. G je vrcholově 2-souvislý, právě když každé dva vrcholy leží na společné kružnici). 117. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice (Vrcholový stupeň souvislosti). Graf G nazveme vrcholově ksouvislým, má-li alespoň 2 vrcholy a vynecháním libovolných k – 1 vrcholů zůstane G souvislý graf, ale odebráním libovolné k-tého vrcholu již bude nesouvislý. Vrchol grafu nazveme artikulací, jestliže jeho odstraněním zvýšíme počet komponent souvislosti. Tvrzení (Menger). Graf je vrcholově k-souvislý právě tehdy, když pro každé dva vrcholy x, y existuje k vrcholově disjunktních cest z x do y, tj. takových cest, které kromě vrcholů x a y nemají společné vrcholy. Tvrzení ( Ford a Fulkerson 1956). Graf je hranově k-souvislý právě tehdy, když pro každé dva vrcholy x, y existuje k hranově disjunktních cest z x do y, tj. takových cest, které nemají žádnou společnou hranu. 118. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Pro graf G = (V,E) definujeme • odebrání hrany G – e = (V,E\{e}), kde e ∈ E(G) je hrana grafu G;

V  • přidání nové hrany G + e´ = (V,E∪{e´}), kde e′ ∈  \ E je hrana  2 grafu G; • odebrání vrcholu G – v = (V\{v},e ∈ E, v ∉ e), kde v V(odebíráme vrchol v a všechny hrany do něj zasahující); • dělení hrany G%e = (V\{z},(E\{{x,y}})∪{{x,y}}{{x,z},{z,y}}), kde {x,y} ∈ E je hrana a z ∉ V je nový vrchol (na hranu {x,y} přikreslíme nový vrchol z).

119.





Definice. Řekneme, že graf G´je dělení grafu G, pokud G´ je isomorfní grafu vytvořenému z grafu G postupným opakováním operace dělení hrany. Tvrzení. Graf G je vrcholově 2-souvislý právě když libovolné jeho dělení je vrcholově 2-souvislé. Důkaz: Stačí dokázat, že G je 2-souvislý právě když G%e je 2souvislý ( pro libovolnou hranu e ∈ E(G) ). Je-li v ∈ V(G) libovolný vrchol grafu G, je snadno vidět, že G – v je souvislý právě když (G%e) – v je souvislý. Dále využijeme skutečnosti, že vrcholově 2souvislý graf zůstane souvislý i po odebrání libovolné hrany. Je-li z nově přidaný vrchol v grafu G%e,je (G%e) – z souvislý právě když G – e je souvislý. Proto je 2-souvislost a G%e ekvivalentní. 121. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Graf G je vrcholově 2-souvislý právě když jej lze vytvořit z trojúhelníku

Tvrzení. Graf G je vrcholově 2-souvislý právě když jej lze vytvořit z trojúhelníku posloupností dělení hran a přidávání hran.



10 Speciální třída grafů – stromy 10.1 Charakteristika stromů 10.2 Isomorfismus stromů 10.3 Kódování stromů 10.4 Kostra grafu 10.5 Problém minimální kostry


Diskrétní matematika 10 Speciální třída grafů - stromy 10.1 Charakteristika stromů 1/4

Definice. Strom je souvislý graf, který neosahuje kružnici. Vrchol stupně 1 se nazývá koncový vrchol nebo list.



Tvrzení. Každý konečný strom s alespoň dvěma vrcholy obsahuje alespoň dva vrcholy stupně 1.

Důkaz: Nechť P = (v0,e1,v1,…,et,vt) je cesta maximální možné délky ve stromu T = (V,E). Délka cesty P je zřejmě alespoň 1. Sporem dokažme, že jak v0, tak vt jsou koncové vrcholy T. Není-li např.v0 koncový vrchol, pak existuje ještě jiná hrana e ≠ e´ obsahující vrchol v0. Označme e = {v0,v} . Pak buď je v = vi, i ≥ 2 a potom T obsahuje kružnici, což je v rozporu s definicí stromu, anebo v ∉ (v0,e1,v1,…,et,vt), a pak bychom mohli cestu P prodloužit a to je spor. Pro vt bychom postupovali obdobně. 125. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Nechť graf G má koncový vrchol v. Potom G je strom právě když G – v je strom.

Důkaz: Nejprve dokážeme implikaci je-li G strom, pak G – v je strom. Jsou-li x, y dva vrcholy grafu G různé od v, uvažme nějakou cestu z x do y. Tato cesta nemůže obsahovat vrchol stupně 1 mimo x a y, a tudíž neobsahuje ani v. Proto je celá cesta obsažena také v G – v, čili G – v je souvislý. Protože G neobsahuje kružnici, ani G – v neobsahuje kružnici a je to tudíž strom. Nyní dokážeme opačnou implikaci. Nechť G – v je strom. Přidáním koncového vrcholu v nemůžeme vytvořit kružnici. Zřejmě je G souvislý: mezi libovolnýma dvěma vrcholy různými od v vedla cesta už v grafu G – v a cesta z nějakého vrcholu x do vrcholu v vznikne prodloužením cesty spojující x s v´ o hranu {v´,v} , kde v´ je jediný soused vrcholu v. 126. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení (charakterizace stromů). Pro graf G = (V,E) jsou následující podmínky ekvivalentní:

1. G je strom

2. (jednoznačnost cesty) Pro každé dva vrcholy x, y ∈ V existuje právě jediná cesta z x do y. 3. .(minimální souvislost) G je souvislý, vynechání libovolné hrany vznikne nesouvislý graf. 4. (maximální graf bez kružnic) Graf G neobsahuje kružnici, ale každý graf vzniklý z G přidáním hrany již kružnici obsahuje. 5. (Eulerův vzorec) G je souvislý a platí |V| = |E| + 1

127.


Diskrétní matematika 10 Speciální třída grafů - stromy 10.2 Izomorfismus stromů 1/4

Definice. Kořenový strom je dvojice(T,r), kde r ∈ V(T) je jeden zvolený vrchol T, zvaný kořen. Je-li {x, y} ∈ E(T) hrana a leží-li x na (jediné) cestě z y do kořene, říkáme, že x je otec y a y je syn x.

Pěstovaný strom je nějaký kořenový strom(T,r) spolu s jeho pevně zvoleným rovinným nakreslením. Přitom kořen se vyznačí šipkou směřující dolů.



Definice. Isomorfismus stromu je zobrazení f : V(T) V(T´) T na T´, jestliže f je vzájemně jednoznačné zobrazení splňující podmínku {x, y} ∈ E(T) právě, když {f(x), f(y)} ∈ E(T´). Tento isomorfismus zapisujeme T ≅ T´.

Isomorfismus kořenových stromů (T, r) a (T´, r´) je takový isomorfismus f stromů T a T´ , pro který navíc platí f(r) = r´. Značíme to (T, r) ´ (T´, r´). Isomorfismus pěstovaných stromů je takový isomorfismus f stromů T a T´ , který navíc zachovává pořadí synů každého vrcholu. Budeme jej značit (T, r, v) ´´ (T´, r´, v´). .



Izomorfismus stromů, kořenových stromů a pěstovaných stromů



Definice. Mějme kořenový strom s kořenem r. Počet hran v cestě z kořene r do vrcholu x nazveme hloubkou vrcholu x. Množinu vrcholů, které jsou ve stejné hloubce, nazveme vrstvou. Výšku vrcholu x definujeme jako největší počet hran v cestě začínající v x a končící v některém listě. Výška stromu je výška jeho kořene.


Diskrétní matematika 10 Speciální třída grafů - stromy 10.3 Kódování stromů 1/6

Pravidla pro kódování pěstěných stromů. K1. Koncovým vrcholům (různým od kořene) přiřadíme kód 01 K2. Buď v nějaký vrchol, v1,…,vt jeho synové v pořadí zleva doprava. Má-li syn vi kód Ai potom vrcholu v přiřadíme kód 0A1A2…At1

.





Lexikografické uspořádání posloupností.

Dvě různé posloupnosti A = (a1,…,an) a B = (b1,…,bm) porovnáváme takto: 1. Je-li A počátečním úsekem B, pak A < B. Je-li B počátečním úsekem A, je B < A. 2. V ostatních případech, buď j nejmenší index takový, že aj ≠ bj. Pak pokud je aj < bj, klademe A < B, a pokud aj > bj, klademe A > B. .



Pravidlo pro kódování kořenových stromů. Pro kódování kořenových stromů přijmeme modifikaci pravidla K2:

K2´. Předpokládejme, že jsme již přiřadili kód A(w) každému synu w vrcholu v. Označme syny w1,…,wt tak, že platí lexikografické uspořádání A(w1) ≤ A(w2) ≤…≤ A(wi). Vrchol v pak dostane kód 0A1A2…At1, kde Ai = A(wi).

Tvrzení. Dva kořenové stromy jsou isomorfní právě když mají . stejný kód. (Při použití pravidla K2´.)



Definice. Pro vrchol v grafu G označíme symbolem exG(v) a nazveme výstřednost (excentricita) maximální vzdálenost vrcholu v od jiného vrcholu grafu G. Označíme C(G) množinu všech vrcholů v grafu G, které mají nejmenší výstřednost exG(v). množinu C(G) nazýváme středem grafu G.

Tvrzení. Pro každý strom T má C(T) nejvýše dva vrcholy. Je-li C(T) tvořeno dvěma vrcholy x a y, pak {x, y} tvoří hranu.



Pravidla kódování obecného stromu. 1. Jestliže střed stromu má jediný vrchol v, potom mu přiřadíme kód jako kořenovému stromu. 2.Je-li střed stromu T tvořen hranou e = {x1, y1} , potom uvažujme graf T – e. Tento graf má právě dvě komponenty T1 a T2, kde xi ∈ V(Ti), i = 1, 2 . Označme kód kořenového stromu (T1, x1) písmenem A a kód kořenového stromu (T2,x2) písmenem B. Pokud je v lexikografickém uspořádání A ≤ B, , kódujeme strom T kódem kořenového stromu (T,x1) a pro A ≥ B kódem kořenového stromu (T,x2). Tvrzení. Dva obecné stromy jsou isomorfní právě když mají stejný kód. 137. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 10 Speciální třída grafů - stromy 10.4 Kostra grafu 1/2

Definice. Nechť G = (V,E) je graf. Libovolný strom tvaru (V,E´), kde E´ ⊆ E, nazveme kostra grafu G. Kostra grafu G je tedy strom, který je podgrafem grafu G a obsahuje všechny vrcholy grafu G.


Diskrétní matematika 10 Speciální třída grafů - stromy 10.4 Kostra grafu 2/2

Algoritmus nalezení kostry I. Buď G = (V,E) graf s n vrcholy a m hranami. Seřaďme hrany grafu G do libovolné posloupnosti (e1,…,e2). V algoritmu budeme postupně konstruovat množiny hran E1,E2,…⊆E tak, že položíme E0 = ∅, byla-li nalezena množina Ei-1, spočítáme množinu Ei takto: Ei = Ei-1∪{ei} neobsahuje-li graf (V,Ei-1∪{ei} kružnici Ei = Ei-1 jinak. Algoritmus nalezení kostry II. Je dán graf G = (V,E) s n vrcholy a m hranami. Budeme postupně vytvářet množiny V0,V1…⊆V vrcholů a množiny E0,E1,…E hran, přičemž E0 = ∅ a V0 = {v}, kde v je libovolně zvolený vrchol. Jsou-li již Vi-1 a Ei-1 vytvořeny, nalezneme nějakou hranu ei = {xi,yi} ∈ E(G) takovou, že xi ∈Vi-1, yi V\Vi-1 a položíme Vi = Vi-1 {yi}, Ei = Ei-1 {ei}. Pokud žádná taková hrana neexistuje, algoritmus končí. 139. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 10 Speciální třída grafů - stromy 10.5 Problém minimální kostry 1/7

Definice. Minimální kostrou grafu G = (V,E) s nezáporně oceněnými hranami nazveme takový jeho podgraf Tm = (V,E´) , pro který nabývá číslo

w( E ′´) =

∑ w(e)

e∈E ′

své minimální hodnoty.



Kruskalův algoritmus Nechť graf G=(V,E) je souvislý graf s n vrcholy a m hranami a má oceněné hrany. Uspořádejme hrany podle jejich ocenění tak, že w(e1) ≤ w(e2) ≤…≤ w(em). Algoritmus nalezení kostry: V algoritmu budeme postupně konstruovat množiny hran E0,E1,…⊆ E tak, že položíme E0 = ∅. byla-li nalezena množina Ei-1, spočítáme množinu Ei takto: Ei = Ei-1∪{ei} neobsahuje-li graf (V,Ei-1∪{ei} kružnici, Ei = Ei-1 jinak.

Kreslíme tedy hrany postupně od nejmenšího ohodnocení a kontrolujeme pouze, zda v daném kroku bude, či nebude uzavřena kružnice. Pokud ano, hranu nepřipojíme a zkoumáme hranu následující. Je-li graf souvislý, skončí algoritmus stromem s n – 1 hranami. Má-li po skončení algoritmu kostra k < n – 1 hran, je G graf nesouvislý s n – k komponentami.

141.



Jarníkův algoritmus. Je dán graf G = (V,E) s n vrcholy a m hranami. Budeme postupně vytvářet množiny V0,V1…⊆V vrcholů a množiny E0,E1,…E hran, přičemž E0 = ∅ a V0 = {v}, kde v je libovolně zvolený vrchol. Jsou-li již Vi-1 a Ei-1 vytvořeny, vyhledáme z hran ei = {xi,yi} ∈ E(G) takových, že xi ∈Vi-1, yi V\Vi-1 (tj. takových, které spojují dosud pospojované vrcholy ještě nepřipojenými) tu, jejíž ocenění je nejmenší a položíme Vi = Vi-1 {yi}, Ei = Ei-1 {ei}. Pokud žádná taková hrana neexistuje, algoritmus končí.



Borůvkův algoritmus. Vycházíme z grafu G = (V,E), jehož ohodnocení jednotlivých hran se alespoň trochu liší a seřadíme je podle velikosti ohodnocení. V algoritmu budeme postupně konstruovat množiny hran E0,E1,…⊆ E a položíme E0 = ∅. Množinu vrcholů V považujeme na počátku rozloženou do n tříd ekvivalence komponent grafu, který ještě neobsahuje žádné hrany. Komponenty jsou tedy na počátku samotné vrcholy. Tento rozklad pak budeme upravovat podle právě vytvořených komponent postupně vznikající kostry. V i-tém kroku máme množinu Ei-1 a rozklad V1,V2,…,Vt množiny V podle již vytvořených komponent. Pro každou třídu tohoto rozkladu Vj najdeme hranu ej = {xj, yj}, kde xj ∈ Vj a yj ∉ Vj , tedy mezi dosud vzniklými komponentami, a jejíž ohodnocení je nejmenší z hran {x, y}, x ∈ Vj, y V\Vj, utvoříme Ei = Ei-1∪{e1,…,et}. Algoritmus končí, má-li graf (V,Ei) jedinou komponentu. 143. RNDr. Ivan Havlíček, CSc., [email protected] ::


Kruskalův algoritmus



Jarníkův algoritmus



Borůvkův algoritmus



11 Rovinné kreslení grafů 11.1 Kreslení do roviny 11.2 Eulerův vztah 11.3 Kreslení na jiné plochy


Diskrétní matematika 11 Rovinné kreslení grafů 11.1 Kreslení do roviny 1/6

Definice. Rovinný graf je graf je takový graf, který lze nakreslit do roviny bez křížení hran.

Oblouk je podmnožina roviny × = 2 tvaru o ={γ(x); x 0,1 }, kde γ : 0,1 → 2, kde je nějaké spojité zobrazení uzavřeného intervalu 0,1 do roviny. Přitom body γ(0) a γ(1) se jmenují koncové body oblouku o. Definice. Nakreslení grafu G = (V,E) nazýváme zobrazení, které každému vrcholu v grafu G přiřazuje bod b(v) roviny, a každé hraně e = {v, v´} ∈ V přiřazuje oblouk o(e) v rovině s koncovými body b(v) a b(v´). Přitom předpokládáme, že zobrazení b je prosté a žádný z bodů b(v) není nekoncovým bodem žádného z oblouků o(e).

Tato definice vylučuje křížení oblouků.



Definice. Graf spolu s nějakým nakreslením se nazývá topologický graf.

2 nazveme souvislou, jestliže pro libovolné Definice. Množinu A dva body x a y A existuje oblouk o ⊆ A s koncovými body x a y.

Definice. Buď G = (V,E) topologický graf. Množina všech bodů roviny, které neleží na žádném z oblouků se rozpadne na konečný počet souvislých oblastí, které nazýváme stěny topologického rovinného grafu.



Stěny grafu.



Definice. Uzavřená křivka v rovině, která sama sebe neprotíná se nazývá topologická kružnice (nebo také Jordanova křivka).

Tvrzení (Jordanova věta o kružnici). Každá topologická kružnice k rozděluje rovinu na právě dvě souvislé části: „vnitřek“ a „vnějšek“ kružnice, přičemž k je jejich společnou hranicí.

Vnitřek a vnějšek budeme nazývat oblastmi kružnice k.



Tvrzení. K5 není rovinný graf. Důkaz: Postupujeme sporem. Nechť b1, b2, b3, b4, b5 jsou body odpovídající vrcholům K5 při nějakém rovinném nakreslení. Oblouk, který spojuje bi a bj označíme o(i,j). Protože b1, b2 a b3 jsou vrcholy kružnice v grafu K5 , tvoří oblouky o(1,2), o(2,3) a o(3,1) topologickou kružnici k. Body b4, b5 musí ležet oba vně nebo oba uvnitř kružnice k, jinak by oblouk o(4,5) protínal kružnici k. předpokládejme nejprve, že b4 leží uvnitř. Potom b5 musí ležet uvnitř kružnice tvořené oblouky o(1,4), o(4,2) a o(1,2), nebo oblouky o(2,3), o(3,4) a o(2,4),nebo oblouky o(1,3), o(3,4), a o(1,4). V prvním případě však oblouk o(3,5) musí protnout kružnici tvořenou oblouky o(1,4), o(4,2) a o(1,2) a podobně v ostatních dvou případech. Pokud body b4, b5 leží vně kružnice k, pak bychom postupovali analogicky. 152. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. K3,3 není rovinný graf.

Tvrzení. Budiž G 2-souvislý rovinný graf. Potom každá stěna v libovolném nakreslení grafu G je oblastí nějaké kružnice grafu G.

Tvrzení. (Kuratowského věta) Graf G je rovinný tehdy a jen tehdy, když žádný jeho podgraf není isomorfní k dělení grafu K3,3 ani k dělení grafu K5.


Diskrétní matematika 11 Rovinné kreslení grafů 11.2 Eulerův vztah 1/7

Tvrzení (Eulerův vzorec). Budiž G = (V,E) souvislý rovinný graf a s počet stěn nějakého rovinného nakreslení G. Pak |V| - |E| + s = 2.

Důkaz: Postupujeme matematickou indukcí podle počtu hran grafu G. Je-li E = ∅, potom |V| = 1 a s = 1 a vzorec platí. Buď |E| ≥ 1 a rozlišíme dvě možnosti: 1. Graf G neobsahuje kružnici. Potom G je strom a |V| = |E| + 1, přitom s = 1. 2. Nějaká hrana e je obsažena v kružnici. Pak je graf G – e souvislý. Pro něj podle indukčního předpokladu platí Eulerův vzorec. Hrana e sousedí se dvěma různými stěnami S a S´, protože e je obsažena v kružnici. Tyto stěny se v grafu G – e stanou stěnou jedinou. Počet hran i stěn v grafu G ve srovnání s grafem G – e stoupl o 1 a počet vrcholů se nezměnil. Eulerův vzorec tedy platí i pro G . 154. . RNDr. Ivan Havlíček, CSc., [email protected] ::


Aplikace na platónská tělesa. Platónská tělesa jsou pravidelné mnohostěny ohraničené pravidelnými mnohoúhelníky, kterých se každého vrcholu dotýká stejný počet: (i) čtyřstěn, ohraničený čtyřmi trojúhelníky a setkávají se vždy 3 v jednom vrcholu, (ii) šestistěn – krychle, (iii) osmistěn ohraničený trojúhelníky (setkávají se vždy čtyři), (iv) dvanáctistěn ohraničený pětiúhelníky, z nichž se vždy 3 setkávají a (v) dvacetistěn s trojúhelníky (setkává se jich vždy 5). V dalším ukážeme, že další tělesa s těmito vlastnostmi nejsou.



Stereografická projekce. Jsou-li uvedená tělesa umístěna v kouli, jejíž střed je uvnitř tělesa a je-li provedena stereografická projekce ze středu na povrch koule, promítnou se na povrch koule vrcholy i hrany tělesa. Nyní se další stereografickou projekcí z koule přenesou projekcí „ze severního pólu“ vrcholy a hrany do roviny a dostaneme rovinné grafy.





Tvrzení. Budiž G = (V,E) topologický graf, jehož každý vrchol má (stejný) stupeň d ≥ 3 a jehož každá stěna má (stejně) k ≥ 3 vrcholů. Pak G je isomorfní s jedním z grafů získaných stereografickou projekcí z platónských těles. Důkaz: Označme |V| = n počet vrcholů, |E| = m počet hran a s počet stěn S grafu G. Podle principu sudosti je ∑ degG (v) = 2 E .

e∈V

tedy v našem případě dn = 2m. Určeme nyní počet uspořádaných dvojic tvaru (e,S), kde e je hrana ležící na hranici stěny S. Těch je ks, protože každá stěna přispěje k dvojicemi, ale také 2m, protože každá hrana 1 1 1 1 přinese 2 dvojice.Tedy ks = 2m . + = + Protože Eulerův vztah zní 2 = n – m + s, dostaneme d k 2 m . Této rovnici vyhoví jen taková d a k, která vedou na levé straně k číslu většímu než ½ (jinak by m bylo záporné) a to jsou dvojice z čísel 3, 4, 5 158. s výjimkou dvojice 4, 4. Dostáváme výsledek RNDr. Ivan Havlíček, CSc., [email protected] ::


d

k

n

m

s

těleso

3

3

4

6

4

čtyřstěn

3

4

8

12

6

krychle

3

5

20

30

12

dvanáctistěn

4

3

6

12

8

osmistěn

5

3

12

30

20

dvacetistěn 159. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. (Maximální počet hran rovinného grafu): Nechť G = (V,E) je rovinný graf s alespoň 3 vrcholy bez smyček. Potom (i) platí |E| ≤ 3|V| - 6. Rovnost nastává pro každý maximální rovinný graf, tj.graf, k němuž nelze přidat žádnou hranu tak, aby zůstal rovinným. (ii) Neobsahuje-li navíc graf G trojúhelník K3 jako podgraf , pak platí |E| ≤ 2|V| - 4. Důsledek. Z (i) plyne, že každý rovinný graf má alespoň jeden vrchol stupně nejvýš 5; a z (ii), že každý rovinný graf bez trojúhelníků má alespoň jeden vrchol stupně nejvýš 3.


Diskrétní matematika 11 Rovinné kreslení grafů 11.2 Kreslení na jiné plochy

Kreslení na nerovinných plochách. Kreslit lze i na jiných „křivých“ plochách, jako například torus (anuloid), Möbiův list a koule s uchem Na torus lze nakreslit graf K5 a na Möbiův list graf K3,3.



12 Barevnost mapy a problém čtyř barev 12.1 Nezávislost, kliky a obarvení vrcholů 12.2 Obarvení mapy 12.3 Problém čtyř a pěti barev


Diskrétní matematika 12 Barevnost mapy – problém čtyř barev 12.1 Nezávislost, klika, obarvení vrcholů 1/5

Definice (Nezávislá množina). Nezávislá množina vrcholů v grafu G je taková množina, jejíž žádné dva vrcholy nejsou spojeny hranou. Nejpočetnější nezávislá množina je nezávislá množina, která má největší počet prvků. Počet vrcholů v nejpočetnější nezávislé množině grafu G nazýváme nezávislostí grafu G a značíme α(G).

V praxi se vyskytují úlohy najít nejdražší nezávislou množinu v závislosti na ohodnocení vrcholů.

Definice (Klika). Klika v grafu G je maximální podgraf G, který je úplným grafem. Počet vrcholů v největší klice nazýváme klikovostí grafu G a značíme ω(G). 163. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice (Obarvení grafu). Nechť G = (V,E) je graf, k přirozené číslo a b zobrazení množiny vrcholů do množiny B = {1,2,…,k} s touto vlastností:

pro každou hranu {x, y} E je b(x) ≠ b(y) . Pak zobrazení b : V → B nazýváme obarvením grafu G pomocí k barev. Minimální počet barev potřebných k obarvení grafu G nazveme barevnost grafu a označíme χ(G).



Tvrzení. Pro graf G bez smyček o n vrcholech platí: 1. χ(G) ≤ n, 2. χ(G) ≥ ω(G), 3. χ(G)α(G) ≥ n, 4. χ(G)+α(G) ≤ n + 1.

.

Důkaz: První tvrzení je zřejmé. Druhé vyplývá z faktu, že všechny vrcholy kliky je třeba obarvit různými barvami. Třetí vyplývá z toho, že stejně obarvené vrcholy tvoří nezávislou množinu. Obarvíme-li tedy graf χ(G) barvami, získáme χ(G) nezávislých množin, z nichž každá obsahuje nejvýše α(G) vrcholů. K důkazu čtvrtého tvrzení obarvíme nejpočetnější nezávislou množinu první barvou. K obarvení zbývajících n – α(G) vrcholů zcela jistě stačí n – α(G) barev. Platí tedy n – α(G) + 1 ≥ χ(G). 165. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Pro libovolný graf G bez smyček platí: 1. χ(G) = 1 právě tehdy, když graf G je diskrétní (bez hran), 2. χ(G) = 2 právě tehdy, když graf G neobsahuje kružnici liché délky, 3. χ(G) = 2 právě tehdy, když graf G je bipartitní. Důkaz: První tvrzení je zřejmé. Druhé tvrzení dokážeme takto: K obarvení kružnice liché délky potřebujeme nejméně 3 barvy. Je-li tedy χ(G) = 2, nemůže graf G takovou kružnici obsahovat. Naopak, nechť graf G neobsahuje kružnici liché délky. Popíšeme, jak lze graf obarvit dvěma barvami. (Je-li graf nesouvislý, obarvíme takto každou komponentu zvlášť.) Zvolme pevně vrchol x. Vrcholy, které mají od vrcholu x lichou vzdálenost (ve smyslu počtu hran v nejkratší cestě), obarvíme barvou 1, vrcholy, které mají sudou vzdálenost (včetně vrcholu x), obarvíme barvou 2. 166. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pokračování důkazu Musíme dokázat, že takto získáme skutečné obarvení, tzn. že žádné dva stejně obarvené vrcholy nejsou spojeny hranou. Vezměme tedy dva libovolné vrcholy u, v, které mají oba lichou vzdálenost od x. Mezi vrcholy u a v vede cesta sudé délky, která je tvořena nejkratšími cestami z u do x a z x do v. Kdyby byly vrcholy u, v spojeny hranou, tvořila by tato hrana spolu s cestou u do v kružnici liché délky. Sestrojili jsme tedy skutečně obarvení dvěma barvami. Třetí tvrzení je snadné. Každé obarvení dvěma barvami určuje rozklad množiny V(G) na dvě disjunktní podmnožiny A a B. Všechny hrany musí vést „přes hranici“ A a B, aby platilo obarvení.. Graf je tedy bipartitní. Je-li naopak graf bipartitní, stačí obarvit každou z jeho stran jednou barvou. 167. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 12 Barevnost mapy – problém čtyř barev 12.2 Obarvení mapy 1/9

Obarvení grafu



Definice (duálního grafu). Buď G = (V,E) topologický rovinný graf a buď S množina stěn grafu G. Definujeme graf G* = (S,E,ε), kde ε je relace na S:

ε(e)= {Si, Sj},

jestliže hrana e je společnou hranicí Si a Sj (přičemž může být i Si = Sj , jestliže hrana e má z obou stran tutéž stěnu). Tento graf G* = (S,E,ε) nazýváme (geometrickým) duálem grafu G.



Konstrukce duálního grafu I. Mějme rovinný graf G. Uvnitř každé stěny S grafu G zvolme bod bS a každé hraně e přiřadíme oblouk protínající hranu e a spojující body bS a bS´ kde S a S´ jsou stěny přiléhající k hraně e. Výsledkem je graf G*, např.:



Konstrukce duálního grafu II.



Tvrzení (vlastnosti duálního grafu). Mějme souvislý rovinný graf G. Duální graf G* má tyto vlastnosti:

1. 2. 3. 4.

Duální graf je také souvislý a rovinný, Duální graf k duálnímu grafu je původní graf (G*)* = G, Dualita převádí vrcholy grafu G na stěny grafu G*, Smyčce v grafu G odpovídá most v grafu G* a naopak.

Tvrzení (problém čtyř barev). Pro každý rovinný graf G platí χ(G) ≤4.

Důkaz tohoto historicky věhlasného tvrzení byl podán teprve nedávno a je mimořádně složitý.

172.



Tvrzení. Pro každý rovinný graf G = (V,E) platí χ ≤5.

Důkaz: Provádí se indukcí podle počtu vrcholů. Pokud je |V| ≤ 5, zvolíme pro každý vrchol jinou barvu. Jestliže je |V| ≥ 6, pak pro jeden z vrcholů je degG(v) ≤ 5. Nechť je degG(v) < 5 a nechť graf G – v je obarvitelný pěti barvami. Pak i graf G je obarvitelný pěti barvami, neboť vrcholu v se přiřadí barva odlišná od barev jeho sousedů. Nedokázán zůstal případ, kdy pro vrchol v je degG(v) = 5. Sousedy vrcholu v označíme po řadě t, u, x, z, y. Opět vyjdeme z předpokladu, že graf G´= G - v je obarven pěti barvami. Je-li |{b(u),b(x),b(y),b(z),b(t)}| < 5, pak vrcholu v přiřadíme některou zbývající barvu. Předpokládejme, že173. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pokračování důkazu |{b(u),b(x),b(y),b(z),b(t)}| = 5, Uvažujme vrcholy x a y a nechť Vx,y je množina všech vrcholů grafu G´, které mají barvu buď b(x) nebo b(y). Samozřejmě je x,y ∈ Vx,y. Nyní rozlišíme dva případy: případ, kdy neexistuje v grafu G cesta z x do y používající pouze vrcholy náležející do Vx,y a případ, kdy taková cesta existuje.



Pokračování důkazu 1. Označíme V´x,y množinu těch vrcholů s V(G´), které jsou v grafu G´spojeny s vrcholem x cestou používající pouze vrcholy z množiny Vx,y. Definujeme nové obarvení b´předpisem b(s) _ pokud__________ ____s ∉Vx′, y  b′(s) = b( y) _ pokud_ s ∈Vx′, y _ a _ b(s) = b(x) b(x) _ pokud_ s ∈V ′ _ a _ b(s) = b( y) x, y 

To znamená, že jsme na množině V´x,y změnili barvy. b´je opět obarvení a protože b´(x) = b´(y) = b(y), můžeme položit b´(v) = b(x) a graf je opět obarven pěti barvami. 175. RNDr. Ivan Havlíček, CSc., [email protected] ::


Pokračování důkazu

Existuje-li cesta P z x do y, jejíž všechny vrcholy jsou prvky množiny Vx,y, potom P spolu s hranami {v,x} a {v,y} tvoří kružnici. Uvážíme dvojici vrcholů t a z. Definujeme množinu Vt,z jako množinu všech takových vrcholů, které jsou obarveny buď barvou b(t) nebo barvou b(z). Množiny Vx,y a Vt,z jsou disjunktní a přitom jeden z bodů t a z leží uvnitř uvedené kružnice a druhý vně. Každá cesta ze z do t musí použít jednoho z vrcholů této kružnice, tedy vrcholu z množiny Vx,y. Z toho plyne že neexistuje cesta z t do z složená pouze z vrcholů množiny Vt,z. Na vrcholy t a z se tedy vztahuje případ 1.



13 Orientované grafy 13.1 Obecné orientované grafy 13.2 Silná souvislost 13.3 Acyklické grafy 13.4 Kořenové orientované stromy


Diskrétní matematika 13 Orientované grafy 13.1 Obecné orientované grafy 1/7

Definice. Orientovaný graf G je dvojice (V,E), kde V je množina vrcholů a E je podmnožina kartézského součinu V × V . Prvky množiny E nazýváme šipky nebo orientované hrany. Šipka e má tvar uspořádané dvojice (x,y) a říkáme, že šipka e vychází z vrcholu x a končí ve vrcholu y. Vrchol, z něhož orientovaná hrana e vychází, nazýváme počátečním vrcholem a značíme Pv(e) a vrchol, v němž hrana e končí, nazýváme koncovým vrcholem a značíme Kv(e).

Definice. Orientovaný tah je posloupnost (v0,e1,v1,…,ek,vk) , pro niž platí, že ei = (vi-1,vi) E pro každé i = 1, 2,…, k a navíc je ei ≠ ej, kdykoli je i ≠ j.



Definice. Orientovaný graf G = (V,E) je eulerovský, když v něm existuje uzavřený orientovaný tah, který obsahuje každou hranu G právě jednou a každý vrchol alespoň jednou.

Definice. Pro daný vrchol v v orientovaném grafu G = (V,E) označíme degG+(v) a nazveme vstupní stupeň vrcholu v počet šipek G, které končí ve v. Obdobně označíme degG-(v) a nazveme výstupní stupeň vrcholu v počet šipek, které začínají ve v. Orientovaný graf G = (V,E) nazýváme vyvážený, jestliže pro každý vrchol v ∈ V platí degG+(v) = degG-(v). 179. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Každému orientovanému grafu G = (V,E) lze přiřadit neorientovaný graf sym(G) = (V,Ē), kde

Ē = {{x,y};(x,y)

E

(y,x)

E}.

Graf sym(G) se nazývá symetrizace grafu G.

Symetrizace grafu G tedy vznikne tak, že v orientovaném grafu G „umažeme hroty šipek“.

Tvrzení. Orientovaný graf je eulerovský právě když je vyvážený a jeho symetrizace je souvislý graf.

180.



Definice (de Bruijnovy posloupnosti). Mějme celé kladné číslo k. De Bruijnova posloupnost je nejdelší cyklická posloupnost nul a jedniček taková, že žádné dvě k-tice po sobě jdoucích cifer nejsou stejné.

Příklad použití: Představme si, že máme na obvod kotouče umístit čísla 0 a 1 tak, že v každé poloze kotouče zjistíme tuto polohu jednoznačně z k-tice po sobě jdoucích čísel. Při daném k chceme navrhnout co největší kotouč. Označíme délku nejdelšího možného cyklického uspořádání (de Bruijnovy posloupnosti) pro dané k symbolem u(k). 181. RNDr. Ivan Havlíček, CSc., [email protected] ::


De Bruijnovy grafy

k=2

tah: 00,01,11,10 posloupnost: 0011

k=3

tah: 000,001,011,111,110,101,010,100 posloupnost: 00011101 182. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Pro každé k ≥ 1 platí u(k) = 2k.

Důkaz: Počet různých posloupností čísel 0 a 1 délky k je 2k. Musí tedy být u(k) ≤ 2k. K důkazu stačí sestrojit u(k) délky 2k Provedeme následující konstrukci orientovaného grafu G = (V,E): • V je množina všech posloupností 0 a 1 délky k – 1; |V| = 2k-1. • Množina šipek E je tvořena množinou všech dvojic tvaru ((a1,…,ak-1),(a2,…,ak)), kde ai je buď 0 nebo 1. Šipky tedy odpovídají posloupnostem tvaru (a1,…,ak) a tudíž |E| = 2k.



Pokračování důkazu

Protože každá k-tice začíná 0 nebo 1, je degG-(v) = 2 a každá k-tice 0 nebo 1 končí, je také degG+(v) = 2 pro každé v. G je tedy vyvážený. Z toho také plyne, že všechny vrcholy grafu sym(G) jsou stupně 2 a sym(G) je tudíž souvislý eulerovský graf. Položíme K = 2k a nechť (1e,…,Ke) je posloupnost šipek v nějakém eulerovském tahu v G. Každá šipka je tvaru ie = (ia1,…,iak). Požadované cyklické uspořádání K číslic 0 a 1 definujeme např. pomocí prvních prvků z každé posloupnosti ie jako (1a1,2a1,…,Ka1). Každá posloupnost délky k se v cyklickém uspořádání (1a1,2a1,…,Ka1) vyskytuje právě jednou. Tím je dokázáno, že u(k) = 2k. 184. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 13 Orientované grafy 13.2 Silná souvislost 1/5

Definice. Orientovaný graf G nazýváme silně souvislým, jestliže pro každou dvojici jeho vrcholů x, y existuje v G orientovaná cesta z x do y a také zpět z y do x. Silně souvislou komponentou grafu G nazýváme podgraf H grafu G, který je silně souvislý a je maximální s touto vlastností (tj. není částí většího silně souvislého podgrafu).

Tvrzení. Na množině vrcholů grafu G definujeme relaci ≈ předpisem x ≈ y právě, když existuje v G orientovaná cesta z x do y a také zpět z y do x. Pak relace ≈ je ekvivalencí.



Tvrzení. Hrana e je obsažena v nějakém cyklu tehdy a jen tehdy, když její počáteční i koncový vrchol leží ve stejné silně souvislé komponentě.

Důkaz: Mějme libovolnou hranu e vedoucí z vrcholu x do vrcholu y. Je-li x = y, pak hrana (smyčka) e je sama cyklus. Je-li x ≠ y je a ležíli x a y ve stejné silně souvislé komponentě, pak musí existovat orientovaná cesta z y do x. Spolu s hranou e tvoří tato cesta cyklus. Obrácená implikace: Je-li naopak hrana e obsažena v cyklu, potom tato hrana je orientovanou cestou z x do y a zbytek cyklu je orientovanou cestou z y do x, tudíž vrcholy x a y leží v téže silně souvislé komponentě. 186. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Kondenzace grafu G je prostý orientovaný graf G´ bez smyček takový, že platí: 1. Vrcholy grafu jsou všechny silně souvislé komponenty grafu G. 2. Vrcholy H1, H2 (které jsou silně souvislými komponentami grafu G) jsou v grafu G´ spojeny orientovanou hranou z H1 do H2 právě tehdy, když H1 ≠ H2 a v grafu G existuje hrana z některého vrcholu silně souvislé komponenty H1 do některého vrcholu silně souvislé komponenty H2.

Tvrzení. Kondenzace orientovaného grafu neobsahuje žádný cyklus. Důkaz: Kdyby kondenzace obsahovala cyklus procházející alespoň dvěma vrcholy, musel by existovat již v původním grafu a procházet mezi silně souvislými komponentami. To je však v rozporu s definicí silně souvislé komponenty. 187. RNDr. Ivan Havlíček, CSc., [email protected] ::




Definice (Dostupnost). Označíme D+(x) = množina všech vrcholů orientovaně dostupných v grafu G z vrcholu x, D-(x) množina všech vrcholů, z nichž je v grafu G orientovaně dostupný vrchol x. Zavedeme matici dostupnosti D takto: dij = 1 je-li vrchol vj orientovaně dostupný z vrcholu vi, dij = 0 jinak.

Tvrzení. Silně souvislá komponenta obsahující vrchol x má množinu . vrcholů rovnu D+(x) ∩ D-(x).


Diskrétní matematika 13 Orientované grafy 13.3 Acyklické grafy 1/4

Definice. Acyklický graf je orientovaný graf, jenž neobsahuje žádný cyklus ani smyčku.

Každá kondenzace je acyklickým grafem.



Tvrzení. Každý acyklický graf G obsahuje alespoň jeden vrchol x, pro který je degG+(x) = 0, a alespoň jeden vrchol y, pro který je degG-(y) = 0.

Důkaz: a) Pro degG+(x): Kdyby pro všechny vrcholy bylo degG+(x) > 0, vycházela by z každého vrcholu alespoň jedna hrana, to znamená, že by bylo možné tvořit sled libovolné délky. Jakmile by však délka tohoto sledu byla větší než |V(G)|, nutně by se vytvořil cyklus. To však acyklický graf vylučuje, a proto musí alespoň pro jeden vrchol být degG+(x) = 0. b) Pro degG-(y) je důkaz obdobný.



Definice. Topologické uspořádání vrcholů grafu G je taková posloupnost v1,v2,…,vn všech vrcholů grafu, že kdykoli vede orientovaná hrana z vi do vj, platí i < j.

Topologické uspořádání hran grafu G je taková posloupnost všech hran grafu e1,e2,…,em, že kdykoli Kv(ei) = Pv(ej), platí i < j.



Tvrzení (vlastnosti acyklických grafů). Nechť G je orientovaný graf. Potom jsou následující podmínky ekvivalentní: 1. Graf G je acyklický. 2. Graf G nemá smyčky a každá jeho silně souvislá komponenta má jen jediný vrchol. 3. Existuje topologické uspořádání vrcholů grafu G. 4. Existuje topologické uspořádání hran grafu G. Důkaz: 1 2: Každá silně souvislá komponenta, která obsahuje alespoň dva vrcholy, obsahuje cyklus. 3 1 a 4 1: Z topologického uspořádání vrcholů a hran vyplývá nepřítomnost cyklů. 1 3 a 1 4: Je-li graf acyklický, pak existuje vrchol v1 , pro který je deg+(v1) = 0. Zařadíme vrchol v1 do posloupnosti vrcholů a odstraníme všechny hrany z něj vycházející a zařadíme je do posloupnosti hran. Zbývající graf je opět acyklický a postup můžeme opakovat. 193. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 13 Orientované grafy 13.4 Kořenové orientované stromy 1/2

Definice. Vrchol x ∈ V(G) je kořen grafu G jestliže DG+(x) = V(G), tj. takový vrchol x, ze kterého je orientovaně dostupný každý vrchol grafu G.

Z definice plyne, že graf může mít buď jeden nebo více kořenů anebo žádný.

Graf se dvěma kořeny (vrcholy b a c).

Tvrzení. Orientovaný graf je silně souvislý právě tehdy, když každý jeho vrchol je kořenem.

194.


Diskrétní matematika 13 Orientované grafy 13.4 Kořenové orientované stromy 2/2

Tvrzení. Nechť G je orientovaný graf s n vrcholy, n ≥ 1. Pak následující tvrzení jsou ekvivalentní: 1. G má kořen a je stromem. 2. G má kořen x a do každého vrcholu vede právě jedna orient. cesta z x. 3. G má kořen a odstraněním libovolné hrany už kořen nemá. 4. G má kořen x takový, že degG-(x) = 0 a pro každý vrchol y ≠ x platí degG-(y) = 1. 5. G neobsahuje cyklus a obsahuje vrchol x takový, že degG-(x) = 0 a pro každý vrchol y ≠ x platí degG-(y) = 1. 6. G má kořen a neobsahuje kružnici. 7. G má kořen a má nejvýše n – 1 hran. 8. G je souvislý a obsahuje vrchol x takový, že degG-(x) = 0 a pro každý vrchol y ≠ x platí degG-(y) = 1. 9. G neobsahuje kružnici a má vrchol x, pro který degG-(x) = 0 a pro 195. každý vrchol y ≠ x platí degG-(y) = 1. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 14 Toky v síti

14 Toky v síti 14.1 Základní pojmy 14.2 Maximální tok a minimální řez


Diskrétní matematika 1.4 Toky v síti

Definice. Mějme orientovaný graf G. Tokem v síti G nazýváme takové ohodnocení hran reálnými čísly f : E(G) → , které pro každý vrchol v splňuje Kirchhoffův zákon

∑

f (e) =

e∈ E + ( v )

∑

f (e)

e∈ E − ( v )

.

Jestliže je splněn Kirchhoffův zákon pro úplně všechny vrcholy gafu G, pak mluvíme o cirkulaci . Je-li splněn Kirchhoffův zákon pro všechny vrcholy grafu G kromě dvou, pak mluvíme o toku od zdroje ke spotřebiči. Ve zdroji tok vzniká a ve spotřebiči se všechen spotřebuje. Neplatnost Kirchhoffova zákona pro celý graf G lze odstranit tzv. návratovou hranou od spotřebiče ke zdroji. 197. RNDr. Ivan Havlíček, CSc., [email protected] ::

Diskrétní matematika 1.4 Toky v síti

Definice. Je-li velikost toku f(e) v jednotlivých hranách omezena, f(e) l(e), c(e) , nazýváme číslo c(e) kapacitou hrany e (horním omezením toku v hraně e) a číslo l(e) dolním omezením toku v hraně e. Tok f, který je mezi těmito omezeními nazýváme přípustným tokem.

Velikost toku od zdroje ke spotřebiči F(f) definujeme jako množství toku, které ve zdroji vzniká

F( f ) =

∑ f (e) − ∑ f (e)

e∈E+ ( z )

e∈E− ( z )



Definice. Nechť A je množina vrcholů. Řez určený množinou A, značíme W(A) je množina hran, jejichž jeden konec leží v množině A a druhý nikoli. Obsahuje-li množina A zdroj, ale ne spotřebič řekneme, že řez W(A) odděluje zdroj a spotřebič. Velikost toku přes řez určený množinou A je množství toku, které hranami řezu proteče z množiny A ven, zmenšené o množství, které se vrací zpět do množiny A

FA ( f ) =

∑

e∈W + ( A)

f (e) −

∑ f (e)

e∈W − ( A)

kde W+(A), resp. W-(A) je množina všech hran, které počínají v množině A a končí mimo A, resp. množina všech hran, které končí v množině A, ale počínají mimo A. 199. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení. Mějme libovolný tok f od zdroje z ke spotřebiči s a mějme libovolný řez W(A) , který odděluje z a s. Pak FA(f) = F(f).

Definice. Kapacita řezu je číslo

C( A) =

∑

c(e) −

e∈W + ( A)

∑l(e)

e∈W − ( A)

Tvrzení. Pro libovolný přípustný tok f a pro libovolný řez W(A) oddělující zdroj a spotřebič je FA(f) ≤ C(A).

Důkaz: Žádný přípustný tok nemůže mít větší velikost, než je kapacita jakéhokoli řezu oddělujícího zdroj a spotřebič. Bylo-li by FA(f) > C(A), nebyl by tok f přípustný, což je spor. 200. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Hrana e může být mimo omezení toku hodnotami l(e) a c(e) ohodnocena ještě číslem a(e), které nazýváme jednotkovou cenou toku v hraně e. Teče-li hranou e tok f(e), pak součin f(e)a(e) nazýváme cenou toku v hraně e. Součet cen toků v jednotlivých hranách

∑

f (e)a (e)

e∈ E ( G )

nazýváme cenou toku v síti.



Definice. Maximální přípustný tok od zdroje ke spotřebiči je přípustný tok f, který má největší velikost F(f). Definice. Minimální řez je řez oddělující zdroj a spotřebič, který má nejmenší kapacitu. Tvrzení. Předpokládejme, že f je přípustný tok ze zdroje z do spotřebiče s a že W(A) je řez, který odděluje zdroj a spotřebič. Jestliže velikost toku f je rovna kapacitě řezu W(A), tj. F(f) = C(A), pak tok f je maximálním tokem ze zdroje do spotřebiče a řez W(A) je minimálním řezem. Důkaz: Velikost žádného přípustného toku nemůže být větší než kapacita řezu W(A), a tedy ani větší než velikost toku f. Tok f je tedy maximální. Podobně, řez W(A) je minimální, protože žádný jiný řez nemůže mít menší kapacitu, než je velikost toku f. 202. RNDr. Ivan Havlíček, CSc., [email protected] ::


Definice. Hranou vpřed nazveme takovou hranu, která je orientována ve směru průchodu cestou. Naopak hrana vzad je orientována proti směru průchodu cestou.

Definice zlepšující cesty. Předpokládejme, že v síti s omezeními toku l a c máme přípustný tok f. Zlepšující cesta vzhledem k toku f je taková neorientovaná cesta ze zdroje z do spotřebiče s, jejíž každá hrana e splňuje:

je-li e hranou vpřed, pak je-li e hranou vzad, pak

f(e) < c(e), f(e) > l(e).



Zlepšující cesta a změna toku. V „čitateli“ jsou omezení toku, ve „jmenovateli“ je velikost toku. Kapacita zlepšující cesty je 2.



Zlepšující cesta a změna toku. V „čitateli“ jsou omezení toku, ve „jmenovateli“ je velikost toku. Kapacita zlepšující cesty je 2.



Algoritmus hledání zlepšující cesty – značkovací procedura.

Inicializace. Označkujeme vrchol z, ostatní vrcholy jsou beze změny. Značkování vpřed. Existuje-li hrana e taková, že Pv(e) má značku, Kv(e) nemá značku a platí f(e) < c(e), pak označkujeme Kv(e). Značkování vzad. Existuje-li hrana e taková, že Kv(e) má značku, Pv(e) nemá značku a platí f(e) > l(e), pak označkujeme Pv(e). Test ukončení. Je-li označkován spotřebič s, značkování končí a zlepšující cesta je nalezena. Není-li spotřebič označkován a nelze-li označkovat další vrchol, značkování končí a zlepšující cesta neexistuje. 206. RNDr. Ivan Havlíček, CSc., [email protected] ::


Fordův-Fulkersonův algoritmus pro maximální tok. Vstup: Orientovaný graf G, zdroj z, spotřebič s, celočíselná omezení toku l a celočíselný přípustný tok f. Výstup: Tok f a množina A V(G) která určuje řez. Úkol: Změnit tok f tak, aby byl maximálním tokem od zdroje z ke spotřebiči s a zároveň najít minimální řez oddělující z a s. Pomocné proměnné: Značky vrcholů a hodnoty ODKUD pro konstrukci cest. Algoritmus: 1. Značkování. Pokud dojde k označkováni spotřebiče s, pokračujeme krokem 2, jinak krokem 3. 2. Změna toku. Zjistíme kapacitu zlepšující cesty (15.2.6) a změníme tok. Pokračujeme krokem 1. 3. Konec výpočtu. Označíme A množinu označkovaných vrcholů. 207. Výpočet končí, f je maximální tok a W(A) je minimální řez. RNDr. Ivan Havlíček, CSc., [email protected] ::


Tvrzení (Fordovo-Fulkersonovo). Velikost maximálního toku od zdroje ke spotřebiči je rovna kapacitě minimálního řezu oddělujícího zdroj a spotřebič.

Důkaz: Vezměme maximální tok a použijme jej jako výchozí tok v předchozím algoritmu. Algoritmus se hned po prvém použití značkovací cesty zastaví a podle věty 15.2.12 najde minimální řez W(A), který má kapacitu velikosti toku .











15 Prohledávání grafu 15.1 Značkování vrcholů 15.2 Prohledávání grafu do šířky 15.3 Prohledávání grafu do hloubky



Algoritmus značkování vrcholů. Mějme graf G = (V,E) a přiřaďme jeho vrcholům značky. Přitom vyjdeme z nějakého výchozího vrcholu r.

1. Inicializace. Označkujeme vrchol r, ostatní vrcholy jsou beze značek. 2. Výběr hrany. Vybereme libovolnou hranu e, jejíž počátek má značku a konec značku nemá. Pokračujeme podle bodu 3. Jestliže žádná taková hrana neexistuje, výpočet končí. 3. Značkování. Označkujeme vrchol Kv(e) a pokračujeme ve výpočtu krokem 2. 214. RNDr. Ivan Havlíček, CSc., [email protected] ::


Algoritmus prohledávání grafu do šířky. Mějme neohodnocený orientovaný graf G = (V,E) a daný jeho vrchol r.

1.Inicializace. Označkujeme vrchol r, ostatní vrcholy jsou beze značek. Položíme VZD(r) := 0 a seznam FRONTA nechť obsahuje jen vrchol r. 1.Test ukončení. Je-li seznam FRONTA prázdný, výpočet končí. 2.Volba vrcholu. Ze začátku seznamu FRONTA odebereme vrchol a označíme jej v. 3.Postup do šířky z vrcholu v. Pro každou hranu e E+(v) označíme w := Kv(e) a jestliže vrchol w nemá značku, položíme ODKUD(w) := e, VZD(w) := VZD(v) + 1 a vrchol w připíšeme na konec seznamu FRONTA. Když projdeme všechny hrany z množiny E+(v), pokračujeme 215. krokem 2. RNDr. Ivan Havlíček, CSc., [email protected] ::


Algoritmus prohledávání grafu do hloubky. Mějme neohodnocený orientovaný graf G = (V,E) a daný jeho vrchol r. Nalezneme všechny vrcholy v, do nichž vede orientovaná cesta z vrcholu r. Budeme vytvářet seznam TRASA, který bude obsahovat vždy posloupnost hran tvořících tzv. aktuální cestu, tj.cestu vedoucí z vrcholu r do aktuálního vrcholu v. Vrcholy, do nichž byla nalezena cesta budeme značkovat podobně jako v algoritmu značkování vrcholů.

1. Inicializace. Položíme v := r, TRASA := 0 a označkujeme vrchol r, ostatní vrcholy jsou beze značek. 2. Volba hrany e. Vezmeme některou dosud nepoužitou hranu e začínající ve vrcholu v a pokračujeme podle kroku 3. Pokud taková hrana neexistuje, pokračujeme podle bodu 5. 216. RNDr. Ivan Havlíček, CSc., [email protected] ::


Algoritmus prohledávání grafu do hloubky - pokračování

3. Test vhodnosti hrany e. Označíme w koncový vrchol hrany e. Je-li vrchol w označkován, pokračujeme krokem 2, jinak krokem 4. 4. Postup do hloubky. Hranu e připíšeme na konec seznamu TRASA, položíme v := w a označkujeme vrchol v. Pokračujeme krokem 2. 5. Návrat z vrcholu v. Není-li seznam TRASA prázdný, odebereme z jeho konce hranu e, její počáteční vrchol nazveme v a pokračujeme krokem 2. Je-li seznam TRASA prázdný, výpočet končí.



Prohledávání do šířky do hloubky



16 Matematické modelování 16.1 Modely a jejich klasifikace 16.2 Operační výzkum a ekonometrie 16.3 Řízení projektů 16.4 Řízení zásob


Diskrétní matematika 16 Matematické modelování





Klasifikace modelů Deterministické a stochastické modely Deterministické modely staví na jednoznačném vztahu příčiny a následku. Stochastické modely jsou založeny na pravděpodobnostech. Statické a dynamické modely Ve statickém modelu čas nevystupuje. Dynamický model vyjadřuje závislosti na čase. Mikroekonomické a makroekonomické modely Mikroekonomické modely se týkají podniku, komodity,spotřebitelů apod. Makroekonomické modely slouží k popisu vývoje celého národního hospodářství.

222.



Matematické modelování = Operační výzkum + Ekonometrie Operační výzkum: Strukturní analýza (1939) Simulační modely (1946) Modely hromadn hromadné obsluhy (1951) Modely řízení zásob (1951) Síťová analýza, řízení projektů (1957)

Teorie her (1944) Lineární programování (1947) Nelineární Neline rn programov programování n (1951) Dynamické programování (1957) Vícekriteriální optimalizace (1970)



Matematické modelování = Operační výzkum + Ekonometrie Operační výzkum: Strukturní analýza (1939) Simulační modely (1946) Modely hromadné obsluhy (1951) Modely řízení zásob (1951) Síťová analýza, řízení projektů (1957)

Teorie her (1944) Lineární programování (1947) Nelineární programování (1951) Dynamické programování (1957) Vícekriteriální optimalizace (1970)







Automobilka plánuje vývoj a sériovou výrobu nového typu osobního automobilu – zjednodušený model











Direktmarketingová firma připravuje pro své zákazníky vydání kolekce českých vánočních koled.









Model s optimální velikostí objednávky Předpoklady •poptávka je v čase konstantní •pořizovací lhůta dodávky je konstantní •čerpání zásob ze skladu je rovnoměrné •velikost všech dodávek je konstantní •nákupní cena je nezávislá na velikosti objednávky •nesmí dojít k nedostatku zásoby •k doplnění skladu dochází v jednom časovém okamžiku 236. RNDr. Ivan Havlíček, CSc., [email protected] ::


Příklad: Pivovar vyrábí 4000 hl piva měsíčně. 25% produkce se prodá v podobě lahvového piva. Prázdné ½ l lahve jsou uloženy v přepravkách po dvaceti, spotřebuje Q= 120000 přepravek/rok. Roční náklady na skladování jedné přepravky jsou 20 Kč. Dodavatel lahví si účtuje 11000 Kč za dodávku a pivovar musí navíc zaúčtovat 1000 Kč za každou objednávku jako vlastní fixní náklady. Doba mezi objednávkou a dodávkou je 0,5 měsíce, tedy d = 1/24roku.



















Hodně úspěchů na VSFS a děkuji za pozornost










Diskrétní matematika DISKRÉTNÍ MATEMATIKA. RNDr. Ivan Havlíček, CSc., ::

Recommend Documents