Multigraphen – Lösung
-
Königsberger Brückenproblem
Man zeichnet einen Graphen direkt im „Stadtplan“ oder gleich als idealisierten Graphen:
siehe auch Graph in Aufgabe 3b) auf dem Arbeitsblatt
Alle vier Knoten besitzen ungerade Ordnung. Da der Graph mehr als zwei ungerade Knoten besitzt, ist ein Rundgang unmöglich.
-
Die Graphen a) bis d) sind Multigraphen, e) ist ein einfacher Graph ohne Mehrfachkanten.
Bei a) ist ein offener EKZ möglich, beide ungeraden Start- bzw. Endknoten sind markiert.
Bei b) und c) sind keine EKZ möglich, beide Graphen besitzen nur ungerade Knoten.
Bei d) sind geschlossene EKZ möglich, da nur gerade Knoten auftreten (vgl. Aufg. 2).
Bei e) sind mindestens 3 weitere Kanten nötig, damit alle Knoten gerade Ordnung haben.
-
Das Nachtwächter-Problem
Als Graph im Grundriss der Fabrikhallen und als idealisierter Graph (ist auch in Aufgabe 3d) abgebildet)
Der Hof und jede der Hallen werden als Knoten und die Verbindungswege durch die Türen als Kanten aufgefasst.
In allen Knoten trifft eine gerade Anzahl an Kanten zusammen. Da nur gerade Knoten auftreten, existiert ein geschlossener Eulerscher Kantenzug, der Rundgang ist möglich.
-
Es müssen mindestens 2 Brücken ergänzt oder entfernt werden, individuelle Lösungen.
-
Nein. In jeder Würfelecke stoßen 3 Kanten zusammen, der zugehörige Graph hat 8 ungerade Knoten und lässt sich daher nicht „in einem Zug“ zeichnen. Ein Graph heißt übrigens „planar“ oder „plättbar“, wenn er wie rechts zu sehen in der Ebene ohne Überschneidungen gezeichnet werden kann.
Multigraphen – Lösung: Herunterladen [odt][320 KB]
Multigraphen – Lösung: Herunterladen [pdf][231 KB]
Weiter zu Übungen