Informatyka MIMUW

Graf pusty to graf bez krawędzi. Antyklika lub graf niezależny to inne nazwy grafu pustego. Antyklikę o $n$ wierzchołkach oznaczać będziemy przez $\mathcal{A}_{n}$.

Graf pełny to graf, w którym każde dwa wierzchołki połączone są krawędzią. Graf pełny nazywany jest także kliką i oznaczany przez $\mathcal{K}_{n}$, gdzie $n$ jest liczbą jego wierzchołków.

Uwaga

Liczba krawędzi w klice $\mathcal{K}_{n}$ wynosi $\frac{n(n-1)}{2}$.

Graf dwudzielny to graf $\mathbf{G}=( V,E )$, w którym zbiór $V$ da się podzielić na dwa rozłączne podzbiory $V_1$ oraz $V_2$ tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru $V_i$ nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez $( V_1\cup V_2,E )$. Zauważmy jednak, że podział taki nie jest jednoznaczny -- np. w antyklice $\mathcal{A}_{n}$ dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Pełny graf dwudzielny to graf dwudzielny $\mathbf{G}=( V_1\cup V_2,E )$, w którym każdy wierzchołek z $V_1$ jest połączony z każdym wierzchołkiem z $V_2$. Pełny graf dwudzielny oznaczać będziemy przez $\mathcal{K}_{r,s}$, gdzie $r$ jest rozmiarem $V_1$, a $s$ rozmiarem $V_2$.

Graf płaski to para $\mathbf{\overline{G}}=( \overline{V},\overline{E} )$, gdzie:

• $\overline{V}$ jest jakimś zbiorem punktów płaszczyzny $\mathbb{R}^2$,

• $\overline{E}$ jest zbiorem nie przecinających się odcinków lub łuków w $R^2$ o końcach ze zbiorze $\overline{V}$.

Graf planarny to graf, który jest prezentowalny jako graf płaski.