Modelování pomocí grafů

Pojem „graf“ má bohužel v češtině několik odlišných významů. Mimo jiné používáme grafy funkcí, grafy pro vizualizaci dat a grafy modelující vztahy mezi objekty.

Zde se zabýváme posledním zmíněným významem. V tomto případě se grafem rozumí vrcholy („tečky“) a hrany („spojnice“). Takovéto grafy se používají pro modelování vztahů mezi objekty, například:

• Dopravní síť: vrcholy jsou města, hrany jsou silnice mezi nimi.
• Sociální síť: vrcholy jsou lidé, hrany odpovídají přátelství.
• Webové stránky: vrcholy jsou jednotlivé stránky, hrany odpovídají odkazům mezi nimi.

Základní témata o grafech se zaměřují na použití grafů na intutivní úrovni (tato témata jsou vhodná i na úrovni základní školy):

• Grafy a abstrakce – použití grafu jako modelu skutečnosti, porozumění významu grafů.
• Grafy sousednosti – jeden konkrétní případ užití grafů, na kterém se dá čistě obrázkovou formou dobře procvičit princip abstrakce.
• Nejkratší cesty – intuitivní příklady na hledání nejkratších cest mezi vrcholy, což je jedna z typických aplikací grafů.
• Izomorfní grafy – téma se složitě znějícím názvem, ale poměrně intuitivními obrázkovými zadáními; hledáme grafy, které mají „stejná spojení“.

Grafy mají v informatice bohaté využití. Abychom mohli s grafy více pracovat, nevystačíme jen s obrázky, ale potřebujeme i přesně pracovat s pojmy. Toto důkladnější pojetí už je na úrovni střední a vysoké školy: základní pojmy, vlastnosti a části grafů, pojmy a abstrakce.

Při řešení složitějšího nebo nepřehledného problému je často dobrý nápad si ho nakreslit. Grafy umožňují jednoduše graficky znázornit situaci s různými objekty, které mezi sebou mají vztahy. Grafy se skládají z vrcholů a hran, které propojují vrcholy mezi sebou. Vrcholy se obvykle zobrazují jako puntíky nebo kroužky, hrany kreslíme jako čáry nebo šipky. K vrcholům i hranám můžeme přidávat různé popisky, pokud se nám to hodí. Vrcholy modelují objekty, zatímco hrany představují vztahy mezi nimi.

Některými příklady modelování pomocí grafů jsou:

Grafy umožňují zachovat důležité informace o skutečnosti a přitom vynechat ty, které pro nás nejsou užitečné. Například, pro nalezení nejkratší cesty mezi vesnicemi nepotřebujeme vědět, jestli je v okolí nějaký rybník nebo les.

Příklad: sociální síť

Lidé jsou vrcholy, kdo koho sleduje modelují šipky (hrany).

Jednou z typických úloh na grafech je hledání cest mezi vrcholy. Pokud chceme v mapě najít co nekratší cestu z jednoho místa do jiného, můžeme mapu převést na graf, v němž budeme hledat nejkratší cestu po hranách. V takové situaci se často hodí k hranám (cestám mezi místy) doplnit údaje o jejich délce.

Z tohoto grafu bychom například zjistili, že nejkratší cesta z Rejšic do Jabkenic má 3 kilometry a vede přes Charvatce.

Cesty je možné kromě prostorové vzdálenosti porovnávat i podle jiných kritérií:

• Když internetový poskytovatel zajišťuje propojení svých sítí, může případná spojení porovnávat podle ceny za jejich pronájem.
• Navigace neporovnává cesty jen podle délky, ale i podle času dojezdu. Cesta po dálnici pravděpodobně bude o mnoho rychlejší, než stejně dlouhá cesta po okresní silnici.

Grafy jsou izomorfní, pokud mají stejný počet vrcholů a „stejná spojení“. Zde nebudeme rozebírat přesnou matematickou definici (tu najdete třeba zde), ale jen intuitivní představu. Představme si vrcholy grafu jako dřevěné kolíčky a hrany jako gumičky mezi nimi. S kolíčky a gumačkami můžeme hýbat a pořád je to „stejný graf“, protože vztah spojení zůstává zachován. Izomorfismus grafů se týká právě tohoto typu „stejnosti“. Můžeme s jedním grafem hýbat tak, až z něj dostaneme ten druhý?

Cvičení na izomorfní grafy nejsou užitečná ani tak kvůli pojmu samotnému, ale především jako trénink abstrakce. Při hledání izomorfních grafů musíme odhlédnout od detailů (jak přesně jsou hrany zakresleny) a soustředit se pouze na důležité vztahy (kdo je s kým spojen).

Graf je struktura, která nám pomáhá znázorňovat objekty a vztahy mezi nimi. Skládá se z vrcholů a hran. Vrcholy často reprezentují reálné objekty a obvykle je kreslíme jako tečky nebo kolečka. Hrany představují vztahy mezi vrcholy, na obrázku obvykle vypadají jako čáry mezi vrcholy. Každá hrana vede mezi dvěma vrcholy, oba její konce tedy musí být připojeny k některému vrcholu.

Mezi základní grafové pojmy patří:

• Stupeň vrcholu je počet hran, které z daného vrcholu vychází.
• Cesta mezi dvěma určenými vrcholy existuje, pokud v grafu dokážeme přejít po hranách z jednoho vrcholu do druhého.
• Vzdálenost dvou vrcholů je délka nejkratší cesty mezi těmito vrcholy. Naopak nám vůbec nezáleží na tom, jak daleko jsou od sebe vrcholy na obrázku, pokud graf nakreslíme.

Dále si ukážeme některá rozšíření obyčejných grafů, tedy druhy grafů, jejichž vlastnosti jsou nějakým způsobem upravené.

V orientovaném grafu mají hrany přesně určený směr, kterým vedou, a tedy i začáteční a koncový vrchol. To je rozdíl od grafů, o kterých jsme uvažovali doposud –⁠ tam hrany vedou „mezi vrcholy“ a nemají dáno, kde začínají a kde končí. Hrany orientovaných grafů se často znázorňují jako šipky.

V ohodnoceném grafu má každá hrana přiřazenu určitou hodnotu (nazývanou také váha). V obrázku píšeme váhy jako čísla ke hranám. Pomocí těchto hodnot můžeme snadno znázornit například délky cest mezi městy.

Graf je souvislý, pokud mezi každými dvěma z jeho vrcholů vede cesta. To znamená, že všechny vrcholy jsou spolu nějak propojené –⁠ dokážeme v grafu přejít po hranách z každého vrcholu do všech ostatních.

Komponenta souvislosti je část grafu, která je souvislá, ale pokud bychom do ní chtěli zahrnout nějaké další hrany nebo vrcholy, souvislá by být přestala. Každý graf je rozdělený na několik komponent souvislosti. Pokud je graf souvislý, tvoří sám o sobě jednu komponentu souvislosti.

Podgraf je část (tedy některé vybrané vrcholy a hrany) grafu, která sama o sobě také tvoří graf. Každá hrana v podgrafu tedy musí mít na obou svých koncích vrchol, který také patří do podgrafu.

V úplném grafu je každý vrchol je spojený s každým. Tento graf má tedy maximální počet hran, který může mít.

Strom je souvislý graf, který neobsahuje žádnou kružnici jako podgraf. Stromy mají mnoho zajímavých vlastností a často se používají v informatice, například pro přehledné a efektivní uložení dat.