MA2BP_PDM1 Diskrétní matematika 1 6. Bipartitní a Hamiltonovské grafy Lukáš Másilko Středisko pro pomoc studentům se specifickými nároky Masarykova univerzita 14. 11. 2017 14. 11. 2017 1/30 Program prezentace □ Bipartitní grafy Hamiltonovské grafy Použité zdroje 14. 11. 2017 2 / 30 Bezproblémové skupiny ve třídě Ve třídě je 12 dětí. Děti bývají pro denní aktivity obvykle rozděleny do tří skupin. Dnes je ale zapotřebí rozdělit je jen do dvou skupin. Je známo, že některé dvojice dětí, když jsou pohromadě, dělají problémy (zlobí se, perou atd.) - viz následující přehled. Zjistěte, zda je možné provést rozdělení dětí tak, aby žádné "problematické" děti nebyly spolu v jedné skupině. c, f g ■■■ d b h r m m m a, i, 1 i... c, f d ... g j ... e, f e ^■n" m m m j, k, 1 k ... e f... 3, Í, j, 1 /... c, e, f 14. 11. 2017 3 / 30 Bezproblémové skupiny grafem Vztahy dětí lze jednoduše znázornit neorientovaným grafem: 14. 11. 2017 4 / 30 Bipartitnŕ grafy Definice 2.1 (MILKOVA): Bipartitní graf je graf G = (V, E), jehož množinu vrcholu můžeme rozdělit do dvou množin V\ a V2 tak, že H Vi n v2 = 0, g V1 U V2 = V a B každá hrana grafu G má jeden koncový vrchol v množině V± a druhý v množině V2. Úplný bipartitní graf Km^n = (Vi U V2, ŕ) je bipartitní graf, kde |Vi| = m, I V2I = n a každý z m vrcholů množiny Vi je spojen s hranou s každým z n vrcholů množiny V2. -' Poznámka: Úplný bipartitní graf Km^n má m • r? hran. 14. 11. 2017 5 / 30 Bezproblémové skupiny - řešení Ještě jednou si zobrazíme graf všech dětí a jejich vztahů: □ S Bezproblémové skupiny - řešení Dítě a nemůže být ve stejné skupině jako děti c, f (hrany a — c, a — f), zároveň děti c, f spolu mohou být ve skupině (neexistuje hrana c — f). 14. 11. 2017 6 / 30 Bezproblémové skupiny - řešení Vi V2 a c, f Dítě f nemůže být ve stejné skupině jako děti které naopak mohou být ve skupině s dítětem a (neexistují hrany a — /, a — j\ a — /). 14. 11. 2017 6 / 30 Bezproblémové skupiny - řešení Vi v2 3, Í, j, 1 c, f Dítě e nemůže být ve stejné skupině jako děti j, /c, /, dítě k naopak může být ve skupině s dětmi a, ij, I (neexistují hrany mezi těmito 5 dětmi). 14. 11. 2017 6 / 30 Bezproblémové skupiny - řešení Vi v2 a, i, j, k, 1 c, e, f Děti d,g nemohou být ve stejné skupině, nemají však vztah s žádným jiným dítětem. Proto je do skupin můžeme rozdělit libovolně. 14. 11. 2017 6 / 30 Bezproblémové skupiny - řešení Vi v2 a, d, i, j, k, 1 c, e, f, g Děti b, h jsou bezkonfliktní, můžeme je tudíž přidat do libovolné skupiny. Abychom měli vyrovnaný počet, budou ve skupině V2. 14. 11. 2017 6 / 30 Bezproblémové skupiny - řešení Výsledné rozdělení (není jediné možné): Vi v2 a, d, i, j, k, 1 b, c, e, f, g, h Kdy jsou kružnice bipartitními grafy? Poznámka: Je patrné, že kružnice sudé délky jsou bipartitními grafy. Názorně si to můžeme ukázat na C4, Q (viz následující obrázek). ©—© 14. 11. 2017 7 / 30 Kdy jsou kružnice bipartitními grafy? Poznámka: Je patrné, že kružnice sudé délky jsou bipartitními grafy. Názorně si to můžeme ukázat na C4, Q (viz následující obrázek). Pro kružnice liché délky platí následující věta: Věta 2.1 (MILKOVA): Pro každý graf G = (V, E) platí: | Graf G je bipartitní právě tehdy, když G neobsahuje kružnici liché délky. I K důkazu Věty 2.1 budeme potřebovat dokázat pomocná tvrzení Lemma 1, Lemma 2 (viz následující slajdy). 14. 11. 2017 7 / 30 Lemma 1 (MILKOVA): Uzavřený sled liché délky k (k > 3) obsahuje kružnici liché délky. Důkaz: Provedeme indukcí vzhledem k délce uzavřeného sledu. Lemma 1 (MILKOVA): Uzavřený sled liché délky k {k > 3) obsahuje kružnici liché délky. Důkaz: Provedeme indukcí vzhledem k délce uzavřeného sledu. Sáze; je-li k = 3, pak uzavřeným sledem délky 3 je "trojúhelník", tj. kružnice liché délky. Lemma 1 (MILKOVA): Uzavřený sled liché délky k (k > 3) obsahuje kružnici liché délky. Důkaz: Provedeme indukcí vzhledem k délce uzavřeného sledu. Sáze; je-li k = 3, pak uzavřeným sledem délky 3 je "trojúhelník", tj. kružnice liché délky. Indukční předpoklad: Uzavřený sled liché délky k {k > 3) obsahuje kružnici liché délky. Lemma 1 (MILKOVA): Uzavřený sled liché délky k {k > 3) obsahuje kružnici liché délky. Důkaz: Provedeme indukcí vzhledem k délce uzavřeného sledu. Sáze; je-li k = 3, pak uzavřeným sledem délky 3 je "trojúhelník", tj. kružnice liché délky. Indukční předpoklad: Uzavřený sled liché délky k {k > 3) obsahuje kružnici liché délky. Indukční krok: Mějme uzavřený sled S = (vq, či, ..., e/r+i, Vk+i, e/c+2> ^o) liché délky k + 2. Pro sled S mohou nastat dva případy: Lemma 1 (MILKOVA): Uzavřený sled liché délky k {k > 3) obsahuje kružnici liché délky. Důkaz: Provedeme indukcí vzhledem k délce uzavřeného sledu. Sáze; je-li k = 3, pak uzavřeným sledem délky 3 je "trojúhelník", tj. kružnice liché délky. Indukční předpoklad: Uzavřený sled liché délky k {k > 3) obsahuje kružnici liché délky. Indukční krok: Mějme uzavřený sled S = (vq, či, ..., e/r+i, Vk+i, e/c+2> ^o) liché délky k + 2. Pro sled S mohou nastat dva případy: □ Uzavřený sled liché délky S je kružnice lemma je dokázáno. Q Uzavřený sled liché délky S není kružnice, viz obrázek: Pokračovaní důkazu Lemmatu 1 Uzavřený sled S liché délky není kružnice: 14. 11. 2017 9 / 30 Pokračování důkazu Lemmatu 1 Uzavřený sled S liché délky není kružnice: —O ©l JS) o —O © (J) o S musí obsahovat kružnici C = (v,-, e,-+i, V7+1,..., e,-, v: = v,-): 14. 11. 2017 9 / 30 Pokračovaní důkazu Lemmatu 1 Je-li kružnice C (vyznačená červeně) liché délky, je důkaz hotov (uzavřený sled liché délky obsahuje kružnici liché délky). 14. 11. 2017 10 / 30 Pokračování důkazu Lemmatu 1 O O Je-li kružnice C (vyznačená červeně) sudé délky, pak odebráním posloupnosti (v/, e/+i, V7+1,..., ej) ze sledu S dostaneme uzavřený sled S' liché délky menší než k. Proč? □ s1 = 1 -o o 14. 11. 2017 10 / 30 Pokračovaní důkazu Lemmatu 1 Je-li kružnice C (vyznačená červeně) sudé délky, pak odebráním posloupnosti (v,-, e,-+i, ..., e/) ze sledu S dostaneme uzavřený sled S; liché délky menší než k. Proč? (Přece sled S byl liché délky a obsahoval kružnici C sudé délky Odebráním sudého počtu hran ze sledu S má zbývající uzavřený sled Sř lichou délku.) 14. 11. 2017 10 / 30 Pokračovaní důkazu Lemmatu 1 Je-li kružnice C (vyznačená červeně) sudé délky, pak odebráním posloupnosti (v,-, e,-+i, ..., vj-i, ej) ze sledu S dostaneme uzavřený sled S' liché délky menší než k. Proč? (Přece sled S byl liché délky a obsahoval kružnici C sudé délky Odebráním sudého počtu hran ze sledu S má zbývající uzavřený sled Sf lichou délku.) Uzavřený sled Sf má lichou délku menší než k. =4> dle indukčního předpokladu sled Sř C S obsahuje lichou kružnici. =4> sled S obsahuje lichou kružnici. =4> Indukční krok a celý důkaz je hotov. 14. 11. 2017 10 / 30 Lemma 2 Lemma 2 (MILKOVA): Kružnice liché délky není bipartitní graf. Důkaz (nebude vyžadován u zkoušky): Předpokládejme sporem, že kružnice liché délky C = (vq, ei, v±,..., e/r, = vq) je bipartitním grafem (/c je liché číslo). 14. 11. 2017 11 / 30 Lemma 2 Lemma 2 (MILKOVA): Kružnice liché délky není bipartitní graf. Důkaz (nebude vyžadován u zkoušky): Předpokládejme sporem, že kružnice liché délky C = (vq, ei, v±,..., e^, = vq) je bipartitním grafem (/c je liché číslo). Rozdělme vrcholy kružnice do dvou skupin, V\ bude mít vrcholy s lichým indexem, V2 vrcholy se sudým indexem. Co vrchol vq = v^? Kam s ním? Barva? j 14. 11. 2017 11 / 30 Podmínka pro bipartitní graf Vraťme se nyní k větě, která udává nutnou a dostačující podmínku pro to, aby graf byl bipartitní. Věta 2.1 (MILKOVA): Pro každý graf G = {V, E) platí: Graf G je bipartitní právě tehdy, když G neobsahuje kružnici liché délky. Důkaz (nebude vyžadován u zkoušky): 14. 11. 2017 12 / 30 Podmínka pro bipartitní graf Vraťme se nyní k větě, která udává nutnou a dostačující podmínku pro to, aby graf byl bipartitní. Věta 2.1 (MILKOVA): Pro každý graf G = {V, E) platí: Graf G je bipartitní právě tehdy, když G neobsahuje kružnici liché délky. Důkaz (nebude vyžadován u zkoušky): Provádíme ověřením obou implikací O G je bipartitní =4> G neobsahuje kružnici liché délky. B G neobsahuje kružnici liché délky =4> G je bipartitní. 14. 11. 2017 12 / 30 Důkaz Věty 2.1 ve směru Tvrzení 1: G je bipartitní =4> G neobsahuje kružnici liché délky. Důkaz: Použijeme metodu obměny (kontrapozice). Ta je založena na následující tautologii: j (-.6 ^A) ^>(A^ B) 14. 11. 2017 13 / 30 Důkaz Věty 2.1 ve směru Tvrzení 1: G je bipartitní =4> G neobsahuje kružnici liché délky. Důkaz: Použijeme metodu obměny (kontrapozice). Ta je založena na následující tautologii: (-.6 ^A) ^ (A^ B) Tvrzení 1 je ve tvaru A =4> B. Vytvořme jeho kontrapozici -iB =4> -iA (*): G obsahuje kružnici liché délky =4> G není bipartitní. 14. 11. 2017 13 / 30 Důkaz Věty 2.1 ve směru Tvrzení 1: G je bipartitní =4> G neobsahuje kružnici liché délky. J Důkaz: Použijeme metodu obměny (kontrapozice). Ta je založena na následující tautologii: (-.6 ^A) ^ (A^ B) Tvrzení 1 je ve tvaru A =4> B. Vytvořme jeho kontrapozici -iB =4> -iA (*): G obsahuje kružnici liché délky =4> G není bipartitní. Tvrzení (*) zřejmě platí, dle Lemmatu 2 (Kružnice liché délky není bipartitní graf). 14. 11. 2017 13 / 30 Důkaz Věty 2.1 ve směru Tvrzení 1: G je bipartitní =4> G neobsahuje kružnici liché délky. J Důkaz: Použijeme metodu obměny (kontrapozice). Ta je založena na následující tautologii: (-.6 ^A) ^ (A^ B) Tvrzení 1 je ve tvaru A =4> B. Vytvořme jeho kontrapozici -iB =4> -iA (*): G obsahuje kružnici liché délky =4> G není bipartitní. Tvrzení (*) zřejmě platí, dle Lemmatu 2 (Kružnice liché délky není bipartitní graf). Závěr: Z platnosti tvrzení (*) vyplývá pravdivost Tvrzení 1. 14. 11. 2017 13 / 30 Důkaz Věty 2.1 ve směru <^= Tvrzení 2: G neobsahuje kružnici liché délky =4> G je bipartitní. Důkaz: Předpokládejme sporem, že Tvrzení 2 neplatí, tj. 14. 11. 2017 14 / 30 Důkaz Věty 2.1 ve směru <^= Tvrzení 2: G neobsahuje kružnici liché délky =4> G je bipartitní._J Důkaz: Předpokládejme sporem, že Tvrzení 2 neplatí, tj. (**) G neobsahuje kružnici liché délky A G není bipartitní. Bez újmy na obecnosti ještě předpokládejme, že je graf G souvislý. 14. 11. 2017 14 / 30 Důkaz Věty 2.1 ve směru <^= Tvrzení 2: G neobsahuje kružnici liché délky =4> G je bipartitní. j Důkaz: Předpokládejme sporem, že Tvrzení 2 neplatí, tj. (**) G neobsahuje kružnici liché délky A G není bipartitní. Bez újmy na obecnosti ještě předpokládejme, že je graf G souvislý. Zvolme pevně vrchol v G V. Rozdělme množinu vrcholů na dvě skupiny: ■ Vi obsahuje ty vrcholy, jejichž nejkratší vzdálenost od v je lichá. ■ V2 obsahuje ty vrcholy, jejichž nejkratší vzdálenost od v je sudá. 14. 11. 2017 14 / 30 Pokračovaní důkazu Věty 2.1 ve směru <^= Znázorněme si rozdělení množiny vrcholů na dvě skupiny V] □ S Pokračovaní důkazu Věty 2.1 ve směru <^= Protože graf G není bipartitní, existuje hrana e = {x,y}, jejíž oba koncové vrcholy patří např. do skupiny V\. 14. 11. 2017 15 / 30 Pokračování důkazu Věty 2.1 ve směru <= Nejkratší cesta z vrcholu v do vrcholu x je liché délky. Nejkratší cesta z vrcholu v do vrcholu y je liché délky. Celkem: nejkratší cesta C z x do y přes vrchol v je sudé délky. □ i3> Pokračovaní důkazu Věty 2.1 ve směru <^= Doplňme sled C o přímou hranu e = {x,y} =4> v grafu G vzniká uzavřený sled S liché délky. 14. 11. 2017 15 / 30 Pokračovaní důkazu Věty 2.1 ve směru <^= Uzavřený sled S liché délky obsahuje dle Lemmatu 1 kružnici liché délky =4> spor s předpokladem (**). Závěr: Tvrzení 2, tj. opak tvrzení (**), platí. 14. 11. 2017 15 / 30 Příklad 1 Rozhodněte, zda je následující graf bipartitní. Svou odpověď zdůvodněte. 14. 11. 2017 16 / 30 Příklad 1 Rozhodněte, zda je následující graf bipartitní. Svou odpověď zdůvodněte. Řešení: Graf není bipartitní, protože obsahuje kružnice liché délky, napr. trojúhelník na vrcholech {e, f, h} či kružnici délky 5 na vrcholech {b, c, f, h, e}. 14. 11. 2017 16 / 30 Příklad 2 Rozhodněte, zda je následující graf bipartitní. Svou odpověď zdůvodněte. ©—© 14. 11. 2017 17 / 30 Příklad 2 Rozhodněte, zda je následující graf bipartitní. Svou odpověď zdůvodněte. ©—© Řešení: Graf je bipartitní, rozdělení vrcholů je následující: Vi = {a,c,e,g,j}, V2 = {b,d,f,h,i}. 14. 11. 2017 17 / 30 Trasa výletu Přátelé s dětmi se vydali na výlet. Rodiče pro své děti vymysleli zajímavý úkol. Na začátku výletu, v obci h, dali dětem do ruky mapu, na níž bylo zakresleno celkem 12 obcí. Dvě obce x,y jsou na mapě propojeny čárou, je-li pěší cesta mezi x,y uskutečnitelná. Úkolem dětí je vymyslet trasu výletu tak, aby začala a končila v obci h a vedla každou obcí právě jednou. Hamiltonovská kružnice a graf Definice 2.2 (MILKOVA): Hamiltonovská kružnice v grafu G je kružnice obsahující všechny vrcholy grafu G. Hamiltonovský graf je graf, ve kterém existuje hamiltonovská kružnice. Historická poznámka: William Rowan Hamilton (1805-1865) vymyslel v r. 1853 hru s názvem Icosian Game (později Cesta kolem světa), v níž použil pravidelný dvanáctistěn. Vrcholy představovaly světová města a byly označeny kolíkem. Cílem hry bylo natáhnout vlákno, které by procházelo kolem všech kolíků a tvořilo tak kružnici. Dvanáctistěn a jeho grafová reprezentace Trasa výletu - řešení Matematicky je možné vyjádřit úkol dětí takto: Najděte hamiltonovskou kružnici v následujícím grafu, která začíná a končí vrcholem h. 14. 11. 2017 21 / 30 Trasa výletu - řešení Matematicky je možné vyjádřit úkol dětí takto: Najděte hamiltonovskou kružnici v následujícím grafu, která začíná a končí vrcholem h. Rešení: h g c b m e j 1 a f d k h □ [S1 ► < -E ► < = 14. 11. 2017 21 / 30 Úloha šachového jezdce Zadání: Šachový jezdec má projít prázdnou šachovnici tak, aby na každé pole vstoupil právě jednou a vrátil se při posledním tahu na výchozí pole. Podmínka návratu na stejné místo často nebývá nutná, v takovém případě jde o hamiltonovskou cestu. Ks \ / / \ v. r 14. 11. 2017 22 / 30 Úloha jezdce - slavný matematický problém ■ Abraham de Moivre (1667-1754): na počátku 18. století podal jedno z prvních řešení - ukážeme si za chvíli jeho princip. ■ Leonard Euler (1707-1783): problémem se začal zabývat v r. 1757, o dva roky později úlohu zobecnil pro šachovnici n x n. m Další úspěšní řešitelé: A. T. Vandermond (1735-1796), C. F. Gauss (1777-1855), K. F. Jánisch (1813-1872, řešení ve tvaru magického čtverce), ... ■ Peter Guthrie Tait (1831-1901): úlohu jako první řešil grafově. Vrcholy grafu reprezentovaly jednotlivé pole šachovnice. Dva vrcholy spojil hranou tehdy, když mezi odpovídajícími poli mohl jezdec vykonat jeden tah. Je zřejmé, že grafová reprezentace řešení příliš neusnadňuje. 14. 11. 2017 23 / 30 Řešení úlohy šachového jezdce (de Moivre) Šachovnici si rozdělíme na dvě části, vnitřních 16 polí a zbylá pole na okraji, na nichž se snažíme jezdcem táhnout. r i 14. 11. 2017 24 / 30 Řešení úlohy šachového jezdce (de Moivre) Šachovnici si rozdělíme na dvě části, vnitřních 16 polí a zbylá pole na okraji, na nichž se snažíme jezdcem táhnout. i 1 14. 11. 2017 24 / 30 Řešení úlohy šachového jezdce (de Moivre) Šachovnici si rozdělíme na dvě části, vnitřních 16 polí a zbylá pole na okraji, na nichž se snažíme jezdcem táhnout. 71 r i 1 2 1 14. 11. 2017 24 / 30 Řešení úlohy šachového jezdce (de Moivre) Dostaneme se do situace, kdy už jezdcem nemůžeme táhnout po okraji šachovnice. Jediná možnost je vstoupit do vnitřní oblasti. 16 5 18 7 15 4 17 6 8 19 3 14 20 9 13 2 12 23 10 21 1 1 11 22 24 14. 11. 2017 25 / 30 Řešení úlohy šachového jezdce (de Moivre) Táhneme tedy jezdcem do vnitřních 16 polí. Dokončit zbývající tahy už nebývá problém. 16 5 18 7 15 4 17 6 8 19 3 14 20 9 13 2 I 12 23 10 21 1 24 11 22 14. 11. 2017 26 / 30 Podmínky pro Hamiltonovský graf Nebyla dosud nalezená nutná a zároveň postačující podmínka pro existenci Hamiltonovského grafu. Postačující podmínky: Q Dirac, 1952: Nechť G = (\/, E) je konečný graf, \ V\ = n > 3 a st x > pro každý uzel x G V. Pak graf G je Hamiltonovský. (Věta 6.12, FUCHS) B Ore, 1960: Buď G = (\/, E) je konečný graf, |\/| > 3. Nechť pro každé uzly x,y G V, které nejsou sousední, platí st x + st y > | V . Pak graf G je Hamiltonovský. (Věta 6.13, FUCHS) Nutná podmínka ; Buď G Hamiltonovský graf. Pak G je uzlově 2-souvislý (tj. i po odebrání vrcholu zůstane souvislý). (Věta 6.11, FUCHS) 14. 11. 2017 27 / 30 Příklady grafů Hamiltonovský graf, který nesplňuje Diracovu (postačující) podmínku vrcholy a, c/, e nemají stupeň > i: Další rady pro hledání hamiltonovské kružnice (MILKOVA) H Jestliže vrchol v má stupeň k, pak hamiltonovská kružnice musí obsahovat právě dvě hrany incidentnís vrcholem v. B Jakmile hamiltonovská kružnice, kterou konstruujeme, prochází vrcholem v, pak ostatní nepoužité hrany incidentnís tímto vrcholem již můžeme vyloučit (nebudou ležet v hamiltonovské kružnici). 14. 11. 2017 29 / 30 Použité zdroje ✓ _ □ MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. 123 s. ISBN 978-80-7435-267-6. B FUCHS, Eduard. Diskrétni matematika pro učitele. 1. vyd. Brno: Masarykova univerzita, 2001. 178 s. ISBN 80-210-2703-7. B SISMA, Pavel. Teorie grafů 1736-1963. 1. vyd. Praha: Přírodovědecká fakulta Masarykovy univerzity v Brně, 1997. ISBN 80-7196-065-9. 14. 11. 2017 30 / 30