Benutzer:Uwe Lück/Multigraph

Diese Seite ist eigentlich nicht ein Vorschlag für einen neuen Artikel Multigraph, sondern dient der Ordnung meiner (Lückenlos^wecken!) 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

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 $G=(V,E)$ mit vier Knoten ($V_{1}$, $V_{2}$, $V_{3}$, $V_{4}$, „vertex“ oder „Viertel“) und sieben Kanten $B_{1}$, …, $B_{7}$ (siehe Diagramm; $V=\{V_{1},\dots ,V_{4}\}$ und $E=\{B_{1},\dots ,B_{7}\}$). Die ursprüngliche Fragestellung lässt sich so formulieren: Gibt es eine Umordnung $(B'_{1},\dots ,B'_{7})$ der sieben Kanten, so dass dass sich $B_{7}$, $B_{1}$ in einem Knoten treffen und dass sich außerdem für $i=1,\dots ,6$ jeweils $B'_{i}$ und $B'_{i+1}$ in einem Knoten treffen? ($B'_{i}=B_{s(i)}$ für eine Permutation $s:\{1,\dots ,7\}\to \{1,\dots ,7\}$.) $(B'_{1},\dots ,B'_{7})$ 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

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 $M$ sei ${\mathcal {P}}_{2}(M):=\{e\subseteq M:|e|=2\}=\{\{x,y\}\subseteq M:x\neq y\}$ – die Menge der zweielementigen Teilmengen von $M$.

Definition: Ein einfacher Graph ist ein Paar $G=(V,E)$ mit $E\subseteq {\mathcal {P}}_{2}(V)$.

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.

Parallele Kanten

Man könnte die Krämerbrücke und die Schmiedebrücke „parallel“ nennen. Tatsächlich gibt es in der Graphentheorie den Begriff parallele Kanten. Formal:

Definition: Ein Graph mit parallelen Kanten ist ein Tripel $(V,E,f)$ aus Mengen $V$, $E$ und einer Abbildung $f:E\to {\mathcal {P}}_{2}(V)$. Kanten $e$, $e'\in E$ heißen parallel, wenn $f(e)=f(e')$.

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

Vorbemerkung

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

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 $(V,E)$; dabei könne $E$ eine Menge sein – oder eben eine Multimenge, in diesem Fall handele es sich um einen Multigraphen.

Quellen

Literatur

• Reinhard Diestel: Graphentheorie. 3. Auflage. Springer, 2006, ISBN 3-540-21391-0 (online; PDF, 2.30 MB). 
• Peter Mahlmann, Christian Schindelhauer: Peer-to-Peer-Netzwerke. Algorithmen und Methoden. Springer, 2007, ISBN 978-3-540-33991-5 (Definition von Multigraph bei Google-Bücher). 

Relevante Wikipedia-Artikel

• Diagramm, Abschnitt Graphen
• Graph (Graphentheorie), Abschnitte
  • Anschauung für spezielle Graphen
  • Definitionen
• Graphentheorie, Kurzdefinition von Multigraph
• Kantenzug
• Königsberger Brücken
• Königsberger Brückenproblem
• Multimenge

Englische Wikipedia

• Multigraph
• Multiple edge/Multiple edges

Weblinks

• Multigraph – Britannica Online Encyclopedia – zuerst eine „anschauliche“ Definition, dann eine mit „Multimenge“ (nur ein Anfang des Texts ist einsehbar)
• Multigraph – Paul E. Black, US-NIST – Definition mit „Multimenge“ („bag“; Paul E. Black, Dictionary of Algorithms and Data Structures [online], U.S. National Institute of Standards and Technology. 2 February 2006.)
• Multigraph – Chris Caldwell, UT Martin, USA 1995 – „parallel“ formal
• Spaziergänge und Buslinien – knappe anschauliche und theoretische Darstellung des Königsberger Brückenproblems mit Hilfe von Kantenzügen (Franz Embacher, Uni Wien)

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

• Multigraph (Warnung wegen Ambiguität)
• Multiple Edge – (anschaulich?) einzelne „multiple“ Kanten, aber „Korrespondenz“ zu bestimmten Inzidenzmatrizen (ganz offensichtlich Adjazenzmatrix gemeint)
• Königsberg Brigde Problem

---