einfacher Graph

Ein einfacher Graph (auch schlichter Graph) ist in der Graphentheorie ein ungerichteter Graph ohne Mehrfachkanten und ohne Schleifen. Ein einfacher Graph ist also ein geordnetes Paar , wobei eine endliche Menge von Knoten und eine Menge von Kanten ist. Die Menge ist dabei Teilmenge der 2-elementigen Teilmengen von , das heißt, jede Kante ist eine Menge von zwei Knoten. Ein einfacher Graph mit Knoten kann demzufolge maximal Kanten haben. Sind alle diese Kanten vorhanden, wird der Graph als vollständiger Graph bezeichnet. Wenn die Kanten des Graphen zusätzlich mit Werten versehen sind (z. B. Entfernungen), spricht man von einer Gewichtung (auch Bewertung) der Kanten und dann von einem kantengewichteten Graphen.