Grafy

V této kapitole se zaměříme na něco, čemu v informatice říkáme graf. Disciplíně, která se grafům věnuje, říkáme Teorie grafů a jako téma je velice bohatá. My se zaměříme jen na naprosté základy, abychom pochopili koncept. V praxi mají totiž grafy až nečekaně široké využití, s jejich aplikací se můžeš setkat v počítačových sítích, v navigaci, v plánování vodovodních potrubí, v biologii a chemii, ale třeba i sociologii.

Co si představíš pod pojmem graf? Spousta lidí si představí sloupcové grafy používané třeba v reklamách, kdy se nás výrobci snaží přesvědčit, abychom si koupili novou a mnohem lepší verzi výrobku. Nebo koláčové grafy, se kterými se můžeme setkat například v průzkumech veřejného mínění. Tyto typy grafů můžeme označit jako statistické.

Jiní si při pojmu graf představí graf nějaké matematické funkce, tedy nějakou křivku v závislosti na typu funkce – např. přímka pro lineární funkci nebo parabola pro kvadratickou.

V informatice grafy myslíme něco úplně jiného – zjednodušeně řečeno kolečka a čárky. V principu jednoduchý koncept, který má až překvapivě mnoho praktických aplikací.

Graf – vrcholy a hrany

V informatice se graf skládá z množiny vrcholů (koleček) a hran (čárek). Hrany spojují vrcholy mezi sebou, ale v grafu můžeme mít i vrcholy, ke kterým žádná hrana nenáleží. Množinu vrcholů značíme zpravidla V (z anglického vertex/vertices), množinu hran E (z anglického edge(s)). Počet uzlů grafu odpovídá velikosti množiny V. Celý graf popisuje dvojice (V, E).

Následuje několik příkladu grafů, které mají stejné vrcholy (V = {A, B, C, D, E}), ale liší se hranami – odpovídající množinu hran popisující daný graf najdeš pod každým obrázkem.

V tomto textu značíme hranu mezi dvěma vrcholy X a Y intuitivně spojením označení obou vrcholů: XY. Z matematického hlediska nejde o úplně přesné vyjádření, ale pro pochopení principů si s ním vystačíme. Kdybychom měli být matematicky přesní, hranu XY bychom zapsali jako dvouprvkovou množinu obsahující odpovídající vrcholy: {X, Y}.

Než si zavedeme několik užitečných pojmů, podíváme se na jednoduché rozšíření, tzv. ohodnocený graf. V ohodnoceném grafu ke každé hraně dostaneme číselné ohodnocení (často toto číslo vyjadřuje cenu, viz dále). O grafech, o kterých jsme mluvili doposud, budeme nadále mluvit jako o grafech (bez přívlastku) nebo jako o neohodnocených grafech. Neohodnocený graf můžeme na ohodnocený převést jednoduše tak, že všem hranám dáme stejné ohodnocení – typicky jedničku.

Užitečným termínem teorie grafů je tzv. cesta v grafu. Cesta je posloupnost na sebe navazujících hran z jednoho vrcholu do druhého bez opakování. V prvním grafu výše nemáme žádnou hranu, takže ani žádnou cestu. V druhém grafu už je cest spousta dokonce i mezi stejnými vrcholy. Například mezi vrcholy B a D máme dvě cesty, první přes hrany AB-AC-CD a druhou přes hrany AB-AE-CE-CD. Pojmem nejkratší cesty mezi dvěma vrcholy myslíme takovou cestu, která se skládá z nejmenšího počtu hran. V případě ohodnocených grafů nemá nejkratší cesta nutně nejmenší počet hran, ale chceme, aby součet jejich ohodnocení byl minimální.

Na následujících příkladech můžeš hezky vidět, jak ohodnocení hran mění vlastnosti grafů, které jsou jinak strukturou stejné.

Z příkladů výše by tě mohlo napadnout, proč při převádění neohodnoceného grafu na ohodnocený dáváme všem hranám stejnou cenu.

Někdy se nebudeme zabývat celým grafem, ale třeba jen jeho částí. Termínem podgraf rozumíme graf, který má alespoň některé vrcholy a hrany původního grafu, ale zároveň nemá žádné hrany ani vrcholy navíc.

Dalším pojem, který si dnes vysvětlíme, je souvislost. O grafu řekneme, že je souvislý, pokud z každého vrcholu grafu vede cesta do libovolného jiného vrcholu (tj. z každého vrcholu se můžeme dostat do jiného). Graf B je souvislým grafem, grafy A a C souvislé nejsou.

Posledním termínem, který si zavedeme, je kostra grafu. Kostra grafu je souvislý podgraf (tj. o kostře se má smysl bavit jen u souvislých grafů), který obsahuje všechny vrcholy původního grafu a pro každou hranu kostry platí, že po jejím odstranění by již nešlo o kostru grafu. Jinak řečeno, kostra obsahuje pouze ty hrany, které jsou potřebné k propojení všech vrcholů a žádné jiné.

V případě ohodnocených grafů pak můžeme mluvit o minimální kostře. To je taková kostra, jejíž součet ohodnocení jejích hran je minimální.

Má smysl mluvit o minimální kostře v neohodnoceném grafu? Proč?

Praktické využití grafů

V předchozí části jsme si zavedli grafy a několik pojmů, teď se podíváme na slíbené praktické aplikace.

První aplikací, na kterou se podíváme, je průchod bludištěm. Bludiště má vchod a východ, přičemž naším úkolem je najít cestu bludištěm tak, abychom se od vchodu dostali k východu. Pojem cesty máme i v grafech, přičemž úloha, kterou budeme řešit, je přesně hledání cesty v grafu. Jediné, co musíme nejprve udělat, je převést bludiště na graf tak, cesta v grafu odpovídala cestě v bludišti. Naštěstí to není vůbec těžké. Než budeš číst dál, zkus se nejdřív zamyslet, jak bys to udělal.

Přišel jsi na to? Jedním z možných řešení je umístit do každé křižovatky / zatáčky bludiště vrchol grafu. Hranami pak spojíme všechny vrcholy, které spolu bezprostředně souvisí a můžeme se mezi odpovídajícími křižovatkami přesouvat (tj. v grafu mezi křižovatkami neleží žádná stěna).

Jak můžeš vidět na příkladu výše, převedli jsme bludiště na graf a hledání cesty ze startu do cíle jsme převedli na hledání cesty v grafu mezi dvěma vrcholy. Dalším praktickým příkladem, který funguje stejně, je běžná navigace. Jediným rozdílem je, že na graf nepřevádíme bludiště, ale reálné ulice – v konečném důsledku v tom ale není příliš velký rozdíl, viď?

Praktickou aplikací z jiného soudku je elektrické vedení. Představme si, že máme elektrárnu a několik vesnic, mezi kterými je potřeba natáhnout elektrické vedení tak, aby všechny vesnice měly zajištěné dodávky elektřiny, ale zároveň aby bylo natažení vedení co nejlevnější.

Stejně jako v případě bludiště a navigace si nejdřív úlohu musíme převést na graf – z vesnic a elektrárny uděláme vrcholy, které propojíme hranami s ohodnocením, které odpovídá ceně natažení vedení. Jakmile máme graf odpovídající úloze, stačí nám najít kostru grafu, respektive minimální kostru grafu, protože chceme, aby nás vedení vyšlo co nejlevněji.

Tímto možnosti aplikace teorie grafů nekončí, jejich další uplatnění lze najít i při výpočtech kapacit vodovodních sítí, párování (např. uchazečů a škol včetně preferencí), ale i v chemii či například lingvistice.