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: Graty 3/91 Graf Definice (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 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: Grafy 8/91 Základní typy grafů Kružnice ■ Kružnice délky nmán>3 vrcholu spojených n hranami do jednoho cyklu. ■ Značí se Cn. 1_2 / \ C6 6 3 \ / 5 — 4 Cesta ■ Cesta délky n > 0 má n + 1 vrcholu 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 různými vrcholy vede hrana. Celkem má tedy (£) hran. ■ Značí se Kn. 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 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. IB112 Základy matematiky: Grafy 13/91 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. ■ Stupně vrcholů 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: Grafy 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: Grafy 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: Graty 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í. 1 a IB112 Základy matematiky: Grafy 19/91 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 IB112 Základy matematiky: Grafy 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: Graty 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: Grafy 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: Grafy 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. Příklad Č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: Graty 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ýš. kořen kořen IB112 Základy matematiky: Graty 50/91 Terminologie 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 potomci/synové uzlu v IB112 Základy matematiky: Grafy 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í. / i \ • • • i \ i • • • / i \ i 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ů. ■ 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 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: Graty 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 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? •-• IXI •-• IB112 Základy matematiky: Graty 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? IB112 Základy matematiky: Grafy 61/91 Kostra grafu 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: Grafy 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). 3 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. Příklad 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 ■ 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? 2/3 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í ||ŕ||. Příklad ■ Je vyznačený tok maximálni? ■ Není. Najděte maximální tok. 2/3 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í ||ŕ||. 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í? 2/3 IB112 Základy matematiky: Grafy 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. 3 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 IB112 Základy matematiky: Grafy 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 IB112 Základy matematiky: Grafy 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: Graty 78/91 Příklad ■ Existuje v daném toku v síti nenasycená cesta ze z do s? 2/3 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 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. 3 3 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: Grafy 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 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. IB112 Základy matematiky: Grafy 88/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ě. 0/3 1/3 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. 0/3 1/3 IB112 Základy matematiky: Grafy 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