Der allgemeine Begriff eines Graphen

 Anschaulich ist ein mathematischer Graph eine Menge von Punkten zusammen mit gewissen Linien oder Pfeilen, die zwei Punkte miteinander verbinden. Die Punkte nennen wir auch Ecken oder Knoten, die Verbindungslinien Kanten. Die Verbindungslinien oder Pfeile können gerade oder auch gebogen sein, sich schneiden und auch von einer Ecke zu sich selbst führen (sog. Schlingen). Weiter können wir Kantengewichte betrachten und jede Kante mit einer Zahl − ihrem Gewicht − versehen. Schließlich sind auch mehrfache Kanten denkbar, die zwei Punkte auf verschiedene Arten und mit verschiedenen Gewichten miteinander verbinden.

Der dargestellte Graph hat fünf Ecken, die mit den Zahlen 1, 2, 3, 4, 5 durchgezählt sind (die Namen der Ecken sind prinzipiell beliebig). Einige Eckenpaare sind durch gerichtete Kanten (Pfeile) miteinander verbunden, etwa die Paare

(4, 1), (5, 3), (4, 4)vorhandene Kanten

Andere Paare sind nicht miteinander verbunden, etwa

(1, 4), (1, 3), (3, 3)fehlende Kanten

Insgesamt besitzt der Graph neun Kanten. Eine Besonderheit sind die Ecken 1, 2, die in beiden Richtungen verbunden sind, sowie die Ecke 4, die durch eine Schlinge mit sich selbst verbunden ist.

 Alle Kanten sind mit Gewichten versehen. So hat die Kante (2, 3) das Gewicht 3, was wir mit w(2, 3) = 3 zum Ausdruck bringen (mit „w“ für „weight“). Analog ist w(1, 2) =1, w(2, 1) = 2 und w (4, 4) = 9. In Modellierungen kann ein „Gewicht“ zum Beispiel eine Länge oder Zeiteinheit bezeichnen.