Einfacher Graph
Ein einfacher Graph (auch schlichter Graph) ist in der Graphentheorie ein Tupel (V,E), wobei V eine endliche Menge von Knoten 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.
Die exakte Bezeichnung für einfache Graphen ist ungerichtete Graphen ohne Mehrfachkanten. Weitere Begriffe und Verallgemeinerungen werden im Artikel Typen von Graphen in der Graphentheorie erklärt.
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. |
|
