Einfacher Graph

Ein einfacher Graph (auch schlichter Graph) i​st in d​er Graphentheorie e​in ungerichteter Graph o​hne Mehrfachkanten u​nd ohne Schleifen.

Ein einfacher Graph ist also ein geordnetes Paar ${\displaystyle (V,E)}$, wobei ${\displaystyle V}$ eine endliche Menge von Knoten und ${\displaystyle E}$ eine Menge von Kanten ist. Die Menge ${\displaystyle E}$ ist dabei Teilmenge der 2-elementigen Teilmengen von ${\displaystyle V}$, das heißt, jede Kante ist eine Menge von zwei Knoten.

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 d​ie Kanten d​es Graphen zusätzlich m​it Werten versehen s​ind (z. B. Entfernungen), spricht m​an von e​iner Gewichtung (auch Bewertung) d​er Kanten u​nd dann v​on einem kantengewichteten Graphen.

Beispiel

Beispielgraph: Deutschland und Nachbarländer

Die Nachbarschaftsbeziehungen zwischen Deutschland und seinen Nachbarländern können als einfacher Graph modelliert werden. In diesem Beispiel umfasst die Menge ${\displaystyle V}$ die Länder und jede Kante steht dafür, dass zwei Länder benachbart sind. In der nebenstehenden Abbildung wird dieser Graph dargestellt, wobei die Knoten als Punkte und die Kanten als Verbindungslinien gezeichnet sind. Man beachte, dass der Graph nur die bestehenden Beziehungen umfasst, dagegen sind Position und Größe der Knoten und Kanten frei gewählt.

Betrachtet man die formale Definition des Graphen als Paar ${\displaystyle (V,E)}$ dann ist die Knotenmenge ${\displaystyle V}$ also durch die Menge {Belgien, Dänemark, Deutschland, Frankreich, Luxemburg, Niederlande, Österreich, Polen, Schweiz, Tschechische Republik} gegeben. Beispiele für Kanten in der Menge ${\displaystyle E}$ sind {Belgien, Deutschland}, {Österreich, Schweiz} und {Deutschland, Polen}. Dabei bezeichnen {Belgien, Deutschland} und {Deutschland, Belgien} die gleiche Kante.

Literatur

• Dieter Jungnickel: Graphen, Netzwerke und Algorithmen. 3. Auflage. BI Wissenschaftsverlag, 1994, ISBN 3-411-14263-4.

• Eric W. Weisstein: Simple Graph. In: MathWorld (englisch).