Abychom mohli s grafy pracovat a jednoduše popsat, co s grafem děláme, potřebujeme znát základní grafové pojmy.

  • Izomorfismus: Izomorfismus není nic jiného něž přejmenování vrcholů. Graf $G$ je izomorfní s grafem $H$ právě tehdy když existuje bijekce $f:V(G)\to V(H)$ taková, že $xy\in E(G) \Longleftrightarrow f(x)f(y) \in E(H)$.

    Jsou výše nakreslené grafy izomorfní? Najděte bijekci.

  • Doplněk grafu: Doplněk grafu $G$ (značíme $\overline{G}$) je graf $(V(G), \overline{E})$, kde $\overline{E}= {V(G) \choose 2} \setminus E(G) = \{ \,xy\, |\, xy\not\in E(G)\,\}$. Jinými slovy, hranami doplňku $G$ jsou “nehrany” grafu $G$.

  • Stupeň vrcholu: Stupeň vrcholu $v$ v grafu $G$ je počet jeho sousedů: $$\deg_G v:= |\{ vx\in E(G) \,:\, \mbox{pro}\,\forall\, x\in V\}|.$$
  • Podgraf grafu: $H$ je podgraf grafu $G$ (značíme $H\subseteq G$) právě tehdy když $H$ je graf a $V(H)\subseteq V(G)$, $E(H)\subseteq E(G)$. Jinými slovy, podgraf $H$ vznikne z grafu $G$ vymazáním některých hran a některých vrcholů včetně hran z nich vedoucích. Obráceně bychom mohli říci, že $G$ je nadgraf grafu $H$. Místo “$H$ je podgraf $G$” někdy říkáme, že graf $G$ obsahuje $H$.
  • Indukovaný podgraf: $H:=G[W]$ je podgraf grafu $G$ indukovaný množinou $W\subseteq V$ právě tehdy když $V(H)=W\subseteq V(G)$ a $E(H)\subseteq E(G) \cap {W \choose 2}$. Jinými slovy, graf $G[W]$ vznikne z $G$ vymazáním vrcholů $V\setminus W$ včetně hran z nich vedoucích. Pokud nechceme množinu $W$ vysloveně uvádět, tak řekneme, že $H$ je indukovaný podgraf grafu $G$ (indukovaný nějakou množinou, která se stane $V(H)$).

    Na obrázku je graf $G$, jeho indukovaný podgraf $H_1=G[\{A,B,C\}]$ a podgraf $H_2 \subseteq G$, který není indukovaným podgrafem.

  • Jednoduché operace na grafu $G=(V,E)$:
    1. přidání hrany: $G+e := (V, E\cup \{ e\})$
    2. smazání hrany: $G-e := (V, E\setminus \{ e\})$
    3. smazání vrcholu: $G-v := (V\setminus \{v\}, E\setminus \{ vw \in E\,:\,\mbox{pro}\,\forall\,w\in V \})$
  • Hranově maximální graf: Graf $G$ je hranově maximální pro nějakou grafovou vlastnost $A$, pokud $G$ splňuje vlastnost $A$ a žádný z grafů $G+xy$, $xy\not\in E(G)$, už ji nesplňuje.

    Příkladem grafové vlastnosti je “graf obsahuje nejvýše $5$ hran”. Složitější vlastnosti naleznete v následující sekci s grafovou botanickou.

  • Maximální/minimální graf: Graf $G$ je maximální/minimální pro nějakou grafovou vlastnost $A$, pokud $G$ splňuje vlastnost $A$ a žádný nadgraf/podgraf už ji nesplňuje.

    V algoritmech často hledáme maximální/minimální graf s určitou vlastností. Jak ale grafy porovnáváme? Který je menší a který větší? Za uspořádání na grafech bereme relaci býti podgrafem. Relace býti podgrafem je relace částečného uspořádání.1 Podívejme se příklad na obrázku. Napravo máme $6$ podgrafů grafu $G$, který je nalevo (velký graf).



    Pro grafy $G$, $H_1$, $H_2$ platí $H_2 \subseteq H_1 \subseteq G$. Podobně $H_5 \subseteq H_4 \subseteq H_3$. To určuje uspořádání na podgrafech. Ne každé dva podgrafy jsou porovnatelné, například $H_2$ a $H_5$ (ani jeden není podgrafem druhého).

    Pozor, je potřeba rozlišovat dva pojmy — maximální a největší.2 Prvek je maximální, právě tehdy když neexistuje žádný větší. Prvek je největší, právě tehdy když je větší než všechny ostatní. Podobně pro minimální a nejmenší prvek.

    Na obrázku je $G$ největším podgrafem, protože obsahuje všechny ostatní jako podgraf. Podgrafy $H_2$ a $H_5$ jsou minimálními neprázdnými podgrafy, ale ani jeden z nich není nejmenší neprázdný podgraf. Nejmenším podgrafem je prázdný podgraf, který obsahuje všechny vrcholy, ale ani $1$ hranu.

    Jako základní učebnici teorie grafů můžeme doporučit Matouška, Nešetřila: Kapitoly z diskrétní matematiky [MatNes96]. Pro pokročilejší teorii anglickou učebnici Diestel: Graph Theory [Diestel05].