Diese Seite ist eigentlich nicht ein Vorschlag für einen neuen Artikel Multigraph, sondern dient der Ordnung meiner (Lückenloswecken!) Gedanken zur Klärung der Begriffe von Multigraph und Wegen in Multigraphen. Die (mehr polemischen) Argumentationen stehen eher auf der zugehörigen Diskussionsseite; ein paar relevante Tatsachen werden jedoch auf der vorliegenden Seite versammelt.

Das Königsberger Brückenproblem
Diagramm des zugehörigen Graphen
Brückenschema von Königsberg 1930

Die Brücken von Königsberg

Bearbeiten

Im 18. Jahrhundert zerteilten Arme des Flusses Pregel die Stadt Königsberg in Preußen (heute russische Stadt Kaliningrad) und bildeten vier „Stadtteile“, die durch sieben Brücken über die Pregelarme verbunden waren. Aus der Fragestellung, ob man einen Spaziergang (mit Rückkehr zum Ausgangspunkt) durch Königsberg unternehmen könne, auf dem man jede der sieben Brücken genau einmal benützt – dem Königsberger Brückenproblem – entstand die Graphentheorie.

„Auswahl“: Die über fünf Brücken mit anderen Stadtteilen verbundene Insel hieß Kneiphof. Die Krämerbrücke (links oben) und die Schmiedebrücke (rechts benachbart) verbanden den nördlichen Kneiphof mit der südlichen Altstadt (siehe Brückenschema).

Erster Bogenschlag zur Graphentheorie: In einem graphentheoretischen Diagramm vertritt man den Kneiphof durch einen Punkt (Knoten), die Altstadt durch einen weiteren, man zeichnet zwei Linien von einem Punkt zum andern (Kanten), eine für die Krämerbrücke, eine für die Schmiedebrücke. Um das Problem des 18. Jahrhunderts, die sieben Brücken betreffend, darzustellen, betrachtet man so insgesamt einen Graphen   mit vier Knoten ( ,  ,  ,  , „vertex“ oder „Viertel“) und sieben Kanten  , …,   (siehe Diagramm;   und  ). Die ursprüngliche Fragestellung lässt sich so formulieren: Gibt es eine Umordnung   der sieben Kanten, so dass dass sich  ,   in einem Knoten treffen und dass sich außerdem für   jeweils   und   in einem Knoten treffen? (  für eine Permutation  .)   wäre dann ein Kantenzug, in dem jede Kante genau einmal auftritt und dessen Endknoten auch sein Anfangsknoten wäre.

Diese Darstellung war immer noch recht anschaulich, genügt aber noch nicht ganz den formalen Anforderungen der modernen Mathematik.

Einfache Graphen

Bearbeiten

Eine „Einführung in die Graphentheorie“ beginnt eher mit sog. einfachen Graphen. „Anschaulich“ sind das Graphen, in denen es Kanten nur zwischen verschiedenen Knoten gibt (Ausschluss von Schlingen) und zwischen je zwei Knoten höchstens eine. (Hinzu kommt, dass Kanten keine Richtung haben – aber auf diese Idee käme man hier sowieso nicht so schnell.) Formal wird das so dargestellt:

Notation: Für jede Menge   sei   – die Menge der zweielementigen Teilmengen von  .

Definition: Ein einfacher Graph ist ein Paar   mit  .

Beobachtung: Der Graph der Königsberger Brücken ist schon anschaulich kein einfacher Graph …

Trick. Es gibt aber einen Trick: Man führt zusätzliche Knoten für „mitten auf der Brücke“ ein. Dann erhält man einen einfachen Graphen.[1]

Parallele Kanten

Bearbeiten

Man könnte die Krämerbrücke und die Schmiedebrückeparallel“ nennen. Tatsächlich gibt es in der Graphentheorie den Begriff parallele Kanten.[2][3][4] Formal:

Definition:[4][5][6] Ein Graph mit parallelen Kanten[7] ist ein Tripel   aus Mengen  ,   und einer Abbildung  . Kanten  ,   heißen parallel,[4] wenn  .

Eine solche Abbildung ordnet sowohl der Krämerbrücke als auch der Schmiedebrücke die aus der südlichen Altstadt und dem Kneiphof bestehende Paarmenge zu.

Multigraphen und Mehrfachkanten

Bearbeiten

Vorbemerkung

Bearbeiten

Man sollte vielleicht irgendwann in Erinnerung rufen, dass sich die Bedeutungen vieler mathematischer Fachausdrücke (in formalen Details) von Buch zu Buch bzw. von Vorlesung zu Vorlesung unterscheiden können. Für mündliche Prüfungen ist es daher auch ganz wichtig, dass man sich entweder auf das Vorlesungsskript des Prüfers oder auf ein Buch (oder mehrere) als Prüfungsstoff einigt.

Ein wirklich „wissenschaftlich“ versierter Mathematiker, der nicht nur Prüfungen besteht, sondern auch Vorlesungen konzipieren kann, hat etwas Übersicht über verschiedene Terminologien, die gerade im Schwange sind.

Gebräuchliche Bedeutungen

Bearbeiten

Geläufig sind die Ausdrücke Multigraph und Mehrfachkante, man findet jedoch jeweils zwei verschiedene Definitionen (oder noch mehr), in manchen Quellen beide gleichzeitig.

Eine Variante ist einfach die, dass ein Multigraph als „Graph mit parallelen Kanten“ im Sinn von weiter oben definiert wird. In der deutschen Wikipedia sind derzeit auch Multigraph und Graph mit Mehrfachkanten synonym. Eine „Mehrfachkante“ kann eine Kante sein, zu der es eine andere, parallele Kante im Sinn von weiter oben gibt – muss aber nicht.

Die Alternative besteht grundsätzlich darin zu sagen, ein Graph habe „ganz allgemein“ immer die Gestalt  ; dabei könne   eine Menge sein – oder eben eine Multimenge, in diesem Fall handele es sich um einen Multigraphen.

Literatur

Bearbeiten

Relevante Wikipedia-Artikel

Bearbeiten

Englische Wikipedia

Bearbeiten
Bearbeiten

Wolfram-Research (Mathematica), mathworld.wolfram.com, mit Literaturübersicht:


Einzelnachweise und Anmerkungen

Bearbeiten
  1. Diestel S. 42, Abbildung 2; vgl. dazu die Fußnote auf S. 23.
  2. Vgl. englische Wikipedia.
  3. Vgl. Diestel S. 30.
  4. a b c C. Caldwell, UT Martin, USA
  5. Vgl. Diskussionsbeitrag von Benutzer:Gunther vom 2. März 2006, der noch im selben Jahr das Handtuch warf.
  6. Für gerichtete [Multi-]Graphen gibt Diestel, S. 30 etwas wie   an mit  ,  ,   ist also Anfangspunkt,   Endpunkt der Kante  , parallele Kanten sind solche, die in Anfangs- und Endpunkt übereinstimmen.
  7. Dieser Ausdruck ist vermutlich neu und wird hier zur Unterscheidung alternativer Definitionen von „Multigraph“ verwendet. Analog zu „Multigraph“ fragt man sich natürlich, ob nicht zusätzlich die Existenz paralleler Kanten im jeweiligen Graphen gefordert werden sollte.