Knobelaufgabe Logik/Mathematik

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Welche Einschränkungen gibt es noch?
      (A) Jede Brücke genau einmal überqueren?
      (B) Am Ende wieder dort stehen, von wo man losgegangen ist?
      (C) Oder keine der Einschränkungen und es wird nach dem kürzsten Weg gesucht, der alle Brücken mindestens einmal überquert?

      Es gibt das Eulerkreisproblem, bei dem es genau um die Aufgabe geht. Euler hat festgestellt:
      (A) + (B) geht genau dann, wenn jeder Knoten geraden Grad hat (= jedes Stück Land A, B, C, D hat eine gerade Anzahl an Brücken). Da C immer ungeraden Grad hat, gibt es auch mit Brücke 8 keinen Eulerkreis (= Weg, der jede Brücke genau einmal überquert und dort aufhört, wo er angefangen hat).

      Nur (A), ohne (B), geht genau dann, wenn es höchstens zwei Knoten mit ungeradem Grad gibt. Ohne Brücke 8 haben A, B, C und D ungeraden Grad, also gibt es keinen Eulerweg (= Weg, der jede Brücke genau einmal überquert, aber wo anders aufhört wie wo er anfängt). Mit Brücke 8 haben nur noch C und B ungeraden Grad, also gibt es einen Eulerweg (zum Beispiel: Start bei B, dann Brücke 7, 8, 6, 3, 5, 4, 1, 2, endet bei C). Jeder Eulerweg startet bei B oder C und endet beim jeweils anderen Knoten mit ungeradem Grad (da A und D geraden Grad haben, kann man dort nicht stecken bleiben).

      Wenn es um (C) geht: Einen Weg mit jeder Brücke nur einmal gibt es also nicht; also muss man für eine optimale Lösung in diesem Sinne mindestens eine Brücke zweimal gehen, z.B. Start bei D: 1 -> 5 -> 4 -> 2 -> 6 -> 7 -> 4 -> 3, Ende bei C

      Eulerkreisproblem: Eulerkreisproblem – Wikipedia

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von algernong ()