IB112 Základy matematiky Grafy Jan Strejček Obsah ■ Základní pojmy m graf, základní typy grafů ■ stupeň vrcholu ■ podgrafy a izomorfismus ■ orientované grafy, ohodnocené grafy, multigrafy ■ Souvislost grafu m souvislé komponenty ■ vyšší stupně souvislosti ■ Stromy m stromy, kořenové stromy, uspořádané stromy ■ izomorfismus stromů ■ kostra grafu ■ Toky v sítích m sítě, toky a řezy ■ Ford-Fulkersonův algoritmus IB112 Základy matematiky: Graty 2/91 Základní pojmy IB112 Základy matematiky: Grafy 3/91 Graf (Neorientovaný) graf je dvojice G = (V,E), kde m V je množina uzlů nebo též vrcholů a m 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}}) 4-3 IB112 Základy matematiky: Grafy 4/91 Poznámky ■ Množiny vrcholu a hran grafu G zapisujeme také V(G), E(G). m Grafy se obvykle znázorňují graficky. IB112 Základy matematiky: Grafy 5/91 Poznámky ■ Množiny vrcholu a hran grafu G zapisujeme také V(G), E(G). m Grafy se obvykle znázorňují graficky. ■ Na rozmístění uzlů nezáleží. IB112 Základy matematiky: Grafy 6/91 Poznámky ■ Množiny vrcholu a hran grafu G zapisujeme také V(G), E(G). m Grafy se obvykle znázorňují graficky. ■ Na rozmístění uzlů nezáleží. ■ Často nám jde spíše o strukturu grafu než o pojmenování uzlů. Jména uzlů pak nepíšeme. IB112 Základy matematiky: Grafy 7/91 Základní typy grafů Kružnice ■ Kružnice délky n má n > 3 vrcholu spojených n hranami do jednoho cyklu. ■ Značí se Cn. 1_2 C6 6 3 \ / 5 — 4 IB112 Základy matematiky: Graty 8 91 Základní typy grafů Kružnice ■ Kružnice délky n má n > 3 vrcholu spojených n hranami do jednoho cyklu. ■ Značí se Cn. 1_2 C6 6 5 — 4 Cesta ■ Cesta délky n > 0 má n + 1 vrcholů spojených do řady n hranami. Značí se Pn. P6 1—2 — 3 — 4 — 5 — 6 — 7 IB112 Základy matematiky: Grafy 9/91 Základní typy grafů Úplný graf ■ Úplný graf s n vrcholy má n > 1 vrcholu a mezi každými dvěma vrcholy vede hrana. Celkem má tedy (£) hran. ■ Značí se Kn. IB112 Základy matematiky: Graty 10/91 Základní typy grafů Úplný bipartitní graf ■ Úplný bipartitní graf s n > 1 a m > 1 vrcholy mán + m vrcholu rozdělených do dvou množin po n a m prvcích. Graf má hranu mezi každými dvěma vrcholy z různých skupin. ■ Značí se Kn^m. Příklad ■ Existuje graf, který je zároveň úplný a úplný bipartitní? IB112 Základy matematiky: Grafy 11/91 Základní typy grafů Úplný bipartitní graf ■ Úplný bipartitní graf s n > 1 a m > 1 vrcholy mán + m vrcholu rozdělených do dvou množin po n a m prvcích. Graf má hranu mezi každými dvěma vrcholy z různých skupin. ■ Značí se Kn^m. Příklad ■ Existuje graf, který je zároveň úplný a úplný bipartitní? ■ Ano. K2 = /<1,1 IB112 Základy matematiky: Grafy 12/91 Stupeň vrcholu Definice (Stupeň vrcholu) Stupeň vrcholu u v grafu G je počet hran vycházejících z u. Stupeň vrcholu značíme óq{u) nebo jen d(u). Příklad ■ Zjistěte stupně vrcholu. 4-3 d{5) = IB112 Základy matematiky: Grafy 13/91 Stupeň vrcholu Definice (Stupeň vrcholu) Stupeň vrcholu u v grafu G je počet hran vycházejících z u. Stupeň vrcholu značíme óq{u) nebo jen d(u). Příklad ■ Zjistěte stupně vrcholu. 4-3 d{5) = 2 m Stupně vrcholu můžeme uspořádat podle velikosti: 1,2,2,3,4 IB112 Základy matematiky: Grafy 14/91 Vlastnosti stupňů Věta Součet stupňů vrcholů v libovolném grafu je vždy sudý a rovný dvojnásobku počtu 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: Graty 15/91 Podgrafy Podgrafem grafu G = (V, E) je libovolný graf H = (V, E') takový, že V c V, E' c E a přitom hrany v E' 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: Graty 16/91 Podgrafy Podgrafem grafu G = (V, E) je libovolný graf H = (V, E') takový, že V c V, E' c E a přitom hrany v E' 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 17/91 Izomorfismus grafů Intuitivně: grafy jsou izomorfní, pokud se liší pouze pojmenováním vrcholů (a/nebo jejich rozmístěním). Definice (Izomorfismus grafů) 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}^E ^ {f(u),f(v)}€E'. Bijekci f pak nazýváme izomorfismus. IB112 Základy matematiky: Grafy 18/91 Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní 5X x2 e-A-:b 4-3 d c IB112 Základy matematiky: Grafy Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní. ■ Ano, jsou. ř(1) = a f(2) = c f(3) = e f(4) = b f(5) = d IB112 Základy matematiky: Grafy 20/91 Izomorfismus grafů IB112 Základy matematiky: Grafy Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní. ■ Ano, jsou. IB112 Základy matematiky: Grafy 22/91 Izomorfismus grafů IB112 Základy matematiky: Grafy Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní. ■ Ne, nejsou. IB112 Základy matematiky: Grafy 24/91 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í nějaké kružnici, m cesta v G, je-li izomorfní nějaké cestě, m klika v G, je-li izomorfní nějakému úplnému grafu. IB112 Základy matematiky: Grafy 25/91 Další typy grafů Orientované grafy ■ Hrany jsou uspořádané dvojice vrcholů. ■ Hrana (ív, v) začíná v uzlu u a vede do uzlu v. ■ Hrana (ív, v) se graficky značí u —> v. m Hrana (ív, ív) se nazývá smyčka. IB112 Základy matematiky: Grafy 26/91 Další typy grafů Ohodnocené grafy ■ Graf je rozšířen o funkci h : H R přiřazující hranám čísla. ■ V grafické reprezentaci se přiřazená čísla napíší k hranám. ■ Ohodnocené grafy mohou být orientované i neorientované. 5 • -s» • 3 IB112 Základy matematiky: Graty 27/91 Další typy grafů Multi grafy ■ V multigrafu může být více různých hran vedoucích mezi stejnými uzly. ■ Multigrafy mohou být ohodnocené i neohodnocené, orientované i neorientované. IB112 Základy matematiky: Grafy 28/91 Znalosti z IB111 Z předmětu IB111 Programování a algoritmizace znáte ■ způsoby reprezentace grafu v počítači ■ matice sousednosti ■ pole ukazatelů na seznamy sousedů ■ ... ■ algoritmy ■ procházení grafu do šířky ■ procházení grafu do hloubky ■ n ej kratší cesty ■ nalezení (minimálni) kostry grafu ■ Eulerovské grafy (nakreslitelné jedním tahem) IB112 Základy matematiky: Grafy 29/91 Souvislost grafu IB112 Základy matematiky: Grafy 30/91 Sled Budeme uvažovat neorientované grafy. Definice (Sled) Sled délky n v grafu G = (V, E) je posloupnost vo,e-\,v-\,e2, v2,..., ľn-i,en, vn, ve které pro každou hranu e, platí e, = { , v,}. Věta Na vrcholech grafu G definujeme binární relaci ~ takto: u ~ v <í=^ existuje sled začínající v u a končící ve v Relace ~ je ekvivalence. IB112 Základy matematiky: Grafy 31/91 Souvislost grafu Definice (Souvislé komponenty, souvislý graf) Třídy ekvivalence ~ se nazývají souvislé komponenty. Jsou-li každé dva vrcholy grafu v relaci ~, pak je graf souvislý. m Souvislé komponenty jsou definovány jako množiny vrcholů. Často se pod tímto názvem ale myslí podgrafy indukované těmito množinami vrcholů. ■ Graf je souvislý, právě když má jedinou souvislou komponentu. IB112 Základy matematiky: Grafy 32/91 Souvislost grafu Příklad ■ Určete, keré z následujících grafů jsou souvislé. Určete počet komponent. IB112 Základy matematiky: Grafy 33/91 Souvislost grafu Příklad ■ Určete, keré z následujících grafů jsou souvislé. Určete počet komponent. ■ Levý graf má dvě souvislé komponenty, není tedy souvislý. ■ Pravý graf má jednu souvislou komponentnu, je souvislý. IB112 Základy matematiky: Grafy 34/91 Vyšší stupně souvislosti Definice Nechť k > 1. Graf G je hranově k-souvislý, je-li souvislý i po odebrání libovolných k - 1 hran. Graf G je vrcholově k-souvislý, je-li souvislý i po odebrání libovolných k - 1 vrcholů. ■ Jedná se o prakticky motivované pojmy. ■ Chceme kupříkladu vědět, kolik úseků elektrického vedení se může zpřetrhat než v nějakém místě sítě dojde k výpadku (hranová souvislost). ■ Podobně vrcholová souvislost například říká, kolik serverů může zkolabovat aniž by byl narušen provoz zbytku sítě. IB112 Základy matematiky: Grafy 35/91 Vyšší stupně souvislosti Příklad ■ Určete hranovou a vrcholovou souvislost tohoto grafu: IB112 Základy matematiky: Grafy 36/91 Vyšší stupně souvislosti Příklad ■ Určete hranovou a vrcholovou souvislost tohoto grafu: ■ Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespoň 3 hran. Kterých? IB112 Základy matematiky: Grafy 37/91 Vyšší stupně souvislosti Příklad ■ Určete hranovou a vrcholovou souvislost tohoto grafu: ■ Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespoň 3 hran. Kterých? IB112 Základy matematiky: Graty 38/91 Vyšší stupně souvislosti Příklad ■ Určete hranovou a vrcholovou souvislost tohoto grafu: ■ Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespoň 3 hran. Kterých? ■ Vrcholová souvislost je 2. Nesouvislý graf získáme odebráním alespoň 2 vrcholů. Kterých? IB112 Základy matematiky: Grafy 39/91 Vyšší stupně souvislosti Příklad ■ Určete hranovou a vrcholovou souvislost tohoto grafu: ■ Hranová souvislost je 3. Nesouvislý graf získáme odebráním alespoň 3 hran. Kterých? ■ Vrcholová souvislost je 2. Nesouvislý graf získáme odebráním alespoň 2 vrcholů. Kterých? IB112 Základy matematiky: Graty 40/91 Mengerova věta Věta (Mengerova věta) 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 vrcholově k-souvislý právě když mezi každými dvěma různými vrcholy existuje alespoň k disjunktních cest (různých až na dva spojované vrcholy). IB112 Základy matematiky: Grafy 41/91 Stromy IB112 Základy matematiky: Grafy 42/91 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 IB112 Základy matematiky: Grafy 43/91 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. Čtyři stromy. Nebo les? IB112 Základy matematiky: Grafy 44/91 Vlastnosti stromů Lemma Mezi každými dvěma vrcholy stromu vede právě jedna cesta. Důkaz ■ Existence cesty mezi každými dvěma uzly plyne ze souvislosti. ■ Kdyby mezi nějakými dvěmi uzly vedly alespoň dvě cesty, musel by graf obsahovat kružnici. □ IB112 Základy matematiky: Grafy 45/91 Vlastnosti stromů Lemma Mezi každými dvěma vrcholy stromu vede právě jedna cesta. Důkaz ■ Existence cesty mezi každými dvěma uzly plyne ze souvislosti. ■ Kdyby mezi nějakými dvěmi uzly vedly alespoň dvě cesty, musel by graf obsahovat kružnici. □ Lemma Přidáme-li do stromu jednu hranu, vznikne právě jedna kružnice. Důkaz ■ Aby přidáním hrany {ív, v} vznikly alespoň dvě kružnice, musí mezi u a v vést alespoň dvě cesty. A to nelze. □ IB112 Základy matematiky: Grafy 46/91 Vlastnosti stromů Lemma Strom s více než jedním vrcholem má nějaký vrchol stupně 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 alespoň 1. ■ Stupeň posledního uzlu sledu je alespoň 1. ■ Kdyby měl poslední uzel stupeň větší než 1, šel by sled prodloužit o uzel, který ve sledu ještě není (graf je necyklický). ■ Poslední uzel sledu má tedy stupeň 1. □ IB112 Základy matematiky: Grafy 47/91 List Definice (List) List je vrchol stromu se stupněm 1. Příklad ■ Kolik má tento strom listů? IB112 Základy matematiky: Grafy 48/91 List Definice (List) List je vrchol stromu se stupněm 1. Příklad ■ Kolik má tento strom listů? ■ Sedm (list = •). IB112 Základy matematiky: Grafy Kořenový strom Definice (Kořenový strom) Kořenový strom je dvojice (T,r), kde T je strom a r je jeho vrchol zvaný kořen. m Kořenové stromy kreslíme zpravidla od kořene směrem dolů. ■ Kořen obvykle nenazýváme listem, i když má stupeň 1. ■ Pod pojmem strom často myslíme právě kořenový strom. ■ Kořen se značí různě nebo se pozná právě tím, že je nejvýš. IB112 Základy matematiky: Grafy 50/91 Terminologie Definice Nechť (T, r) je kořenový strom a v je jeho uzel. Nechť u je předposlední uzel na cestě z kořene r do v. Pak u se nazývá rodič uzlu v a v se nazývá potomek uzlu u. ■ Místo pojmů rodič a potomek se také říká otec a syn. rodič/otec uzlu v ■>■• • .......... -::........ i potomci/synové uzlu v • IB112 Základy matematiky: Graty 51/91 Izomorfismus stromů Definice Kořenové stromy (T, r) a (V, ŕ) jsou izomorfní, pokud existuje izomorfismus mezi grafy T a V takový, že kořen r je zobrazen na kořen ť. Příklad ■ Grafy vlevo jsou izomorfní, ale pokud je chápeme jako kořenové stromy, tak izomorfní nejsou. ■ Kořenové stromy vpravo jsou izomorfní. IB112 Základy matematiky: Grafy 52/91 Uspořádaný strom Definice (Uspořádaný strom) Kořenový strom (T, r) je uspořádaný, pokud je pro každý vrchol stromu jednoznačně dáno pořadí jeho potomků. m V grafické podobě je uspořádání dáno pořadím nakreslení potomků. IB112 Základy matematiky: Grafy 53/91 Izomorfismus uspořádaných stromů Dva uspořádané kořenové stromy jsou izomorfní, pokud mezi nimi existuje izomorfismus f kořenových stromů, který zachovává pořadí potomků (tj. má-li uzel u potomky poradě v-\,v2,...,vn, pak f(u) musí mít potomky poradě f(v-\),f(v2),... ,f{vn)). Příklad ■ Uvedené uspořádané stromy nejsou izomorfní. / i \ • • • i \ i • • • / i \ i IB112 Základy matematiky: Grafy 54/91 Příklad ■ Lze ve stromu nalevo zvolit uzel r tak, aby byl kořenový strom (T, r) izomorfní kořenovému stromu vpravo? IB112 Základy matematiky: Grafy 55/91 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. IB112 Základy matematiky: Grafy 56/91 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é kořenové stromy izomorfní? IB112 Základy matematiky: Grafy 57/91 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é kořenové stromy izomorfní? ■ Ne. Tradiční zobrazení levého uspořádaného kořenového stromu vypadá takto: IB112 Základy matematiky: Grafy 58/91 Kostra grafu Definice Podgraf G' souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároveň je stromem. Příklad ■ Kolik různých koster má úplný graf se 4 vrcholy K4? IB112 Základy matematiky: Grafy 59/91 Kostra grafu Definice Podgraf G' souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároveň je stromem. Příklad ■ Kolik různých koster má úplný graf se 4 vrcholy K4? Celkem 16. IB112 Základy matematiky: Grafy 60/91 Kostra grafu Definice Podgraf G' souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároveň je stromem. Příklad ■ Kolik různých koster má úplný graf se 4 vrcholy K4? Celkem 16. ■ Jaká bude odpověď, kdybych počítal všechny izomorfní kostry jako jednu? 4x 4x 4x 2x 2x IB112 Základy matematiky: Graty 61/91 Kostra grafu Definice Podgraf G' souvislého grafu G nazýváme kostrou, pokud obsahuje všechny vrcholy grafu G a zároveň je stromem. Příklad ■ Kolik různých koster má úplný graf se 4 vrcholy K4? Celkem 16. ■ Jaká bude odpověď, kdybych počítal všechny izomorfní kostry jako jednu? Pouze 2. IB112 Základy matematiky: Grafy 62/91 Toky v sítích IB112 Základy matematiky: Grafy 63/91 Sítě Definice (Síť) Síť je čtveřice (G, z, s, w), kde ■ G je orientovaný graf, ■ z, s g V(G) jsou vrcholy G zvané zdroj (z) a stok (s), ■ w : E(G) ->• M+ je kladné ohodnocení hran zvané kapacita hran. m Sítěmi se modelují situace, kdy přepravujeme nějaký materiál pomocí daného systému cest (vodovodní potrubí, plynovod, dopravní síť, internet, atd.). ■ Zpravidla nás zajíma, kolik nejvíc materiálu lze přepravovat pomocí dané sítě od zdroje ke stoku. IB112 Základy matematiky: Graty 64/91 Grafické znázornění sítě ■ Síť (G, z, s, w) znázorňujeme jako ohodnocený orientovaný graf (G, w), kde označíme zdroj a stok (například šipkami do uzlu a z uzlu). IB112 Základy matematiky: Grafy 65/91 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 přepravovaného od zdroje ke stoku. ■ Pro zjednodušení zápisu budeme psát e ->• v ve smyslu "hrana e vedoucí do v" a e ^— v ve smyslu "hrana e vedoucí z v" a Definice (Tok, velikost toku) Tok v síti (G, z, s, w) je funkce f : E (G) ->• splňující ■ pro všechny hrany e e E (G) platí Q < f {e) < w(e), m pro každý vrchol v e V (G) \ {z, s} platí ^ f (e) = ^ f (e). e—>v e^v Velikost toku je definována jako \\f\\ = ^ f (e) - ^ f (e). e^z e—>z IB112 Základy matematiky: Graty 66/91 Poznámky k definici toku Definice (Tok, velikost toku) Tok v síti (G, z, s, w) je funkce f : E (G) ->• splňující m pro všechny hrany e e E(G) platí Q < f {e) < w(e), m pro každý vrchol v e V(G) \ {z, s} platí ^ f {e) = ^ f {e). e—>v e^v Velikost toku je definována jako \\f\\ = ^ f (e) - ^ f (e). e^z e—>z m První podmínka říká, že tok nesmí překročit kapacitu žádné hrany. ■ Druhá podmínka říká, že není-li vrchol zdroj nebo stok, pak z něj musí odtéct tolik materiálu, kolik do něj přitéká. ■ Velikost toku se definuje jako množství materiálu odtékajícího ze zdroje po odečtení materiálu, který do zdroje přitéká. ■ Velikost toku lze alternativně definovat i u stoku. IB112 Základy matematiky: Grafy 67/91 Grafické znázornění toku v síti ■ Tok v síti znázorňujeme stejně jako síť, akorát ohodnocení každé hrany e bude mít tvar f(e)/w(e), tedy tok/kapacita. IB112 Základy matematiky: Grafy 68/91 Grafické znázornění toku v síti ■ Tok v síti znázorňujeme stejně jako síť, akorát ohodnocení každé hrany e bude mít tvar f(e)/w(e), tedy tok/kapacita. Příklad 2/3 ■ Jaká je velikost toku? IB112 Základy matematiky: Grafy 69/91 Grafické znázornění toku v síti ■ Tok v síti znázorňujeme stejně jako síť, akorát ohodnocení každé hrany e bude mít tvar f(e)/w(e), tedy tok/kapacita. Příklad 2/3 ■ Jaká je velikost toku? ■ Velikost je 4. IB112 Základy matematiky: Grafy 70/91 Problém maximálního toku Problém maximálního toku v síti Nechť (G, z, s, w) je síť. Problémem maximálního toku v síti rozumíme úkol nalézt v dané síti tok f s maximálni možnou velikostí ||ŕ||. Příklad ■ Je vyznačený tok maximálni? IB112 Základy matematiky: Grafy 71/91 Problém maximálního toku Problém maximálního toku v síti Nechť (G, z, s, w) je síť. Problémem maximálního toku v síti rozumíme úkol nalézt v dané síti tok f s maximálni možnou velikostí llfll. Příklad ■ Je vyznačený tok maximální? ■ Není. Najděte maximální tok. IB112 Základy matematiky: Grafy 72/91 Problém maximálního toku Problém maximálního toku v síti Nechť (G, z, s, w) je síť. Problémem maximálního toku v síti rozumíme úkol nalézt v dané síti tok f s maximálni možnou velikostí \\f\\. Příklad ■ Je vyznačený tok maximálni? ■ Není. Najděte maximální tok. ■ Umíte dokázat, že je velikost toku je maximální? IB112 Základy matematiky: Graty 73/91 Řez v síti Definice (Řez, velikost řezu) Řez v síti(G, z, s, w) je podmnožina hran C c E (G) taková, že po jejich odstranění z grafu G neexistuje orientovaná cesta ze z do s. Velikost řezu C je součet kapacit hran v C, tedy \\C\\ = ^ w(e). eeC Příklad ■ Nalezněte nějaký řez a určete jeho velikost. IB112 Základy matematiky: Grafy 74/91 Řez v síti Definice (Řez, velikost řezu) Řez v síti(G, z, s, w) je podmnožina hran C c E (G) taková, že po jejich odstranění z grafu G neexistuje orientovaná cesta ze z do s. Velikost řezu C je součet kapacit hran v C, tedy \\C\\ = ^ w(e). eeC Příklad ■ Nalezněte nějaký řez a určete jeho velikost. ■ Vyznačený řez má velikost 6. 3 IB112 Základy matematiky: Grafy 75/91 Vztah řezů a toků Maximální velikost toku v síti je rovna minimální velikosti řezu. Intuitivně platí, že řez je množina hran, které nelze obejít žádnou cestou ze zdroje do stoku. Velikost libovolného řezu je tedy větší nebo rovna velikosti libovolného toku. K důkazu, že nalezený tok má maximální velikost, stačí nalézt řez stejné velikosti. Je daný tok v síti maximální? 2/3 2/2 IB112 Základy matematiky: Graty 76/91 Vztah řezů a toků Maximální velikost toku v síti je rovna minimální velikosti řezu. Intuitivně platí, že řez je množina hran, které nelze obejít žádnou cestou ze zdroje do stoku. Velikost libovolného řezu je tedy větší nebo rovna velikosti libovolného toku. K důkazu, že nalezený tok má maximální velikost, stačí nalézt řez stejné velikosti. Je daný tok v síti maximální? 2/3 2/2 IB112 Základy matematiky: Graty 77/91 Nenasycená cesta Definice (Nenasycená cesta) Mějme síť (G, z, s, w) a v ní tok f. Nenasycená cesta z vrcholu u do vrcholu v je neoreintovaná cesta (tj. posloupnost navazujících hran e-i, e2,..., en chápaných neorientovane) z u do v, kde pro všechny hrany e, ve směru z u do v platí f (ei) < w(e,) a pro všechny hrany e, v opačném směru platí f (ei) > 0. ■ Po nenasycené cestě lze přepravit více materiálu z u do v. m Rezerva kapacity pro hranu e, ve směru z u do v je dána rozdílem w(e,) - r(e,-). Pro hranu v opačném směru je rezerva kapacity přímo ř(e,-). IB112 Základy matematiky: Grafy 78/91 Příklad ■ Existuje v daném toku v síti nenasycená cesta ze z do s? IB112 Základy matematiky: Grafy 79/91 Příklad ■ Existuje v daném toku v síti nenasycená cesta ze z do s? ■ Ano. 2/3 3/3 IB112 Základy matematiky: Grafy 80/91 Příklad Existuje v daném toku v síti nenasycená cesta ze z do s? Ano. Určete rezervu kapacity jednotlivých hran. IB112 Základy matematiky: Grafy Příklad Existuje v daném toku v síti nenasycená cesta ze z do s? Ano. Určete rezervu kapacity jednotlivých hran. IB112 Základy matematiky: Grafy Příklad ■ Existuje v daném toku v síti nenasycená cesta ze z do s? ■ Ano. ■ Určete rezervu kapacity jednotlivých hran. 2/3 3/3 ■ Tok v síti lze vždy zvýšit o minimální rezervu na nenasycené cestě ze zdroje do stoku. IB112 Základy matematiky: Grafy 83/91 Ford-Fulkersonův algoritmus Vstup: Síť (G,z,s, w) 1 pro všechny hrany e e E(G) nastav f(e) = 0 2 repeat 3 najděme množinu U všech vrcholů, do kterých vedou nenasycené cesty ze z 4 if s g U then 5 tok na nalezené nenasycené cestě ze z do s zvýšíme o minimální rezervu kapacity hran na této cestě. 6 until s 0 U 7 na výstup vypíšeme získaný tok IB112 Základy matematiky: Grafy 84/91 Příklad Pomocí Ford-Fulkersonova algoritmu spočítejte maximální tok. IB112 Základy matematiky: Grafy 85/91 Příklad Pomocí Ford-Fulkersonova algoritmu spočítejte maximální tok. O Inicializujeme tok na nulové hodnoty. IB112 Základy matematiky: Graty 86/91 Příklad Pomocí Ford-Fulkersonova algoritmu spočítejte maximální tok. O Inicializujeme tok na nulové hodnoty. H Spočítáme množinu uzlů, kam vedou nenasycené cesty ze z. IB112 Základy matematiky: Grafy 87/91 Pomocí Ford-Fulkersonova algoritmu spočítejte maximální tok. Inicializujeme tok na nulové hodnoty. Spočítáme množinu uzlů, kam vedou nenasycené cesty ze Zvolíme nějakou nenasycenou cestu ze z do s. IB112 Základy matematiky: Grafy Příklad Pomocí Ford-Fulkersonova algoritmu spočítejte maximální tok. O Inicializujeme tok na nulové hodnoty. H Spočítáme množinu uzlů, kam vedou nenasycené cesty ze z. Q Zvolíme nějakou nenasycenou cestu ze z do s. □ Zvýšíme tok o minimální rezervu kapacity hran na cestě. IB112 Základy matematiky: Grafy 89/91 Příklad Pomocí Ford-Fulkersonova algoritmu spočítejte maximální tok. O Inicializujeme tok na nulové hodnoty. H Spočítáme množinu uzlů, kam vedou nenasycené cesty ze z. Q Zvolíme nějakou nenasycenou cestu ze z do s. □ Zvýšíme tok o minimální rezervu kapacity hran na cestě. B Kroky 2-4 opakujeme dokud je s v množině počítané krokem 2. IB112 Základy matematiky: Graty 90/91 Poznámky ■ Sítě lze snadno rozšířit i o kapacitu uzlů. ■ Má smysl uvažovat i minimální kapacity hran, úloha je stále snadno řešitelná. ■ Algoritmus pro nalezení maximálního toku má kromě zjevných technických aplikací i aplikace v matematice, např. pro nalezení párování v bipartitním grafu nebo pro určení vyšší grafové souvislosti. IB112 Základy matematiky: Grafy 91/91