Ein einfacher Graph (auch schlichter Graph) ist in der Graphentheorie ein Tupel (V,E), wobei V eine endliche Menge von Knoten (auch Ecken) und E eine Menge von Kanten ist.
Die Menge E ist Teilmenge der 2-elementigen Teilmengen von V, d.h. jede Kante ist eine Menge zwei Knoten. Diese beiden Knoten werden Endknoten der Kante genannt. Man sagt auch, dass die beiden Knoten durch die Kante verbunden sind.
Die exakte Bezeichnung für einfache Graphen ist ungerichtete Graphen ohne Mehrfachkanten. Weitere Begriffe und Verallgemeinerungen werden im Artikel Graph (Graphentheorie) erklärt.
Knoten und Kanten eines Graphen können markiert, d.h. mit eindeutigen Bezeichnern versehen sein. Es gibt verschiedene Graphen bei n markierten Knoten.
Viele Probleme lassen sich mit einfachen Graphen modellieren. Wo diese nicht ausreichen, ist das Modell einfacher Graphen in der Graphentheorie erweitert worden, z.B. durch Einführung von gerichteten Kanten, Färbungen und Mehrfachkanten.
Beispiel
Nebenstehender Graph kann als eine Modellierung der Nachbarschaftsbeziehungen von Deutschland und seinen Nachbarländern verstanden werden. In diesem Beispiel steht eine Kante dafür, dass zwei Länder benachbart sind.
Man beachte, dass Position und Größe der Knoten und Kanten nicht Bestandteil des Graphen sind. Wesentlich ist seine topologische Struktur.
Wenn die Kanten zusätzlich mit Werten versehen sind (z.B. Entfernungen), spricht man von einer Gewichtung der Kanten. |
|
