IB112 Základy matematiky Grafy Jan Strejček Obsah ■ Základní pojmy m graf, základní typy grafů ■ stůpen vrcholů ■ podgrafy a izomorfismůs ■ orientované grafy, ohodnocené grafy, můltigrafy ■ Souvislost grafu u soůvislé komponenty ■ vyšší stůpne soůvislosti ■ Stromy u stromy, kořenové stromy, ůsporádané stromy ■ izomorfismůs stromů ■ kostra grafů ■ Toky v sítích u síte, toky a rezy ■ Ford-Fůlkersonův algoritmůs IB112 Základy matematiky: Grafy 2/108 Základní pojmy IB112 Základy matematiky: Grafy 3/108 Graf (Neorientovaný) graf je dvojice G = (V, E), kde ■ V je množina uzlů nebo též vrcholů a ■ E je množina hran, kde hrana je dvouprvková podmnožina množiny V. Příklad G = ({1, 2,3,4,5}, {{1, 2}, {2,5}, {2,3}, {3,4}, {3,5}}) 1 , 5 2 4 3 IB112 Základy matematiky: Grafy 4/108 Poznámky ■ Množiny vrcholů a hran grafu G zapisujeme také V (G), E (G). ■ Grafy se obvykle znázorňují graficky. 1 5-2 4-3 IB112 Základy matematiky: Grafy 5/108 Poznámky ■ Množiny vrcholů a hran grafu G zapisujeme také V (G), E (G). ■ Grafy se obvykle znázorňují graficky. ■ Na rozmístení uzlů nezáleží. \ / 4 —f-V- 2 5 1 1 4 3 IB112 Základy matematiky: Grafy 6/108 Poznámky ■ Množiny vrcholů a hran grafu G zapisujeme také V (G), E (G). ■ Grafy se obvykle znázorňují graficky. ■ Na rozmístení uzlů nezáleží. ■ Casto nám jde spíše o strukturu grafu než o pojmenování uzlů. Jména uzlu pak nepíšeme. 3 5 2 4 3 4 5 IB112 Základy matematiky: Grafy 7/108 Základní typy grafů Kružnice ■ Kružnice délky n má n > 3 vrcholů spojených n hranami do jednoho cyklů. ■ Znací se Cn. 1_2 Ce 6/// IB112 Základy matematiky: Grafy 8/108 Základní typy grafů Kružnice ■ Kružnice délky n má n > 3 vrcholů spojených n hranami do jednoho cyklů. ■ Znací se Cn. 1 — 2 Ce 6 / \ \ 3 \ 5 —A Cesta ■ Cesta délky n > 0 má n + 1 vrcholů spojených do řady n hranami. ■ ZnaCí se Pn. Pe 1—2 — 3 — 4 — 5 — 6 — 7 IB112 Základy matematiky: Grafy 9/108 Základní typy grafů Úplný graf ■ Úplný graf s n vrcholy má n > 1 vrcholů a mezi každými dvema vrcholy vede hrana. Celkem má tedy (2) hran. ■ Znací se Kn. K1 • K2 • — • K3 • •-• K4 K5 •-• IB112 Základy matematiky: Grafy 10/108 Základní typy grafů Úplný bipartitní graf ■ Úplný bipartitní graf s n > 1 a m > 1 vrcholy má n + m vrcholů rozdelených do dvoů množin po n a m prvcích. Graf má hranů mezi každými dvema vrcholy z různých skůpin. ■ Znacíse Knm. Příklad ■ Existůje graf, který je zároven úplný a úplný bipartitní? IB112 Základy matematiky: Grafy 11/108 Základní typy grafů Úplný bipartitní graf ■ Úplný bipartitní graf s n > 1 a m > 1 vrcholy má n + m vrcholů rozdelených do dvoů množin po n a m prvcích. Graf má hranů mezi každými dvema vrcholy z různých skůpin. ■ Znacíse Knm. Příklad ■ Existůje graf, který je zároven úplný a úplný bipartitní? ■ Ano. IB112 Základy matematiky: Grafy 12/108 Stupeň vrcholu Definice (Stupeň vrcholu) Stupen vrcholu u v grafu G je poCet hran vycházejících z u. Stupen vrcholu znacíme dG(u) nebo jen d (u). Příklad ■ Zjistete stupne vrcholu. / d(1) d(2) d(3) d(4) d(5) 5 2 IB112 Základy matematiky: Grafy 13/108 Stupen vrcholu Definice (Stupen vrcholu) Stupeň vrcholu u v grafu G je počet hran vycházejících z u. Stupeň vrcholu znacíme dG(u) nebo jen d (u). Příklad ■ Zjistete stupne vrcholu. / d(1) d (2) d(3) d(4) d(5) 2 3 4 1 2 Stupne vrcholu mužeme uspořádat podle velikosti: 1, 2,2,3,4 5 2 IB112 Základy matematiky: Grafy 14/108 Vlastnosti stupňů Veta Součet stupňů vrcholů v libovolném grafu je vždy sudý a rovný dvojnásobku poCtu hran. Důkaz Každá hrana vychází ze dvou uzlů a je tedy započítaná dvakrát do součtu stupňů. □ IB112 Základy matematiky: Grafy 15/108 Havlova-Hakimiho veta Veta (Havlova-Hakimiho veta) Necht d1 < d2 < ... < dn jsou nezáporná celá čísla. Existuje graf s n vrcholy stupni d1, d2,..., dn práve tehdy, když existuje graf s n - 1 vrcholy stupnu d1, d2, . . . , dn-dn-2, dn-dn-1 - 1, dn-dn - 1, . . . , dn-2 - 1, dn-1 - 1. Upravené stůpne vrcholů odpovídají tomů, že jsme odstranili vrchol s maximálním stůpnem, z nehož vedlo dn hran do vrcholů s nejvyššími st pni. IB112 Základy matematiky: Grafy 16/108 Havlova-Hakimiho veta Veta (Havlova-Hakimiho veta) Necht d1 < d2 < ... < dn jsou nezáporná celá císla. Existuje graf s n vrcholy stupnu d1, d2,..., dn práve tehdy, když existuje graf s n - 1 vrcholy stupnu d1, d2, . . . , dn-dn-2, dn-dn-1 - 1, dn-dn - 1, . . . , dn-2 - 1, dn-1 - 1. Důkaz "«=" Necht' existuje graf s n - 1 vrcholy, které mají stupne d1 , d2, . . . , dn- dn-2, dn- dn- 1 - 1 , dn-dn - 1 , . . . , dn- 1 - 1. Pokud k tomuto grafu přidáme jeden uzel, z kterého povedou hrany do dn vrcholu, které odpovídají posledním dn stupnum v uvedené posloupnosti, získáme graf s n vrcholy, které mají stupneř d1 , d2, . . . , dn. IB112 Základy matematiky: Grafy 17/108 Havlova-Hakimiho veta Veta (Havlova-Hakimiho veta) Necht d1 < d2 < ... < dn jsou nezáporná celá Čísla. Existuje graf s n vrcholy stupni d1, d2,..., dn práve tehdy, když existuje graf s n - 1 vrcholy stupnu d1, d2, . . . , dň-dň-2, dn-dn-1 - 1, dn-dn - 1, . . . , dn-2 - 1, dn-1 - 1. Důkaz "=>" Tvrzení je zrejmé, pokud z vrcholu w se stupněm dn vedou hrany do dn vrcholu s dalšími nejvyššími stupni. ... IB112 Základy matematiky: Grafy 18/108 Havlova-Hakimiho veta Veta (Havlova-Hakimiho veta) Necht d1 < d2 < ... < dn jsou nezáporná celá čísla. Existuje graf s n vrcholy stupni d1, d2,..., dn práve tehdy, když existuje graf s n - 1 vrcholy stupnu d1, d2,..^ dn-dn-2, dn-dn-1 - 1, dn-dn - 1,. . . , dn-2 - 1, dn-1 - 1. Důkaz "=>" ... V opacném případe existůjí ůzly u, v se stůpni d (u) < d (v) takové, že existůje hrana {u, w}, ale neexistůje hrana {v, w}. Pak existůje i hrana {v, v'}, kde v' = u. Hrany {u, w}, {v, v'} nahradíme hranami {u, v'}, {v, w}. Upravený graf má stejné stůpne vrcholů. ^-w w Postůp opakůjeme až získáme graf, pro nejž je tvrzení zrejmé. IB112 Základy matematiky: Grafy 19/108 Vlastnosti stůpnů Příklad ■ Existůje graf se stůpni vrcholů 1, 1, 1, 2,3,4? IB112 Základy matematiky: Grafy 20/108 Vlastnosti stůpnů Prříklad ■ Existůje graf se stůpni vrcholů 1, 1, 1, 2,3,4? ■ Dle vety je to ekvivalentní existenci grafů se stůpni 1, 0,0,1, 2. IB112 Základy matematiky: Grafy 21/108 Vlastnosti stupnu Příklad ■ Existuje graf se stupni vrcholu 1, 1, 1, 2,3,4? ■ Dle vety je to ekvivalentní existenci grafu se stupni 1, 0,0,1, 2. ■ Po seřazení stupnu řešíme existenci grafu se stupni 0,0,1, 1, 2. IB112 Základy matematiky: Grafy 22/108 Vlastnosti stůpnů Prříklad ■ Existůje graf se stůpni vrcholů 1, 1, 1, 2,3,4? ■ Dle vety je to ekvivalentní existenci grafů se stůpni 1, 0,0,1, 2. ■ Po seřazení stůpnů řešíme existenci grafů se stůpni 0,0,1, 1, 2. ■ Dle vety je to ekvivalentní existenci grafů se stůpni 0,0,0,0. IB112 Základy matematiky: Grafy 23/108 Vlastnosti stupňů Příklad ■ Existuje graf se stupni vrcholů 1,1,1,2,3,4? ■ Dle vety je to ekvivalentní existenci grafu se stupni 1,0,0,1, 2. ■ Po seřazení stupnu řešíme existenci grafu se stupni 0,0,1, 1, 2. ■ Dle vety je to ekvivalentní existenci grafu se stupni 0,0,0,0. ■ Takový graf zjevne existuje. 0, 0, 0, 0 IB112 Základy matematiky: Grafy 24/108 Vlastnosti stupňů Příklad ■ Existuje graf se stupni vrcholů 1,1,1,2,3,4? ■ Dle vety je to ekvivalentní existenci grafu se stupni 1,0,0,1, 2. ■ Po seřazení stupnu řešíme existenci grafu se stupni 0,0,1, 1, 2. ■ Dle vety je to ekvivalentní existenci grafu se stupni 0,0,0,0. ■ Takový graf zjevne existuje. ■ Postupne ho doplníme na puvodne požadovaný graf. 0,0,1,1,2 IB112 Základy matematiky: Grafy 25/108 Vlastnosti stupňů Příklad ■ Existuje graf se stupni vrcholů 1,1,1,2,3,4? ■ Dle vety je to ekvivalentní existenci grafu se stupni 1,0,0,1, 2. ■ Po seřazení stupnu řešíme existenci grafu se stupni 0,0,1, 1, 2. ■ Dle vety je to ekvivalentní existenci grafu se stupni 0,0,0,0. ■ Takový graf zjevne existuje. ■ Postupne ho doplníme na puvodne požadovaný graf. 1,1,1,2,3,4 IB112 Základy matematiky: Grafy 26/108 Vlastnosti stupnu Příklad ■ Existuje graf se stupni vrcholu 1, 1, 1, 1, 2,3,4,6,7? IB112 Základy matematiky: Grafy 27/108 Vlastnosti stupnu Příklad ■ Existuje graf se stupni vrcholu 1, 1, 1, 1, 2,3,4,6,7? ■ Práve když existuje graf se stupni 1, 0,0,0,1, 2,3,5. IB112 Základy matematiky: Grafy 28/108 Vlastnosti stůpnů Prříklad ■ Existůje graf se stůpni vrcholů 1, 1, 1, 1, 2, S, 4,6, ľ? ■ Práve když existůje graf se stůpni 1, ü, ü, ü, 1, 2, S, 5. ■ Práve když existůje graf se stůpni ü, ü, ü, 1, 1, 2, S, 5. IB112 Základy matematiky: Grafy 29/1üB Vlastnosti stupnu Příklad ■ Existuje graf se stupni vrcholu 1, 1, 1, 1, 2,3,4,6,7? ■ Práve když existuje graf se stupni 1, 0,0,0,1, 2,3,5. ■ Práve když existuje graf se stupni 0,0,0,1, 1, 2,3,5. ■ Práve když existuje graf se stupni -1, 0,0,0,0,1, 2. IB112 Základy matematiky: Grafy 30/108 Vlastnosti stupnu Příklad ■ Existuje graf se stupni vrcholu 1, 1, 1, 1,2,3,4,6,7? ■ Práve když existuje graf se stupni 1, 0,0,0,1, 2,3,5. ■ Práve když existuje graf se stupni 0,0,0,1, 1, 2,3,5. ■ Práve když existuje graf se stupni -1, 0,0,0,0,1, 2. ■ Takový graf zjevne neexistuje. IB112 Základy matematiky: Grafy 31/108 Vlastnosti stupnu Příklad ■ Existuje graf se stupni vrcholu 1, 1, 1, 1, 2,3,4,6,7? ■ Práve když existuje graf se stupni 1, 0,0,0,1, 2,3,5. ■ Práve když existuje graf se stupni 0,0,0,1, 1, 2,3,5. ■ Práve když existuje graf se stupni -1, 0,0,0,0,1, 2. ■ Takový graf zjevne neexistuje. ■ Neexistuje tedy ani graf se stupni 1, 1, 1, 1, 2,3,4,6,7. IB112 Základy matematiky: Grafy 32/108 Podgrafy Podgrafem grafu G = (V, E) je libovolný graf H = (V, E') takový, že V' c V, E' c E a pritom hrany v E1 vedou pouze mezi vrcholy ve V'. Podgraf H = (V', E') grafu G je indukovaný (množinou vrcholí V), jestliže množina jeho hran E' obsahuje všechny hrany z E vedoucí mezi vrcholy z V'. Příklad ■ H je podgraf, ale není indukovaný. •-• IB112 Základy matematiky: Grafy 33/108 Podgrafy Podgrafem grafu G = (V, E) je libovolný graf H = (V, E') takový, že V' c V, E' c E a pritom hrany v E1 vedou pouze mezi vrcholy ve V'. Podgraf H = (V', E') grafu G je indukovaný (množinou vrcholí V), jestliže množina jeho hran E' obsahuje všechny hrany z E vedoucí mezi vrcholy z V'. Příklad ■ H je podgraf, ale není indukovaný. ■ H' je indukovaný podgraf. •-• •-• IB112 Základy matematiky: Grafy 34/108 Izomorfismus grafu Intuitivne: grafy jsou izomorfní, pokud se liší pouze pojmenováním vrcholu (a/nebo jejich rozmístením). Definice (Izomorfismus grafu) Grafy G = (V, E) a H = (V', E') jsou izomorfní, píšeme G ~ H, pokud existuje bijekce f: V -» V taková, že pro každé dva vrcholy u, v g V platí {u, v} g E <š=> [f(u), f (v)} g E'. Bijekci f pak nazýváme izomorfismus. IB112 Základy matematiky: Grafy 35/108 Izomorfismus grafu Příklad ■ Rozhodnete, zda jsou následující dva grafy izomorfní. 1 a d c IB112 Základy matematiky: Grafy 36/108 Izomorfismůs grafů Prříklad ■ Rozhodnete, zda jsoů následůjící dva grafy izomorfní. ■ Ano, jsoů. f (1) = a f(2) = c f(3) = e f(4) = b f(5) = d IB112 Základy matematiky: Grafy 37/108 Izomorfismus grafu Příklad ■ Rozhodnete, zda jsou následující dva grafy izomorfní. / / / / ■ • \ \ \ \ / •-• / / IB112 Základy matematiky: Grafy 38/108 Izomorfismus grafu Příklad ■ Rozhodnete, zda jsou následující dva grafy izomorfní. ■ Ano, jsou. / / / / \ \ \ \ / •-• / / IB112 Základy matematiky: Grafy 39/108 Izomorfism ů s graf ů Příklad ■ Rozhodnete, zda jso ů násled ů jící dva grafy izomorfní. / / / / ■ • \ \ \ \ / •-• / / •-• —^\^^-< •-• IB112 Základy matematiky: Grafy 40/108 Izomorfismus grafu Příklad ■ Rozhodnete, zda jsou následující dva grafy izomorfní. ■ Ne, nejsou. / / / / \ \ \ \ / •-• / / •-• —^\^^-< •-• IB112 Základy matematiky: Grafy 41/108 Kružnice, cesta a klika v grafu Definice (Kružnice, cesta a klika v grafu) Podgraf H grafu G se nazývá m kružnice v G, je-li izomorfní nejaké kružnici. m cesta v G, je-li izomorfní nejaké ceste. m klika v G, je-li izomorfní nejakému úplnému grafu. IB112 Základy matematiky: Grafy 42/108 Další typy grafů Orientované grafy ■ Hrany jsoů uspořádané dvojice vrcholů. ■ Hrana (u, v) zaCíná v ůzlů u a vede do ůzlů v. ■ Hrana (u, v) se graficky znaCí u —> v. ■ Hrana (u, u) se nazývá smyčka. IB112 Základy matematiky: Grafy 43/108 Další typy grafu Ohodnocené grafy ■ Graf je rozšíren o funkci h : H — R prirazující hranám císla. ■ V grafické reprezentaci se prirazená císla napíší k hranám. ■ Ohodnocené grafy mohou být orientované i neorientované. -4 /4//// // • -3- • 3 -2 \ 5 3 IB112 Základy matematiky: Grafy 44/108 Další typy grafů Multigrafy ■ V můltigrafů může být více různých hran vedoucích mezi stejnými ůzly. ■ Můltigrafy mohoů být ohodnocené i neohodnocené, orientované i neorientované. IB112 Základy matematiky: Grafy 45/108 Znalosti z IB111 Z predmetu IB111 Programování a algoritmizace znáte ■ zpusoby reprezentace grafu v pocítací ■ matice sousednosti ■ pole ukazatelu na seznamy sousedu ■ ... ■ algoritmy ■ procházení grafu do šírky ■ procházení grafu do hloubky ■ nejkratší cesty ■ nalezení (minimální) kostry grafu ■ Eulerovské grafy (nakreslitelné jedním tahem) IB112 Základy matematiky: Grafy 46/108 Souvislost grafu IB112 Základy matematiky: Grafy 47/108 Sled Budeme uvažovat neorientované grafy. Definice (Sled) Sled délky n v grafu G = (V, E) je posloupnost V0, e1, V1, e2, V2, . . . , Vn_1, en, Vn, ve které pro každou hranu e-, platí e-, = [v-,_1, v}. Veřta Na vrcholech grafu G definujeme binární relaci ~ takto: u ~ v <í=> existuje sled zacínající v u a koncící ve v Relace ~ je ekvivalence. IB112 Základy matematiky: Grafy 48/108 Soůvislost grafů Definice (Soůvislé komponenty, soůvislý graf) Trídy ekvivalence ~ se nazývají souvislé komponenty. Jsou-li každé dva vrcholy grafu v relaci ~, pak je graf souvislý. ■ Soůvislé komponenty jsoů definovány jako množiny vrcholů. Casto se pod tímto názvem ale myslí podgrafy indůkované temito množinami vrcholů. ■ Graf je soůvislý, práve když májedinoů soůvisloů komponentů. IB112 Základy matematiky: Grafy 49/108 Souvislost grafu Příklad ■ Určete, keré z následujících grafu jsou souvislé. Určete počet komponent. •--/-V-• \7 V \ \ \ • - • IB112 Základy matematiky: Grafy 50/108 Souvislost grafu Příklad ■ Urcete, keré z následujících grafu jsou souvislé. Urcete pocet komponent. •--/-V-• \/ \/ \ \ • —//-/— * \ • - • Levý graf má dve souvislé komponenty, není tedy souvislý. Pravý graf má jednu souvislou komponentnu, je souvislý. IB112 Základy matematiky: Grafy 51/108 Vyšší stupne souvislosti Definice Necht k > 1. Graf G je hranove k-souvislý, je-li souvislý i po odebrání libovolných k - 1 hran. Graf G je vrcholove k-souvislý, je-li souvislý i po odebrání libovolných k - 1 vrcholu. m Jedná se o prakticky motivované pojmy. ■ Chceme kupříkladu vedet, kolik úseku elektrického vedení se muže zpretrhat než v nejakém míste síte dojde k výpadku (hranová souvislost). ■ Podobne vrcholová souvislost například ríká, kolik serveru muže zkolabovat aniž by byl narušen provoz zbytku síte. IB112 Základy matematiky: Grafy 52/108 Vyšší stupne souvislosti Příklad ■ Určete hranovou a vrcholovou souvislost tohoto grafu: •-• IB112 Základy matematiky: Grafy 53/108 Vyšší stůpne soůvislosti Příklad ■ UrCete hranovoů a vrcholovoů soůvislost tohoto grafů: •-• ■ Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespoň 3 hran. Kterých? IB112 Základy matematiky: Grafy 54/108 Vyšší stůpne soůvislosti Příklad ■ Urcete hranovoů a vrcholovoů soůvislost tohoto grafů: •-• ■ Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespoň 3 hran. Kterých? IB112 Základy matematiky: Grafy 55/108 Vyšší stůpne soůvislosti Prříklad ■ Urcete hranovoů a vrcholovoů soůvislost tohoto grafů: •-• ■ Hranová soůvislost je 3. Nesoůvislý graf získáme odebráním alespon 3 hran. Kterých? ■ Vrcholová soůvislost je 2. Nesoůvislý graf získáme odebráním alespon 2 vrcholů. Kterých? IB112 Základy matematiky: Grafy 56/108 Vyšší stupne souvislosti Prříklad ■ Urcete hranovou a vrcholovou souvislost tohoto grafu: / // O : ■ • // 7 Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespon 3 hran. Kterých? Vrcholová souvislost je 2. Nesouvislý graf získáme odebráním alespon 2 vrcholu. Kterých? IB112 Základy matematiky: Grafy 57/108 Mengerova veta Veta (Mengerova veta) Graf G je hranově k-souvislý právě když mezi každými dvěma různými vrcholy existuje alespoň k hranově disjunktních cest (vrcholy mohou být sdílené). Graf G je vrcholove k-souvislý práve když mezi každými dvema různými vrcholy existuje alespon k disjunktních cest (různých až na dva spojované vrcholy). IB112 Základy matematiky: Grafy 58/108 Stromy IB112 Základy matematiky: Grafy 59/108 Les a strom Bůdeme ůvažovat neorientované grafy. Stromy i lesy lze definovat i na orientovaných grafech. Definice (Les,strom) Les je graf bez kružnic. Strom je souvislý graf bez kružnic. Prříklad • • • • • • IB112 Základy matematiky: Grafy 60/108 Les a strom Budeme uvažovat neorientované grafy. Stromy i lesy lze definovat i na orientovaných grafech. Definice (Les,strom) Les je graf bez kružnic. Strom je souvislý graf bez kružnic. Příklad • • • • • • Čtyři stromy. Nebo les? IB112 Základy matematiky: Grafy 61/108 Vlastnosti stromů Lemma Mezi každými dvema vrcholy stromu vede práve jedna cesta. Důkaz ■ Existence cesty mezi každými dvema ůzly plyne ze soůvislosti. ■ Kdyby mezi nejakými dvemi ůzly vedly alespon dve cesty, můsel by graf obsahovat krůžnici. □ IB112 Základy matematiky: Grafy 62/108 Vlastnosti stromu Lemma Mezi každými dvema vrcholy stromu vede práve jedna cesta. Důkaz ■ Existence cesty mezi každými dvema uzly plyne ze souvislosti. ■ Kdyby mezi nejakými dvemi uzly vedly alespon dve cesty, musel by graf obsahovat kružnici. □ Lemma Pridáme-li do stromu jednu hranu, vznikne práve jedna kružnice. Důkaz ■ Aby přidáním hrany {u, v} vznikly alespon dve kružnice, musí mezi u a v vést alespon dve cesty. A to nelze. □ IB112 Základy matematiky: Grafy 63/108 Vlastnosti stromu Lemma Strom s více než jedním vrcholem má nejaký vrchol stupne 1. Důkaz ■ V grafu najdeme sled maximální délky, ve kterém se uzly neopakují. ■ Graf má více než jeden uzel, délka sledu je proto alespon 1. ■ Stupen posledního uzlu sledu je alespon 1. ■ Kdyby mel poslední uzel stupen vetší než 1, šel by sled prodloužit o uzel, který ve sledu ješte není (graf je necyklický). ■ Poslední uzel sledu má tedy stupen 1. □ IB112 Základy matematiky: Grafy 64/108 List Definice (List) List je vrchol stromu se stupněm 1. Prříklad ■ Kolik má tento strom listů? • • • • • • • IB112 Základy matematiky: Grafy 65/108 List Definice (List) List je vrchol stromu se stupne m 1. Příklad ■ Kolik má tento strom listu? ■ Sedm (list = •). • • • • • • • IB112 Základy matematiky: Grafy 66/108 Kořenový strom Definice (Kořenový strom) Kořenový strom je dvojice (T, r), kde T je strom a r je jeho vrchol zvaný koren. ■ Kořenové stromy kreslíme zpravidla od kořene smerem dolů. ■ Kořen obvykle nenazýváme listem, i když má stůpen 1. ■ Pod pojmem strom Často myslíme práve korenový strom. ■ Kořen se značí různe nebo se pozná práve tím, že je nejvýš. kořen ® i •..................... • • • korřen 4......■> • •• / I IB112 Základy matematiky: Grafy 67/108 Terminologie Definice Necht (T, r) je koreňový strom a v je jeho uzel. Necht u je předposlední uzel na ceste z kořene r do v. Pak u se nazývá rodiC uzlu v a v se nazývá potomek uzlu u. m Místo pojmu rodic a potomek se také ríká otec a syn. rodic/otec uzlu v • • • i ,- * .- * * * * * potomci/synové uzlu v * IB112 Základy matematiky: Grafy 68/108 Izomorfismus stromů Definice Kořenové stromy (T, r) a (T, r') jsou izomorfní, pokud existuje izomorfismus mezi grafy T a T' takový, že kořen r je zobrazen na kořen r'. Příklad ■ Grafy vlevo jsou izomorfní, ale pokud je chápeme jako kořenové stromy, tak izomorfní nejsou. ■ Korenové stromy vpravo jsou izomorfní. / i ' •• i \ •• i \ IB112 Základy matematiky: Grafy 69/108 Uspořádaný strom Kořenový strom (T, r) je uspořádaný, pokud je pro každý vrchol stromu jednoznacne dáno pořadí jeho potomku. ■ V grafické podobe je usporádání dáno poradím nakreslení potomku. • • • i / i \ • • • • IB112 Základy matematiky: Grafy 70/108 Izomorfismus usporádaných stromu Definice (Izomorfismus usporádaných stromu) Dva uspořádané kořenové stromy jsou izomorfní, pokud mezi nimi existuje izomorfismus f korenových stromu, který zachovává pořadí potomku (tj. má-li uzel u potomky pořade v1, v2,..., vn, pak f (u) musí mít potomky pořade f (v1), f (v2),..., f (vn)). Příklad ■ Uvedené uspořádané stromy nejsou izomorfní. • / \ \ ••• i \ ••• • • • • IB112 Základy matematiky: Grafy 71/108 Príklad ■ Lze ve stromu nalevo zvolit uzel r tak, aby byl korenový strom (T, r) izomorfní kořenovému stromu vpravo? • • • — • • •-• • •-• • • ^^m^ • • • • • • • • • • • IB112 Základy matematiky: Grafy 72/108 Príklad ■ Lze ve stromu nalevo zvolit uzel r tak, aby byl korenový strom (T, r) izomorfní korřenovému stromu vpravo? ■ Ano, lze. • • • — • • •-• • •-• • • ^^w^^ • • • • • • • • • • • IB112 Základy matematiky: Grafy 73/108 Príklad ■ Lze ve stromů nalevo zvolit ůzel r tak, aby byl kořenový strom (T, r) izomorfní kořenovémů stromů vpravo? ■ Ano, lze. ■ Bůdoů vzniklé ůspořádané korenové stromy izomorfní? • • • — • • •-• • •-• • • ^^w^^ • • • • • • • • • • • IB112 Základy matematiky: Grafy 74/108 Příklad ■ Lze ve stromu nalevo zvolit uzel r tak, aby byl kořenový strom (T, r) izomorfní kořenovému stromu vpravo? ■ Ano, lze. ■ Budou vzniklé uspořádané korenové stromy izomorfní? ■ Ne. Tradiční zobrazení levého usporádaného korenového stromu vypadá takto: • • • — • • •-• • •-• • • ^^w^^ • • • • • • • • • • • IB112 Základy matematiky: Grafy 75/108 Kostra grafu Definice Podgraf G souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároven je stromem. Příklad ■ Kolik ruzných koster má úplný graf se 4 vrcholy K4? IB112 Základy matematiky: Grafy 76/108 Kostra grafu Definice Podgraf G souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároven je stromem. Příklad ■ Kolik nuzných koster má úplný graf se 4 vrcholy K4? Celkem 16. .....>..... 4x 4x 4x 2x 2x IB112 Základy matematiky: Grafy 77/108 Kostra grafů Definice Podgraf G souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároven je stromem. Prříklad m Kolik různých koster má úplný graf se 4 vrcholy K4? Celkem 16. ■ Jaká bůde odpoved', kdybych poccítal všechny izomorfní kostry jako jednů? 4x 4x 4x 2x 2x IB112 Základy matematiky: Grafy 78/108 Kostra grafu Definice Podgraf G souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároven je stromem. Prříklad m Kolik ruzných koster má úplný graf se 4 vrcholy K4? Celkem 16. ■ Jaká bude odpoved', kdybych poccítal všechny izomorfní kostry jako jednu? Pouze 2. • — • • — • — • — • l\ IB112 Základy matematiky: Grafy 79/108 Toky v sítích IB112 Základy matematiky: Grafy 80/108 Síte Definice (Síť) Sít je ctverice (G, z, s, w), kde m G je orientovaný graf, m z, s g V(G) jsou vrcholy G zvané zdroj (z) a stok (s), m w : E (G) — R+ je kladné ohodnocení hran zvané kapacita hran. m Sítemi se modelují situace, kdy přepravujeme nejaký materiál pomocí daného systému cest (vodovodní potrubí, plynovod, dopravní sít', internet, atd.). ■ Zpravidla nás zajíma, kolik nejvíc materiálu lze prepravovat pomocí dané síteř od zdroje ke stoku. IB112 Základy matematiky: Grafy 81/108 Grafické znázornení síte ■ Síť (G, z, s, w) znázomujeme jako ohodnocený orientovaný graf (G, w), kde označíme zdroj a stok (napríklad šipkami do uzlu a z uzlu). 3 IB112 Základy matematiky: Grafy 82/108 Tok v síti ■ Tok v síti formalizuje momentální proudění materiálu od zdroje ke stoku. ■ Velikost toku je celkové množství materiálu prepravovaného od zdroje ke stoku. ■ Pro zjednodušení zápisu budeme psát e — v ve smyslu "hrana e vedoucí do v" a e 0. ■ Po nenasycené ceste lze prepravit více materiálu z u do v. ■ Rezerva kapacity pro hranu ei ve smeru z u do v je dána rozdílem w(ei) - f(ei). Pro hranu v opacném smeru je rezerva kapacity prřímo f(ei). IB112 Základy matematiky: Grafy 95/108 Príklad ■ Existuje v daném toku v síti nenasycená cesta ze z do s? 2/3 \ 2/4 3 3 IB112 Základy matematiky: Grafy 96/108 Príklad ■ Existuje v daném toku v síti nenasycená cesta ze z do s? ■ Ano. 2/3 \ 2/4 3 3 IB112 Základy matematiky: Grafy 97/108 Príklad Existuje v daném toku v síti nenasycená cesta ze z do s? Ano. UrCete rezervu kapacity jednotlivých hran. 2/3 \ 2/4 3 3 IB112 Základy matematiky: Grafy 98/108 Príklad Existuje v daném toku v síti nenasycená cesta ze z do s? Ano. Urcete rezervu kapacity jednotlivých hran. 2/3 » \ 1 2/3 ^ \ 2/4 3/3 2 IB112 Základy matematiky: Grafy 99/108 Príklad Existuje v daném toku v síti nenasycená cesta ze z do s? Ano. Urcřete rezervu kapacity jednotlivých hran. 2/3 » \ 1 2/3 ^ s. 2/4 3/3 Tok v síti lze vždy zvýšit o minimální rezervu na nenasycené cesteř ze zdroje do stoku. 2 IB112 Základy matematiky: Grafy 100/108 Ford-Fulkersonuv algoritmus Vstup: Síť (G, z, s, w) 1 pro všechny hrany e e E (G) nastav f(e) = 0 2 repeat 3 najdeme množinu U všech vrcholu, do kterých vedou nenasycené cesty ze z 4 if s e U then 5 tok na nalezené nenasycené ceste ze z do s zvýšíme o minimální rezervu kapacity hran na této ceste. 6 until s e U 7 na výstup vypíšeme získaný tok IB112 Základy matematiky: Grafy 101/108 Príklad Pomocí Ford-Fulkersonova algoritmu spoCítejte maximální tok. 3 3 IB112 Základy matematiky: Grafy 102/108 Príklad Pomocí Ford-Fůlkersonova algoritmů spoCítejte maximální tok. jl Inicializůjeme tok na nůlové hodnoty. 0/3 0/3 IB112 Základy matematiky: Grafy 103/108 Príklad Pomocí Ford-Fulkersonova algoritmu spocítejte maximální tok. ji Inicializujeme tok na nulové hodnoty. ^| Spocítáme množinu uzlu, kam vedou nenasycené cesty ze z. 0/3 0/3 IB112 Základy matematiky: Grafy 104/108 Príklad Pomocí Ford-Fulkersonova algoritmu spocítejte maximální tok. ji Inicializujeme tok na nulové hodnoty. ^ Spocítáme množinu uzlu, kam vedou nenasycené cesty ze z. ^| Zvolíme nejakou nenasycenou cestu ze z do s. 0/3 0/3 IB112 Základy matematiky: Grafy 105/108 Příklad Pomocí Fořd-Fulkeřsonova algoritmu spočítejte maximální tok. ji Inicializujeme tok na nulové hodnoty. ^ Spočítáme množinu uzlu, kam vedou nenasycené cesty ze z. ^ Zvolíme nejakou nenasycenou cestu ze z do s. ^ Zvýšíme tok o minimální řezeřvu kapacity hřan na ceste. 0/3 1/1 1/3 IB112 Základy matematiky: Gřafy 106/108 Příklad Pomocí Fořd-Fulkeřsonova algoritmu spočítejte maximální tok. ji Inicializujeme tok na nulové hodnoty. ^ Spočítáme množinu uzlu, kam vedou nenasycené cesty ze z. ^ Zvolíme nejakou nenasycenou cestu ze z do s. ^ Zvýšíme tok o minimální řezeřvu kapacity hřan na ceste. ^| Křoky 2—4 opakujeme dokud je s v množine pocítané křokem 2. 0/3 vy T 1/1 1/3 IB112 Základy matematiky: Gřafy 107/108 Poznámky ■ Síte lze snadno rozšířit i o kapacitu uzlu. ■ Má smysl uvažovat i minimální kapacity hran, úloha je stále snadno rešitelná. ■ Algoritmus pro nalezení maximálního toku má krome zjevných technických aplikací i aplikace v matematice, napr. pro nalezení párování v bipartitním grafu nebo pro urcení vyšší grafové souvislosti. IB112 Základy matematiky: Grafy 108/108