Zur Hauptnavigation springen [Alt]+[0] Zum Seiteninhalt springen [Alt]+[1]

Multigraphen

  1. Königsberger Brückenproblem1

    In der Innenstadt von Königsberg vereinen sich der Alte und der Neue Pregel zu einem Fluss, dem Pregel. Im 18. Jahrhundert führten sieben Brücken über die Flüsse. Folgendes Rätsel beschäftigte damals Königsberg und die mathematische Elite Europas:

    Abbildung 1 Multigraphen

    Kann man einen Stadtrundgang so planen, dass jede Brücke genau einmal überquert wird?

    Diskutiert das Problem und sucht nach einer Lösungsstrategie.

    Tipp: Mit Graphen lassen sich viele Probleme übersichtlich darstellen.

    Multigraphen

    Sind zwei Knoten durch mehrere Kanten verbunden, so spricht man von „Mehrfachkanten“ und nennt die zugehörigen Graphen Multigraphen. Ein Graph ohne Mehrfachkanten wird als „einfacher Graph“ bezeichnet.

  2. Notiert, welche der folgenden Graphen Multigraphen sind. Begründet, ob es Eulersche Kantenzüge gibt und markiert ggf. Start.- und Endknoten.

    Abbildung 2 Multigraphen

    Fügt dem Graphen in 3e) möglichst wenige Kanten hinzu, so dass alle Knoten gerade sind.

  3. Das Nachtwächter-Problem

    Abbildung 3 Multigraphen

    Ein Nachtwächter muss auf dem Betriebsgelände einer Firma mehrmals pro Nacht alle Türen eines Gebäudes mit 5 Hallen kontrollieren. Ist es möglich, dass er bei seinem Rundgang durch die Fabrikhallen jede Tür genau einmal passiert?

    1. Entfernt im Königsberger Stadtplan Brücken, so dass ein Stadtrundgang mit Rückkehr zum Ausgangspunkt möglich wird.
    2. Ergänzt Brücken, anstatt welche zu entfernen, so dass dies gelingt.
  4. Kann man einen Draht zu einem vollständigen Kantenmodell eines Würfels biegen? Zeichnet einen passenden Graphen und begründet damit eure Antwort.

1 Die erste Arbeit über Graphen (bzw. Graphentheorie) wurde von dem Schweizer Mathematiker Leonhard Euler (1701-1783) geschrieben. Sie erschien 1737 und begann mit dem berühmten Königsberger Brückenproblem.

 

Übungen

andere Reihenfolge

 

Multigraphen: Herunterladen [odt][206 KB]

Multigraphen: Herunterladen [pdf][151 KB]

 

Weiter zu Übungen