Multigraph

In Multigraphen können zwei Knoten durch mehrere Kanten (bei gerichteten Graphen: in derselben Richtung) verbunden sein, was in einfachen Graphen nicht erlaubt ist. Außerdem dürfen Multigraphen Schleifen enthalten: Kanten, die zum selben Knoten führen, von dem sie ausgehen.^[1]

Anwendung kann ein Multigraph beispielsweise bei der Optimierung des Problem des Handlungsreisenden mit unterschiedlichen Zielfunktionen finden (kürzester Weg, kürzeste Zeit): dann wäre jeweils eine Kante für den Weg zwischen zwei Knoten und eine Kante für die Reisezeit zwischen zwei Knoten vorhanden.

Visualisierung

Multigraph: Mehrfachkanten werden durch eine gewichtete Kante visualisiert. Anstatt viele Kanten zu zeichnen, wird nur eine Kante gezeichnet und das Kantengewicht zeigt die Zahl der Kanten an.

Sind Knoten durch mehrere Kanten (bei gerichteten Graphen: in derselben Richtung) verbunden, wird häufig nur eine Kante gezeichnet und die Anzahl der Kanten zwischen diesen beiden Knoten als Kantengewicht an die eine Kante geschrieben. Im Beispiel gibt es 60 Kanten zwischen Knoten A und D. Anstatt alle 60 Kanten zu zeichnen, wird eine Kante mit dem Kantengewicht 60 gezeichnet.

Einzelnachweise

↑ Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 1–34 (online: 4th elektronische Ausgabe 2010 – Erstausgabe: 1996).

[Diestel2010-1] Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 1–34 (online: 4th elektronische Ausgabe 2010 – Erstausgabe: 1996).

[1]