Definition
Ein Graph G ist ein Tupel (V, E), wobei V eine Menge von Knoten (oft auch Ecken genannt) und E eine Menge von Kanten bezeichnet. Dabei ist E eine Teilmenge aller 2-elementigen Teilmengen von V.
Einordnung
So definierte Graphen nennt man auch oft schlicht oder einfach, da sie die simpelste Art von Graphen darstellen. Zur Unterscheidung von gerichteten Graphen verwendet man auch oft die Bezeichnung ungerichteter Graph.
Weitere generalisierte Formen von Graphen sind Multigraphen und Hypergraphen.
In der Regel betrachtet man nur endliche Graphen, bei denen die Menge der Knoten endlich ist. Zwangsläufig ist dann auch die Menge der Kanten endlich. Graphen mit unendlich vielen Knoten bezeichnet man als unendliche Graphen. Normalerweise läßt man das Attribut "endlich" weg und kennzeichnet nur unendliche Graphen explizit.
Anschauung
Anschaulich ist ein Graph eine Menge von Punkten, die den Knoten entsprechen, welche durch Linien miteinander verbunden sind, die den Kanten entsprechen. Dabei können im Unterschied zu Multigraphen zwei Punkte nur durch maximal eine Linie verbunden sein.
Beispiel
Folgendes Bild zeigt einen Graphen.
Formal schreibt sich dieser wie folgt:
G = ({1,2,3,4,5,6,...???},{???})