Základní pojmy teorie grafů

V této kapitole jsou definicemi zavedeny grafy a jejich komponenty, a větami podány jejich vlastnosti a vztahy. Vzhledem k zaměření publikace jsou věty uváděny bez důkazů. Je použita běžná symbolika výrokového a predikátového počtu, shrnutá v následující tabulce:

 

Symbol

Význam, příklad

Ů

funktor konjunkce (a současně). A Ù B (A a současně B)

Ú

funktor disjunkce ("nevylučovací" nebo). A Ú B (A nebo B nebo obojí)

Þ

funktor implikace (jestliže ... pak). A Þ B (jestliže A, pak B; z A plyne B)

Û

funktor ekvivalence (právě tehdy). A Û B (A právě tehdy, když B)

"

obecný kvantifikátor (pro všechna). " x [V(x)] (pro všechna x platí vlastnost V)

$

existenční kvantifikátor (alespoň jedno). $ x [V(x)] (existuje x, které má vlastnost V)

Tab. 2.0: Symboly výrokového a predikátového počtu

 

Vzhledem k zaměření práce budou pro jednotlivé zaváděné pojmy často uváděny příklady z oblasti vodohospodářských systémů.

Základní pojmy teorie grafů

Teorií grafů se zabývá řada autorů. Jde o poměrně mladý obor a proto naneštěstí není ještě zcela ustálena terminologie (např. pro jeden ze základních pojmů používají někteří autoři (např. [23]) termín uzly, někteří (např. [24]) termín vrcholy). Autor této práce se nakonec v podstatné části přidržel symboliky užívané v [2], která je navíc orientována přímo pro vysoké školy technické.

Definice grafu

Mějme konečnou množinu V; její prvky nazývejme vrcholy nebo také uzly; množina V je tedy množina vrcholů nebo také množina uzlů.

Mějme konečnou množinu E; její prvky nazývejme hrany. Množina E je tedy množina hran.

Označme ve shodě s obecně známou množinovou symbolikou:

V2 = V x V = { [u,v] | u Î V Ù v Î V }

V2 = V * V = { {u,v} | u Î V Ù v Î V }

V2 je tedy kartézský součin (= množina uspořádaných dvojic) vrcholů, uzlů z V. V2 je množina všech dvouprvkových množin (= neuspořádaných dvojic), jejichž prvky jsou vrcholy, uzly z V.

Označme dále

J = VxV È V*V = V2 È V2

(konečnou) množinu, jejímiž prvky jsou všechny uspořádané dvojice vrcholů, uzlů (prvky VxV) a všechny neuspořádané dvojice vrcholů, uzlů (prvky V*V).

Označme konečně F zobrazení

F: E ® J

(F je obecně zobrazení z E do J). Je-li tedy e Î E hrana jakožto vzor v zobrazení F, je F(e)=v Î J buď uspořádaná dvojice vrcholů (uzlů) nebo neuspořádaná dvojice vrcholů (uzlů) jakožto obraz ve zobrazení F. Zobrazení F nazývejme zobrazení incidence.

Příklad z oblasti VS: Hranou může být jakákoliv část jakékoliv transportní cesty. Transportní cesta je lineární útvar (polyline) tvořený posloupností bodů, kterými cesta prochází. Jakákoliv její část je vymezena nějakými dvěma body z této posloupnosti. Množina E pak může být množina nějakých částí nějakých transportních cest. Je-li množina V množina všech bodů vymezujících tyto části transportních tras, pak zobrazením F může být např. takové zobrazení, které každé části cesty z E přiřadí dvouprvkovou množinu bodů tuto část cesty vymezující.

Definice: Trojici G = (V,E,F), kde V je množina vrcholů (uzlů), E množina hran a F zobrazení incidence, nazýváme grafem; v některých literaturách se také používá termínu obecný graf.

Definice: Graf G, kde E Í J a pro jehož zobrazení incidence F platí F(e)=e pro každé eÎE, nazýváme prostým grafem.

Označení: Symbolem V(G) budeme označovat množinu všech vrcholů (uzlů) grafu G, symbolem E(G) množinu všech hran grafu G.

Definice: Nechť G, H jsou dva grafy. Je-li V(G) Í V(H) a současně E(G) Í E(H), nazýváme graf G podgrafem grafu H a zapisujeme G Í H.

Příklad z oblasti VS: Grafem může být vodohospodářský systém České republiky. Podgrafem může být povodí Ohře.

Definice: Nechť G Í H. Je-li V(G)=V(H), nazýváme graf G faktorem grafu H.

Faktor G grafu H je tedy takový podgraf grafu H, který obsahuje stejné vrcholy jako H, nemusí však obsahovat všechny hrany H.

Definice: V obecném grafu může zobrazení incidence F přiřazovat dvěma nebo více různým hranám stejnou dvojici vrcholů (uzlů). Zobrazení tedy nemusí být prosté. Různé hrany, které jsou zobrazeny na stejnou dvojici vrcholů (uzlů), se nazývají rovnoběžné (paralelní) hrany. Zobrazení F v prostém grafu je prosté, proto prostý graf nemá rovnoběžné hrany.

Příklad z oblasti VS: Grafem může být vodohospodářský systém České republiky. Mějme v něm dvě nádrže tvořící přečerpávací hydroelektrárnu v bezprostřední kaskádě. Odtok horní (a tedy přítok dolní) nádrže, a potrubí nebo štola vedoucí vody zpět z dolní do horní nádrže, jsou rovnoběžné hrany.

Definice: Množinu všech e Î E takových, že F(e) Í V2 nazýváme množinou neorientovaných hran grafu G a její prvky neorientované hrany.

Definice: Množinu všech e Î E takových, že F(e) Í V2 nazýváme množinou orientovaných hran grafu G a její prvky orientované hrany.

Příklad z oblasti VS: Je jen velmi málo příkladů na neorientované hrany. Většina hran ve VS je zobrazena na uspořádanou dvojici vrcholů (uzlů) - to proto, že voda v hraně v naprosté většině proudí, a to z prvního do druhého vrcholu (uzlu).

Definice: Množinu všech e Î E takových, že F(e) Î { {v,v} | v Î V } nazýváme množinou neorientovaných smyček grafu G a její prvky neorientované smyčky.

Definice: Množinu všech e Î E takových, že F(e) Î { [v,v] | v Î V } nazýváme množinou orientovaných smyček grafu G a její prvky orientované smyčky.

Příklad z oblasti VS: Opět je jen velmi málo příkladů na neorientované smyčky. Orientovanou smyčkou je např. potrubí, které přivádí vodu odtékající z chladící věže zpět pro účely téhož chlazení.

Definice: Pokud množina E obsahuje pouze neorientované hrany a neorientované smyčky, nazývá se graf G neorientovaný graf. Pokud množina E obsahuje pouze orientované hrany a orientované smyčky, nazývá se graf G orientovaný graf.

Příklad z oblasti VS: Z předchozích dvou příkladů vyplývá, že naprostá většina VS jsou orientované grafy. Lze dokonce tvrdit toto: Každý VS může být převeden na orientovaný graf. Stačí ke každé neorientované hraně přidat hranu s ní paralelní a následně obě orientovat, každou z nich navzájem "opačně" - přesněji viz dále.

Vrcholy (uzly)

Definice: Buď e Î E neorientovaná hrana. Je tedy F(e) = {u,v} Î V2. Vrcholy (uzly) u a v nazýváme krajní vrcholy (uzly) hrany e.

Definice: Buď e Î E orientovaná hrana. Je tedy F(e) = [u,v] Î V2. Vrchol (uzel) u nazýváme počátečním vrcholem (uzlem) hrany e. Vrchol (uzel) v nazýváme koncovým vrcholem (uzlem) hrany e.

Příklad z oblasti VS: Netřeba komentovat; počáteční vrchol je ten, ze kterého voda do hrany vstupuje, koncový vrchol je ten, ze kterého voda z hrany vystupuje.

Definice: Buď e Î E orientovaná hrana. Je tedy F(e) = [u,v]Î V2. Vrchol (uzel) u nazýváme bezprostředním předchůdcem (také rodičem) vrcholu (uzlu) v. Vrchol (uzel) v nazýváme bezprostředním následníkem (také potomkem) vrcholu (uzlu) u.

Krajní vrcholy (uzly) neorientované smyčky jsou totožné. Počáteční a koncový vrchol (uzel) orientované smyčku jsou totožné.

Označení: Symbolem U+G(v), kde v Î V je libovolný vrchol grafu G, budeme označovat množinu všech bezprostředních následníků (=potomků) vrcholu v. Symbolem U-G(v), kde v Î V je libovolný vrchol grafu G, budeme označovat množinu všech bezprostředních předchůdců (=rodičů) vrcholu v.

Poznámka: Bude-li zřejmé, o jaký graf jde, používá se označení jen U-(v) a U+(v).

Příklad z oblasti VS: Důležitý je fakt, že každý vrchol (uzel) může mít více předchůdců (ale i žádného) a více následníků (ale i žádného). Vrchol bez předchůdců je např. pramen nebo podzemní zdroj (abstrahujme od podzemní hydrogeologie), vrcholem bez následníků je např. trativod chápaný jako místo vypouštění vod. Vrchol s více předchůdci je např. vyústění jedné kanalizace do sběrného kanálu druhé. Vrchol s více následníky je např. místo, odkud podnik odebírá pitnou vodu z vodovodního řadu podniků Vodovody a kanalizace.

Definice: Počet hran, jimž je vrchol (uzel) v neorientovaného grafu G krajním vrcholem, se nazývá stupněm vrcholu (uzlu) v.

Označení: Symbolem M+G(v), kde v Î V je libovolný vrchol orientovaného grafu G, budeme označovat množinu všech hran, jimž je vrchol v počátečním vrcholem. Symbolem M-G(v), kde v Î V je libovolný vrchol orientovaného grafu G, budeme označovat množinu všech hran, jimž je vrchol v koncovým vrcholem.

Příklad z oblasti VS: Považujme podnik Vodovody a kanalizace za vrchol v. Množina  M+G(v) je např. souhrn všech přípojek, kterými Vodovody a kanalizace dodávají vodu svým odběratelům.  Považujme dále ČOV (čistírnu odpadních vod) podniku za vrchol v. Množina M-G(v) je pak souhrn všech kanálů přivádějících znečištěnou vodu do ČOV.

Definice: Počet hran, jimž je vrchol (uzel) v orientovaného grafu G počátečním vrcholem, se nazývá výstupním stupněm vrcholu (uzlu) v. Počet hran, jimž je vrchol (uzel) v orientovaného grafu G koncovým vrcholem, se nazývá vstupním stupněm vrcholu (uzlu) v.

Poznámka z oblasti VS: Ačkoliv se to z hlediska geometrického uspořádání zdá nadbytečné, z hlediska vodního hospodářství podniků jsou významné vrcholy (uzly), pro něž výstupní stupeň = vstupní stupeň = 1. Jsou to především místa, kde se ve vnitřním podnikovém subsystému voda používá a v naprosté většině se tam mění její kvalita. V takových místech rovněž dochází ke změně kvantity - odpary, vsaky do materiálů apod.

Výstupním stupněm vrcholu v je tedy počet prvků množiny M+(v). Vstupním stupněm vrcholu v je tedy počet prvků množiny M-(v).

Popis grafu

Popsat (definovat) graf G znamená popsat (definovat) každý element trojice V, E a F. Způsob popisu množin V a E je diskutován v předchozí kapitole, stejně jako definice funkce. Uveďme příklad popisu (definice) grafu G takovým způsobem:

G = {V, E, F}

V = { 1, 2, 3, 4, 5 }

E = { a, b, c, d, e, f, g }

F = { [a,{1,2}], [b,[1,2]], [c,{1,3}], [d,{3}], [e,[3,4]], [f,{2,4}], [g,[4,5]] }

Tato definice grafu je sice exaktní, ale pro složitější grafy se stává velmi nepřehlednou. proto se často používá "obrazové" znázornění grafu. Obrázek pro shora definovaný graf G je např. následující:

Obr. 2.1: Příklad grafu

Sledy, dostupnost

Definice: Nechť G = {V, E, F} je neorientovaný graf. Nechť v0, v1, ... , vn-1, vn jsou vrcholy (uzly) z V. Nechť h1, h2, ... , hn jsou hrany z E takové, že F(hi) = {vi-1,vi}.pro všechna i z <1,n>. Pak posloupnost s=[v0, h1, v1, ... , hn, vn] se nazývá (neorientovaným) sledem mezi vrcholy (uzly) v0 a vn. Říkáme také, že v0 a vn jsou dostupné, nebo že v0 (vn) je dostupný z vn (v0).

Definice: Nechť G = {V, E, F} je orientovaný graf. Nechť v0, v1, ... , vn-1, vn jsou vrcholy (uzly) z V. Nechť h1, h2, ... , hn jsou hrany z E takové, že F(hi) = [vi-1,vi] pro všechna i z <1,n>. Pak posloupnost s = [v0, h1, v1, ... , hn, vn] se nazývá orientovaným sledem mezi vrcholy (uzly) v0 a vn (v tomto pořadí!). Říkáme také, že v0 a vn jsou orientovaně dostupné, nebo že vn je orientovaně dostupný z v0.

Příklad z oblasti VS: Orientovaným sledem je např. posloupnost {Vodovodní řad; vstupní šachtice; koupelna; kanalizační přípojka; ČOV}

Označení: Nechť G je orientovaný graf, G=(V,E,F). Nechť v Î V je vrchol (uzel) grafu. Symbolem D+G(v) budeme označovat množinu všech vrcholů (uzlů), orientovaně dostupných z vrcholu v. Symbolem D-G(v) budeme označovat množinu všech vrcholů (uzlů), ze kterých je vrchol (uzel) v dostupný.

Příklad z oblasti VS: Množina D+G(v) je tedy množina míst, do kterých může z v "dotéci voda". Analogicky pro druhý symbol. Je však třeba důrazně připomenout, že zaváděné pojmy jsou "místopisné" a nic nevypovídají o množstvích a zvláště kvalitě vod, která se může při průchodu jednotlivými místy velmi podstatně měnit.

Definice: Množina D-G(v) z předchozího označení se nazývá množina předchůdců vrcholu (uzlu) v v orientovaném grafu G, množina D+G(v) z předchozího označení se nazývá množina následníků vrcholu (uzlu) v v orientovaném grafu G

Poznámka 1: Bude-li zřejmé, o jaký graf jde, používá se označení jen D-(v) a D+(v).

Poznámka 2: Srovnej množiny U+G(v) a U-G(v) (množiny bezprostředních následníků a předchůdců) výše.

Cesty, dráhy

Definice: Neorientovaný sled, v němž se každá hrana vyskytuje jen jednou, se nazývá cesta. Cesta, v níž se každý vrchol (uzel) vyskytuje jen jednou, se nazývá prostá cesta. Platí-li pro prostou cestu s = [v0, h1, v1, ... , hn, vn] rovnost v0=vn, nazývá se taková prostá cesta kružnice.

Definice: Orientovaný sled, v němž se každá hrana vyskytuje jen jednou, se nazývá dráha. Dráha, v níž se každý vrchol (uzel) vyskytuje jen jednou, se nazývá prostá dráha. Platí-li pro prostou dráhu s = [v0, h1, v1, ... , hn, vn] rovnost v0=vn, nazývá se taková prostá dráha cyklus.

Věta: Jestliže v neorientovaném (orientovaném) grafu G existuje mezi uzly u a v sled, pak mezi těmito uzly existuje také prostá cesta (prostá dráha).

Příklad z oblasti VS: Vodohospodářské systémy jsou často velmi složité - především ty, které obsahují např. průmyslové celky. Systémy s kružnicemi a cykly se běžně vyskytují ve velkých průmyslových podnicích s vlastními úpravnami a čistírnami. Jde o uzavřené okruhy s recirkulovanou vodou, vratné vody apod.

Vzdálenosti

Definice: Počet hran ve sledu (cestě, dráze, kružnici, cyklu) se nazývá délkou sledu (cesty, dráhy, kružnice, cyklu).

Je zřejmé, že existuje-li mezi dvěma uzly sled, může mezi nimi existovat sledů více. Každý z těchto sledů má jistou délku. Mezi těmito délkami (což jsou přirozená čísla) jistě existuje jedna nebo více délek s nejmenší hodnotou. Jsou to délky nejkratších sledů.

Definice: Nechť G je neorientovaný graf. Nechť u a v jsou uzly takové, že existuje sled mezi u a v. Pak délku libovolného nejkratšího sledu mezi uzly u a v nazýváme vzdáleností mezi uzly u a v.

Definice: Nechť G je orientovaný graf. Nechť u a v jsou uzly takové, že existuje sled z uzlu u do uzlu v. Pak délku libovolného nejkratšího sledu z uzlu u do uzlu v nazýváme vzdáleností z uzlu u do uzlu v.

Označení: Vzdálenosti definované předchozími dvěma definicemi označujeme d(u,v).

Definice: Jestliže mezi uzly u a v neexistuje sled, klademe d (u,v) = ¥. Symbol ¥ chápeme jako vyjádření té skutečnosti, že jakákoliv reálná vzdálenost je menší než ¥.

Věta: Nechť v neorientovaném grafu G existuje sled mezi u a v a také sled mezi uzly v a w. Pak jistě existuje sled mezi u a w a platí (trojúhelníková) nerovnost

d (u,w) £ d (u,v) + d (v,w)

Analogicky platí věta pro orientované grafy. Pro neorientované grafy platí: d (u,v) = d (v,u). Pro libovolný graf platí d (u,u)=0.

Poznámka: Délka sledu resp. vzdálenost takto definována je rovna délce sledu resp. vzdálenosti v triviálním ohodnocení - viz dále.

Poznámka z oblasti VS: Vzdálenosti a délky sledů takto definované se ve VS uplatní jen zřídka. Zvláště z ekonomických důvodů podniky nezajímá počet kusů např. potrubí vodohospodářské sítě, ale její kilometrová délka apod. O tom je pojednáno dále v kapitole o ohodnocených grafech, jimž je tento odstavec nutným předchůdcem.

Souvislost grafu

Definice: Platí-li pro libovolné dva uzly u a v grafu G d (u,v) ¹ ¥, pak graf G se nazývá souvislý graf.

Souvislý graf je tedy takový, že mezi libovolnými uzly existuje sled (a tedy i prostá cesta pro neorientované, prostá dráha pro orientované grafy). Následující obrázek ukazuje graf, který není souvislý; neexistuje sled např. mezi uzlem 1 a uzlem 8.

Obr. 2.2: Příklad nesouvislého grafu

Poznámka z oblasti VS: Je zřejmé, že nesouvislý vodohospodářský systém lze monitorovat a vyhodnocovat jako dva nebo více dílčích nezávislých subsystémů, z nichž každý je souvislý. Patří-li však do správy jediného právního subjektu, je nutno souhrnné údaje zpracovávat např. z hlediska zákonů o vodním hospodářství.

Dezorientace a orientace grafu

Nechť G = (V, E, F) je orientovaný graf. Podle definice podané shora jsou všechny jeho hrany orientované. Pro každou hranu e Î E je tedy F(e)=[u,v], u,vÎV, uspořádaná dvojice vrcholů (uzlů) z V. Definujme zobrazení H tak, že je-li F(e)=[u,v], je H(e)={u,v}. Obrazem hrany ve zobrazení H je tedy neuspořádaná dvojice (přesněji dvouprvková množina) vrcholů (uzlů) z V.

Definice: Nechť G = (V, E, F) je orientovaný graf. Je-li H zobrazení právě popsané, nazveme graf GD = (V,E,H) dezorientací grafu G.

Je zřejmé, že pro každý orientovaný graf zobrazení H existuje, a to jediné. Pro každý orientovaný graf tedy existuje jediný neorientovaný graf vzniklý dezorientací orientovaného grafu.

Poznámka z oblasti VS:  Modely vodohospodářského subsystému např. podniku existují z evidentních důvodů jako orientované grafy. Takové grafy, zvláště ve spojení s jejich ohodnocením (viz dále), jsou komplexními modely. I dezorientace grafu má však význam, např. při projektování a výstavbě sítě transportních cest a při jejich údržbě, kde nezáleží na směru vedení vody.

Nechť naopak G = (V, E, F) je neorientovaný graf. Podle definice podané shora jsou všechny jeho hrany neorientované. Pro každou hranu eÎE je tedy F(e)={u,v}, u,vÎV, neuspořádaná dvojice - přesněji dvouprvková množina - vrcholů (uzlů) z V. Definujme zobrazení H tak, že je-li F(e)={u,v}, je H(e)=[u,v]. Obrazem hrany ve zobrazení H je tedy uspořádaná dvojice vrcholů (uzlů) z V.

Definice: Nechť G = (V, E, F) je neorientovaný graf. Je-li H zobrazení právě popsané, nazveme graf GO = (V,E,H) orientací grafu G.

Je zřejmé, že pro každý neorientovaný graf G zobrazení H existuje. Je-li však {u,v}, u ¹ v, dvouprvková množina vrcholů (uzlů), lze vytvořit dvě uspořádané dvojice: [u,v] a [v,u]. Je-li n počet hran grafu G, pak pro neorientovaný graf G existuje nejvýš 2n různých orientovaných graf vzniklý orientací neorientovaného grafu.

Poznámka z oblasti VS:  Grafy G modelující VS mají většinu hran orientovaných; orientace zde udává směr vedení vody. Existují-li i některé hrany schopny vést vodu v obou směrech, nelze graf prostě orientovat. Lze však vytvořit nový graf (nový model) GO následujícím způsobem:
   * Vrcholy GO jsou všechny vrcholy G
   * Hrany GO jsou všechny orientované hrany G doplněné o všechny dvojice orientací neorientovaných hran
   * Je zřejmé, že GO je opět grafem, a to grafem orientovaným, který případně obsahuje paralelní hrany.

Les, strom

Definice: Neorientovaný graf bez kružnic se nazývá les.

Definice: Souvislý les se nazývá strom.

Definice: Orientovaný graf ze nazývá orientovaným lesem, právě když graf vzniklý jeho dezorientací je lesem.

Definice: Orientovaný graf ze nazývá orientovaným stromem, právě když graf vzniklý jeho dezorientací je stromem.

Poznámka z oblasti VS:  Vodohospodářský systém málokdy bývá stromem nebo lesem. Často se však pro účely vyhodnocení dílčích částí systému uvažuje subsystém, který je právě orientovaným stromem (jakožto podgraf grafu modelujícího celý systém). Jde např. o sledování, jak je nakládáno se znečištěním, vznikajícím v kořenovém uzlu a postupujícím dále.

Poznámka: terminologie (les, strom) vznikla z pohledu na "obrázkové" znázornění grafu. Následující obrázek ukazuje graf, který je lesem ("má dva stromy"):

Obr. 2.3: Graf, který je lesem

Kostra grafu

Definice: Nechť H je souvislý neorientovaný graf, G jeho faktor. Je-li G zároveň stromem, říkáme, že podgraf G je kostrou grafu H.

Definice: Nechť H je souvislý orientovaný graf. Jeho podgraf G je jeho kostrou, je-li dezorientace grafu G kostrou dezorientace grafu H.

Věta: V každém souvislém neorientovaném grafu existuje alespoň jedna kostra.

Věta: Kostra s n uzly má n-1 hran.

Důsledek: Všechny kostry daného souvislého neorientovaného grafu mají týž počet hran.

Následující obrázek ukazuje graf G a tři jeho kostry A, B a C:

Obr. 2.4: Kostry grafu

Poznámka z oblasti VS:  Pojem kostry grafu bývá často používán jako minimální východisko při projektování a optimalizaci vodohospodářských sítí. Výběr konkrétní kostry pak závisí na konkrétních podmínkách, např. tvar terénu, náročnost zemních prací, naléhavost zásobování vodou apod.

Ohodnocené grafy

Ohodnocení

Nechť je dána množina M, na které je definována binární operace Å : MxM ® M. Tuto operaci budeme často - zvláště je-li M množina číselných hodnot - označovat také jen symbolem +. Jsou-li m1, m2, ... , mn prvky M, budeme používat zřejmého označení åmi pro prvek (((...(m1 Å m2) Å ... ) Å mn. Dále nechť je nad M definována reflexivní, antisymetrická a tranzitivní relace, kterou budeme označovat £ (neostré uspořádání).

Poznámka z oblasti VS: V této oblasti je v naprosté většině množinou M množina reálných čísel, operací Å operace "normálního" sčítání. Prvky množiny M (tj. "normální" čísla) jsou však chápány v různých kontextech a samozřejmě v různých jednotkách - jako objemy vod, jako koncentrace nějaké látky, jako délka potrubí, jako ekonomické náklady na jednotku délky apod.

Definice: Nechť je dán graf G = (V,E,F). Existuje-li zobrazení OH:E(G)®M, říkáme, že graf G je hranově ohodnocený. Prvek OH(e) = m Î M se nazývá ohodnocení hrany e.

Příklad z oblasti VS: Je-li u každé hrany známo, jaký objem protekl každou hranou celkem v pátek 6. října 2000, pak je tím dáno jedno z hranových ohodnocení grafu. Obecně lze říci, že "cokoliv na hranách sledujeme, tvoří ohodnocení": znečištění, cena dodané vody apod.

Definice: Nechť je dán graf G = (V,E,F). Existuje-li zobrazení OV:V(G)®M, říkáme, že graf G je vrcholově (uzlově) ohodnocený. Prvek OV(v) = m Î M se nazývá ohodnocení vrcholu (uzlu) v.

Příklad z oblasti VS: Je-li u každého vrcholu (uzlu) známo, jaké jsou ztráty při průchodu vody vrcholem (uzlem), je tím dáno jedno z vrcholových ohodnocení grafu. Toto ohodnocení je podstatné zvláště u modelů průmyslových podniků, protože determinuje chování celého systému. Ztráty mohou být jak kladné (odpary, použití do výrobku), tak i záporné (např. průsak vody z podloží, srážková činnost).

Definice: Nechť je dán hranově ohodnocený graf G a v něm sled s. Označme e1, e2, ... , en hrany tohoto sledu. Prvek m = å OH(ei) Î M nazveme délkou sledu s v ohodnocení OH.

Poznámka: Na jednom grafu může být současně definováno více ohodnocení. Existuje tedy tolik délek téhož sledu s, kolik existuje různých ohodnocení grafu.

Příklad z oblasti VS: Jsou-li hranovým ohodnocením roční udržovací náklady pro každou hranu, pak délka kteréhokoliv sledu v tomto ohodnocení je rovna ekonomickým nákladům na údržbu tohoto sledu.

V naprosté většině praktických aplikací jsou - stejně jako v příkladech z oblasti VS - hrany a vrcholy (uzly) ohodnoceny numericky. Množinou M je pak množina všech reálných čísel, případně pro konkrétní úlohy množina racionálních, celých nebo i jen přirozených čísel.

Triviální ohodnocení

Definice: Nechť G je graf G=(V,E,F). Označme M množinu přirozených čísel, označme O1 zobrazení O1:E(G)® 1 (tj. O1(e)=1 pro všechna e Î E). Je zřejmé, že zobrazení O1 existuje vždy. Podle definice je O1 hranové ohodnocení, které nazveme triviální ohodnocení.

Je zřejmé, že délka (dle definice výše) sledu v triviálním ohodnocení je rovna počtu hran tohoto sledu a tedy délce téhož sledu dle definice. Obdobná poznámka platí pro pojem "vzdálenost".

Minimální kostra

Podle odstavců výše má každá kostra K souvislého neorientovaného grafu G stejný počet hran. Zcela jistě existuje triviální ohodnocení grafu G i kostry K jako jeho podgrafu. Počet hran K je pak roven součtu ohodnocení všech hran v K v triviálním ohodnocení. Tedy každá kostra grafu G má součet ohodnocení hran v triviálním ohodnocení stejný.

Jinak je však tomu tehdy, existuje-li v souvislém neorientovaném grafu G ohodnocení OH, které není triviální. V něm může každé kostře K příslušet jiný součet ohodnocení hran. Pro kostru K označme tento součet OH(K). Přitom všech koster je konečný počet.

Definice: Takovou kostru Km, pro níž je OH(Km) = min ( OH(Ki) ), nazýváme minimální kostra grafu G v ohodnocení OH.

Poznámka: Minimálních koster tedy může být více. V triviálním ohodnocení je každá kostra minimální.

Příklad z oblasti VS: Na pojmu minimální kostry je založena řada úloh; jednou z nejdůležitějších jsou např. optimalizační úlohy. Nechť jest ohodnocením hran cena vybudování, grafem přitom všechny technologicky možná vedení všech tras. Vyhledáním minimální kostry grafu v daném ohodnocení se pak zjistí nejlevnější možná varianta výstavby potřebného vodohospodářského systému.

Orientované grafy

Tento odstavec zavádí některé pojmy a popisuje některé vlastnosti, které se týkají pouze orientovaných grafů.

Obrácený graf

Nechť G je orientovaný graf, G=(V,E,F). F je podle definice zobrazení incidence: pro všechny hrany eÎE existují vrcholy (uzly) u,vÎV tak, že F(e)=[u,v]. Označme H zobrazení takové, že je-li F(e)=[u,v], je H(e)=[v,u]. Je zřejmé, že takové zobrazení existuje vždy, a to jediné.

Definice: Nechť G je orientovaný graf, G=(V,E,F). Nechť H je zobrazení podle předchozího odstavce. Graf Gx=(V,E,H), se nazývá obrácený graf ke grafu G.

Populárně řečeno, obrácený graf je takový, ve kterém "všechny šipky směřují obráceně".

Silná souvislost, silně souvislé komponenty

Definice: Orientovaný graf G=(V,E,F) ze nazývá silně souvislý, jestliže pro každou dvojici vrcholů (uzlů) u, v Î V existuje dráha z u do v a současně dráha z v do u.

Definice: Každý podgraf H orientovaného grafu G nazveme silně souvislou komponentou, je-li H silně souvislý a je zároveň "maximální" silně souvislý v tomto smyslu: je-li L jiný podgraf G, který je zároveň podgrafem H, pak již L není silně souvislý.

Věta: Každý vrchol grafu leží právě v jedné silně souvislé komponentě.

Věta: Hrana e je obsažena v nějakém cyklu právě tehdy, když oba její vrcholy (uzly) leží v téže silně souvislé komponentě.

Důsledek: Graf G je silně souvislý právě tehdy, když je souvislý a každá jeho hrana leží v nějakém cyklu.

Bezprostředně z definice silně souvislé komponenty a množin D+ a D- vyplývá věta:

Věta: Silně souvislá komponenta obsahující vrchol v má množinu vrcholů rovnou D+(v) Č D-(v).

Příklad z oblasti VS: Je zřejmé, že pouze uzavřený vodohospodářský systém tvoří silně souvislý graf. Dále je zřejmé, každý vodohospodářký systém lze převést na silně souvislý, přijme-li se myšlenka, že všechna voda, která projde procesem spotřeby, se vrací po vyčištění znovu do spotřeby. Při zjednodušeném pohledu to takto funguje v přírodě, přidáním fiktivního globálního "distribučního" uzlu, "sběracího" uzlu a jejich propojením se stává z každého VS silně souvislý graf. Toho se výhodně využívá při modelování složitých, zvláště dynamických systémů.

Kondenzace grafu

Shora definovaný pojem silně souvislé komponenty a zvláště jejich vyznačení v zobrazení grafu vede k myšlence "odstranění" cyklů a k jakémusi "globálnějšímu" pohledu na graf. Uvažujme následující graf:

Obr. 2.5: Silně souvislé komponenty

V grafu na tomto obrázku jsou rámečky vyznačeny všechny silně souvislé komponenty. Graf je souvislý, ale nikoliv silně souvislý. Za povšimnutí stojí, že v komponentě K každá hrana leží v nějakém cyklu, ale neexistuje cyklus, který by obsahoval všechny vrcholy K. Myšlenkou tzv. kondenzace je považovat silně souvislé komponenty za vrcholy nějakého nového grafu.

Definice: Nechť je dán orientovaný graf G. Označme VK množinu všech silně souvislých komponent Ki grafu G. Vytvořme množinu EK uspořádaných dvojic [Ki,Kj] takto: [Ki,Kj]ÎEK právě tehdy, když Ki¹Kj a v grafu G existuje hrana z nějakého vrcholu v Î Ki do nějakého vrcholu u Î Kj. Je-li e=[Ki,Kj]ÎEK, pak identita H(e)=e je zobrazení H:EKàVKxVK. Uspořádaná trojice K=(VK,EK,H) tedy splňuje definici grafu; tento graf K nazveme kondenzací grafu G.

Kondenzace grafu z předchozího obrázku je následující:

Obr. 2.6: Kondenzace grafu

Podle definice kondenzace neobsahuje kondenzace K grafu G smyčky. Kdyby kondenzace K grafu G obsahovala cyklus procházející alespoň dvěma různými vrcholy (vrchol K = silně souvislá komponenta G!), existoval by již v grafu G cyklus procházející přes tyto komponenty, což je ve sporu s definicí silně souvislé komponenty. Proto platí věta:

Věta: Kondenzace libovolného orientovaného grafu neobsahuje žádný cyklus.

Příklad z oblasti VS: Kondenzace grafu se používá k syntetickému pohledu na (zvláště složitější) vodohospodářské subsystémy. Vrcholy kondenzace pak mohou být nazírány relativně samostatně. Souhrnný vodohospodářský systém rozsáhlého trustu podniků (jako např. důlní podniky Severní Moravy) tvoří velmi složitý graf. Jeho kondenzací lze určit takové subsystémy, která mají s ostatními společnou vždy jen jednu hranu. Vrcholy kondenzace často jsou (ale nemusí být) totožné s hospodářskou organizační jednotkou (podnikem, provozem podniku). Z hlediska řídících pracovníků pak je možno optimalizovat činnosti (příp. počet) vodohospodářů jednotlivých organizačních jednotek.

Acyklické grafy, topologické uspořádání

Definice: Orientovaný graf G je acyklický, když neobsahuje žádný cyklus ani orientovanou smyčku.

Příklad z oblasti VS: Vodohospodářský subsystém podniku bez vratné a recirkulované vody acyklickým grafem.

Věta: Každý acyklický graf obsahuje alespoň jeden vrchol u, pro nějž je D-(u)={Æ}, a alespoň jeden vrchol v, pro nějž je D+(v)={Æ}.

Příklad z oblasti VS: V grafových modelech vodohospodářských subsystémů podniků bez vratné a recirkulované vody jsou podniky Vodovodů a kanalizací na jedné straně a podniky Povodí XY na straně druhé abstrahovány do jednotlivých vrcholů (uzlů). Proto Vodovody a kanalizace jsou vrcholem, pro který  D-(u)={Æ}a Povodí XY vrcholem, pro který D+(u)={Æ}.

Definice: Nechť [v1, v2, ... , vn] je posloupnost všech vrcholů orientovaného grafu G. Nechť v této posloupnosti platí: kdykoliv je vi rodičem vj, je i<j. Pak tuto posloupnost nazveme topologické uspořádání vrcholů (uzlů) grafu G.

V topologickém uspořádání vrcholů tedy platí: počáteční vrchol každé hrany "předchází" koncovému vrcholu této hrany.

Definice: Nechť [e1, e2, ... , em] je posloupnost všech hran orientovaného grafu G. Nechť v této posloupnosti platí: kdykoliv je koncový vrchol hrany ei roven počátečnímu vrcholu hrany ej, je i<j. Pak tuto posloupnost nazveme topologické uspořádání hran grafu G.

V topologickém uspořádání hran tedy platí: všechny hrany, mající koncový vrchol v, předchází všem hranám, majících v za počáteční vrchol.

Věta: Topologické uspořádání vrcholů existuje tehdy a jen tehdy, existuje-li topologické uspořádání hran.

Věta: Topologické uspořádání vrcholů orientovaného grafu G existuje tehdy a jen tehdy, je-li graf G acyklický.

Poznámka z oblasti VS: Předchozí důležité věty stanovují, že topologické uspořádání (vrcholů i hran) existují jen ve vodohospodářských systémech bez recirkulované a vratné vody.

Kořeny, listy a zdroje

Definice: Nechť v Î V(G) je vrchol orientovaného grafu G. Řekneme, že v je kořen grafu G, jestliže D+(v)=V(G), tj. jestliže každý vrchol grafu G je orientovaně dostupný z vrcholu v.

Definice: Nechť v Î V(G) je vrchol orientovaného grafu G. Řekneme, že v je list grafu G, jestliže D+(v) = {Æ}, tj. jestliže vrchol v grafu G nemá bezprostředního následníka.

Příklad z oblasti VS: Ve vodohospodářském subsystému podniku jsou listy grafového modelu ta ("bezodtoková") místa, do kterých podnik vypouští svou vodu..

Definice: Nechť v Î V(G) je vrchol orientovaného grafu G. Řekneme, že v je zdroj grafu G, jestliže D-(v) = {Æ}, tj. jestliže vrchol v grafu G nemá bezprostředního předchůdce.

Příklad z oblasti VS: Dodavatelé vod do podniku jsou ve vodohospodářském subsystému podniku zdroje grafového modelu. Za povšimnutí stojí, že ne každý zdroj je kořenem! K tomu viz následující poznámka.

Poznámka: Má-li orientovaný graf jediný kořen, je tento kořen zdrojem (a naopak). Má-li orientovaný graf více kořenů, nemá zdroj (a naopak).

Definice kořene uvedená shora nevylučuje, aby graf měl více kořenů (v tom případě obsahuje graf alespoň jeden cyklus), jak to ukazuje následující obrázek; tento graf nemá zdroj:

Obr. 2.7: Orientovaný graf se třemi kořeny

Definice: Orientovaný graf, který je stromem a má kořen, se nazývá kořenový strom.

Velká skupina praktických úloh se opírá právě o kořenové stromy. Některé vlastnosti kořenových stromů je možno vyjádřit následující větou:

Věta: Nechť G=(V,E,F) je orientovaný graf s n vrcholy (uzly). Pak následující tvrzení jsou ekvivalentní:

a. Graf G je kořenovým stromem.

b. Graf G má kořen v a do každého vrcholu u různého od v vede právě jediná orientovaná cesta.

c. Graf G má kořen a po odstranění libovolné hrany již kořen nemá.

d. Graf G má kořen a neobsahuje kružnici.

e. Graf G má kořen a má nejvýše n-1 hran.

Důsledek: Kořenový strom má zdroj, a to jediný.

Poznámka: Výrok předchozí věty, že např. "tvrzení a je ekvivalentní tvrzení d" se lépe čte takto: (Graf G je kořenovým stromem) právě tehdy, když (Graf G má kořen a neobsahuje kružnici).

Uvedená věta dovoluje jednak lehce rozhodnout, je-li daný graf kořenovým stromem, jednak umožňuje sestavit algoritmy např. pro vyhledání kořenového stromu s daným vrcholem.

Příklad z oblasti VS: Uvedená věta dovoluje řešit např. úlohy šíření znečištění apod.

Sítě, toky

Definice: Libovolný orientovaný hranově ohodnocený graf se nazývá síť, je-li ohodnocením zobrazení OH:E(G)®R (R je množina reálných čísel). Toto zobrazení se nazývá kapacita sítě. Hodnotu OH(e)=rÎR se nazývá kapacita hrany e.

Poznámka: protože na jednom grafu může být dáno více ohodnocení, upřesňuje se pak síť XY podle příslušného konkrétního ohodnocení XY.

Příklad z oblasti VS: Libovolný vodohospodářský subsystém je sítí, je-li na něm definována kapacita. Tou může být např. číslo udávající maximální průtok každou hranou. Z vodohospodářského hlediska je pak zajímavá úloha směřující k určení maximálního množství vody, které může protékat celou sítí.

Definice toku 1: Nechť je dána síť. Její ohodnocení OH se nazývá tokem, platí-li pro každý vrchol vÎV tzv. 1. Kirchhoffův zákon ("ve vrcholech se nic nehromadí"):

                                         (1)

Příklad z oblasti VS: Kromě maximálního průtoku hranami je nejčastějším ohodnocením ve vodohospodářských subsystémech ohodnocení množstvím vody prošlé každou hranou za jisté období (průtok). Libovolný vodohospodářský subsystém je pak tokem, platí-li pro jeho hranové ohodnocení: množství vody přitékající do kteréhokoliv uzlu je rovno množství vody, které z něj odteče. Na první pohled je zřejmé, že ohodnocení množstvím vody pro většinu vodohospodářských subsystémů není v praxi tokem. Např. přírodní nádrže - zvláště s větší plochou - mají jednak ztráty způsobené výparem, jednak průsaky mohou vodu jak přivádět, tak odvádět. Souhrn množství těchto neevidovatelných pohybů může být značný vzhledem k přirozeným přítokům a odtokům. Navíc (protože k obdobným disproporcím dochází ze stejných důvodů i u hran) není hranové ohodnocení konstanta.

Poznámka z oblasti VS: Ohodnocení množstvím vody lze na tok převést přidáním jednoho nebo více fiktivních uzlů; nazvěme je "Ostatní zdroje vod" a "Ostatní ztráty vod" a směrujme do nich fiktivní hrany z jednoho nebo více uzlů, kde dochází ke ztrátám nebo přírůstkům vod.

V praxi není tokem mnoho ohodnocení, které by (1) splňovaly, nemít graf kořeny a (nebo) listy. Proto pojem toku lze modifikovat takto:

Definice toku 2: Ohodnocení je tokem, platí-li (1) pro všechny vrcholy až na případný konečný počet vrcholů, pro které platí, že buď levá strana (1) nebo pravá strana (1) je rovna nule.

Příklad z oblasti VS: Ohodnocení množstvím vody je podle definice toku 2 tokem i pro subsytémy obsahující např. studny nebo bezodtoká místa vypouštění.

Právě grafů, na kterých je definován tok, se týká řada úloh aplikovatelných beze změny ve vodohospodářských subsystémech. Jde o již shora uvedený výpočet maximálního toku nebo (v případě dolního a horního omezení pro ohodnocení hran) o obecnější úlohu stanovení přípustného toku. Je-li oceněním finanční hodnota, pak často řešenou úlohou je zjištění nejlevnějšího toku atd.