Ungerichteter Multigraph/Schleifenfrei/Einführung/Textabschnitt

Aus Wikiversity



Definition  

Ein Multigraph besteht aus einer Knotenmenge , einer Kantenmenge und einer Abbildung

Genauer spricht man von einem ungerichteten Multigraphen ohne Schleifen. In der Definition ist zunächst eine abstrakte Kantenmenge, wobei erst über durch die Abbildung die beiden Punkte aus miteinander „verbindet“. Einen Multigraphen kann man einfach skizzieren, indem man als Punktemenge skizziert und für jede abstrakte Kante jeweils eine Verbindungskante zwischen den zugehörigen Punkten zeichnet. Zwei Punkte können dann durch mehrere Kanten miteinander verbunden sein. Wichtig ist, dass die Kanten als verschieden anzusehen sind, was von einem Bildchen her klar ist. Die Kanten haben eine eigene Identität.

Ein Multigraph ist etwas anderes als ein einfacher ungerichteter Graph, bei dem die Kanten noch zusätzlich positive natürliche Zahlen (Gewichte) bekommen. Man überlege sich, was jeweils ein Unterobjekt ist.

Ein ungerichteter Graph ist dasselbe wie ein Multigraph, bei dem die Abbildung injektiv ist. In diesem Fall kann man mit einer gewissen Menge von zweielementigen Teilmengen der Knotenmenge identifizieren.