Graf Jedną z definicji grafu jest: graf (nieskierowany) składa się z dwóch zbiorów: oraz przy czym jest niepustym zbiorem, którego elementy nazywane są wierzchołkami, a jest rodziną dwuelementowych podzbiorów zbioru wierzchołków zwanych krawędziami: Definicja ta nie wymaga, by i były skończone. W praktyce rozważa się także grafy o nieskończonej liczbie wierzchołków – wtedy liczba krawędzi może być zarówno skończona, jak i nieskończona.
Graf skierowany
Graf skierowany lub inaczej digraf składa się z dwóch zbiorów – niepustego zbioru wierzchołków oraz rodziny par uporządkowanych elementów zbioru zwanych krawędziami lub łukami grafu skierowanego. Kolejność wierzchołków w parze wyznacza kierunek krawędzi – w przypadku pary łuk biegnie z wierzchołka do wierzchołka . Podobnie, jak w przypadku grafu nieskierowanego, definicja ta ma sens zarówno wtedy, gdy zbiory lub są skończone, jak i nieskończone.
Graf mieszany
Graf mieszany to uporządkowana trójka grafu gdzie zbiory są zdefiniowane jak wyżej, czyli zawiera jednocześnie krawędzie skierowane i nieskierowane.