Graf

Schematyczny rysunek przedstawiający pewne zależności, w postaci układu wierzchołków tak połączonych liniami lub strzałkami, że każda linia lub strzałka kończy się i zaczyna w którymś z wierzchołków (Wielki słownik języka polskiego).

Mat. obiekt G = (V, E), składający się z niepustego zbioru wierzchołków V oraz zbioru połączeń między nimi (krawędzi) E, będącego zbiorem 2-elementowych podzbiorów V.
Graf można przedstawić graficznie przyporządkowując wierzchołkom punkty i łącząc je liniami odpowiadającymi krawędziom; każdy graf skończony (o skończonej liczbie wierzchołków i krawędzi) można przedstawić w przestrzeni trójwymiarowej w taki sposób, że linie odpowiadające krawędziom nie przecinają się w punktach wewnętrznych. Do najważniejszych pojęć związanych z grafem należą: podgraf — niepusty podzbiór V1 zbioru V i podzbiór E1 zbioru E, taki że jeśli (x, y) ∈ E1, to x, y ∈ V1; droga — ciąg wierzchołków, z których każde 2 kolejne są połączone krawędzią; cykl — droga zaczynająca i kończąca się w tym samym wierzchołku; odległość d(x, y) między wierzchołkami x, y — długość najkrótszej drogi o początku x i końcu y (d(x, y) = ∞, jeśli nie ma żadnej takiej drogi).