Königsberger Brückenproblem - Eulerkreis

Letztmalig dran rumgefummelt: 17.01.26 05:46:57

	DLeonhard Euler fragte in seiner Arbeit 1736 zum Königsberger Brückenproblem – übersetzt in die heutige Fachsprache –, ob der durch die Pregelbrücken der Stadt gegebene Graph ein semi-eulerscher Graph ist, das heißt, ob ein Eulerweg existiert, und verneinte dies, da der Graph mehr als zwei Knoten mit ungeradem Grad hatte. Euler bewies, dass ein semi-eulerscher Graph höchstens zwei Knoten ungeraden Grades haben kann. Er vermutete und gab ohne Beweis an, dass dies eine hinreichende Bedingung sei: Ein zusammenhängender Graph, in dem jeder Knoten geraden Grad hat, ist ein Eulergraph. Ein Beweis des Satzes wurde zuerst von Carl Hierholzer 1873 veröffentlicht. Auf dem Beweis basiert der Algorithmus von Hierholzer zum Auffinden eines Eulerwegs.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für das Königsberger-Brückenproblem Logo  Das Ist Das Haus Vom Ni Ko Laus begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	der "Worst-Case" liegt hier sicher nicht in der Komplexität zum Aufwand für den Lösungsalgorithmus - er ist hier allein in der Mächtigkeit des Problems zu suchen
	die Anzahl der Zwischenwerte, die zur Lösung für ein Argument benötigt werden ist schlichtweg enorm und steigt mit n-polinomial
	Es begann eigentlich ganz harmlos im Jahr 1736 mit der Frage Leonhard Eulers (1707 - 1783), ob durch die Stadt Königsberg (heute Kaliningrad) ein Rundgang möglich sei, bei dem man jede der sieben Brücken genau einmal passieren würde (ohne ein Boot zu benutzen).     Die sieben Brücken von Königsberg mit einer ungeraden Anzahl von Brücken bei dieser Anordnung von Knoten lässt sich das Problem nicht lösen Diese Animation demonstriert einen erfolglosen Versuch. Aus diesem Problem entwickelte sich einige Zeit später die Graphentheorie, ein Teilgebiet der Mathematik. Auch wenn es zunächst sehr abstrakt wirkt, lassen sich damit viele Probleme lösen. Eine Biografie Eulers finden Sie unter homepages.compuserve.de/thweidenfeller/mathematiker/euler.htm.
	Beachte vor allem bei Problemlösungsalgorithmen: Murphys Gesetze sowie deren Optimierung durch Computer sowie deren Optimierung durch Computer

1. Problembeschreibung

	ztrgilt.
	Blick auf das heutige Kaliningrad und die Insel zwischen den Flussläufen - einige Brücken sind so heute nicht mehr vorhanden
	... das ist das Haus vom Ni ko laus Hierholzer-Algorithmus
	... das ist das Haus vom Nikolaus  - alle 44 möglichen Lösungen ... EULER-Graph ... EULER-Graph   ... EULER-Graph ... EULER-Graph ... EULER-Graph ... EULER-Graph ... gerade Anzahl von Knoten ... EULER-Graph

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Der Lösungsalgorithmus für die Türme von Hanoi
	effiziente Lösung nur als rekursiver Algorithmus

3. Lösungsalgorithmus

	Wenn es mindestens einen Lösungsansatz gibt, dann versuche, aus den gegebenen Wortpaaren identische Sätze auf beiden Seiten der Gleichung zu bilden. Wiederhole dies solange, bis keine weitere Möglichkeit mehr existiert.

4. Programmvorschläge

5. Zusammenfassung

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig - er ist n-polinomial
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

6. Weiterführende Literatur

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig
	es muss also insgesamt hoher Lösungsaufwand betrieben werden - auch ein Computer wird für n=1000 in absehbarer Zeit keine Lösung bringen

7. Links zum Thema

	Viele gibt es - die meisten sind JAVA-basierte Spiele, um den erkannten Lösungsalgorithmus nach zu vollziehen. Wie gesagt, wenn Du vor hast, das Spiel noch am laufenden Tag zu beenden, verwende keine Scheibenzahl größer 20 - das ist dann schon nicht mehr zu schaffen.
	http://www.blinde-kuh.de/spiele/hanoi/
	http://www.cut-the-knot.org/recurrence/hanoi.shtml

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem der Kaprekar-Algorithmus das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im März 2004