Teoria grafów to dział
matematyki zajmujący się badaniem własności
grafów. Rozwijanie
algorytmów wyznaczających pewne właściwości grafów jest jednym z bardziej znaczących pól działania
informatyki.
Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.
Graf jest definiowany jako zbiór punktów (zwanych
wierzchołkami lub
węzłami) połączonych
krawędziami (które czasem nazywa się też
łukami).
Bardziej formalnie,
graf prosty to
zbiór wierzchołków
V i
zbiór E nieuporządkowanych par różnych elementów
zbioru V zwany
zbiorem krawędzi.
Przykład grafu o sześciu wierzchołkach oraz siedmiu krawędziach:
W tym przypadku
V = {1, 2, 3, 4, 5, 6} a
E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}.
Graf prosty o
n wierzchołkach można także opisać (z dokładnością do
izomorfizmu) za pomocą symetrycznej
macierzy kwadratowej
A =
[1], gdzie
i,j = 1,...,n, w ten sposób, że
aks = 1, gdy wierzchołki o numerach
k i
s są połączone krawędzią, w przeciwnym przypadku
aks = 0.
Dla przykładu, graf z powyższego rysunku może być przedstawiony za pomocą następującej macierzy:
\[A=\left[ \begin{matrix}
0 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0
\end{matrix}\right] \]
Pojęcia
Sąsiad: Dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi. W powyższym grafie wierzchołki
1 i
2 sąsiadują ze sobą, ale na przykład
2 i
4 już nie.
Stopień wierzchołka: Stopień wierzchołka to liczba jego sąsiadów. W powyższym grafie wierzchołki
1 i
3 mają stopień 2, wierzchołki
2,
4 i
5 mają stopień 3, zaś wierzchołek 6 ma stopień 1. Suma stopni wszystkich wierzchołków jest równa podwojonej liczbie krawędzi grafu.
Ścieżka: Ciąg wierzchołków, w którym każdy wierzchołek jest sąsiadem zarówno poprzedniego, jak i następnego. Ścieżkę uważa się za
prostą, jeśli żaden z wierzchołków ścieżki nie powtarza się. W powyższym grafie {
1,
2,
5,
1,
2,
3} jest ścieżką, a {
5,
2,
1} jest ścieżką prostą. Jeśli od każdego wierzchołka grafu istnieje ścieżka do dowolnego innego, to graf jest
spójny.
Cykl: Jest to ścieżka, która zaczyna się i kończy w tym samym wierzchołku. W powyższym grafie {
1,
5,
2,
1} jest jedynym cyklem długości 3.
Drzewo: Jest to graf spójny bez cykli. Równoważnie: drzewo o
n wierzchołkach to graf spójny o dokładnie
n - 1 krawędziach. Drzewa są używane jako
struktury danych w
informatyce.
Graf pełny: Taki graf, w którym każdy wierzchołek jest sąsiadem każdego innego. Powyższy graf nie jest pełny. Graf pełny o
n wierzchołkach oznacza się przez
Kn. Posiada on
n * (n-1) / 2 krawędzi - tyle, ile par różnych wierzchołków.
Klika: Podzbiór wierzchołków danego grafu, z których każdy jest sąsiadem każdego innego (czyli podgraf pełny).
Graf ważony: Graf ważony to graf, w którym każdej krawędzi przypisana jest pewna waga. Wag używa się na przykład w algorytmie
znajdowania optymalnej drogi.
Graf planarny: Graf, który można narysować na płaszczyźnie w taki sposób, że żadne dwie krawędzie się nie przecinają. Powyższy graf jest planarny. Graf pełny
Kn nie jest planarny dla
n > 4.
Graf eulerowski: Graf, który można narysować nie odrywając ołówka od papieru, przechodząc przy tym przez każdą
krawędź dokładnie raz. Graf jest eulerowski wtedy i tylko wtedy gdy posiada dokładnie zero lub dwa wierzchołki o nieparzystej liczbie sąsiadów oraz musi być spójny.
Graf hamiltonowski: Graf, który ma cykl przechodzący przez każdy
wierzchołek dokładnie raz. Założeniem jest spójność grafu.
Multigraf: Graf, w którym te same
wierzchołki są połączone kilkoma
krawędziami.
Graf dwudzielny: Jeżeli w zbiorze wiechołków grafu można wydzielić
dwa rozłączne podzbiory V1 i V2, tak, że
każda krawędź grafu łączy wierzchołek ze zbioru V1 z wierzchołkiem ze zbioru V2, to taki graf jest
grafem dwudzielnym.
Zagadnienia teorii grafów
- kolorowanie grafów
- problem znajdowania drogi
- problem rekonstrukcji
- zagadnienienia związane z sieciami przepływowymi, maksymalny przepływ
- dominacja
- ekstremalna teoria grafów
- liczby Ramseya
- maksymalne skojarzenie
- izomorfizm grafów
- grafy losowe
- prawdopodobieństwo spójności grafu losowego
Ważne algorytmy