grafów

Grafy to podstawowe obiekty w teorii grafów służące do modelowania zależności między obiektami. Każdy graf G składa się z zestawu wierzchołków V i zestawu krawędzi E, czyli G = (V,E). Grafy mogą быть nieskierowane lub skierowane (digrafy). W grafach nieskierowanych krawędź łączy dwa wierzchołki bez kierunku; w digrafach krawędzie mają kierunek i zapisuje się je jako pary (u,v). Grafy mogą być proste (bez pętli i wielokrawędzi między tymi samymi wierzchołkami) lub ogólne (z pętlami i wielokrawędziami).

Stopnie wierzchołków: w grafach nieskierowanych deg(v) to liczba krawędzi incydynych do v; w digrafach mamy out-degree od(v) i in-degree in(v). Suma stopni w grafie nieskierowanym równa się 2|E|. Grafy mogą być spójne lub niespójne; w grafie spójnym istnieje droga między dowolnymi dwoma wierzchołkami. Droga to sekwencja krawędzi, a ścieżka to droga bez powtórzeń wierzchołków. Cykl to ścieżka zaczynająca i kończąca się w tym samym wierzchołku. Planarne grafy da się narysować na płaszczyźnie bez skrzyżowań.

W reprezentacjach stosuje się m.in. macierz sąsiedztwa, macierz incydencji i listę sąsiedztwa. Ważne pojęcia to izomorfizm grafów (równoważne struktury można przemapować na siebie) oraz grafy dwudzielne, które można podzielić na dwa zbiory tak, aby każda krawędź łączyła wierzchołki z różnych zbiorów.

Zastosowania obejmują modele sieci komputerowych, transportu, relacji społecznych, chemii i biochemii, a także liczne algorytmy wyszukiwania najkrótszych ścieżek, planowania tras i analizy struktury.