Nastavení

Neorientovaný graf je uspořádaná dvojice $(V, E)$ kde

• $V$ je neprázdná konečná množina vrcholů,

• $E$ je množina hran,

Hrana je dvouprvková podmnožina $V$ (čili neuspořádaná dvojice vrcholů), značíme $\{u,v\}$

Orientovaný graf je uspořádaná dvojice $(V, E)$ kde

• $V$ je neprázdná konečná množina vrcholů,

• $E$ je množina orientovaných hran (zobrazujeme jako šipky),

Orientovaná hrana $(u, v)$ je uspořádaná dvojice vrcholů $u,v \in V$, kde $u$ nazýváme předchůdcem $v$ a $v$ nazýváme následníkem $u$

Orientovaná hranu $(u,u)$ nazýváme smyčkou.

Množinu všech hran (všech dvouprvkových podmnožin množiny $V$) budeme označovat $V \choose 2$

Doplněk grafu $G = (V,E)$ je graf $\bar G = (V, { V \choose 2 } \setminus E)$

Nechť $G$ je graf. Pak

• $V(G)$ je množina jeho vrcholů (verticies). Počet vrcholů značíme $n = |V(G)|$

• $E(G)$ je množina jeho hran (edges). Počet vrcholů značíme $m = |E(G)|$

Nechť $e = \{u,v\}$ je hrana v grafu $G$. Pak řekneme, že

• vrcholu $u$ a $v$ jsou koncové vrcholy hrany $e$

• $u$ je sousedem $v$ v $G$ (a naopak)

• $u$ i $v$ jsou incidentní s hranou $e$

Graf $H$ je podgrafem grafu $G$ právě tehdy když $V(H) \subseteq V(G)$ a $E(H) \subseteq E(G)$

Graf $H$ je indukovaným podgrafem grafu $G$ právě tehdy když $V(H) \subseteq V(G)$ a $E(H) = E(G) \cap {V(H) \choose 2}$

Je-li $G=(V,E)$ a $V' \subseteq V$, pak $G[V']$ označuje graf $(V', E(G) \cap {V' \choose 2})$ a říkáme mu podgraf indukovaný množinou vrcholů $V'$

Úplný graf na $n \ge 1$ vrcholech je graf $K_n = (V, { V \choose 2 })$

Tedy mezi každými dvěma vrcholy vede hrana.

Úplný bipartitní graf tvořený dvěma partitiami o $n_1$ a $n_2$ vrcholech je graf $K_{n_1, n_2} = (A \cup B, \{\{a,b\}\mid a \in A, b \in B\})$

Kde $A \cap B = \emptyset$, $|A| = n_1 \ge 1$, $|B| = n_2 \ge 1$

Bipartitní graf je podgraf úplného bipartitního grafu

Klika v grafu $G$ je podmožina vrcholů, z nichž každé dva jsou sousední (čili spojeny hranou)