Grafy, které splňují určitou vlastnost, mají svůj název. Mezi základní “druhy” grafů patří:

  • Úplné grafy:1 Úplný graf obsahuje všechny možné hrany: $K_n = ([n], {[n]\choose 2} )$, kde $[n]=\{1,2,\dots, n\}$.
  • Cesty: Cesta je neprázdný graf $P=(V,E)$, kde $V=\{x_0, x_1, \dots, x_k\}$ a $E=\{ x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k \}$. Vrcholům $x_0$ a $x_k$ říkáme koncové vrcholy cesty. Ostatní vrcholy jsou vnitřní. Délka cesty je počet hran na cestě.
  • Kružnice: Kružnice je neprázdný graf $P=(V,E)$, kde $V=\{x_0, x_1, \dots, x_k\}$ a $E=\{ x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k \} \cup \{x_kx_0\}$. Délka kružnice je její počet hran.

Podgrafy grafu $G$, které jsou izomorfní výše uvedeným druhům, často bereme jakou součást grafu. Například cesta v grafu je podgraf izomorfní cestě.

  • Cesta v grafu: Cesta v grafu $G$ je podgraf grafu $G$, který je izomorfní cestě. Někdy za cestu $P$ v $G$ bereme posloupnost vrcholů $(x_0, x_1, \dots, x_k)$ takovou, že $x_{i-1}x_i\in E(G)$ pro $i\in\{1,2,\dots, k\}$. Říkáme, že cesta $P$ vede mezi vrcholy $x_0$ a $x_k$. Proto ji někdy značíme jako $x_0Px_k$. Díky tomu můžeme jednoduše označovat “podcesty” (pro $0\leq i \leq j \leq k$): [eqnarray] \nonumber Px_i &:= (x_0 \dots x_i) \\ \nonumber x_iP &:= (x_i \dots x_k) \\ \nonumber x_iPx_j &:= (x_i \dots x_j) [/eqnarray] ale i některé operace, například zřetězení úseků $xPy$ a $yQz$ je cesta $xPyQz$.
  • Kružnice v grafu: Kružnice v grafu $G$ je podgraf grafu $G$, který je izomorfní kružnici. Někdy za kružnici $C$ v $G$ bereme posloupnost vrcholů $(x_0, x_1, \dots, x_k)$ takovou, že $x_{i-1}x_i\in E(G)$ pro $i\in\{1,2,\dots, k\}$ a $x_0x_k\in E(G)$.
  • Hamiltonovské kružnice: Kružnice je hamiltovnoská právě tehdy když obsahuje všech $n$ vrcholů grafu.
  • Souvislost grafu: Graf $G$ je souvislý, pokud mezi každou dvojicí vrcholů $x,y\in V$ existuje cesta.
  • Klika v grafu: Klika v grafu $G$ je indukovaný podgraf grafu $G$, který je izomorfní úplnému grafu. Někdy za kliku bereme pouze podmnožinu vrcholů $Q\subseteq V(G)$ takovou, že každé dva vrcholy $x,y\in Q$ jsou spojeny hranou $xy\in E(G)$.
  • Nezávislá množina v grafu: Vrcholy grafu $G$, mezi kterými nevede žádná hrana, se nazývají nezávislé. Nezávislá množina $W\subseteq V(G)$ v grafu $G$ je množina navzájem nezávislých vrcholů. Podgraf $G$ indukovaný nezávislou množinou je doplňkem úplného grafu.
  • Stromy: Strom $T$ je souvislý graf bez kružnic. Pokud zakážeme pouze kružnice, ale nevyžadujeme souvislost, tak dostaneme graf skládající se z několika stromů. Takovému grafu se říká les. Vrcholy stromu stupně $1$ se nazývají listy.

    O stromech koluje i několik grafových vtipů: Víte, proč pařez není strom? Protože obsahuje kružnice.2 A víte, že souvislý les je strom?

  • Kostry: Kostra grafu $G$ je strom $T\subseteq G$ na všech $n$ vrcholech.
  • Bipartitní graf: Graf $G=(V,E)$ je bipartitní, právě tehdy když můžeme jeho vrcholy rozdělit do dvou množin $V_1$ a $V_2$ tak, že každá hrana vede mezi $V_1$ a $V_2$. $V=V_1 \cup V_2$. Množinám $V_1$ a $V_2$ se říká partity grafu.
Příklad: V následujícím grafu je cesta $(B, C, D, E, H, F)$ vyznačena tučně. Dále graf obsahuje kružnici $(D, E, F, G, H, I)$, ale i kružnici $(E, I, F, H)$. Klika $\{ E, F, H, I \}$ je vyznačena šedě a nezávislá množina $\{ A, C, E, G\}$ má vrcholy označeny bíle.

Rozmyslete si, jestli je vyznačená klika i nezávislá množina maximální. Také si rozmyslete, jak vypadá minimální souvislý podgraf tohoto grafu.