Kategorie: Graphentheorie

Ein Graph in der Graphentheorie besteht aus Knoten und Kanten. Die Knoten werden mit den Kanten verbunden. Eine Kante darf dabei nicht „ins Nichts“ führen.
Knoten können zum Beispiel Städte repräsentieren und Kanten die Entfernung zwischen den Städten. Die genaue Entfernung in km oder Fahrstunden kann man bei der Kante als Gewicht angeben.

18. April 2019 0 Von m roh

Graphentheorie – Kürzester Weg

Wer findet den kürzesten Weg? Eine Prinzessin benötigt die Hilfe ihres Prinzen, um ihr Volk zu retten. So muss dieser so schnell wie möglich zur Stelle sein! Welcher Weg ist wohl der kürzeste? Dieses Arbeitspaket bietet in zwei Stationen intuitive Hands-On-Varianten zum Finden des kürzesten Weges von einem Knoten zum anderen. Wer bei einer Station den kürzesten Faden am Ende in der Hand hält, hat den besten Weg gefunden!

10. April 2019 0 Von m roh

Graphentheorie – Traveling Santa

Santa muss noch Geschenke ausliefern. Dabei soll er besonders schnell alle Städte genau einmal besuchen. Welche Route ist die beste?
Dieses Arbeitspaket behandelt das „Traveling-Salesman-Problem“. Kinder probieren sich an der Lösung der Frage, welchen Weg Santa Claus am besten wählen soll, um besonders schnell die Geschenke verteilen zu können und lernen mehr über Graphen, kürzeste Wege und Probleme der Informatik, die nicht einfach zu lösen sind.

13. Januar 2021 0 Von m roh

Graphentheorie – Der Dijkstra Algorithmus

lgorithmen findet man im Alltag überall. Um den kürzesten Weg zwischen zwei Orten mittels GPS und Datentransfer zu finden, wird der Dijkstra-Algorithmus angewendet. Dieser sucht den kürzesten Weg von einem Start- zu einem Endknoten oder auch allen anderen Knoten in einem Graphen. Wie dieser Algorithmus funktioniert, wird in diesem Arbeitspaket thematisiert ….