MA2BP_PDM1 Diskrétní matematika 1 1. Základní pojmy Lukáš Másilko Středisko pro pomoc studentům se specifickými nároky Masarykova univerzita 19. 9. 2017 Program prezentace Organizace předmětu Graf, vrcholy, hrany Skóre grafu Úplný graf, doplněk grafu 19. 9. 2017 2 / 26 Výuka Dva předměty vzájemně provázané □ MA2BP_PDM1 Diskrétní matematika 1 - přednáška se koná v pondělí od 15:45 do 17:25, je individuálně nahrazena v termínu úterý 9:00-10:35 v učebně 117 Střediska Teiresiás. B MA2BP_CDM1 Cvičení z diskrétní matematiky 1 - v termínu středa 7:30-8:15 v učebně 24 Pedagogické fakulty, Poříčí 31. B Podpůrná výuka, v níž budeme probírat nejasnosti z přednášek a cvičení - v termínu středa 12:20-13:55 v učebně 117 Střediska Teiresiás. 19. 9. 2017 3 / 26 Požadavky □ MA2BP_CDM1 Cvičení z diskrétní matematiky 1: zápočtový test na konci semestru, v době konání poslední přednášky - k udělení zápočtu je třeba získat 60 % bodů. Zápočet je podmínkou pro připuštění ke kolokviu. B MA2BP_PDM1 Diskrétní matematika 1: kolokvium formou ústní zkoušky u dr. Břetislava Fajmona 19. 9. 2017 4 / 26 Literatura Doporučená literatura □ FUCHS, Eduard. Diskrétní matematika pro učitele. 1. vyd. Brno: Masarykova univerzita, 2001. 178 s. ISBN 80-210-2703-7. B MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. 123 s. ISBN 978-80-7435-267-6. Doplňující, nepovinná literatura ■ NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL-Nakladatelství technické literatury, 1979. 316 s. 19. 9. 2017 5 / 26 Konkurz Jedna instituce vypsala konkurz na obsazení 5 míst pro překladatele, a to z ruštiny, němčiny, angličtiny, francouzštiny a španělštiny. Přihlásilo se 5 uchazečů, kteří ovládali některé z těchto jazyků. ■ Bárta ovládal všech 5 jazyků, ■ Kopal angličtinu, francouzštinu a ruštinu, ■ Lehký němčinu a ruštinu, ■ Novák angličtinu a němčinu a ■ Zeman ruštinu a němčinu. Mohla instituce přijetím těchto uchazečů obsadit místa tak, aby každý z nich překládal jen z jednoho jazyka? Pokud ano, navrhněte řešení. 19. 9. 2017 6 / 26 Konkurz - grafová reprezentace Graf, vrcholy, hrany Definice 1.1 (Milkova): Obyčejný graf je uspořádaná dvojice (\/, E), kde ■ V je neprázdná množina vrcholů (někdy též uzlů, angl. vertex), m E je množina hran (angl. edge), přičemž hrana e je dvouprvková podmnožina množiny V. Poznámky □ Vrcholy zakreslujeme v rovině pomocí kružnic, hrany jsou úsečky spojující dva vrcholy. Q Definice odpovídá tzv. neorientovanému grafu, tj. hrany nemají orientaci. (Je-li e hrana mezi uzly x,y, pak vztah chápeme obousměrně: x —> y, y —> x.) 19. 9. 2017 8 / 26 Zadání grafu Matematicky: G = (\/, E); V = {a, b, c, c/, e}; E = Ua> ía> c}> {3> d}> ib, c}> {^^ d}> íc> d}> íc> e}} Maticí sousednosti í° 1 1 1 0 \ 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 0 0 Tabulkou a b c d e a 0 1 1 1 0 b 1 0 1 1 0 c 1 1 0 1 1 d 1 1 1 0 0 e 0 0 1 0 0 Grafem - zkuste zakreslit sami <0 0,0 19. 9. 2017 9 / 26 Další pojmy Definice 1.2 (Milkova): Nechť e = {v, w} je hrana grafu G. ■ Vrcholy v, w nazýváme koncovými vrcholy hrany e nebo též vrcholy incidentní s hranou e. ■ Vrchol v nazýváme sousedním vrcholem vrcholu w, resp. vrchol w nazýváme sousedním vrcholem vrcholu v. Příklad: v následujícím grafu je vrchol a incidentní s vrcholy b, c, d. Pouze vrchol c je sousedním vrcholem uzlu e. Další pojmy (2) Definice 1.3 (Milkova): H Graf G = (V,E)se rovná grafu Gf = {V\ E'), jestliže V = V a E = E'. B Graf G = (V, E) je podgraf grafu G' = (W, E'), jestliže \/ C W a £CP, B Graf G = (V, E) je podgraf grafu G' — {V1\ E') indukovaný vrcholy množiny V, jestliže V C V' a E C E;, přičemž v množině E jsou právě všechny hrany z množiny E;, jejichž koncové vrcholy leží v množině V. Alternativní definice 3: Graf G = (V, E) je podgraf grafu G' — (V, E') indukovaný vrcholy množiny V, jestliže ■ G je podgrafem G' a zároveň ■ G obsahuje všechny hrany grafu G' mezi dvojicemi vrcholů z G. 19. 9. 2017 11 / 26 Příklad Na následujících obrázcích je tentýž graf G, v němž je barevně zvýrazněna určitá množina G' vrcholů a hran. Určete, zda G' je podgraf grafu G, resp. zda G' je indukovaný podgraf grafu G. 19. 9. 2017 12 / 26 Stupeň grafu Definice 1.4 (Milkova): Stupeň vrcholu v v grafu G je číslo rovnající se počtu hran incidentních s vrcholem v. Značíme jej degc(v) nebo krátce dcjv)._ Příklad: v následujícím grafu platí: dG(a) = dG(b) = dG(d) = 3, dG(c) = 4, dG(e) = 1 Konkurz - řešení Mohla instituce přijetím těchto uchazečů obsadit místa tak, aby každý z nich překládal jen z jednoho jazyka? 19. 9. 2017 14 / 26 Konkurz - řešení 19. 9. 2017 15 / 26 Konkurz - řešení 19. 9. 2017 16 / 26 Konkurz - řešení 19. 9. 2017 17 / 26 Konkurz - řešení 19. 9. 2017 18 / 26 Konkurz - řešení 19. 9. 2017 19 / 26 Princip sudosti Věta 1.1 (Milkova): Pro každý graf G = (!/,£) platí vztah Y,vevdg{y) = 2- |E|. Poznámka: Jinými slovy: součet stupňů všech vrcholů je dvojnásobkem počtu hran. Důkaz: □ Libovolná hrana je incidentní právě s dvěma uzly. B V součtu Ylvev ^g{v) stupňů všech vrcholů je tedy každá hrana započítána dvakrát. B Sečteme-li stupně všech vrcholů, dostaneme dvojnásobek počtu hran. Důsledek 1.1 (Milkova): Počet vrcholů lichého stupně v grafu G je sudý. 19. 9. 2017 20 / 26 Skóre grafu Definice 1.5 (Milková): Necht G = (\/, E) je graf s n vrcholy vii v2i • • • i vn- Skóre grafu je posloupnost (č/ n — dn. Potom D je skóre grafu, právě když D' je skóre grafu. Poznámka: Věta 1.2 dává návod, jak zjistit, zda zadané skóre určuje graf. Postupně vytváříme posloupnosti, které mají vždy o jeden prvek méně. Skončíme tehdy, když je jasné, zda aktuálně skóre jsme schopni " přeměnit" v graf. Sérii posloupností lze následně použít i pro nakreslení grafu daného počáteční posloupností. Za chvíli si ukážeme jak. 19. 9. 2017 22 / 26 Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je skóre grafu. Řešení: Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je skóre grafu. Řešení: □ Nejprve ověříme, zda počet lichých čísel je sudý (důsledek principu sudosti) a zda poslední číslo posloupnosti je menší počet jejích prvků. 2 I 3 Ta 5 19. 9. 2017 23 / 26 Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je skóre grafu. Řešení: □ Nejprve ověříme, zda počet lichých čísel je sudý (důsledek principu sudosti) a zda poslední číslo posloupnosti je menší počet jejích prvků. B počet prvků: 8, as = 6, předěl: 8 — 6 = 2: (1, 2, 4, 4, 4, 4, 5, 6) ~> (1, 1, 3, 3, 3, 3, 4) 19. 9. 2017 23 / 26 Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je skóre grafu. Řešení: Nejprve ověříme, zda počet lichých čísel je sudý (důsledek principu sudosti) a zda poslední číslo posloupnosti je menší počet jejích prvků počet prvků: 8, as = 6, předěl: 8 — 6 = 2: (1, 2, 4, 4, 4, 4, 5, 6) ~> (1, 1, 3, 3, 3, 3, 4) počet prvků: 7, aj = 4, předěl: 7 — 4 = 3: (1, 1, 3, 3, 3, 3, 4) (1, 1, 2, 2, 2, 2) 19. 9. 2017 23 / 26 Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je skóre grafu. Řešení: □ Nejprve ověříme, zda počet lichých čísel je sudý (důsledek principu sudosti) a zda poslední číslo posloupnosti je menší počet jejích prvků B počet prvků: 8, as = 6, předěl: 8 — 6 = 2: (1, 2, 4, 4, 4, 4, 5, 6) ~> (1, 1, 3, 3, 3, 3, 4) B počet prvků: 7, a7 = 4, předěl: 7 — 4 = 3: (1, 1, 3, 3, 3, 3, 4) (1, 1, 2, 2, 2, 2) □ počet prvků: 6, a§ = 2, předěl: 6 — 2 = 4: (1, 1, 2, 2, 2, 2) (1, 1, 2, 1, 1) (1, 1, 1, 1, 2) 19. 9. 2017 23 / 26 Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je skóre grafu. Řešení: □ Nejprve ověříme, zda počet lichých čísel je sudý (důsledek principu sudosti) a zda poslední číslo posloupnosti je menší počet jejích prvků. B počet prvků: 8, as = 6, předěl: 8 — 6 = 2: (1, 2, 4, 4, 4, 4, 5, 6) ~> (1, 1, 3, 3, 3, 3, 4) B počet prvků: 7, a7 = 4, předěl: 7 — 4 = 3: (1, 1, 3, 3, 3, 3, 4) (1, 1, 2, 2, 2, 2) □ počet prvků: 6, ag = 2, předěl: 6 — 2 = 4: (1, 1, 2, 2, 2, 2) (1, 1, 2, 1, 1) (1, 1, 1, 1, 2) B počet prvků: 5, a5 = 2, předěl: 5 — 2 = 3: (1, 1, 1, 1, 2) (1, 1, 0, 0) (0, 0, 1, 1) <□► -íťp^ -<^i^ Ě <0<^O 19. 9. 2017 23 / 26 Jak zjistit, že skóre určuje graf? Příklad: Určete pomocí Věty 1.2, zda posloupnost (1,2,4,4,4,4,5,6) je I skóre grafu. I Řešení: □ Nejprve ověříme, zda počet lichých čísel je sudý (důsledek principu sudosti) a zda poslední číslo posloupnosti je menší počet jejích prvků. B počet prvků: 8, as = 6, předěl: 8 — 6 = 2: (1, 2, 4, 4, 4, 4, 5, 6) (1, 1, 3, 3, 3, 3, 4) B počet prvků: 7, aj = 4, předěl: 7 — 4 = 3: (1, 1, 3, 3, 3, 3, 4) (1, 1, 2, 2, 2, 2) □ počet prvků: 6, ag = 2, předěl: 6 — 2 = 4: (1, 1, 2, 2, 2, 2) (1, 1, 2, 1, 1) (1, 1, 1, 1, 2) Q počet prvků: 5, a$ = 2, předěl: 5 — 2 = 3: (1, 1, 1,1, ) (1, 2, 4, 4, 4, 4, 5, 6) (0, 0, 1, 1): (1, 1, 1, 1,2): (1, 1,3, 3, 3, 3, 4): 19. 9. 2017 24 / 26 Úplný graf Definice 1.6 (Milkova): Úplný graf na množině n vrcholů je graf s n vrcholy (r? > 1), ve kterém je každý uzel spojen se všemi ostatními vrcholy hranou. Značíme jej Kn. Příklady: K2 K3 o o © 19. 9. 2017 25 / 26 Doplněk grafu Definice 1.7 (Milkova): Doplněk grafu G = {V,-E) grafu G = {V, E) je graf, jehož množina hran -E je množina všech hran úplného grafu na množině vrcholů V, které neleží v E. Příklad: na následujícím obrázku je graf o pěti vrcholech a jeho doplněk.