Nastavení

Graf $G$ je souvislý, jestliže v něm pro každé jeho dva vrcholy $u$, $v$ existuje $u$ - $v$-cesta.

Jinak je $G$ nesouvislý.

Indukovaný podgraf $H$ grafu $G$ je souvislou komponentou, pokud

1. je souvislý

2. neexistuje žádný souvislý podgraf $F$, $F \neq H$, grafu $G$ takový, že $H \subseteq F$

(Souvislá komponenta je tedy v inkluzi maximální souvislý podgraf grafu $G$.)

Symetrizace orientovaného grafu $G = (V,E)$ je neorientovaný graf $\text{sym}(G) = (V,E')$, kde ${u,v} \in E'$ právě tehdy, když $(u,v) \in E$ nebo $(v, u) \in E$

Orientovaný graf $G = (V,E)$ nazveme slabě souvislý, pokud je souvislá jeho symetrizace $\text{sym}(G)$

Orientovaný graf $G = (V,E)$ nazveme silně souvislý, pokud pro každé dva vrhcolý $u,v \in V$ existuje v $G$ orientovaná cesta z $u$ do $v$ a současně orientovaná cesta z $v$ do $u$.

Nechť $G$ a $H$ jsou dva grafy.

Funkce $f: V(G) \to V(G)$ je izomorfismus grafů $G$ a $H$, pokud

1. $f$ je bijekce

2. $(\forall u,v \in V(G))({u,v} \in E \iff {f(u), f(v)} \in E(H))$

Dva grafy $G$ a $H$ jsou izomorfní, pokud existuje izomorfismus grafu $G$ a $H$

Tento fakt značíme $G \simeq H$

Automorfismus grafu $G$ je izomorfismus se sebou samým, tedy funkce $f : V(G) \to V(G)$ taková že,

1. $f$ je bijekce

2. $(\forall u,v \in V(G))({u,v} \in E \iff {f(u), f(v)} \in E(H))$