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 ${\displaystyle (V,E)}$, wobei ${\displaystyle V}$ eine Menge von Knoten und ${\displaystyle E}$ eine Menge von Kanten ist. Die Menge ${\displaystyle E}$ ist dabei eine Menge von 2-elementigen Teilmengen von ${\displaystyle V}$.

Ein einfacher Graph mit ${\displaystyle n}$ Knoten kann demzufolge maximal ${\displaystyle \textstyle {n \choose 2}={\frac {n(n-1)}{2}}}$ Kanten haben. Sind alle diese Kanten vorhanden, wird der Graph als vollständiger Graph ${\displaystyle K_{n}}$ 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.