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

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika DISKRTN MATEMATIKA

pro obor aplikovan informatika

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika

diskrtn

1. ohledupln, taktn2. zachovvajc tajemstv3. nespojit, petrit

Akademick slovnk cizch slov (1998):


LiteraturaBerka, 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 VB, TU Ostrava, skripta.Fbry, J., Matematick modelovn, Nakladatelstv Oeconomica, VE FIS, Praha 2007.Hlinn, P., Diskrtn matematika, FEI VB, TU Ostrava 2005, (http://cs.vsb.cz/hlineny/vyuka/DIM-slides/DIM-text05.pdf). Konopk, M., Abstraktn datov typ graf vod do teorie graf, KIV, ZU. (http://www.kiv.zcu.cz/~konopik/sem/cech/index.html).Kovr, M., Diskrtn matematika, FIT VUT, Brno 2002. (http://www.umat.feec.vutbr.cz/~kovar/webs/vyuka/fit/2006/ida/soubory/IDM.pdf). Kovr, M., Cvien zdiskrtn matematiky, FIT VUT, Brno 2003, (http://www.umat.feec.vutbr.cz/~kovar/webs/vyuka/fit/2006/ida/soubory/IDMCV.pdf). Kov, P., Diskrtn matematika, FAM VB, TU Ostrava (http://homel.vsb.cz/~kov16/predmety_dm.php).Kemen, J.,Modely a systmy,Academia a MT, Praha 2007.Matouek, J. a Neetil,J., Kapitoly zdiskrtn 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.Ryjek, Z., Teorie graf a diskrtn optimalizace, KMA ZCU 2005, (http://www.kma.zcu.cz/TGD1).


1 Matematick logika

1.1 Vroky a sudky 1.2 Vrokov logika 1.3 Prediktov logika

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.1 sudky a vroky 1/4Definice. Vrokem je jakkoli tvrzen, o kterm lze ci, e je pravdiv nebo, e je nepravdiv.

sudkem nazvme duevn postup, pi nm usuzujeme na pravdivost vroku A na zklad pravdivosti vrok B1, B2,, Bn. Vroky B1, B2,, Bn nazvme pedpoklady neboli premisy a vrok A nazvme zvr. Peme B1, B2,, Bn A.

Definice.sudek B1, B2,, Bn A je platn, jestlie zvr A logicky vyplv z pedpoklad B1, B2,, Bn. Platn sudek zname B1, B2,, Bn |= A.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.1 sudky a vroky 2/4

Nkolik platnch sudk.

Vichni psi tkaj. Pudl je pes. Pudl tk.

V seznamu novodobch mskch csa nen dn ena. Marie Terezie byla ena. Marie Terezie nebyla msk csaovna.

Je doma nebo odeel do kavrny. Je-li doma, pak ns oekv. Jestlie ns neoekv, pak odeel do kavrny.

Je-li tento kurz dobr, pak je uiten. Bu je pednejc shovvav, nebo je tento kurz neuiten. Ale pednejc nen shovvav. Tento kurz je patn.


Definice. Jestlie je vrok A pravdiv za vech okolnost, kme, e je platn, nebo e je tautologi a zname |= A.

Jestlie pedpoklady v mnoin {B1 ,B2 ,..., Bn} nemohou bt souasn vechny splnny, kme, e mnoina {B1 ,B2 ,..., Bn} je kontradiktorick (sporn, nesplniteln). Kontradikci zname {B1 ,B2 ,..., Bn} |=.

Z kontradiktorick mnoiny premis plyne jakkoli zvr.


Vlastnosti deduktivnch sudk.Logicky sprvn sudek me mt nepravdiv zvr (nap.: Vechny kobry jsou jedovat. Tato hl je kobra. Tato hl je jedovat.) V takovm ppad vak mus bt nkter z pedpoklad nepravdiv.

Jestlie plat B1, B2,, Bn |= A, plat i B1, B2,, Bn, Bn+1 |= A pro libovoln dal pedpoklad Bn+1. Tato vlastnost zvru se nazv monotnnost.Jestlie plat B1, B2,, Bn |= A a C1, C2,, Cn |= A , pak plat B1, B2,, Bn, C1, C2,,Cn |= A a zrove B1, B2,, Bn, C1, C2,, Cn |= A . Tato vlastnost se nazv tranzitivita.Jestlie je A rovno jedn z premis B1, B2,, Bn, pak plat B1, B2,, Bn |= A. Tato vlastnost se nazv reflexivita.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.2 Vrokov logika 1/7

Definice jazyka vrokov logiky

Abeceda jazyka vrokov logiky je mnoina nsledujcch symbol:

Vrokov symboly p, q, r,A, B,.

Symboly logickch spojek (funktor) , , ,, .

Pomocn symboly (zvorky) ( ),[ ],{ },....

Symboly , , , , nazvme po ad funktory negace, konjunkce, disjunkce, implikace, ekvivalence.


Definice jazyka vrokov logiky - pokraovn

Gramatika jazyka vrokov logiky rekurzivn definuje formule:

1. Vrokov symboly jsou formule.

2. Jsou-li A, B formule, pak jsou formulemi i vrazy (A), (A B), (A B), (A B), (A B).

3. Jinch formul vrokov logiky ne tch, kter vzniknou aplikac podle bod 1. a 2., nen.

Jazyk vrokov logiky je mnoina vech formul vrokov logiky.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.2 Vrokov logika 3/7Definice logickch funktor

Negace vroku A se zna A a znamen nen pravda, e.Konjunkce vrok A a B se zna A B a znamen, e plat zrove A a zrove B.Disjunkce (alternativa) vrok A a B se zna A B a znamen, e plat bu A nebo B (nebo oboj).Implikace: Vyplv-li z vroku A vrok B, kme, e z A plyne B nebo e A implikuje B nebo jestlie A, pak B nebo kdy A, tak B, a peme A B.Ekvivalence nastane, plat-li zrove A B a B A a kme, e vroky A a B jsou ekvivalentn, a zname A B . Ekvivalenci teme tak: B plat prv, kdy plat A nebo B plat tehdy a jen tehdy, plat-li A.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.2 Vrokov logika 4/7Definice smantiky vrokov logikyInterpretace pravdivostn ohodnocen (valuace) J piazuje kad formuli pravdivostn hodnotu z mnoiny {1,0}, kter kduje mnoinu {pravda, nepravda}. Tautologie je formule, kter nabv hodnoty pravda pi kad interpretaci.Kontradikce je formule, kter nabv hodnoty nepravda pi kad interpretaci.Pravdivostn tabulka A BA BA BABAB 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1


Zjistme, zda mnoina formul M ={p r, q r, p q} je splniteln, tj zda plat p r, q r, p q |= r

pqrp r q r p q111 1 1 1110 0 0 1101 1 1 1100 0 1 1011 1 1 1010 1 0 1001 1 1 0000 1 1 0

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.2 Vrokov logika 6/7Seznam nkterch tautologi A) Tautologie s jedinm vrokovm symbolem: ( p p) zkon sporu ( p p) zkon vylouenho tetho p p zkon totonosti p p zkon dvoj negace p ( p p) zkon idempotence p ( p p) zkon idempotenceB) ( p p) q zkon Dunse Scota p (q p) zkon simplifikace ( p q)(q p) zkon kontrapoziceC) De Morganovy zkony:( p q) (p q)( p q) (p q)

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.2 Vrokov logika 7/7Pevod z pirozenho jazyka do jazyka vrokov logikyJe doma (p) nebo odeel do kavrny (p). Je-li doma, pak ns oekv (q). Jestlie ns neoekv, pak odeel do kavrny. ( p q) (q p)

Pevod z pirozenho do symbolickho jazyka nemus bt vdy zcela jednoznan.Jestlie m lovk vysok tlak (p) a patn se mu dch (q) nebo m zvenou teplotu (r), pak je nemocen (s). Meme pevdt jako1. monost: [(p q) r] s 2. monost: [p (q r)] s.Ob formule jsou rzn, ob vyhovuj zadn, ale ze zadn nepoznme, jak bylo tvrzen myleno.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.3 Prediktov logika 1/6Definice jazyka prediktov logiky

Abeceda prediktov logiky (nsledujc symboly): a. Logick symbolyi. individuov promnn x,y,z, individuov konstanty a,b,c, .ii. symboly pro spojky ,,,,,iii. symboly pro kvantifiktory ,,iv. ppadn binrn prediktov symbol = (prediktov logika s rovnost). b. Speciln symbolyi. prediktov symboly p,q,r,,ii. funkn symboly f,g,h,. c. Pomocn symboly zvorky.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.3 Prediktov logika 2/6

Definice jazyka prediktov logiky - pokraovnII) Gramatika, kter udv, jak tvoit a. termy: jsou promnn nebo konstanty b. atomick formule: i. je-li p n-rn prediktov symbol a jsou-li t1,,tn termy, pak vraz p(t1,,tn) je atomick formule, ii. jsou-li t1 a t2 termy, pak vraz (t1 = t2) je atomick formule. c. formule: i. kad atomick formule je formule, ii. je-li vraz A formule, pak A je formule, iii. jsou-li A a B formule, pak vrazy (A B),(A B),(A B) , (A B) jsou formule, iv. je-li x promnn a A formule, pak vrazy xA a xA jsou formule, v. jen vrazy dle i. iv. jsou formule.


Kvantifiktory.

Kvantifiktor nazvme obecnm (velkm) kvantifiktorem a vyjaduje kad; dn; vechna; kterkoli; libovoln;.

Kvantifiktor je existennm (malm) kvantifiktorem a vyjaduje existuje; nkter; lze nalzt; alespo jeden;. Nkdy se pouv ! pro vyjden existuje prv jeden.

*.RNDr. Ivan Havlek, CSc., [email protected] ::

Diskrtn matematika 1. Matematick logika 1.3 Prediktov logika 4/6

Univerzum. Univerzum je mnoina individu, kter spadaj do naeho uvaovn. Mme- li na mysli nap. ti dvky, Annu, Bru a Gabrielu, pak tyto ti dvky tvo nae univerzum U. Dvky po ad ozname , , , tedy U ={ , ,}.

Predikt. Prediktov symbol je vraz oznaujc predikt, tedy vlastnost nebo vztah, kter lze vypovdt (predikovat) o individuu. Vlastnost bt dvka je predikovateln o tech individuch nmi uvaovanho univerza a peme P(x).


Pklady pevodu z pirozenho jazyka do symbolickho jazyka prediktov logiky

1) Nikdo, kdo nen zapracovn (P), nepracuje samostatn (S).x[P(x) S(x)]

2) Ne kad talentovan (T) spisovatel (Sp) je slavn (Sl).x{[T(x) Sp(x)] Sl(x)}

3) Pouze zamstnanci (Z) pouvaj vtah (V). x[V (x)Z(x)]

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 1. Matematick logika 1.3 Prediktov logika 6/6Pklady pevodu z pirozenho jazyka do symbolickho jazyka prediktov logiky - pokraovn

4) Ne kad lovk (C), kter hodn mluv (M), nem co ci (R).x{[C(x) M(x)] R(x)}

5) Nkdo je spokojen (Sn) a nkdo nen spokojen. xSn(x) ySn( y)

6) Nkte chyt lid (Ch) jsou ln (L). x[Ch(x) L(x)]

7) Vichni zamstnanci (Z) pouvaj vtah (V). x[Z(x)V(x)]


2 Dokazovn vdiskrtn matematice

2.1 Stavba matematiky 2.2 Matematick dkazy

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 2 Dokazovn v diskrtn matematice 2.1 Stavba matematiky

Ucelenou matematickou teorii tvo:

- axiomy,- definice,- vty neboli tvrzen,- lemmata, matematick dkazy.


Axiomy mnoiny pirozench selGiuseppe Peano 1891

P1. Existuje pirozen slo, kter nen nslednkem dnho pirozenho sla. Nazveme ho 1.

P2. Kad pirozen slo m prv jednoho nslednka.

P3. Kad pirozen slo je nslednkem nejve jednoho pirozenho sla.

P4. Kad mnoina, kter obsahuje pirozen slo 1 a skadm pirozenm slem obsahuje i jeho nslednka, je mnoinou pirozench sel.


Eukleidovy axiomyKonec 4. stol. ped n.l.E1. Od kadho bodu ke kadmu lze vst pmou spojnici.

E2. Ohranienou spojnici lze libovoln prodlouit.

E3. Z kadho stedu a polomru lze narsovat krunici.

E4. Vechny prav hly jsou navzjem shodn. E5. Danm bodem lze s danou pmkou vst prv jednu rovnobku.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 2 Dokazovn v diskrtn matematice 2.2 Matematick dkazy 1/5

Dkaz je posloupnost ovitelnch elementrnch krok, kter pomoc ji dokzanch fakt (pop. axiom) podle logickch pravidel dospj k poadovanmu tvrzen (vt).

Rozliujeme:

a) dkaz pevedenm na znm (ji dokzan) tvrzen, b) nepm dkaz, c) dkaz sporem, d) dkaz matematickou (tzv. plnou) indukc, e) dkaz konstrukc nebo potnm.


Diskrtn matematika 2 Dokazovn v diskrtn matematice 2.2 Matematick dkazy 2/5

Dkaz pevedenm na znm tvrzen provdme postupnmi implikacemi z pedpokladu A (jednoho nebo vce) A B , B C , ,Y Z a dojdeme k danmu tvrzen Z.

Tvrzen: hlopky v kosotverci se navzjem pl a jsou k sob kolm.Dkaz: Z definice kosotverce plyne, e strany jsou stejn dlouh a po dvou rovnobn. hlopky vytvo se stranami tyi trojhelnky. Dva protilehl trojhelnky vytvo mezi hlopkami a stranami kosotverce dv dvojice stejnch stdavch hl. Podle vty s jsou tyto trojhelnky shodn. Pak podle vty sss jsou s nimi shodn i zbvajc trojhelnky. Z toho plyne, e se hlopky pl. V prseku hlopek se stkaj tyi shodn hly, mus tedy bt prav.



Dkaz sporem. Msto implikace AB dokazujeme (A B)C ,kde C je jasn nepravdiv vrok nebo je ve sporu s pedpokladem. Tm jsme doli ke sporu a tud AB .

Tvrzen: Mezi pirozenmi sly menmi ne 8 je nejv5 prvosel.Dkaz: Pedpokldejme pro spor, e je jich 6. Pak mezi nimi mus bt nejmn dv sla sud, jedno rovn dvma a druh tedy rzn od dvou, kter tud nen prvoslo, a to je spor s pedpokladem o esti prvoslech. Tm je tvrzen dokzno.



Matematick indukce.

Mjme tvrzen P(n) s pirozenm (nebo celoselnm) parametrem n.

Nech plat:

Tvrzen P(n) je pravdiv pro nejmen ppustn n. Toto tvrzen nazvme zklad indukce.

2) Pro libovoln pirozen (i cel) n0 plyne z platnosti P(n0) tak platnost tvrzen P(n0 + 1).

Pak P(n) plat pro vechna pirozen (i cel) n.



Tvrzen: Vztah

plat pro libovoln n.Dkaz: Nejprve ukeme dosazenm, e vztah plat pro nejmen uvaovan n, v naem ppad n = 1. V druhm kroku vyjdeme z platnosti vztahu pro njak n0 a dokeme, e plat i pro n = n0 + 1. Tedy

co je pvodn vraz pro n = n0 + 1 a tvrzen je dokzno.


3 Mnoiny

3.1 Zkladn mnoinov operace 3.2 sla a seln mnoiny 3.3 Princip inkluze a exkluze 3.4 Kartzsk souin

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 3. Mnoiny3.1 Zkladn mnoinov operace 1/7Definice Ozname X = {x} mnoinu X obsahujc prvky x; tak peme x X .Mnoinu, kter nem dn prvek, nazvme przdnou mnoinou a zname ji .

Podmnoina X mnoiny Y je jej st: X Y (xX xY)

Rovnost mnoin X a Y nastane, maj-li stejn prvky:

X = Y X Y Y X

Sjednocen mnoin je mnoina Z obsahujc prvky, kter jsou bu prvky X nebo prvky Y (nebo obou):

X Y ={(xX yY)}


Diskrtn matematika 3. Mnoiny3.1 Zkladn mnoinov operace 2/7

Definice - pokraovnPrnik mnoin X a Y je mnoina Z obsahujc prvky, kter jsou prvky X a zrove prvky Y:

X Y ={a (aX aY)}

Mnoiny, jejich prnik je przdn mnoina, nazvme disjunktn.

Rozdl mnoin X a Y je mnoina Z obsahujc prvky, kter jsou prvky X a nejsou prvky Y :

X \Y ={a X a Y}

Jestlie je Y X , pak Y = X \Y nazvme doplkem mnoiny Y v mnoin X.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 3. Mnoiny3.1 Zkladn mnoinov operace 3/7

Vennv diagram: a) A B b) A B c) A \ Bd) doplnk B v A


Vlastnosti mnoinovch operac.

Nech A, B, C jsou mnoiny. Pak plat:

1. A B = B A komutativn zkony

2. AB = B A

3. (A B)C = A(B C) asociativn zkony

4. (A B)C = A(B C)

5. (A B)C =(AC)(B C) distributivn zkony

6. (A B)C =(AC)(B C)



Pro konenou mnoinu X budeme symbolem |X| oznaovat jej mohutnost neboli poet prvk. Je-li mohutnost |X| sud, kme, e mnoina X je sud velikosti, je-li lich, kme, e X je lich velikosti.


Poet podmnoin - 1

Tvrzen: Nech mnoina X m n prvk. Pak X m 2n podmnoin .Dkaz: 1. Pro n = 0 tvrzen plat, nebo przdn mnoina m jedinou, opt przdnou, podmnoinu.2. Nech plat dokazovan tvrzen pro n 0 . Vezmeme libovoln prvek a X , kde |X| = n +1. Utvome mnoinu X = X \{a}, take |X | = n , pro n podle pedpokladu tvrzen plat. Uvaujme libovolnou, pevn zvolenou podmnoinu P X a mme dv monosti: bu je a P nebo je a P .Nen-li a P , je P podmnoinou X a takovch P je podle induknho pedpokladu 2n . Je-li a P , je P = P \{a} podmnoinou Xa takovch P je opt 2n . Dohromady je tedy 2n+1 monost volby P X.



Poet podmnoin - 2

Tvrzen: Kad n-prvkov ( n 1) mnoina m prv 2n-1 podmnoin sud velikosti a 2n-1 podmnoin lich velikosti.

Dkaz: Opt pomoc matematick indukce. 1. Pro n = 1 tvrzen plat, nebo jednoprvkov mnoina m jednu podmnoinu lich velikosti (przdnou) a jednu sud velikosti (przdnou a s jednm prvkem). 2. Nech mnoina X m libovoln zvolen poet prvk n a plat pro ni dokazovan tvrzen. pedchoz tvrzen.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 3. Mnoiny3.2 sla a seln mnoiny 1/5

Mnoina pirozench sel je {1,2,3,4,5,...} a zname ji .Interval pirozench sel a < b zname

[a,b] = {a,a +1,...,b 1,b}.

Cel st sla x se zna takto: x. Znamen to, e nap. 3,14159 = 3.

Mnoina celch sel se zna = {,-3,-2,-1,0,1,2,3,}

V diskrtn matematice se pracuje s pirozenmi sly rozenmi o nulu, tj. {0,1,2,3,4,5,...}


Diskrtn matematika 3. Mnoiny3.2 sla a seln mnoiny 2/5

Racionln sla jsou sla, kter vzniknou podlem dvou celch sel (krom dlen nulou). Jejich desetinn vyjden m konen poet nenulovch desetinnch mst nebo je ukoneno opakujc se skupinou slic - periodou.

Iracionln sla jsou ta sla, kter nelze vyjdit jako podl dvou celch sel. Maj nekonen mnoho slic za desetinou rkou, je se neopakuj. Iracionln je vtina odmocnin, hodnot goniometrickch funkc, logaritm apod.Racionln a iracionln sla dohromady tvo reln sla .



Spoetn mnoina je mnoina, jej prvky dokeme seadit do poad oslovanho pirozenmi sly. Mnoiny, kter nejsou spoetn, oznaujeme jako nespoetn.

Mnoina pirozench sel, a nekonen, je spoetn. Jej mohutnost oznaujeme prvnm kardinlnm slem 0 (alef nula).

Tvrzen: Racionlnch sel je spoetn mnoho.

Dkaz: Racionln sla seadme 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 seazen racionln sla se daj oslovat.



Tvrzen. Relnch sel je nespoetn mnoho.Dkaz: Dokeme, e i v intervalu (0,1) je nespoetn mnoho relnch sel. K dkazu sporem vyjdeme z pedpokladu, e relnch sel v (0,1) je spoetn mnoho. Pak existuje zpsob, jak je seadit za sebou jako pirozen sla. Nech je to toto uspodn

kde aij jsou sla 0, 1, 2,,9 a k,l jsou pirozen sla.



Pokraovn dkazu: Budeme uvaovat nsledujc slo

b = 0,b1 ,b2 ,

podle pravidla: Je-li na m-tm desetinnm mst sla am slo 5, bude bm = 4, nen-li na m-tm desetinnm mst sla am slo 5, bude bm = 5.Takto utvoen slo b se nutn li od sla am na m-tm desetinnm mst pro libovoln m. Li se tedy od vech sel, kter jsou vpedpokldanm uspodn, to znamen e pedpoklad o spoetnosti relnch sel intervalu (0,1) byl nesprvn. Sprvn je tedy dokazovan tvrzen tj., e relnch sel je nespoetn mnoho.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 3 Mnoiny3.3 Princip inkluze a exkluze

Tvrzen (Princip inkluze a exkluze). Mjme mnoiny Ai , i = 1,,n a uvaujme vechny neprzdn podmnoiny I {1,,n}. Pak pro mohutnost sjednocen mnoin plat

|A1 A2| = |A1| + |A2| - |A1 A2|

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

..atd.


Diskrtn matematika 3. Mnoiny3.4 Kartzsk souin

Uspodan dvojice, je dvojice prvk (x,y), u n zle na poad x a y.

Kartzsk souin mnoin X a Y , XY, je mnoina vech uspodanch dvojic (x,y), kde xX a yY.


4 Relace

4.1 Binrn relace 4.2 Ekvivalence4.3 Zobrazen 4.4 Skldn zobrazen 4.5 Relace uspodn


Diskrtn matematika4 Relace4.1 Binrn relace Definice. Binrn relace R mezi dvma mnoinami X a Y je mnoina uspodanch dvojic (x,y), kde x X a y Y. R je tedy podmnoinou kartzskho souinu. Vznikne-li dvojice (x,y) relac R, kme, e (x,y) nle R a peme (x,y) R nebo jednodue xRy.

Definice. Relace na mnoin X je mnoina dvojic prvk X. Matice sousednosti relace R na mnoin X o n prvcch je n n matice A = (aij) , kde

aij = 1 jestlie (xi,yj) R,aij = 0 jestlie (xi,yj) R.


Diskrtn matematika 4 Relace4.2 Ekvivalence 1/2

Definice. Relace R na mnoin X je reflexivn, jestlie pro kad x X plat xRx, je symetrick, jestlie kdykoliv plat xRy, plat i yRx,je transitivn, jestlie ze vztah xRy a yRz plyne xRz.

Relace R na X, kter je reflexivn, symetrick a transitivn se nazv ekvivalence na X.

Nech R je ekvivalence na mnoin X, nech x je libovoln prvek X. Ozname symbolem R[x] mnoinu vech prvk y, kter jsou ekvivalentn sx. R[x] se nazv tda ekvivalence R uren prvkem x.


Diskrtn matematika4 Relace4.2 Ekvivalence 2/2

Tvrzen. Pro kadou ekvivalenci R na mnoin X plat:

1) R[x] je neprzdn mnoina pro kad prvek x X.

2) Pro kad dva prvky x,y mnoiny X je bu R[x] = R[y] nebo je R[x] R[y] = (przdn mnoina).

3) Tdy ekvivalence jednoznan uruj R.

Dkaz: Plyne z definice ekvivalence.


Diskrtn matematika4 Relace4.3 Zobrazen Definice. Zobrazen f mnoiny X do mnoiny Y je relace f X Y, pro kterou plat, e pro kad prvek x X existuje prv jedin prvek y Y tak, e xfy; peme y = f(x), nebo tak f : X Y.

Definice. Zobrazen nazvme

prost (neboli injektivn), jestlie pro x y je f(x) f(y),

b) zobrazen na (neboli surjektivn), jestlie pro kad y Y existuje x X splujc rovnost f(x) = y a

c) vzjemn jednoznan zobrazen (neboli bijektivn), jestlie f je prost a na a peme f : X Y.


Diskrtn matematika4 Relace4.4 Skldn zobrazen Definice. Jsou-li f : X Y a g : Y Z zobrazen, pak lze pro vechna x X definovat zobrazen h : X Z takto h(x) = g(f(x)).Zobrazen h nazvme sloenm zobrazen f a g a budeme ho znait g f.

Tvrzen. Nech f : X Y a g : Y Z jsou zobrazen. Pak plat:

Jsou-li f, g prost zobrazen, je rovn g f prost zobrazen.Jsou-li f, g zobrazen na, je rovn g f zobrazen na.Jsou-li f, g zobrazen vzjemn jednoznan, je rovn g f zobrazen vzjemn jednoznan.Pro kad zobrazen f : X Y existuj mnoina Z, prost zobrazen h : Z Y a zobrazen na g : X Z tak, e f = h g.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 4 Relace4.5 Relace uspodn 1/4Definice. Relace R na mnoin X se nazv slab antisymetrick, jestlie pro kad x, y X plat, e pokud xRy a zrove yRx, potom mus bt x = y.Relace R na mnoin X se nazv (siln) antisymetrick, jestlie pro kad plat, e pokud xRy, pak mus bt (yRx).Relace R na mnoin X se nazv antireflexivn, jestlie pro kad je (xRx).

Definice. Uspodn (slab) na njak mnoin X je kad relace na X, kter je reflexivn, slab antisymetrick a tranzitivn. Upodan mnoina je dvojice (X,R), kde X je mnoina a R je uspodn na X.Ostr uspodn je relace, kter je antireflexivn, tranzitivn a antisymetrick.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 4 Relace4.5 Relace uspodn 2/4Pro relace uspodn se pouvaj symboly


Diskrtn matematika4 Relace4.5 Relace uspodn 3/4 Definice. kme, e prvky a, b vstenm uspodn jsou neporovnateln, pokud neplat ani jedno z a b a b a.kme, e posloupnost tvo etzec vstenm uspodn pokud .kme, e prvek m je nejmen vstenm uspodn mnoiny A, pokud kad jin prvek je vt ne m, tj. . Nejvt prvek vstenm uspodn definujeme analogicky knejmenmu prvku.

Definice. Nech (X,) je uspodan mnoina. ekneme, e prvek x je bezprostednm pedchdcem prvku y a budeme znait xy, jestlie a neexistuje dn prvek z X takov, e xzy.


Diskrtn matematika4 Relace4.5 Relace uspodn 4/4

Tvrzen. Nech (X, ) je konen uspodan mnoina a je pslun relace bezprostednho pedchdce. Potom pro libovoln dva prvky x,y X a k plat, e x y prv, kdy existuj prvky x1,xk X takov, e x x1 xk y Je-li k = 0, je pmo x y.

Dkaz: Jedna implikace je zejm: mme-li x x1 xk y, pak podle definice je i xx1xky.Opanou implikaci dokeme indukc podle k.


5 Kombinatorick potn

5.1 Podmnoiny 5.2 Permutace 5.3 Kombinan sla 5.4 Binomick vta

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika5 Kombinatorick potn5.1 Podmnoiny 1/2Tvrzen. Nech N je njak n-prvkov mnoina n 0 a M je m-prvkov mnoina m 1. Pak poet vech zobrazen f : N M je mn.

Dkaz: Provedeme jej indukc podle n. Pro n = 0 se jedn o zobrazen (relaci) przdn mnoiny. Takov relace je jedna, toti przdn. Tvrzen tedy plat pro n = 0.Pedpokldejme, e tvrzen plat pro vechna n n0 a pro kad m. Mjme nyn n = n0 + 1-prvkovou mnoinu N a m-prvkovou mnoinu M. Zvolme libovoln jeden prvek a N. Zadat zobrazen f : N M znamen zadat hodnotu f(a) M a f : N\{a} M zobrazen zbvajcch prvk. Hodnotu f(a) meme zvolit m zpsoby a pro volbu f mme podle induknho pedpokladu mn-1 monost. Kadou volbu f(a) meme kombinovat sf , take mme celkem m. mn-1 - mn monost pro f.


Diskrtn matematika5 Kombinatorick potn5.1 Podmnoiny 2/2 Tvrzen. Pro m,n 0 existuje prv

prostch zobrazen n-prvkov mnoiny do m-prvkov mnoiny.

Dkaz: Tvrzen se jednodue doke indukc. Zkusme n = 0: przdn zobrazen je prost. Mjme nyn n-prvkovou mnoinu N, n 0 a m-prvkovou mnoinu M, m n. Vybereme prvek a N a zvolme jeho funkn hodnotu f(a) M libovoln, jednm zm zpsob. Zbv zobrazit prostm zobrazenm prvky mnoiny N\{a} do mnoiny M\{f(a)}. Takovch prostch zobrazen je podle induknho pedpokladu . Celkem tedy je m prostch zobrazen m .


Diskrtn matematika5 Kombinatorick potn5.2 Permutace Definice. Prost zobrazen konen mnoiny X do sebe se nazvaj permutace mnoiny X.

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

Tvrzen. Zobrazen podle pedchoz definice jsou zrove na.


Diskrtn matematika5 Kombinatorick potn5.3 Kombinan sla 1/5 Definice. Nech n a k jsou nezporn sla. Binomick koeficient neboli kombinan slo je funkce promnnch n, k definovan vzorcem

.Takov kombinan slo teme n nad k.

Definice. Nech X je mnoina a kcel nezporn slo. Symbolem budeme znait mnoinu vech k-prvkovch podmnoin mnoiny X.

Specieln budeme oznaovat mnoinu vech dvouprvkovch

podmnoin mnoiny X.


Diskrtn matematika5 Kombinatorick potn5.3 Kombinan sla 2/5 Tvrzen. Pro kadou konenou mnoinu X je poet jejch k-

prvkovch podmnoin roven . ili , anebo je poet

vech k-prvkovch podmnoin n-prvkov mnoiny.Dkaz: Ozname n = |X|. Budeme dvma zpsoby potat vechny uspodan k-tice, kter lze utvoit zprvk mnoiny X (bez opakovn). Na jedn stran tento poet podle tvrzen je n(n -1) (n k + 1). Na

druh stran zjedn k-prvkov podmnoiny meme vytvoit k!

rznch uspodanch k-tic a kadou uspodanou k-tici dostaneme znjak podmnoiny prv jednou. Take

.


Diskrtn matematika5 Kombinatorick potn5.3 Kombinan sla 3/5 Definice. O permutacch sopakovnm mluvme vppad, e seazujeme dan prvky do posloupnosti, ve kter prvky maj pedepsan nenulov poet identickch kopi (tzn. prvky se opakuj).

Tvrzen. Poet vech permutac sopakovnm zkprvk, kde se i-t prvek opakuje mi-krt pro i = 1,,k, je


Diskrtn matematika5 Kombinatorick potn5.3 Kombinan sla 4/5

Pklad. Kolika rznmi zpsoby meme seadit do posloupnosti psmena souslov DISKRETNIMATEMATIKA?een: Pouijeme metodu dvojho potn. Poet vech seazen bez ohledu na to zda se nkter psmena opakuj (jako bychom si je oslovali): Ozname x vsledn poet rznch seazen danch psmen, (vtomto potu se nesm odrazit skutenost, e se nkter psmena vyskytuj vce ne jednou). Abychom tedy dostali hledan poet seazen, vynsobme slo x jet 3! za permutace psmen A, 3! za permutace psmen I, atd. Zrove vak stejn poet dostaneme jako poet permutac 19-ti sel. Mme tedy

z toho.


Diskrtn matematika5 Kombinatorick potn5.3 Kombinan sla 4/4 Zkombinanch sel meme tvoit Pascalv trojhelnk

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika5 Kombinatorick potn5.4 Binomick vtaTvrzen (Binomick vta) Binomick vta (ve specielnm tvaru) k, e pro n 0 plat

.Dkaz: Pi algebraickm souinu binom vyuvme pravidlo nsobit kad len skadm. To znamen, e vrozvoji

nm len xk vyjde tolikrt, kolikrt lze vybrat (neuspodanou) k-

tici zn len. To je prv krt .


6 Diskrtn pravdpodobnost

6.1 Konen pravdpodobnostn prostory 6.2 Nezvisl jevy 6.3 Nhodn vbry 6.4 Stedn hodnoty


Diskrtn matematika6 Diskrtn pravdpodobnost6.1 Konen pravdpodobnostn prostory 1/2 Definice. Pod pojmem konen pravdpodobnostn prostor rozumme dvojici (,P), kde je konen mnoina a P je zobrazen piazujc kad podmnoin mnoiny slo zintervalu , takov, e

1. P() = 0,2. P() = 1,3. P(AB) = P(A) + P(B) pro libovoln mnoiny A, B a AB = .

Prvky mnoiny se nazvaj elementrn jevy a P se nazv funkce pravdpodobnosti.


Diskrtn matematika6 Diskrtn pravdpodobnost6.1 Konen pravdpodobnostn prostory 2/2 Tvrzen. Pro libovoln mnoiny m funkce pravdpodobnosti tyto dal vlastnosti:

1.

2. je-li pak je ,

3. .


Diskrtn matematika6 Diskrtn pravdpodobnost6.2 Nezvisl jevy 1/2 Definice. Podmnn pravdpodobnost, e nastane jev A za pedpokladu, e jev B nastal je (pedpokldme, e )

Definice. Nech . Potom jevy A a B jsou nezvisl tehdy a jen tehdy, kdy

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

tj. pravdpodobnost jevu A nen ovlivnna tm, e jev B nastal.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika6 Diskrtn pravdpodobnost6.2 Nezvisl jevy 2/2Tvrzen. Jevy A, B jsou nezvisl prv tehdy, kdy plat . Jev B je nezvisl na jevu A, pokud je pravdpodobnost P(B) pi nastalm jevu A stejn, jako pravdpodobnost P(B) jevu B samotnho. Tedy

.


Diskrtn matematika6 Diskrtn pravdpodobnost6.3 Nhodn vbry Nhodn podmnoina. Zdan n-prvkov mnoiny vybrme libovolnou z2n jejch podmnoin, kadou spravdpodobnost 2-n.

Nhodn permutace. Ze vech n! permutac n-prvkov mnoiny vybrme libovolnou jednu spravdpodobnost 1/n!.

Nhodn kombinace. Ze vech k-prvkovch kombinac dan

n-prvkov mnoiny vybrme jednu spravdpodobnost 1/ .

Nhodn posloupnost bit. Vybrme libovoln dlouhou posloupnost z0 a 1 tak, e kad dal bit je vybrn spravdpodobnost zcela nezvisle na vech pedchozch bitech. Tzn. kad vybran podposloupnost tto nhodn posloupnosti m stejnou anci se objevit.


Diskrtn matematika6 Diskrtn pravdpodobnost6.4 Stedn hodnota 1/2 Definice. Nech nhodn promnn X nabv kmonch hodnot z selnmnoiny X {h1,,hk} , kde jev [X=hi] , tj. X nabv hodnoty hi nastv spravdpodobnost pi a p1 + p2 ++pk = 1. Stedn hodnotou promnn X je pak slo

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

Definice. Dv nhodn promnn X = {x1,,xk} a Y = {y1,,yl} jsou nezvisl, jestlie jevy [X=xi] a [Y=yj] jsou nezvisl pro kad i = 1,,k a kad j = 1,,l.


Diskrtn matematika6 Diskrtn pravdpodobnost6.4 Stedn hodnota 2/2

Tvrzen. Pro libovoln dv nhodn promnn X, Y plat

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

Tvrzen. Pro libovoln dv nezvisl nhodn promnn X, Y plat

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

Stedn hodnota sel padlch na hrac kostce je E(X) = (1/6)(1 + 2 + 3 + 4 + 5 + 6 ) = 3,5 . Stedn hodnota souinu sel padlch na dvou hracch kostkch je E(X1.X2) = E(X1).E(X2) = 3,5.3,5 = 12,25.


7 Neorientovan graf

7.1 Pojem grafu 7.2 Dleit grafy 7.3 Isomorfismus graf 7.4 Podgrafy 7.5 Souvislost, komponenty 7.6 Matice sousednosti


Diskrtn matematika7 Neorientovan graf7.1 Pojem grafu 1/2 Graf je tvar, kter se skld zbod, kter nazvme vrcholy nebo uzly, a ar, kter tyto body spojuj, ty nazvme hrany nebo oblouky.


Diskrtn matematika7 Neorientovan graf7.1 Pojem grafu 2/2

Definice. kme, e graf G je uspodan dvojice (V,E), kde Vje neprzdn mnoina vrchol a E mnoina dvoubodovch podmnoin mnoiny V, tzn. mnoina hran. Abychom vyznaili, e se jedn o mnoiny Va E psluejc grafu G, zname tak V(G) nebo E(G). Graf G zapeme G = (V,E). Hranu, kterou je pipojen vrchol vnazvme incidentn hranou svrcholem v. Poet incidentnch hran s vrcholem v nazvme stupe vrcholu v.


Diskrtn matematika7 Neorientovan graf7.2 Dleit grafy 1/4 pln graf. pln graf je graf, vnm kad dva rzn vrcholy jsou spojeny prv jednou hranou. pln graf o n

vrcholech zname Kn. Pro plat.

K3 K4 K5 K6


Diskrtn matematika7 Neorientovan graf7.2 Dleit grafy 2/4 Cesta. Cesta je graf, jen je posloupnost navzjem rznch vrchol, kter jsou spojeny hranami. Tedy pro m hrany E = {{i 1, i}, i = 1,,n}..


Diskrtn matematika7 Neorientovan graf7.2 Dleit grafy 3/4 Krunice. Krunice je cesta, jej oba konce splynuly. Tedym hrany .

C3 C4 C5 C6


Diskrtn matematika7 Neorientovan graf7.2 Dleit grafy 4/4 pln bipartitn graf. pln bipartitn graf je graf, jeho vrcholy jsou rozdleny do dvou mnoin a hrany vdy vedou pes hranici tchto mnoin. Tedy Kn,m, (n,m 1) m vrcholy V = UW = {u1,,un}{w1,wm} a hrany E = {{ui,wj}, i = 1,,n, j = 1,,m} a UW = .

K1,1 K1,2 K1,3 K2,3 K3,3


Diskrtn matematika7 Neorientovan graf7.3 Izomorfismus graf 1/2 Definice. Dva grafy G = (V,E) a G = (V,E) nazveme isomorfn, jestlie existuje vzjemn jednoznan zobrazen tak, e plat Zobrazen f se nazv isomorfismus a zname G GOzname-li na dvou grafech vrcholy sly 1,,n, jsou tyto grafy isomorfn tehdy a jen tehdy, jestlie meme pevst vrcholy na sebe tak, e zstanou zachovna spojen hranami mezi pslunmi vrcholy. Jinak eeno, jestlie meme posouvnm vrchol a prodluovnm, zkracovnm a ohbnm hran pevst druh graf na tvar stejn sprvnm grafem.


Diskrtn matematika7 Neorientovan graf7.3 Izomorfismus graf 2/2 Tvrzen. Relace bt isomorfn na mnoin vech graf je ekvivalenc.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 7 Neorientovan graf7.4 Podgrafy 1/3Definice. Graf H je podgrafem grafu G jestlie mnoiny vrchol a hran grafu H jsou podmnoinami mnoin vrchol a hran grafu G.


Diskrtn matematika 7 Neorientovan graf7.4 Podgrafy 2/3 Cesta Pt v grafu G je podgraf grafu G tvoen posloupnost

(v0,e1,v1.e2,,et-1,et,vt),

kde vi jsou navzjem rzn vrcholy grafu G a ei = {vi-1,vi} jsou hrany grafu G. kme, e cesta z v0 do vt m dlku t.

Krunice Ct (t 3) v grafu G je podgraf grafu G tvoen posloupnost

(v0,e1,v1.e2,,et-1,et,v0),

kde v0,v1,,vt-1 jsou navzjem rzn vrcholy grafu G.


Diskrtn matematika7 Neorientovan graf7.4 Podgrafy 3/3 Definice. Graf G nazvme faktorem grafu G, vznikne-li zgrafu G pouhm vynechnm nkterch hran a pitom mnoina vrchol zstv zachovna, tedy V(G) = V(G).

.Definice. Graf G nazvme podgrafem indukovanm mnoinou vrchol, A V(G), jestlie podgraf Gm mnoinu vrchol A a obsahuje vechny hrany grafu G, jejich oba vrcholy jsou z mnoiny A.

Podgrafindukovanmnoinou{a,c,d,e,f}


Diskrtn matematika7 Neorientovan graf7.5 Souvislost, komponenty grafu Definice. Graf G je souvisl, jestlie pro kad dva jeho vrcholy x a y vnm existuje cesta zx do y.

Definice. Relaci ~ (cesta) na mnoin vrchol grafu G definujeme vztahem: x ~ y prv, kdy vgrafu G existuje cesta zx do y.

Tvrzen. Relace ~ je ekvivalence.Dkaz: Relace ~ je reflexivn, protoe zx do x vede nulov cesta. Je symetrick, protoe existuje-li cesta zx do y, lze jt i opan zy do x. Tranzitivitu dokeme nsledujcm zpsobem: Nech posloupnost (x=v0,e1,v1,,er,vr=y) je cesta z x do y a posloupnost je cesta z y do z. Ozname t maximln index, pro kter je a ozname jet Potom hledan posloupnost z x do z je


Diskrtn matematika7 Neorientovan graf7.6 Matice sousednosti v grafu Definice. Nech G = (V,E) je graf bez smyek sn vrcholy. Ozname vnjakm libovolnm poad vrcholy v1,...,vn. Matice sousednosti grafu G je tvercov n n matice AG = (aij)ni,j=1 definovan pedpisem

aij = 1 pro {vi, vj} E

aij = 0 jinak.


8 Sledy a dlky cest

8.1 Sled 8.2 Ohodnocen graf a vzdlenosti vgrafu 8.3 Hledn nejkrat cesty 8.4 Provn


Diskrtn matematika8 Sledy a dlky cest8.1 Sled v grafu Definice. Sled dlky 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 mnoinou vrchol V = {v1,,vn} a matic sousednosti A. Ozname Ak k-tou mocninu matice A a a(k)ij prvek matice Ak v pozici (i,j). Pak a(k)ij je poet sled dlky k z vrcholu vi do vrcholu vj.


Diskrtn matematika8 Sledy a dlky cest8.2 Ohodnocen graf a vzdlenost v grafu 1/2 Definice. Grafem sohodnocenmi hranami rozumme graf G = (V,E), jeho kad hran e E(G) je piazeno reln slo w(e), kter meme chpat nap. jako dlku hrany e. Dlka cesty vohodnocenm grafu je rovna soutu dlek jejch hran. Nejkrat vzdlenost vrchol u a vozname dG,w(u,v) a ta je rovna nejkrat zdlek vech cest spojujcch u a v.

Grafem sohodnocenmi vrcholy rozumme graf G = (V,E), jeho kadmu vrcholu v V(G) je piazeno reln slo w(v), kter meme chpat nap. jako prostupnost vrcholu.


Diskrtn matematika8 Sledy a dlky cest8.2 Ohodnocen graf a vzdlenost v grafu 2/2

Definice (vzdlenost vgrafu). Nech G = (V,E) je souvisl graf. Pro vrcholy v, v definujeme slo dG(v,v) jako dlku nejkrat cesty z v do v v grafu G. slo dG(v,v) se nazv vzdlenost vrchol v a v v grafu G.

Tvrzen (trojhelnkov nerovnost). Zobrazen dG : V V , kter nazvme metrika grafu G m tyto vlastnosti:

1. dG(v,v) 0 a dG(v,v) = 0 prv, kdy v = v,

2. (symetrie) dG(v,v) = dG(v,v) pro kadou dvojici vrchol v, v,

3. (trojhelnkov nerovnost) dG(v,v) dG(v,v) + dG(v,v) pro kadou trojici v, v,v vrchol z V.


Diskrtn matematika8 Sledy a dlky cest8.3 Hledn nejkrat cesty 1/2 Dijkstrv (Dijkstra) algoritmus. Je dn graf G = (V,E), ohodnocen jeho hran w : E (0, ) a poten vrchol s V. Pro kad vrchol v V se vypot slo dG,w(s,v), ili nejkrat vzdlenost z s do v:

Pro kad vrchol v zavedeme promnnou d(v) jako momentln odhad k dG,w(s,v). Poten odhady jsou d(v) = 0 pro v = s a d(v) = pro v s. Mnoina A (A V) je na zatku A = V\{s}, tj. vechny vrcholy, kter budeme teprve zkoumat pat do A. Vrcholy, pro kter je d(v) nejmen, utvo mnoinu N a vyjmou se z mnoiny A. Pepotou se hodnoty d(x) pro sousedy vrchol z N. Pro kadou 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 pes v krat cesta a dosavadn d(y) se nahrad hodnotou d(v) + w({v,y}). Algoritmus kon, jestlie A je bu przdn mnoina, nebo obsahuje jen vrcholy nedosaiteln z vrcholu s.


Diskrtn matematika8 Sledy a dlky cest8.3 Hledn nejkrat cesty 2/2

krokabcdefNA0.0a,b,c,d,e,f01.01bb,c,d,e,f12.014cc,d,e,f43.0145dd,e,f54.01456ee,f65.014568ff86.014567f7


Diskrtn matematika8 Sledy a dlky cest8.4 Provn 1/9 Definice. Bu dn graf G = (V,E). Provn vgrafu G je takov mnoina hran P E(G) e dn dv hrany zmnoiny P nemaj spolen vrchol. O vrcholech, kter jsou incidentn snkterou hranou provn P kme, e jsou provnm P nasyceny nebo t pokryty. O ostatnch vrcholech kme, e jsou voln. Provn, kter nasycuje vechny vrcholy grafu, nazvme perfektnm provnm.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 2/9lohy o provn. Praktick lohy vedouc na provn lze zpravidla zaadit do nkter znsledujcch kategori:1. Vdanm grafu najt maximln provn, tj. provn, kter obsahuje nejvt poet hran.2. Vgrafu, jeho hrany jsou ohodnoceny cenami, najt nejlevnj maximln provn, tj. nejlevnj provn ze vech, kter jsou maximln.3. Vohodnocenm grafu najt nejdra provn, tj. provn snejvtm soutem cen.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 3/9Definice. Bu dn graf G a v nm provn P. Stdav cesta vzhledem kprovn P je takov neorientovan cesta, e jej hrany stdav le a nele vP a je-li krajn vrchol cesty nasycen vprovn P, pak hrana, kter jej nasycuje, je st cesty.

Stdav krunice vzhledem kprovn P je krunice, jej hrany stdav le a nele vprovn P.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 4/9Definice (zmna podl stdav cesty/krunice). Pomoc stdavch cest a krunic lze provn snadno mnit tm, e u hran, kter le na cest nebo krunici, zmnme pslunost kprovn. Je-li H mnoina hran tvocch stdavou cestu nebo krunici vzhledem kprovn P, vytvome nov provn P takto:

jestlie e H, pak e P e P jestlie e H, pak e P e P. .Takovou zmnu provn budeme nazvat zmnou podl stdav cesty nebo krunice.


Diskrtn matematika8 Sledy a dlky cest8.4 Provn 5/9 Tvrzen. Bu dn prost graf G a vnm libovoln provn P1. Pak pro kad provn P2 vgrafu G existuje soustava vrcholov disjunktnch stdavch cest a stdavch krunic takov, e zmnami podl vech tchto cest a krunic lze zprovn P1 zskat provn P2.Dkaz: Uvaujme faktor Ggrafu G smnoinou hran (P1\P2)(P2\P1). Graf Gobsahuje prv ty hrany, kter le pesn v jednom provn. Pro kad vrchol x V(G) = V(G) nastane jedna ze ty monost:Nen-li vrchol x nasycen v ani P1 ani v P2, je izolovanm v G.Je-li x nasycen v jednom z P1 a P2, m v grafu Gstupe 1.Je-li x nasycen vP1 i vP2 tou hranou, pak tato hrana nele vG a vrchol x je vG izolovanm vrcholem.Je-li x nasycen vP1 i vP2 rznmi hranami e1 P1, e2 P2, pak ob tyto hrany le v Ga stupe vrcholu x je 2.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 6/9Pokraovn dkazu

Kad vrchol m tedy vgrafu G stupe nejve 2. Ztoho plyne, e graf G m komponenty souvislosti t typ:izolovan vrchol,krunice sud dlky, jej hrany le stdav vP1 a P2,cesta, jej hrany stdav le vP1 a P2 a jej krajn vrcholy jsou rzn, piem kad znich je nasycen vjednom zobou provn P1, P2.Komponenty souvislosti grafu G pmo uruj stdav cesty a krunice. Provedenm zmn provn P1 podl vech tchto cest a krunic dostaneme provn P2.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 7/9Tvrzen. Provn P vgrafu G je maximln prv tehdy, kdy vgrafu G vzhledem kprovn P neexistuje stdav cesta spojujc dva voln vrcholy.Dkaz: Je-li provn maximln, pak vzhledem knmu neme existovat stdav cesta spojujc dva voln vrcholy. Kdyby existovala, mohli bychom podl n provn zvtit.Nen-li naopak provn P maximln, vezmeme njak maximln provn P1. Podle pedchozho tvrzen existuje soustava stdavch cest a krunic takov, e zmnami podl nich dostaneme provn P1 zprovn P. Ponvad je |P|

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 8/9Definice. Bu graf G, jeho hrany jsou ohodnoceny cenami c : E(G) . Dle bu vgrafu G provn P a vzhledem knmu stdav cesta, pop. krunice. Mnoinu hran tto cesty, pop. krunice ozname H.Cenu stdav cesty, pop. krunice stanovme jako

Tvrzen. M-li stdav cesta, pop. krunice cenu C a provedeme-li podl n zmnu, pak cena provn vzroste o hodnotu C.

Tvrzen. Provn P vgrafu G je nejdra prv tehdy, kdy vgrafu G vzhledem kprovn P neexistuje ani stdav cesta, ani stdav krunice skladnou cenou.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika8 Sledy a dlky cest8.4 Provn 9/9Stdav cesta a zmna provn


9 Eulerovsk grafy a k-souvislost

9.1 Skre grafu 9.2 Eulerovsk tahy a grafy a hamiltonovsk krunice a cesty 9.3 Algoritmus kreslen grafu jednm tahem9.4 Stupn souvislosti 9.5 Grafov operace

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.1 Skre grafu 1/3

Definice. Nech v V je vrchol grafu G = (V,E). Poet hran obsahujcch vozname degG(v) a nazveme stupnm vrcholu vvgrafu G.Nech v1,,vn jsou vrcholy grafu G vlibovolnm poad. Posloupnost (degG(v1),,degG(vn)) se nazv skre grafu G.


Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.1 Skre grafu 2/3

Tvrzen (princip sudosti vgrafech bez smyek). Pro kad graf G = (V,E) bez smyek plat

Dkaz: Pi stn stup vrchol vgrafu zapotme kadou hranu dvakrt za kad jej konec.

Dsledek. Kad graf bez smyek m sud poet vrchol lichho stupn

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.1 Skre grafu 3/3Tvrzen. Nech D = d1,,dn je posloupnost pirozench sel. Pedpokldejme, e d1 d2 dn, a ozname symbolem D posloupnost (d1,,dn-1), kde

di= di pro i < n dn,di= di 1 pro i n dn.

Potom D je skre grafu prv kdy D je skre grafu.

Pklad. Existuje graf se stupni vrchol (1,1,1,1,2,3,4,6,7)?een: Upravme na (1,0,0,0,1,2,3,5) a uspodme (0,0,0,1,1,2,3,5), znovu upravme (0,0,-1,0,0,1,2) a to u nen skre grafu, protoe stupe vrcholu neme bt zporn.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.1 Eulerovsk tahy a grafy a hamiltonovsk krunice a cesty 1/7Definice. Uzavenm) eulerovskm tahem rozumme takov uzaven sled (v0,e1,v1,,em-1,vm-1,em,v0), vnm se kad hrana vyskytuje prv jednou a kad vrchol alespo jednou.

Definice. Eulerovsk graf je takov, kter m alespo jeden (uzaven) eulerovsk tah.

Tvrzen. Graf G je eulerovsk tehdy a jen tehdy, kdy je souvisl a kad jeho vrchol m sud stupe.


Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.1 Eulerovsk tahy a grafy a hamiltonovsk krunice a cesty 2/7

Pedchoz tvrzen pedstavuje nutnou a postaujc podmnku pro existenci eulerovskho tahu a pedstavuje siln kritrium. Nutn podmnka: je-li G eulerovsk, pak kad vrchol G m sud stupe .Postaujc podmnka je: Jestlie kad vrchol m sud stupe, pak G je eulerovsk.



Definice. Hamiltonovsk cesta vgrafu G je cesta obsahujc vechny vrcholy grafu G. Hamiltonovsk krunice vgrafu G je krunice obsahujc vechny vrcholy grafu G. Graf obsahujc hamiltonovskou krunici se nazv hamiltonovsk graf.

Nutn podmnka pro existenci hamiltonovsk krunice nebyla zatm nalezena. Jsou nalezeny pouze nkter postaujc podmnky.



loha nskho poka. Pok m projt vechny ulice msta a vrtit se do vchozho msta a pitom ujt co nejmn kilometr. Jinmi slovy: je dn neorientovan souvisl graf, jeho hrany jsou ohodnoceny kladnmi sly a kolem je najt nejkrat uzaven sled, kter obsahuje vechny hrany grafu.een: Je-li graf eulerovsk, tj. existuje-li vnm uzaven eulerovsk graf, je loha tmto tahem ji vyeena.Pokud vgrafu eulerovsk tah neexistuje, pak sled, kter obsahuje vechny hrany, mus projt nktermi hranami dvakrt nebo vcekrt. Lze vak dokzat, e nejkrat sled prochz kadou hranou pouze jedenkrt nebo nejve dvakrt.Vnejkratm sledu, kter obsahuje vechny hrany grafu, tvo opakovan prochzen hrany soustavu cest spojujcch vdy dva vrcholy lichho stupn. Lze ukzat, e takov cesty jsou disjunktn (dn hrana grafu nele ve dvou takovch cestch).



een lohy nskho poka - pokraovn

Pi een lohy nskho poka je mon postupovat takto:Vdanm grafu G najdeme mnoinu L vrchol slichm stupnm.Pro vechny dvojice (x,y) vrchol mnoiny L vypoteme dlku d(x,y) nejkrat cesty zx do y.Na mnoin vrchol L definujeme pln graf K,jeho hrany jsou ohodnoceny dlkami nejkratch cest d(x,y).Vgrafu Knajdeme nejlevnj perfektn provn P.Pro kadou hranu (x,y) grafu K, kter le vprovn P, vezmeme vechny hrany pvodnho grafu G, kter tvo nejkrat cestu zx do y a ke grafu G pidme kopie tchto hran (dostaneme nsobn hrany). Vgrafu G, kter takto zskme, maj vechny hrany sud stupe.Vgrafu G sestrojme eulerovsk tah. Tento tah prochz tak vemi pidanmi hranami, co odpovd opakovanm prchodm hranami pvodnho grafu.Veulerovskm tahu nahradme vechny pidan hrany jim odpovdajcmi hranami grafu pvodnho. Tak zskme hledan nejkrat sled, kter prochz vemi hranami grafu G.



Problm obchodnho cestujcho. Obchodn cestujc m povinnost navtvit n mst vlibovolnm poad a vrtit se do vchozho bodu tak, aby jeho cesta byla co nejkrat. Pitom pedpokldme, e jsou znmy vzdlenosti mezi vemi jednotlivmi msty ohodnocen grafu.

een spov vnalezen nejkrat hamiltonovsk krunice vplnm ohodnocenm grafu.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.3 Algoritmus kreslen grafu jednm tahem 1/3 Definice. Hranu e E v grafu G = (V,E) nazveme mostem, jestlie graf G = (V,E\{e}) m vt poet komponent ne graf G.


Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.3 Algoritmus kreslen grafu jednm tahem 2/3

Tvrzen. Nech G = (V,E) je graf, jeho stupn vech vrchol jsou sud. Potom graf G neobsahuje most.Dkaz provedeme sporem: Nech hrana {v,v} = e je most grafu G. Nech V1,,Vn jsou vechny komponenty grafu G oznaen tak, e

{v,v}V1. Uvaujme graf G1 = (V1,E1) =

Graf G1 je souvislou komponentou grafu G, m tedy vechny stupn sud a hrana e je mostem grafu G1. Zejm graf (V1,E1\{e}) je nesouvisl a m dv komponenty. Jedna obsahuje vrchol va druh vrchol v a tyto dva vrcholy jsou lichho stupn. To je spor spedpokladem sudosti.


Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.3 Algoritmus kreslen grafu jednm tahem 3/3

Algoritmus pro nakreslen grafu jednm tahem. Nech G = (V,E) je graf, jeho vechny vrcholy maj sud stupe, nech |E| = m.

1. krok: Zvol v0 V libovoln. Polo T0 = v0,

2. krok: Opakuj nsledujc 3. krok pro i = 0, 1, 2,, dokud je to mon. Pokud u 3. krok nelze provst, potom i = m a Tm je hledan tah.

3. krok: (prodlouen tahu): Nech Ti = (v0,e1,,ei,vi) je ji definovan tah. Zvol hranu ei+1 = E\{e1,,ei} obsahujc vrchol vi. Pokud je to mon, zvol ei+1 navc tak, aby grafy (V,E\{e1,,ei} a (V,E\{e1,,ei,ei+1} mly stejn poet komponent.


Diskrtn matematika9 Eulerovsk grafy a k-souvislost9.4 Stupn souvislosti 1/6

Definice (Hranov stupe souvislosti). Graf G nazveme hranov k-souvislm, m-li alespo 3 vrcholy a vynechnm libovolnch k 1 hran zstane G souvislm grafem, ale odebrnm 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 kad dva jeho vrcholy existuje vgrafu G krunice, kter je obsahuje (tj. G je vrcholov 2-souvisl, prv kdy kad dva vrcholy le na spolen krunici).



Definice (Vrcholov stupe souvislosti). Graf G nazveme vrcholov k-souvislm, m-li alespo 2 vrcholy a vynechnm libovolnch k 1 vrchol zstane G souvisl graf, ale odebrnm libovoln k-tho vrcholu ji bude nesouvisl. Vrchol grafu nazveme artikulac, jestlie jeho odstrannm zvme poet komponent souvislosti.

Tvrzen (Menger). Graf je vrcholov k-souvisl prv tehdy, kdy pro kad dva vrcholy x, y existuje kvrcholov disjunktnch cest zx do y, tj. takovch cest, kter krom vrchol x a y nemaj spolen vrcholy.

Tvrzen ( Ford a Fulkerson 1956). Graf je hranov k-souvisl prv tehdy, kdy pro kad dva vrcholy x, y existuje khranov disjunktnch cest zx do y, tj. takovch cest, kter nemaj dnou spolenou hranu.



Definice. Pro graf G = (V,E) definujeme odebrn hrany G e = (V,E\{e}), kde e E(G) je hrana grafu G;

pidn nov hrany G + e = (V,E{e}), kde je hrana grafu G;

odebrn vrcholu G v = (V\{v},e E, v e), kde v V(odebrme vrchol va vechny hrany do nj zasahujc);

dlen 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} pikreslme nov vrchol z).



Definice. ekneme, e graf Gje dlen grafu G, pokud G je isomorfn grafu vytvoenmu zgrafu G postupnm opakovnm operace dlen hrany.

Tvrzen. Graf G je vrcholov 2-souvisl prv kdy libovoln jeho dlen je vrcholov 2-souvisl.Dkaz: Sta dokzat, e G je 2-souvisl prv kdy G%e je 2-souvisl ( pro libovolnou hranu e E(G) ). Je-li v V(G) libovoln vrchol grafu G, je snadno vidt, e G vje souvisl prv kdy (G%e) vje souvisl. Dle vyuijeme skutenosti, e vrcholov 2-souvisl graf zstane souvisl i po odebrn libovoln hrany. Je-li znov pidan vrchol v grafu G%e,je (G%e) zsouvisl prv kdy G e je souvisl. Proto je 2-souvislost a G%e ekvivalentn.



Tvrzen. Graf G je vrcholov 2-souvisl prv kdy jej lze vytvoit ztrojhelnku

Tvrzen. Graf G je vrcholov 2-souvisl prv kdy jej lze vytvoit ztrojhelnku posloupnost dlen hran a pidvn hran.


10 Speciln tda graf stromy

10.1 Charakteristika strom 10.2 Isomorfismus strom 10.3 Kdovn strom 10.4 Kostra grafu 10.5 Problm minimln kostry

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.1 Charakteristika strom 1/4Definice. Strom je souvisl graf, kter neosahuje krunici. Vrchol stupn 1 se nazv koncov vrchol nebo list.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.1 Charakteristika strom 2/4Tvrzen. Kad konen strom salespo dvma vrcholy obsahuje alespo dva vrcholy stupn 1.

Dkaz: Nech P = (v0,e1,v1,,et,vt) je cesta maximln mon dlky ve stromu T = (V,E). Dlka cesty P je zejm alespo 1. Sporem dokame, e jak v0, tak vt jsou koncov vrcholy T. Nen-li nap.v0 koncov vrchol, pak existuje jet jin hrana e e obsahujc vrchol v0. Ozname e = {v0,v} . Pak bu je v = vi, i 2 a potom T obsahuje krunici, co je vrozporu sdefinic stromu, anebo v (v0,e1,v1,,et,vt), a pak bychom mohli cestu P prodlouit a to je spor. Pro vt bychom postupovali obdobn.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.1 Charakteristika strom 3/4Tvrzen. Nech graf G m koncov vrchol v. Potom G je strom prv kdy G vje strom.

Dkaz: Nejprve dokeme implikaci je-li G strom, pak G vje strom. Jsou-li x, y dva vrcholy grafu G rzn od v, uvame njakou cestu zx do y. Tato cesta neme obsahovat vrchol stupn 1 mimo x a y, a tud neobsahuje ani v. Proto je cel cesta obsaena tak vG v, ili G vje souvisl. Protoe G neobsahuje krunici, ani G vneobsahuje krunici a je to tud strom.Nyn dokeme opanou implikaci. Nech G vje strom. Pidnm koncovho vrcholu vnememe vytvoit krunici. Zejm je G souvisl: mezi libovolnma dvma vrcholy rznmi od vvedla cesta u vgrafu G va cesta znjakho vrcholu x do vrcholu vvznikne prodlouenm cesty spojujc x s v o hranu {v,v} , kde v je jedin soused vrcholu v.


Diskrtn matematika10 Speciln tda graf - stromy10.1 Charakteristika strom 4/4

Tvrzen (charakterizace strom). Pro graf G = (V,E) jsou nsledujc podmnky ekvivalentn:

G je strom

(jednoznanost cesty) Pro kad dva vrcholy x, y V existuje prv jedin cesta z x do y.

(minimln souvislost) G je souvisl, vynechn libovoln hrany vznikne nesouvisl graf.

(maximln graf bez krunic) Graf G neobsahuje krunici, ale kad graf vznikl zG pidnm hrany ji krunici obsahuje.

(Eulerv vzorec) G je souvisl a plat |V| = |E| + 1

.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.2 Izomorfismus strom 1/4Definice. Koenov strom je dvojice(T,r), kde r V(T) je jeden zvolen vrchol T, zvan koen. Je-li {x, y} E(T) hrana a le-li x na (jedin) cest zy do koene, kme, e x je otec y a y je syn x.

Pstovan strom je njak koenov strom(T,r) spolu sjeho pevn zvolenm rovinnm nakreslenm. Pitom koen se vyzna ipkou smujc dol.


Diskrtn matematika10 Speciln tda graf - stromy10.2 Izomorfismus strom 2/4

Definice. Isomorfismus stromu je zobrazen f : V(T) V(T) T na T, jestlie f je vzjemn jednoznan zobrazen splujc podmnku {x, y} E(T) prv, kdy {f(x), f(y)} E(T). Tento isomorfismus zapisujeme T T.

Isomorfismus koenovch strom (T, r) a (T, r) je takov isomorfismus f strom T a T , pro kter navc plat f(r) = r. Zname to (T, r) (T, r).

Isomorfismus pstovanch strom je takov isomorfismus f strom T a T , kter navc zachovv poad syn kadho vrcholu. Budeme jej znait (T, r, v) (T, r, v). .



Izomorfismus strom, koenovch strom a pstovanch strom



Definice. Mjme koenov strom skoenem r. Poet hran vcest zkoene r do vrcholu x nazveme hloubkou vrcholu x. Mnoinu vrchol, kter jsou ve stejn hloubce, nazveme vrstvou. Vku vrcholu x definujeme jako nejvt poet hran vcest zanajc vx a konc vnkterm list. Vka stromu je vka jeho koene.


Diskrtn matematika10 Speciln tda graf - stromy10.3 Kdovn strom 1/6

Pravidla pro kdovn pstnch strom. K1. Koncovm vrcholm (rznm od koene) piadme kd 01K2. Bu vnjak vrchol, v1,,vt jeho synov vpoad zleva doprava. M-li syn vi kd Ai potom vrcholu vpiadme kd 0A1A2At1 .

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.3 Kdovn strom 2/6



Lexikografick uspodn posloupnost.

Dv rzn posloupnosti A = (a1,,an) a B = (b1,,bm) porovnvme takto:1. Je-li A potenm sekem B, pak A < B. Je-li B potenm sekem A, je B < A.2. Vostatnch ppadech, 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 kdovn koenovch strom. Pro kdovn koenovch strom pijmeme modifikaci pravidla K2:

K2. Pedpokldejme, e jsme ji piadili kd A(w) kadmu synu w vrcholu v. Ozname syny w1,,wt tak, e plat lexikografick uspodn A(w1) A(w2) A(wi). Vrchol v pak dostane kd 0A1A2At1, kde Ai = A(wi).

.

Tvrzen. Dva koenov stromy jsou isomorfn prv kdy maj stejn kd. (Pi pouit pravidla K2.)



Definice. Pro vrchol vgrafu G ozname symbolem exG(v) a nazveme vstednost (excentricita) maximln vzdlenost vrcholu vod jinho vrcholu grafu G. Ozname C(G) mnoinu vech vrchol vgrafu G, kter maj nejmen vstednost exG(v). mnoinu C(G) nazvme stedem grafu G.

Tvrzen. Pro kad strom T m C(T) nejve dva vrcholy. Je-li C(T) tvoeno dvma vrcholy x a y, pak {x, y} tvo hranu.



Pravidla kdovn obecnho stromu. 1. Jestlie sted stromu m jedin vrchol v, potom mu piadme kd jako koenovmu stromu. 2.Je-li sted stromu T tvoen hranou e = {x1, y1} , potom uvaujme graf T e. Tento graf m prv dv komponenty T1 a T2, kde xi V(Ti), i = 1, 2 . Ozname kd koenovho stromu (T1, x1) psmenem A a kd koenovho stromu (T2,x2) psmenem B. Pokud je vlexikografickm uspodn A B, , kdujeme strom T kdem koenovho stromu (T,x1) a pro A B kdem koenovho stromu (T,x2).

Tvrzen. Dva obecn stromy jsou isomorfn prv kdy maj stejn kd.


Diskrtn matematika10 Speciln tda graf - stromy10.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 vechny vrcholy grafu G.


Diskrtn matematika10 Speciln tda graf - stromy10.4 Kostra grafu 2/2

Algoritmus nalezen kostry I. Bu G = (V,E) graf sn vrcholy a m hranami. Seame hrany grafu G do libovoln posloupnosti (e1,,e2). V algoritmu budeme postupn konstruovat mnoiny hran E1,E2,E tak, e polome E0 = , byla-li nalezena mnoina Ei-1, spotme mnoinu Ei takto: Ei = Ei-1{ei} neobsahuje-li graf (V,Ei-1{ei} krunici Ei = Ei-1 jinak.

Algoritmus nalezen kostry II. Je dn graf G = (V,E) sn vrcholy a m hranami. Budeme postupn vytvet mnoiny V0,V1V vrchol a mnoiny E0,E1,E hran, piem E0 = a V0 = {v}, kde vje libovoln zvolen vrchol. Jsou-li ji Vi-1 a Ei-1 vytvoeny, nalezneme njakou hranu ei = {xi,yi} E(G) takovou, e xi Vi-1, yi V\Vi-1 a polome Vi = Vi-1{yi}, Ei = Ei-1{ei}. Pokud dn takov hrana neexistuje, algoritmus kon.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.5 Problm minimln kostry 1/7Definice. Minimln kostrou grafu G = (V,E) snezporn ocennmi hranami nazveme takov jeho podgraf Tm = (V,E) , pro kter nabv slo

sv minimln hodnoty.


Diskrtn matematika10 Speciln tda graf - stromy10.5 Problm minimln kostry 2/7

Kruskalv algoritmus Nech graf G=(V,E) je souvisl graf sn vrcholy a m hranami a m ocenn hrany. Uspodejme hrany podle jejich ocenn tak, e w(e1) w(e2) w(em).Algoritmus nalezen kostry: V algoritmu budeme postupn konstruovat mnoiny hran E0,E1, E tak, e polome E0 = . byla-li nalezena mnoina Ei-1, spotme mnoinu Ei takto:Ei = Ei-1{ei} neobsahuje-li graf (V,Ei-1{ei} krunici, Ei = Ei-1 jinak.

Kreslme tedy hrany postupn od nejmenho ohodnocen a kontrolujeme pouze, zda vdanm kroku bude, i nebude uzavena krunice. Pokud ano, hranu nepipojme a zkoumme hranu nsledujc. Je-li graf souvisl, skon algoritmus stromem sn 1 hranami. M-li po skonen algoritmu kostra k < n 1 hran, je G graf nesouvisl sn kkomponentami.



Jarnkv algoritmus. Je dn graf G = (V,E) sn vrcholy a m hranami. Budeme postupn vytvet mnoiny V0,V1V vrchol a mnoiny E0,E1,E hran, piem E0 = a V0 = {v}, kde vje libovoln zvolen vrchol. Jsou-li ji Vi-1 a Ei-1 vytvoeny, vyhledme z hran ei = {xi,yi} E(G) takovch, e xi Vi-1, yi V\Vi-1 (tj. takovch, kter spojuj dosud pospojovan vrcholy jet nepipojenmi) tu, jej ocenn je nejmen a polome Vi = Vi-1{yi}, Ei = Ei-1{ei}. Pokud dn takov hrana neexistuje, algoritmus kon.



Borvkv algoritmus. Vychzme zgrafu G = (V,E), jeho ohodnocen jednotlivch hran se alespo trochu li a seadme je podle velikosti ohodnocen. V algoritmu budeme postupn konstruovat mnoiny hran E0,E1, E a polome E0 = . Mnoinu vrchol Vpovaujeme na potku rozloenou don td ekvivalence komponent grafu, kter jet neobsahuje dn hrany. Komponenty jsou tedy na potku samotn vrcholy. Tento rozklad pak budeme upravovat podle prv vytvoench komponent postupn vznikajc kostry. Vi-tm kroku mme mnoinu Ei-1 a rozklad V1,V2,,Vt mnoiny Vpodle ji vytvoench komponent. Pro kadou tdu tohoto rozkladu Vj najdeme hranu ej = {xj, yj}, kde xj Vj a yj Vj , tedy mezi dosud vzniklmi komponentami, a jej ohodnocen je nejmen zhran {x, y}, x Vj, y V\Vj, utvome Ei = Ei-1{e1,,et}. Algoritmus kon, m-li graf (V,Ei) jedinou komponentu.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.5 Problm minimln kostry 5/7Kruskalv algoritmus

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.5 Problm minimln kostry 6/7Jarnkv algoritmus

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika10 Speciln tda graf - stromy10.5 Problm minimln kostry 7/7Borvkv algoritmus


11 Rovinn kreslen graf

11.1 Kreslen do roviny 11.2 Eulerv vztah 11.3 Kreslen na jin plochy

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika11 Rovinn kreslen graf 11.1 Kreslen do roviny 1/6

Definice. Rovinn graf je graf je takov graf, kter lze nakreslit do roviny bez ken hran.

Oblouk je podmnoina roviny = 2 tvaru o ={(x); x 0,1}, kde : 0,1 2, kde je njak spojit zobrazen uzavenho intervalu 0,1 do roviny. Pitom body (0) a (1) se jmenuj koncov body oblouku o.

Definice. Nakreslen grafu G = (V,E) nazvme zobrazen, kter kadmu vrcholu vgrafu G piazuje bod b(v) roviny, a kad hran e = {v, v} V piazuje oblouk o(e) vrovin skoncovmi body b(v) a b(v). Pitom pedpokldme, e zobrazen b je prost a dn zbod b(v) nen nekoncovm bodem dnho zoblouk o(e).

Tato definice vyluuje ken oblouk.


Diskrtn matematika11 Rovinn kreslen graf 11.1 Kreslen do roviny 2/6

Definice. Graf spolu snjakm nakreslenm se nazv topologick graf.

Definice. Mnoinu A 2 nazveme souvislou, jestlie pro libovoln dva body x a y A existuje oblouk o A skoncovmi body x a y.

Definice. Bu G = (V,E) topologick graf. Mnoina vech bod roviny, kter nele na dnm zoblouk se rozpadne na konen poet souvislch oblast, kter nazvme stny topologickho rovinnho grafu.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika11 Rovinn kreslen graf 11.1 Kreslen do roviny 3/6Stny grafu.



Definice. Uzaven kivka vrovin, kter sama sebe neprotn se nazv topologick krunice (nebo tak Jordanova kivka).

Tvrzen (Jordanova vta o krunici). Kad topologick krunice k rozdluje rovinu na prv dv souvisl sti: vnitek a vnjek krunice, piem k je jejich spolenou hranic.

Vnitek a vnjek budeme nazvat oblastmi krunice k.



Tvrzen. K5 nen rovinn graf.Dkaz: Postupujeme sporem. Nech b1, b2, b3, b4, b5 jsou body odpovdajc vrcholm K5 pi njakm rovinnm nakreslen. Oblouk, kter spojuje bi a bj ozname o(i,j).Protoe b1, b2 a b3 jsou vrcholy krunice vgrafu K5 , tvo oblouky o(1,2), o(2,3) a o(3,1) topologickou krunici k. Body b4, b5 mus leet oba vn nebo oba uvnit krunice k, jinak by oblouk o(4,5) protnal krunici k. pedpokldejme nejprve, e b4 le uvnit. Potom b5 mus leet uvnit krunice tvoen 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). Vprvnm ppad vak oblouk o(3,5) mus protnout krunici tvoenou oblouky o(1,4), o(4,2) a o(1,2) a podobn vostatnch dvou ppadech.Pokud body b4, b5 le vn krunice k, pak bychom postupovali analogicky.



Tvrzen. K3,3 nen rovinn graf.

Tvrzen. Budi G 2-souvisl rovinn graf. Potom kad stna vlibovolnm nakreslen grafu G je oblast njak krunice grafu G.

Tvrzen. (Kuratowskho vta) Graf G je rovinn tehdy a jen tehdy, kdy dn jeho podgraf nen isomorfn k dlen grafu K3,3 ani k dlen grafu K5.

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika11 Rovinn kreslen graf 11.2 Eulerv vztah 1/7

Tvrzen (Eulerv vzorec). Budi G = (V,E) souvisl rovinn graf a spoet stn njakho rovinnho nakreslen G. Pak |V| - |E| + s = 2.

Dkaz: Postupujeme matematickou indukc podle potu hran grafu G. Je-li E = , potom |V| = 1 a s = 1 a vzorec plat. Bu |E| 1 a rozlime dv monosti:1. Graf G neobsahuje krunici. Potom G je strom a |V| = |E| + 1, pitom s = 1.2. Njak hrana e je obsaena vkrunici. Pak je graf G e souvisl. Pro nj podle induknho pedpokladu plat Eulerv vzorec. Hrana e soused se dvma rznmi stnami Sa S, protoe e je obsaena vkrunici. Tyto stny se vgrafu G e stanou stnou jedinou. Poet hran i stn vgrafu G ve srovnn sgrafem G e stoupl o 1 a poet vrchol se nezmnil. Eulerv vzorec tedy plat i pro G . .


Diskrtn matematika 11 Rovinn kreslen graf 11.2 Eulerv vztah 2/7

Aplikace na platnsk tlesa. Platnsk tlesa jsou pravideln mnohostny ohranien pravidelnmi mnohohelnky, kterch se kadho vrcholu dotk stejn poet: (i) tystn, ohranien tymi trojhelnky a setkvaj se vdy 3 vjednom vrcholu, (ii) estistn krychle, (iii) osmistn ohranien trojhelnky (setkvaj se vdy tyi), (iv) dvanctistn ohranien ptihelnky, znich se vdy 3 setkvaj a (v) dvacetistn strojhelnky (setkv se jich vdy 5). Vdalm ukeme, e dal tlesa stmito vlastnostmi nejsou.



Stereografick projekce. Jsou-li uveden tlesa umstna vkouli, jej sted je uvnit tlesa a je-li provedena stereografick projekce ze stedu na povrch koule, promtnou se na povrch koule vrcholy i hrany tlesa. Nyn se dal stereografickou projekc zkoule penesou projekc ze severnho plu vrcholy a hrany do roviny a dostaneme rovinn grafy.



Tvrzen. Budi G = (V,E) topologick graf, jeho kad vrchol m (stejn) stupe d 3 a jeho kad stna m (stejn) k 3 vrchol. Pak G je isomorfn sjednm zgraf zskanch stereografickou projekc z platnskch tles.Dkaz: Ozname |V| = n poet vrchol, |E| = m poet hran a spoet stn Sgrafu G. Podle principu sudosti je tedy vnaem ppad dn = 2m. Ureme nyn poet uspodanch dvojic tvaru (e,S), kde e je hrana lec na hranici stny S. Tch je ks, protoe kad stna pispje kdvojicemi, ale tak 2m, protoe kad hrana pinese 2 dvojice.Tedy ks = 2m .Protoe Eulerv vztah zn 2 = n m + s, dostaneme .Tto rovnici vyhov jen takov d a k, kter vedou na lev stran kslu vtmu ne (jinak by m bylo zporn) a to jsou dvojice zsel 3, 4, 5 svjimkou dvojice 4, 4. Dostvme vsledek .



dknmstleso33464tystn348126krychle35203012dvanctistn436128osmistn53123020dvacetistn



Tvrzen. (Maximln poet hran rovinnho grafu): Nech G = (V,E) je rovinn graf salespo 3 vrcholy bez smyek. Potom(i) plat |E| 3|V| - 6. Rovnost nastv pro kad maximln rovinn graf, tj.graf, knmu nelze pidat dnou hranu tak, aby zstal rovinnm.(ii) Neobsahuje-li navc graf G trojhelnk K3 jako podgraf , pak plat |E| 2|V| - 4.

Dsledek. Z (i) plyne, e kad rovinn graf m alespo jeden vrchol stupn nejv 5; a z (ii), e kad rovinn graf bez trojhelnk m alespo jeden vrchol stupn nejv 3.


Diskrtn matematika 11 Rovinn kreslen graf11.2 Kreslen na jin plochy

Kreslen na nerovinnch plochch. Kreslit lze i na jinch kivch plochch, jako napklad torus (anuloid), Mbiv list a koule suchem Na torus lze nakreslit graf K5 a na Mbiv list graf K3,3.


12 Barevnost mapy a problm ty barev 12.1 Nezvislost, kliky a obarven vrchol 12.2 Obarven mapy 12.3 Problm ty a pti barev

*.RNDr. Ivan Havlek, CSc., [email protected] ::Diskrtn matematika 12 Barevnost mapy problm ty barev12.1 Nezvislost, klika, obarven vrchol 1/5Definice (Nezvisl mnoina). Nezvisl mnoina vrchol vgrafu G je takov mnoina, jej dn dva vrcholy nejsou spojeny hranou. Nejpoetnj nezvisl mnoina je nezvisl mnoina, kter m nejvt poet prvk. Poet vrchol vnejpoetnj nezvisl mnoin grafu G nazvme nezvislost grafu G a zname (G).

Vpraxi se vyskytuj lohy najt nejdra nezvislou mnoinu vzvislosti na ohodnocen vrchol.

Definice (Klika). Klika vgrafu G je maximln podgraf G, kter je plnm grafem. Poet vrchol vnejvt klice nazvme klikovost grafu G a zname (G).


Diskrtn matematika 12 Barevnost mapy problm ty barev12.1 Nezvislost, klika, obarven vrchol 2/5

Definice (Obarven grafu). Nech G = (V,E) je graf, kpirozen slo a b zobrazen mnoiny vrchol do mnoiny B = {1,2,,k} stouto vlastnost:

pro kadou hranu {x, y} E je b(x) b(y) .

Pak zobrazen b : V B nazvme obarvenm grafu G pomoc kbarev. Minimln poet barev potebnch kobarven grafu G nazveme barevnost grafu a ozname (G).



Tvrzen. Pro graf G bez smyek o n vrcholech plat: (G) n, (G) (G), (G)(G) n, (G)+(G) n + 1.

Dkaz: Prvn tvrzen je zejm. Druh vyplv zfaktu, e vechny vrcholy kliky je teba obarvit rznmi barvami. Tet vyplv ztoho, e stejn obarven vrcholy tvo nezvislou mnoinu. Obarvme-li tedy graf (G) barvami, zskme (G) nezvislch mnoin, znich kad obsahuje nejve (G) vrchol.Kdkazu tvrtho tvrzen obarvme nejpoetnj nezvislou mnoinu prvn barvou. Kobarven zbvajcch n (G) vrchol zcela jist sta n (G) barev. Plat tedy n (G) + 1 (G).

.


Diskrtn matematika 12 Barevnost mapy problm ty barev12.1 Nezvislost, klika, obarven vrchol 4/5 Tvrzen. Pro libovoln graf G bez smyek plat: (G) = 1 prv tehdy, kdy graf G je diskrtn (bez hran), (G) = 2 prv tehdy, kdy graf G neobsahuje krunici lich dlky, (G) = 2 prv tehdy, kdy graf G je bipartitn.Dkaz: Prvn tvrzen je zejm. Druh tvrzen dokeme takto: Kobarven krunice lich dlky potebujeme nejmn 3 barvy. Je-li tedy (G) = 2, neme graf G takovou krunici obsahovat. Naopak, nech graf G neobsahuje krunici lich dlky. Popeme, jak lze graf obarvit dvma barvami. (Je-li graf nesouvisl, obarvme takto kadou komponentu zvl.) Zvolme pevn vrchol x. Vrcholy, kter maj od vrcholu x lichou vzdlenost (ve smyslu potu hran vnejkrat cest), obarvme barvou 1, vrcholy, kter maj sudou vzdlenost (vetn vrcholu x), obarvme barvou 2.



Pokraovn dkazu

Musme dokzat, e takto zskme skuten obarven, tzn. e dn dva stejn obarven vrcholy nejsou spojeny hranou.Vezmme tedy dva libovoln vrcholy u, v, kter maj oba lichou vzdlenost od x. Mezi vrcholy u a vvede cesta sud dlky, kter je tvoena nejkratmi cestami zu do x a zx do v. Kdyby byly vrcholy u, v spojeny hranou, tvoila by tato hrana spolu scestou u do vkrunici lich dlky. Sestrojili jsme tedy skuten obarven dvma barvami.Tet tvrzen je snadn. Kad obarven dvma barvami uruje rozklad mnoiny V(G) na dv disjunktn podmnoiny A a B. Vechny hrany mus vst pes hranici A a B, aby platilo obarven.. Graf je tedy bipartitn. Je-li naopak graf bipartitn, sta obarvit kadou zjeho stran jednou barvou.


Diskrtn matematika 12 Barevnost mapy problm ty barev12.2 Obarven mapy 1/9

Obarven grafu



Definice (dulnho grafu). Bu G = (V,E) topologick rovinn graf a bu Smnoina stn grafu G. Definujeme graf G* = (S,E,), kde je relace na S:

(e)= {Si, Sj},

jestlie hrana e je spolenou hranic Si a Sj (piem me bt i Si = Sj , jestlie hrana e m zobou stran tut stnu). Tento graf G* = (S,E,) nazvme (geometrickm) dulem grafu G.



Konstrukce dulnho grafu I. Mjme rovinn graf G. Uvnit kad stny Sgrafu G zvolme bod bS a kad hran e piadme oblouk protnajc hranu e a spojujc body bS a bS kde S a S jsou stny pilhajc khran e. Vsledkem je graf G*, nap.:



Konstrukce dulnho grafu II.



Tvrzen (vlastnosti dulnho grafu). Mjme souvisl rovinn graf G. Duln graf G* m tyto vlastnosti:

Duln graf je tak souvisl a rovinn,Duln graf kdulnmu grafu je pvodn graf (G*)* = G,Dualita pevd vrcholy grafu G na stny grafu G*,Smyce vgrafu G odpovd most vgrafu G* a naopak.

Tvrzen (problm ty barev). Pro kad rovinn graf G plat (G) 4.

Dkaz tohoto historicky vhlasnho tvrzen byl podn teprve nedvno a je mimodn sloit.



Tvrzen. Pro kad rovinn graf G = (V,E) plat 5.

Dkaz: Provd se indukc podle potu vrchol.Pokud je |V| 5, zvolme pro kad vrchol jinou barvu. Jestlie je |V| 6, pak pro jeden z vrchol je degG(v) 5. Nech je degG(v) < 5 a nech graf G vje obarviteln pti barvami. Pak i graf G je obarviteln pti barvami, nebo vrcholu vse piad barva odlin od barev jeho soused.Nedokzn zstal ppad, kdy pro vrchol v je degG(v) = 5. Sousedy vrcholu vozname po ad t, u, x, z, y. Opt vyjdeme zpedpokladu, e graf G= G - v je obarven pti barvami. Je-li

|{b(u),b(x),b(y),b(z),b(t)}| < 5,

pak vrcholu vpiadme nkterou zbvajc barvu. Pedpokldejme, e



Uvaujme vrcholy x a y a nech Vx,y je mnoina vech vrchol grafu G, kter maj barvu bu b(x) nebo b(y). Samozejm je x,y Vx,y. Nyn rozlime dva ppady: ppad, kdy neexistuje vgrafu G cesta zx do y pouvajc pouze vrcholy nleejc do Vx,y a ppad, kdy takov cesta existuje.Pokraovn dkazu|{b(u),b(x),b(y),b(z),b(t)}| = 5,



Pokraovn dkazu

1. Ozname Vx,y mnoinu tch vrchol s V(G), kter jsou vgrafu Gspojeny svrcholem x cestou pouvajc pouze vrcholy zmnoiny Vx,y. Definujeme nov obarven bpedpisemTo znamen, e jsme na mnoin Vx,y zmnili barvy. bje opt obarven a protoe b(x) = b(y) = b(y), meme poloit b(v) = b(x) a graf je opt obarven pti barvami.



Pokraovn dkazu

Existuje-li cesta P zx do y, jej vechny vrcholy jsou prvk

Date post:	01-Jan-2016
Category:	Documents
Upload:	emmanuel-parsons
View:	48 times
Download:	1 times

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

Documents