Benutzer:Uwe Lück/Multigraph
Die Brücken von Königsberg
[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]Man könnte die Krämerbrücke und die Schmiedebrücke „parallel“ 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 | Quelltext bearbeiten]Vorbemerkung
[Bearbeiten | Quelltext 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 | Quelltext 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.
Quellen
[Bearbeiten | Quelltext bearbeiten]Literatur
[Bearbeiten | Quelltext bearbeiten]- 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
[Bearbeiten | Quelltext bearbeiten]- Diagramm, Abschnitt Graphen
- Graph (Graphentheorie), Abschnitte
- Graphentheorie, Kurzdefinition von Multigraph
- Kantenzug
- Königsberger Brücken
- Königsberger Brückenproblem
- Multimenge
Englische Wikipedia
[Bearbeiten | Quelltext bearbeiten]Weblinks
[Bearbeiten | Quelltext bearbeiten]- 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
Einzelnachweise und Anmerkungen
[Bearbeiten | Quelltext bearbeiten]- ↑ Diestel S. 42, Abbildung 2; vgl. dazu die Fußnote auf S. 23.
- ↑ Vgl. englische Wikipedia.
- ↑ Vgl. Diestel S. 30.
- ↑ a b c C. Caldwell, UT Martin, USA
- ↑ Vgl. Diskussionsbeitrag von Benutzer:Gunther vom 2. März 2006, der noch im selben Jahr das Handtuch warf.
- ↑ 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.
- ↑ 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.