Ein Graph (V, E) besteht aus einer Menge V von Knoten (Vertices), die verbunden sein können durch eine Menge E von gerichteten oder ungerichteten Kanten (Edges). Entsprechend spricht man von gerichteten und ungerichteten Graphen. Die Kanten kann man als geordnete bzw. ungeordnete Paare von Knoten auffassen; die Kanten in einem gerichteten Graphen nennt man oft auch Pfeile.
Eine Folge von aneinanderstoßenden Kanten, bzw. von Pfeilen mit gleicher Richtung, nennt man einen Weg oder Pfad. Ein geschlossener Weg heißt ein Kreis oder ein Zyklus. Ein Kreis der Länge 1 heißt Schlinge.
Je nach der Anwendung sind ungerichtete oder gerichtete Graphen zur Modellierung zweckmäßiger; dazwischen überzugehen ist einfach. Zu jedem gerichteten Graphen gibt es einen zugeordneten ungerichteten Graphen, den man bekommt, indem man die Richtung der Pfeile ignoriert; dabei verliert man natürlich Information. Umgekehrt kann man einen ungerichteten Graphen durch einen gerichteten Graphen darstellen: man ersetzt jede Schlinge durch einen geschlossenen Pfeil, und jede Kante, die keine Schlinge ist, durch ein Paar einander entgegengerichteter Pfeile.
Ein ungerichteter Graph, in dem es von jedem Knoten zu jedem anderen Knoten einen Weg gibt, heißt zusammenhängend. Allgemein gibt es zu jedem Knoten seine Zusammenhangskomponente: den größten zusammenhängenden Teilgraphen, in dem er liegt, also die Menge der Knoten, die von ihm aus durch Wege erreichbar sind. Wenn es zwischen je zwei Knoten je nur maximal einen Weg gibt, heißt der Graph einfach zusammenhängend.
Zur technischen Darstellung von Graphen gibt es mehrere Möglichkeiten: