Přehled grafů

Graf je základní matematická struktura, která se používá k modelování relací (vztahů - např. býti rodičem) mezi objekty. Grafy se využívají v mnoha oblastech informatiky, například při hledání nejkratších cest, plánování, závislostech mezi úlohami, v počítačových a sociálních sítích a dalších oblastech.

Definice Grafu

Graf $G$ je definován jako uspořádaná dvojice množin:

$$G=(V,E)$$

kde:

• $V$ je konečná množina vrcholů (angl. vertices, někdy také nodes),
• $E\subseteq V\times V$ je množina hran (angl. edges), které reprezentují spojení mezi vrcholy.
  • Zápis $V\times V$ znamená, že se jedná o dvojice vrcholů (mezi kterými je ta hrana), kdy platí, že oba vrcholy jsou z množiny všech vrocholů $V$

Podgraf grafu $G$ je graf $P$ = ($V_1$, $E_1$) takový, že $V_1\subseteq V$ a $E_1\subseteq E$

Symbol $\subseteq$

Symbol $\subseteq$ se využívá ve významu býti podmnožinou. Tedy například $A\subseteq B$ čteme jako A je podmnožinou B. Zároveň může platit, že $A=B$.

Orientovanost grafu

Graf může být:

• Neorientovaný – hrany nemají směr, tedy spojení mezi vrcholy je vzájemné.
  • Například: dálnice
• Orientovaný – hrany mají směr, což znamená, že spojení z $u$ do $v$ neznamená existenci spojení spojení z $v$ do $u$.
  • Například: jednosměrná silnice

Stupeň vrcholu deg(V)

Stupeň vrcholu (anglicky degree of a vertex) udává, kolik hran je s daným vrcholem přímo spojeno. U orientovaných grafů se stupeň vrcholů dělí na vstupní stupeň (kolik hran vstupuje) a výstupní stupeň (kolik hran vystupuje).

Cesta v grafu

Cesta (angl. path) v grafu je posloupnost vrcholů $v_1,v_2,...,v_n$, taková, že mezi každými dvěma po sobě jdoucími vrcholy $(v_i,v_{i+1})$ existuje hrana.

• V neorientovaném grafu je důležité, že mezi vrcholy existuje spojení, bez ohledu na směr.
• V orientovaném grafu musí cesta respektovat směr hran.

Souvislost grafu

Neorientovaný graf je souvislý, pokud pro každé dva různé vrcholy $u$ a $v$ existuje cesta, která je spojuje.

U orientovaných grafů se rozlišuje:

• Silně souvislý graf – mezi každými dvěma vrcholy existuje cesta v obou směrech.
• Slabě souvislý graf – po ignorování orientace hran je graf souvislý.

Komponenta souvislosti

Komponenta souvislosti je maximální podmnožina vrcholů grafu, které jsou navzájem spojeny cestami.

A dále platí:

• V každé komponentě existuje cesta mezi libovolnými dvěma vrcholy.
• Graf může být složen z více komponent souvislosti.

Cykličnost grafu

Graf obsahuje cyklus, pokud v něm existuje cesta, která začíná a končí ve stejném vrcholu, přičemž ostatní vrcholy na cestě se neopakují.

Dle toho lze grafy dělit na:

• Acyklické grafy – neobsahují žádný cyklus.
• Cyklické grafy – obsahuje alespoň jeden cyklus.

Ohodnocený graf

Ohodnocený graf (také vážený graf) má každé hraně přiřazenu hodnotu, tzv. váhu (angl. weight).

A dále platí:

• Váha může reprezentovat např. délku, cenu, kapacitu, čas.
• Používá se při algoritmech jako je Dijkstra, Kruskal atd.
• Ohodnocení může být kladné, nulové nebo záporné

Reprezentace grafů v paměti

Grafy mohou být v paměti uloženy různými způsoby. Více informací lze nalézt na stránce Reprezentace grafů.