Ein Graph wird durch eine Knotenmenge V sowie durch eine Kantenmenge E beschrieben. Dabei soll V nicht die leere Menge sein, d.h., V≠{}. Im Allgemeinen muss nicht ein Graph eine Kante haben, bzw. muss also nicht jeder Knoten über eine Kante mit einem anderen Knoten verbunden sein.