Mehrfachgraphen

Mehrfachgraphen sind eine Verallgemeinerung der Graphentheorie, bei der zwischen zwei Scheitelpunkten mehr als eine Kante existieren kann. In einem ungerichteten Mehrfachgraph G=(V,E) besteht V aus einer endlichen Menge von Scheitelpunkten und E aus einer Multimenge von Kanten, wobei jede Kante zwei Endpunkte verbindet. Mehrfachkanten mit denselben Endpunkten dürfen mehrfach auftreten. Schleifen, das sind Kanten, die einen Scheitelpunkt mit sich selbst verbinden, können erlaubt oder ausgeschlossen sein; je nach Konvention unterscheidet man Mehrfachgraphen mit Schleifen von solchen ohne Schleifen.

Eigenschaften: Die Anzahl der Kanten ist k=|E|. Der Grad eines Scheitelpunkts v entspricht der Summe der Anzahlen, mit denen Kanten v berühren; bei Schleifen zählt eine Schleife doppelt zum Grad. In gerichteten Mehrfachgraphen unterscheidet man eingehenden und ausgehenden Grad. Adjazenz- und Inzidenzmatrizen ähneln denen einfacher Graphen, weisen aber Einträge auf, die die Mehrfachheit der Kanten widerspiegeln (z. B. Zählwerte statt Nur-oder-Nicht). Mehrfachgraphen können sowohl ohne als auch mit Schleifen betrachtet werden, je nach definierter Struktur.

Beispiele: V={a,b,c}, E={{a,b},{a,b},{b,c}} definiert zwei parallele Kanten zwischen a und b und eine zwischen b und c. Mit Schleifen könnte E={{a,a},{a,b},{b,c}} enthalten sein.

Beziehung zu anderen Konzepten: Ein Mehrfachgraph ist eine Erweiterung eines einfachen Graphen; durch Entfernen von Kanten oder das Zusammenführen paralleler Kanten lässt sich ein einfacher Graph erhalten. Anwendungen finden sich in Netzwerken und Verkehrsmodellen, wo mehrere Verbindungen oder Kapazitäten zwischen gleichen Knoten berücksichtigt werden müssen.