Przykłady grafów o ciekawych własnościach

Grafy puste składają się jedynie z wierzchołków, nie zawierają źadnych krawędzi.
Graf pusty o $n$ wierzchołkach oznaczamy $N_n$.

Grafy puste mają następujące własności:
$\delta(N_n)$ $= 0$,
$\Delta(N_n)$ $= 0$,
$\kappa(N_n)$ $= 0$,
$\kappa'(N_n)$ $= 0$,
$\chi(N_n)$ $= 1$,
$\chi'(N_n)$ $= 0$,
Cykl Hamiltona: nie posiadają.
Cykl Eulera: nie posiadają.
Są planarne.

Spróbuj zastanowić się, dlaczego tak jest.

Grafy pełne to grafy, w których każde dwa wierzchołki są połączone krawędzią. Graf pełny o $n$ wierzchołkach oznaczamy $K_n$.
$K_1$

Grafy pełne o $n$ wierzchołkach mają następujące własności:
Mają \( n(n-1)2 \) krawędzi.
$\delta(K_n)$ $= n - 1$,
$\Delta(K_n)$ $= n - 1$,
$\kappa(K_n)$ $= n - 1$,
$\kappa'(K_n)$ $= n - 1$,
$\chi(K_n)$ $= n$,
$\chi'(K_n)$ $=$
dla n nieparz. n>1
dla n parzystych

Cykl Hamiltona: posiadają.
Cykl Eulera: posiadają jeśli $n$ jest nieparzyste.
Są planarne tylko dla $n \leq 4$.
Spróbuj zastanowić się, dlaczego tak jest.

Grafy pełne dwudzielne to grafy dwudzielne, które zawierają wszystkie możliwe krawędzie przy zadanym podziale zbioru wierzchołków.
Graf pełny dwudzielny, którego wierzchołki podzielone są na zbiór $m$ elementowy i $n$ elementowy oznaczamy $K_{m,n}$.

$K_{1,3}$
$K_{3,3}$
$K_{4,4}$
$K_{4,5}$

Grafy pełne dwudzielne o $K_{m,n}$ mają następujące własności:
Mają $nm$ krawędzi.
$\delta(K_{m,n})$ $= min\{m,n\}$,
$\Delta(K_{m,n})$ $= max\{m,n\}$,
$\kappa(K_{m,n})$ $= min\{m,n\}$,
$\kappa'(K_{m,n})$ $= min\{m,n\}$,
$\chi(K_{m,n})$ $= 2$,
$\chi'(K_{m,n})$ $= max\{m,n\}$,
Cykl Hamiltona: posiadają jeśli $m = n$.
Cykl Eulera: posiadają jeśli $m$ i $n$ są parzyste.
Są planarne tylko dla dla $min\{m,n\} \leq 2$.
Spróbuj zastanowić się, dlaczego tak jest.


W 1930 roku polski matematyk Kazimierz Kuratowski udowodnił, że najmniejsze grafy nieplanarne to $K_5$ i $K_{3,3}$, oraz że grafy nieplanarne to tylko te, które w pewien sposób zawierają któryś z tych dwóch grafów.

Litera "K" w oznaczeniu grafów pełnych pochodzi właśnie od jego nazwiska, a grafy $K_5$ i $K_{3,3}$ często nazywa się grafami Kuratowskiego

Koła to grafy powstałe przez dodanie do cyklu jeszcze jednego wierzchołka i połączenie tego wierzchołka ze wszystkimi wierzchołkami cyklu.
Koło o $n$ wierzchołkach oznaczamy $W_n$.


Koła o $n$ wierzchołkach mają następujące własności:
Istnieją dla $n \geq 4$.
Mają $2(n-1)$ krawędzi.
$\delta(W_n)$ $= 3$,
$\Delta(W_n)$ $= n - 1$,
$\kappa(W_n)$ $= 3$,
$\kappa'(W_n)$ $= 3$,
$\chi(W_n)$ $=$
dla n nieparz.
dla n parzystych

$\chi'(W_n)$ $= n - 1$,
Cykl Hamiltona: posiadają.
Cykl Eulera: nie posiadają.
Są planarne.

Spróbuj zastanowić się, dlaczego tak jest.

Drzewa to grafy spójne nie zawierające żadnego cyklu.
Istnieje wiele różnych (nieizomorficznych) drzew o tej samej liczbie wierzchołków. Oto przykłady drzew o $n$ wierzchołkach.

$n = 4$
$n = 8$
$n = 25$

Drzewa $G$ o $n$ wierzchołkach mają następujące własności:
Mają $n-1$ krawędzi.
$\delta(G)$ $= 1$,
$\kappa(G)$ $= 1$,
$\kappa'(G)$ $= 1$,
$\chi(G)$ $= 2$,
$\chi'(G)$ $= \Delta(G)$,
Cykl Hamiltona: nie posiadają.
Cykl Eulera: nie posiadają.
Są planarne.

Spróbuj zastanowić się, dlaczego tak jest.



Graf, którego każda składowa jest drzewem nazywamy lasem. Oto przykład lasu:

Grafy platońskie to grafy utworzone z krawędzi i wierzchołków wielościanów foremnych.

czworościan: sześcian:
ośmiościan:
dwunastościan:
dwudziestościan:

O wielościanach foremnych wspomina też wykład z Algebry. A miniprogram pozwala na bliższe zaznajomienie się z nimi.

Wszystkie grafy platońskie są regularne i planarne.

Łatwo można się przekonać, że grafy platońskie spełniają formułę Eulera, którą możemy zapisać:

\begin{displaymath}n-eąf=2\end{displaymath}

gdzie $n$ oznacza liczbę wierzchołków grafu, $e$ liczbę krawędzi, a $f$ liczbę obszarów grafu. Przez obszary rozumiemy obszary spójne, na które dzielą płaszczyznę krawędzie grafu narysowanego na tej płaszczyżnie. (Dla bryły będą to po prostu jej ściany). Należy pamiętać przy tym, żeby policzyć też "obszar nieskończony", czyli "zewnętrze" grafu.

Formułę Eulera spełniają wszystkie grafy planarne narysowane w ten sposób, że ich krawędzie nie przecinają się.

Graf Petersena:

Graf Petersena jest 3-regularny.
$\delta(G)$ $= 3$,
$\Delta(G)$ $= 3$,
$\kappa(G)$ $= 3$,
$\kappa'(G)$ $= 3$,
$\chi(G)$ $= 3$,
$\chi'(G)$ $= 4$,
Cykl Hamiltona: nie posiada.
Cykl Eulera: nie posiada.
Nie jest planarny.

Spróbuj zastanowić się, dlaczego tak jest.

Graf Grötzscha:

Graf Grötzscha ma następujące własności:
$\delta(G)$ $= 3$,
$\Delta(G)$ $= 5$,
$\kappa(G)$ $= 3$,
$\kappa'(G)$ $= 3$,
$\chi(G)$ $= 4$,
$\chi'(G)$ $= 5$,
Cykl Hamiltona: posiada.
Cykl Eulera: nie posiada.
Nie jest planarny.

Spróbuj zastanowić się, dlaczego tak jest.


[ Początek strony ] [ MiNIWykłady ]

Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej