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ův-Fulkersonův algoritmus IB112 Základy matematiky: Grafy 2/91 Základní pojmy IB112 Základy matematiky: Grafy 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 vrcholů 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 vrcholů a hran grafu G zapisujeme také V(G), E(G). ■ 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 vrcholů 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 vrcholů spojených n hranami do jednoho cyklu. ■ Značí se Cn. -j_2 IB112 Základy matematiky: Grafy 8/91 Základní typy grafů Kružnice ■ Kružnice délky n má n > 3 vrcholů spojených n hranami do jednoho cyklu. ■ Značí se Cn. -j_2 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 vrcholů a mezi každými dvěma různými vrcholy vede hrana. Celkem má tedy (£) hran. ■ Značí se Kn. IB112 Základy matematiky: Grafy 10/91 Základní typy grafů Úplný bipartitní graf ■ Úplný bipartitní graf s n > 1 a m > 1 vrcholy má n + m vrcholů 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 vrcholů 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 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 dG{u) nebo jen d (u). Příklad ■ Zjistěte stupně vrcholů. 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 dG{u) nebo jen d (u). Příklad ■ Zjistěte stupně vrcholů. ■ 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 Pod grafy Podgrafem grafu G = (V, E) je libovolný graf H = (V, E') takový, že V (Z 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 Pod grafy Podgrafem grafu G = (V, E) je libovolný graf H = (V, E') takový, že V (Z 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ý. ■ Hf 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 -s- V taková, že pro každé dva vrcholy u, v e V platí {u,v}eE {f(u),f(v)}eE'. 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 4-3 b d c IB112 Základy matematiky: Grafy 19/91 Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní. ■ Ano, jsou. f(1) = a f (2) = c f(3) = e f {A) = b f(5) = d IB112 Základy matematiky: Grafy 20/91 Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní. IB112 Základy matematiky: Grafy 21/91 Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní ■ Ano, jsou. IB112 Základy matematiky: Grafy Izomorfismus grafů Příklad ■ Rozhodněte, zda jsou následující dva grafy izomorfní 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 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 {u, v) začíná v uzlu u a vede do uzlu v. ■ Hrana {u, v) se graficky značí u —> v. ■ Hrana (i/, ú) se nazývá smyčka. IB112 Základy matematiky: Grafy 26/91 Další typy grafů Ohodnocené grafy ■ Graf je rozšířen o funkci h : E -> 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 •-^ • 3 IB112 Základy matematiky: Grafy 27/91 Další typy grafů Multigrafy ■ 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 odjinud? Předmětu IB111 dříve pokrýval ■ 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 ■ nej kratší cesty ■ nalezení (minimální) 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,..., vn-\, em vn, ve které pro každou hranu e, platí e j = ,17}. Věta A/a 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ý. ■ 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: 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: •............o ■ 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. 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 {u, 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 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 (7", r), kde T je strom a r je jeho vrchol zvaný kořen. ■ 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ť (7, 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 v ■y T......^ potomci/synové uzlu v IB112 Základy matematiky: Grafy 51/91 Izomorfismus stromů Definice Kořenové stromy (T, r) a (V\r') 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 (7", 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ů Definice (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ě r(v-i), f(v2),..., f{yn)). Příklad ■ Uvedené uspořádané stromy nejsou izomorfní. • • • i \ i • • • /1 \ 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 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: 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? 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 ye orientovaný graf, ■ z, s g l/(G) /sol/ vrcholy G zvané zdroj (z) a stok (s), ■ w : E( G) M+ ye kladné ohodnocení hran zvané kapacita hran. ■ 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). 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) mq splňující ■ pro všechny hrany e e E"(G) p/aŕ/'O < ŕ(e) < w(e), ■ pro /cazc/ý wcfto/ v g \/(G) \ {z, s} p/atf ^ ŕ(e) = ^ ŕ(e). e—»y Velikost toku je definována jako \\f\\ = y^ f (e) - y^ f(e). IB112 Základy matematiky: Grafy 66/91 Poznámky k definici toku Definice (Tok, velikost toku) Tok v síti (G, z, s, w) je funkce f: E (G) M J splňující m pro všechny hrany e e E(G) p/aŕ/'O < ŕ(e) < w(e), ■ pro /cazc/ý wc/70/ v e \/(G) \ {z, s} p/atf ^ f (é) = ^ ŕ(e). e—»y e^v Velikost toku je definována jako \\f\\ = y^ f (e) - y^ f(e). ■ 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(é)/w(é), 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(é)/w(é), 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(é)/w(é), 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í f 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í f 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ální? ■ 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). 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). 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 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 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 (ej) < w(e,-) a pro všechny hrany e, v opačném směru platí f (ej) > 0. ■ Po nenasycené cestě lze přepravit více materiálu z u do v. ■ Rezerva kapacity pro hranu e, ve směru z u do v je dána rozdílem w(eí) - f{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. 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. 2/3 3/3 IB112 Základy matematiky: Grafy 81/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. 2/3 3/3 IB112 Základy matematiky: Grafy 82/91 ■ Existuje v daném toku v síti nenasycená cesta ze z do s? ■ Ano. ■ Určete rezervu kapacity jednotlivých hran. ■ 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 Fordův-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 Pomocí Fordova-Fulkersonova algoritmu spočítejte maximální tok. IB112 Základy matematiky: Grafy 85/91 Příklad Pomocí Fordova-Fulkersonova algoritmu spočítejte maximální tok. □ Inicializujeme tok na nulové hodnoty. IB112 Základy matematiky: Grafy 86/91 Příklad Pomocí Fordova-Fulkersonova algoritmu spočítejte maximální tok. D 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í Fordova-Fulkersonova algoritmu spočítejte maximální tok. D 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í Fordova-Fulkersonova algoritmu spočítejte maximální tok. D 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. Q Zvýšíme tok o minimální rezervu kapacity hran na cestě. 0/3 1/3 IB112 Základy matematiky: Grafy 89/91 Pomocí Fordova-Fulkersonova algoritmu spočítejte maximální tok. D Inicializujeme tok na nulové hodnoty. B Spočítáme množinu uzlů, kam vedou nenasycené cesty ze z. B Zvolíme nějakou nenasycenou cestu ze z do s. Q 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 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