Co je to graf? Grafem v teorii grafů myslíme něco jiného než je graf funkce nebo například sloupcový graf. Graf $G$ je dvojice $(V,E)$. Prvkům množiny $V$ říkáme vrcholy a prvkům $E\subseteq\{\,\{u,v\}\,|\, u,v\in V\, \}$ hrany.

Hrana $e\in E$ je neuspořádaná dvojice vrcholů, tedy $e = \{u,v\}$ pro $u,v\in V$. Vrcholy $u,v$ jsou konce hrany $e$. Protože $v\in e$, tak říkáme že $v$ náleží do $e$, nebo použijeme cizí slovo a řekneme, že $v$ je incidentní s $e$. Často existenci hrany vyjadřujeme slovy: “vrcholy $u,v$ jsou spojeny hranou $e$”, “z $u$ vede hrana do $v$”, “vrchol $u$ sousedí s vrcholem $v$”. Vrcholy, se kterými je vrchol $u$ spojen hranou, se nazývají sousedi vrcholu $u$. Množinu všech neuspořádaných dvojic vrcholů $V$ budeme značit $V \choose 2$.1 Potom se dá napsat, že $E \subseteq {V \choose 2}$.

Ačkoliv je graf abstraktní pojem, často ho kreslíme na papír. Vrcholy kreslíme jako “puntíky” a hrany jako čáry, které je spojují.2

Grafem můžeme jednoduše zachytit celou řadu souvislostí mezi různými objekty:

Vztahy mezi lidmi. Vrcholy grafu jsou lidé, konkrétně $V=($ Adéla, Franta, Káča, Lukáš, Marek, Silvie $)$. Dva lidé jsou spolu spojeny hranou, pokud mezi sebou mají určitý vztah. Například pokud spolu kamarádí.

Barvení mapy. Zjednodušení struktury nám může pomoci lépe a přehledněji vyřešit požadovaný problém. Například chceme obarvit mapu Jižní Ameriky tak, aby sousední státy měly jinou barvu (jinak by na první pohled vypadaly jako $1$ velký stát). Nejprve si vytvoříme pomocný graf. Do každého státu umístíme vrchol (například do hlavního města) a vrcholy dvou států spojíme hranou, pokud spolu sousedí. Teď stačí obarvit vrcholy grafu tak, aby vrcholy spojené hranou měly různou barvu.




Silniční síť si také můžeme zjednodušeně zachytit grafem. Křižovatky znázorníme jako vrcholy, a silnice, které je spojují, jako hrany.

 

Každá silnice má svojí délku. Tuto délku můžeme připsat ke každé hraně. Dostaneme tím ohodnocený graf. Ohodnocený graf $G$ je graf $G=(V,E)$, ke kterému přidáme funkci $h:E\to \RR$, která každé hraně $e$ přiřadí hodnotu $h(e)$.

Teoreticky by se mohlo stát, že dvě křižovatky budou spojeny dvěmi různými silnicemi. Jinými slovy, mohlo by se stát, že dva vrcholy budou spojeny dvěmi různými hranami. Běžné grafy nám neumožňují takové věci zachytit. Museli bychom pojem grafu zobecnit tak, že každé hraně přiřadíme její násobnost $N:E\to \NN$. Násobnost vyjadřuje, kolikrát je hrana v grafu zastoupena. Tím dostaneme multigrafy.

Jiné zavedení multigrafů pracuje se zobrazením, které každé hraně přiřadí dva vrcholy, které jsou její konce. To už je blíže tomu, jak multigrafy používá programátor.

V některých aplikacích se můžeme použití multigrafů (a násobných hran) vyhnout tím, že na jednu hranu umístíme fiktivní vrchol/křižovatku, který hranu rozdělí na dvě.

Web. Chtěli bychom si znázornit “strukturu” webových stránek. Vrcholy grafu budou webové stránky. Dva vrcholy (webové stránky) spojíme hranou, pokud z jedné stránky vede odkaz do druhé. Jak je ale vidět, tento vztah není symetrický. Ze stránky A může vést odkaz na stránku B, ale naopak už to platit nemusí. Abychom lépe zachytili strukturu webu, tak z každé hrany uděláme šipku. Z vrcholu A povede šipka do vrcholu B, pokud ze stránky A vede odkaz na stránku B. Dostaneme tím orientovaný graf.

Orientovaný graf je graf, kde každé hraně udělíme orientaci. Na obrázku se dá říci, že z hran uděláme šipky. Formálně, orientovaný graf $G=(V,E)$, kde $V$ jsou vrcholy a $E\subseteq V \times V$ jsou hrany. Hrany jsou orientované, v prvním vrcholu začínají a ve druhém končí. Proto $(u,v)\not = (v,u)$.

V orientovaných grafech se může stát, že existuje hrana $xy\in E$, ale i $yx\in E$. Dokonce se může stát, že v grafu bude hrana $xx\in E$. Takovým hranám říkáme smyčky.

Odkud pochází název hrana, vrchol? Pochází z mnohostěnů. Mnohostěny, například krychle, mají také vrcholy a hrany. Vrcholy jsou body a hrany jsou úsečky spojující dva vrcholy. Jak spolu souvisí mnohostěn a graf? Ke každému mnohostěnu můžeme najít graf popisující jeho strukturu. Představte si mouchu, která si sedne na stěnu velké skleněné krychle. Skrz skleněnou krychli moucha uvidí obrázek napravo. Ten odpovídá nakreslení grafu.

Značení používané této knize. Pokud mluvíme pouze o grafu, tak myslíme obyčejný neorientovaný graf. Když bychom chtěli mluvit o jiném grafu, tak to vždy zdůrazníme.

Protože budeme grafy používat hodně často a většinou budeme pracovat jen s jedním grafem $G$, tak budeme počet vrcholů grafu $G$ označovat písmenem $n$ a počet hran písmenem $m$. Také budeme zjednodušeně psát $uv \in E$ místo $\{u,v \}\in E$ a v orientovaných grafech $uv \in E$ místo $(u,v)\in E$.