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.
Beispiel
Die Nachbarschaftsbeziehungen zwischen Deutschland
und seinen Nachbarländern können als einfacher Graph modelliert
werden. In diesem Beispiel umfasst die Menge
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
dann ist die Knotenmenge
also durch die Menge {Belgien, Dänemark, Deutschland, Frankreich, Luxemburg,
Niederlande, Österreich, Polen, Schweiz, Tschechische Republik} gegeben.
Beispiele für Kanten in der Menge
sind {Belgien, Deutschland}, {Österreich, Schweiz} und {Deutschland, Polen}.
Dabei bezeichnen {Belgien, Deutschland} und {Deutschland, Belgien} die gleiche
Kante.
Wikipedia.de
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 10.02. 2019