Weihnachtsmann rot

Aufgabe vom 11. Dezember

Die U-Bahn des Weihnachtsmanns

Autor: Niels Lindner

Aufgabe:

Der Weihnachtsmann ist besonders stolz auf das U-Bahn-Netz am Nordpol und hat einen großen Netzplan in seinem Büro hängen, siehe Abbildung 1.


PIC

Abbildung 1: Netzplan aus dem Weihnachtsmannbüro. Das U-Bahn-Netz besteht aus 12 Stationen und 6 Linien, die sich aus einzelnen Strecken zusammensetzen. Auf einer Strecke können mehrere Linien verlaufen, z.B. gibt es 3 Linien auf der Strecke zwischen Süßigkeitenlager und Geschenkezentrum.

Aber immer, wenn sein Kumpel Niko vorbeikommt, gibt es eine sehr angeregte Diskussion über die Schönheit von Netzplänen. Beim nächsten Besuch will der Weihnachtsmann Niko mit einem besonders schönen Netzplan des U-Bahn-Nordpol-Netzes überraschen. Beide sind sich darüber einig, dass ein Netzplan oktilinear sein sollte, d.h., es müssen folgende zwei Eigenschaften erfüllt sein:

  1. Die Stationen müssen so angeordnet sein, dass die Strecken (das sind die Gradenstücke zwischen den Stationen) einen Steigungswinkel haben, der ein ganzzahliges Vielfaches von 45° beträgt (horizontal bezogen).
  2. Es gibt keine sich kreuzenden Strecken.

Außerdem gibt es noch folgende Merkmale, die einen Netzplan beschreiben:

  • schräge Strecken: Eine Strecke ist schräg, wenn sie einen Steigungswinkel von 45°, 135°, 225° oder 315° hat.
  • Krümmungszahl einer Linie: Die Krümmungszahl einer Linie ist die Anzahl Stationen, die die Linie nicht in einem Winkel von 180° durchläuft, Anfangs- und Endpunkt der Linie ausgenommen.
  • Kreuzen zweier Linien: Zwei Linien kreuzen sich in einer Station s, wenn sich ihre Linien(wege) in s schneiden und sie auf mindestens einer an s anliegenden Strecke gemeinsam verlaufen.

Der Netzplan im Büro des Weihnachtsmanns ist oktilinear. Er hat 4 schräge Strecken. Die Krümmungszahl der roten Linie ist 2 und die Krümmungszahl summiert über alle Linien ist 7. Es kreuzen sich z.B. die beiden grünen Linien in der Station Süßigkeitenlager oder die blaue und rote Linie in der Station Spielzeughalle. (Der Schnittpunkt ist in der Abbildung unter den Stationen versteckt.) Im Gegensatz dazu kreuzen sich die blaue und orange Linie an der Station Schokoladenfabrik nach obiger Definition nicht, weil sie weder direkt davor noch danach über eine gemeinsame Strecke verlaufen.

Der Weihnachtsmann hat alle Wichtel gebeten, sich Gedanken darüber zu machen, wie man das U-Bahn-Netz vom Nordpol noch darstellen kann. Während er sich ihre Aussagen ansieht und dabei überlegt, wie wohl der schönste Netzplan aussieht, bekommt er die Ahnung, dass sich ein Fehler eingeschlichen hat.

Welche der folgenden Aussagen ist nicht richtig?

Die Aufgabe als PDF runterladen

Antwortmöglichkeiten:

  1. Wenn die Stationen an den Stellen bleiben, wie sie auf dem Netzplan im Weihnachtsmannbüro sind, dann gibt es keine Möglichkeit die Linien kreuzungsfrei zu zeichnen.

  2. Es gibt aber eine oktilineare Darstellung des Netzes, in der sich keine Linien kreuzen.

  3. In jeder oktilinearen Darstellung ist die Summe der Krümmungszahlen der beiden grünen Linien größer als 0.

  4. Es gibt keine oktilineare Darstellung, in der die blaue Linie Krümmungszahl 0 hat.

  5. Es gibt eine oktilineare Darstellung, in der die blaue Linie eine kleinere Krümmungszahl hat als die braune Linie.

  6. Unter allen oktilinearen Darstellungen ist die kleinstmögliche Summe der Krümmungszahlen aller Linien 4.

  7. Es gibt eine oktilineare Darstellung des Netzes, in der die 12 Stationen in einem Raster von 4 × 3 Punkten angeordnet sind.

  8. Es gibt eine oktilineare Darstellung, die mit genau 2 schrägen Strecken auskommt.

  9. In jeder oktilinearen Darstellung führen mindestens 3 Linien über schräge Strecken.

  10. Falls die von vielen gewünschte Linie, die die Stationen Schlittengarage über das Süßigkeitenlager zur Spekulatiusbäckerei verbinden würde, eingeführt werden sollte, so ist es nicht möglich, eine oktilineare Darstellung des neuen Netzes anzufertigen.

Sie müssen sich einloggen um die Aufgaben abgeben zu können.

Projektbezug:

Das Projekt MI7 – Routing Structures and Periodic Timetabling – beschäftigt sich mit der Optimierung von Fahrplänen, sodass Fahrgäste so wenig wie mglich warten müssen. Dabei wird die Auswahl der Fahrtroute in die Erstellung des Fahrplans miteinbezogen. Die Visualisierung von Verkehrsnetzen führt auf eine Reihe schwieriger Probleme, wie z.B. das Finden oktilinearer Darstellungen und das Minimieren von Krümmungen und Kreuzungen.