Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- schule:graphen:einstieg [2018/05/26 14:57] – [Beispiele] ahrens
+++ schule:graphen:einstieg [2018/06/09 15:27] (aktuell) – [Wege in Graphen] ahrens
@@ Zeile 80: / Zeile 80: @@
 ====== Wege in Graphen ======
-Moderne Navigationsgeräte wären ohne die Wegfindungsalgorithmen der Graphentheorie sicher nicht so leistungsfähig.
+Moderne Navigationsgeräte wären ohne die Wegfindungsalgorithmen der Graphentheorie, vor allem der Dijkstra-Algorithmus, sicher nicht so leistungsfähig.
 Sucht man Wege in Graphen, kann man zwei Herangehensweisen unterscheiden:
-  - Wege über alle Knoten ([[.:euler|Eulersche Graphen]])
+  - Touren über alle Kanten ([[.:euler|Eulersche Graphen]])
-  - Wege über alle Kanten ([[.:hamilton|Hamiltonsche Graphen]])
+  - Kreise durch alle Knoten ([[.:hamilton|Hamiltonsche Graphen]])
+    - optimiert, mit Kantengewicht: [[.:hamilton#travelling_salesman_problem|Travelling Salesman Problem]]
+  - kürzester Weg von einem Startknoten zu allen anderen Knoten
+    - ohne Kantengewicht: [[.:breitensuche|Breitensuche]]
+    - mit Kantengewicht: [[.:dijkstra|Dijkstra-Algorithmus]]
 ====== Weitere Themen aus Sicht der Graphentheorie ======
@@ Zeile 92: / Zeile 96: @@
   * [[.:platon|Platonische Körper]]
-{{tag>Graphentheorie, Isomorphie, Adjazenzmatrix}}
+{{tag>Graphentheorie Isomorphie Adjazenzmatrix}}
+====== Literatur ======
+Manfred Nitzsche: Graphen für Einsteiger (Rund um das Haus des Nikolaus), Vieweg (2005)