Graf

Graf (ang. graph) – struktura matematyczna składająca się z wierzchołków (zwanych też nodami) oraz krawędzi łączących pary wierzchołków. Grafy są podstawowymi obiektami teorii grafowej i znajdują zastosowanie w wielu dziedzinach informatyki, fizyki, biologii oraz nauk społecznych.

Definicje

Formalnie, graf nieskierowany definiujemy jako parę uporządkowaną G = (V, E), gdzie:

V – skończony zbiór wierzchołków,
E – zbiór dwuelementowych podzbiorów V, czyli krawędzi łączących dwa (różne) wierzchołki.

Dla grafu skierowanego (digrafu) G = (V, A) zbiór A składa się z uporządkowanych par (u, v), co pozwala na rozróżnienie krawędzi wchodzącej i wychodzącej.

Rodzaje grafów

Graf nieskierowany – krawędzie nie mają określonego kierunku.
Graf skierowany – każda krawędź posiada początek i koniec.
Graf cykliczny – zawiera co najmniej jeden cykl.
Graf acykliczny – nie zawiera cykli (np. drzewo).
Graf planarny – można go narysować w płaszczyźnie tak, aby krawędzie nie przecinały się (twierdzenie Kuratowskiego).
Graf spójny – istnieje ścieżka pomiędzy dowolną parą wierzchołków.
Graf ważony – każdej krawędzi przypisano wagę (np. odległość, koszt).
Graf dwudzielny – wierzchołki można podzielić na dwie klasy tak, że każda krawędź łączy wierzchołki z różnych klas.

Własności i pojęcia pomocnicze

W teorii grafowej wprowadzono szereg pojęć opisujących strukturę i zachowanie grafu:

Stopień wierzchołka – liczba krawędzi incydentnych z danym wierzchołkiem.
Ścieżka – ciąg kolejnych krawędzi łączących wierzchołki, w którym żaden wierzchołek nie powtarza się (w grafie prostym).
Cykle – zamknięte ścieżki, w których początkowy i końcowy wierzchołek jest ten sam.
Składowa spójna – maksymalny podzbiór wierzchołków, w którym każda para jest połączona ścieżką.
Krótkie ścieżki – najkrótsze (np. pod względem sumy wag) połączenia między dwoma wierzchołkami; typowe algorytmy to algorytm Dijkstry i algorytm Bellmana‑Ford.
Kolorowanie grafów – przydzielanie kolorów wierzchołkom lub krawędziom tak, aby niepowtarzające się elementy nie miały tego samego koloru (twierdzenie czterech kolorów).

Algorytmy pracujące na grafach

Grafy są podstawą wielu algorytmów wykorzystywanych w informatyce:

Breadth‑First Search (BFS) – przeszukiwanie wszerz, służące m.in. do wyznaczania najkrótszych ścieżek w grafach niewagowych.
Depth‑First Search (DFS) – przeszukiwanie w głąb, wykorzystywane do znajdowania komponentów spójnych, mostów i punktów artykulacji.
Algorytm Kruskala oraz algorytm Prima – konstrukcja minimalnego drzewa rozpinającego (MST).
Algorytm Floyda‑Warshalla – wyznaczanie najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków.
Algorytm Tarjana – znajdowanie silnie spójnych składowych w grafach skierowanych.
Algorytm Kahn’a – topologiczne sortowanie skierowanego grafu acyklicznego (DAG).

Zastosowania

Grafy pojawiają się w praktycznie każdej dziedzinie techniki i nauki:

Sieci komputerowe – modelowanie połączeń między urządzeniami; algorytmy trasowania (np. Dijkstra) określają najefektywniejsze trasy.
Systemy transportowe – planowanie dróg, linii kolejowych, tras lotniczych; optymalizacja pod kątem czasu lub kosztu.
Biologia – analiza sieci białkowych, drzew filogenetycznych, interakcji genów.
Sztuczna inteligencja – grafy wiedzy, sieci semantyczne, rozwiązania problemów kombinatorycznych (np. problem komiwojażera).
Systemy rekomendacyjne – modelowanie relacji użytkownik‑produkt jako graf bipartytowy.
Geografia – mapowanie dróg i szlaków, analizy przepływu ludzi i towarów.

Historia

Początki teorii grafów sięgają drugiej połowy XIX wieku, kiedy Leonhard Euler rozwiązał problem słynnych siedmiu mostów Konigsbergu (problem Eulera), wprowadzając pojęcie stopnia wierzchołka i ścieżki.

Później, w latach 30. i 40. XX wieku, prace Oystein Russell i Kurt Gödel przyczyniły się do rozwoju metod kombinatorycznych, a w latach 50. i 60. powstały podwaliny współczesnej algorytmiki. W kolejnych dekadach, wraz z rozwojem komputerów, grafy stały się nieodzownym narzędziem w informatyce i inżynierii.

Powiązane pojęcia

Więcej informacji można znaleźć w następujących artykułach: