imported>Biggerj1 am 10. April 2025 um 19:51 Uhr

2025-04-10T19:51:08Z

Neue Seite

In '''Multigraphen''' können zwei Knoten durch mehrere Kanten (bei [[gerichteter Graph|gerichteten Graphen]]: in derselben Richtung) verbunden sein, was in [[Einfacher Graph|einfachen Graphen]] nicht erlaubt ist. Außerdem dürfen Multigraphen Schleifen enthalten: Kanten, die zum selben Knoten führen, von dem sie ausgehen.<ref name="Diestel2010">{{Literatur |Autor=[[Reinhard Diestel]] |Titel=Graphentheorie |Auflage=4. |Verlag=Springer |Ort=Berlin u. a. |Datum=2010 |ISBN=978-3-642-14911-5 |Seiten=1–34 |JahrEA=1996 |Online=[https://diestel-graph-theory.com/basic.html online: 4th elektronische Ausgabe 2010]}}</ref>

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 ==
[[Datei:CPT-Graphs-directed-weighted-ex1.svg|mini|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 [[gerichteter Graph|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 ==
<references/>

[[Kategorie:Graphentheorie]]

Multigraph - Versionsgeschichte

imported>Biggerj1 am 10. April 2025 um 19:51 Uhr