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