| |
| faecher:informatik:oberstufe:graphen:graphen:einfuehrung [10.10.2022 07:59] – Mareike Nutz | faecher:informatik:oberstufe:graphen:graphen:einfuehrung [11.09.2025 13:19] (aktuell) – Externe Bearbeitung 127.0.0.1 |
|---|
| |
| ===== Was ist ein Graph? ===== | ===== Was ist ein Graph? ===== |
| {{ :faecher:informatik:oberstufe:graphen:graphen:graph.drawio.png?400|}} | {{ graph.drawio.png?400|}} |
| |
| Ein Graph ist ein Gebilde, das aus Knoten und Kanten besteht. Jede Kante verbindet zwei Knoten oder einen Knoten mit sich selbst. Von einem Knoten können eine, mehrere oder keine Kanten ausgehen. | Ein Graph ist ein Gebilde, das aus Knoten und Kanten besteht. Jede Kante verbindet zwei Knoten oder einen Knoten mit sich selbst. Von einem Knoten können eine, mehrere oder keine Kanten ausgehen. |
| **Kantengewichte** | **Kantengewichte** |
| |
| Die Kanten eines Graphen können gewichtet bzw. bewertet sein. Jeder kannte ist dann ein sogenanntes Kantengewicht zugewiesen (siehe Abb. rechts). Damit können zum Beispiel Kosten oder Entfernungen zwischen zwei Punkten (Knoten) dargestellt werden. | Die Kanten eines Graphen können gewichtet bzw. bewertet sein. Jeder Kante ist dann ein sogenanntes Kantengewicht zugewiesen (siehe Abb. rechts). Damit können zum Beispiel Kosten oder Entfernungen zwischen zwei Punkten (Knoten) dargestellt werden. |
| |
| {{:aufgabe.png?nolink |}} (5) Das //Traveling Salesman Problem// ist ein typisches Beispiel für ein Problem auf einem gewichteten Graphen. Es handelt sich um dabei um ein Problem, das sowohl im Alltag als auch in vielen anderen Bereichen seine Anwendung findet und immer wieder gelöst werden muss. Recherchiere weitere Anwendungsgebiete des TSP. | {{:aufgabe.png?nolink |}} (5) Das //Traveling Salesman Problem// ist ein typisches Beispiel für ein Problem auf einem gewichteten Graphen. Es handelt sich dabei um ein Problem, das sowohl im Alltag als auch in vielen anderen Bereichen seine Anwendung findet und immer wieder gelöst werden muss. Recherchiere weitere Anwendungsgebiete des TSP. |
| |
| ---- | ---- |
| {{:aufgabe.png?nolink |}} (7) Zeichne im Graphen aus Aufgabe (1) den Pfad ''p = (1,8),(8,42),(42,3),(3,29),(29,8)'' ein. Handelt es sich um einen einfachen oder einen zyklischen Pfad? Erkläre. | {{:aufgabe.png?nolink |}} (7) Zeichne im Graphen aus Aufgabe (1) den Pfad ''p = (1,8),(8,42),(42,3),(3,29),(29,8)'' ein. Handelt es sich um einen einfachen oder einen zyklischen Pfad? Erkläre. |
| |
| Ein Zyklus, der jeden Knoten eines Graphen genau einmal enthält, heißt **Hamilton-Kreis**. Dieses Begriff habt ihr im Spiel bereits unter dem Namen "Rundreise" kennengelernt. | Ein Zyklus, der jeden Knoten eines Graphen genau einmal enthält, heißt **Hamilton-Kreis**. Diesen Begriff habt ihr im Spiel bereits unter dem Namen "Rundreise" kennengelernt. |
| |
| {{:aufgabe.png?nolink |}} (8) Findest du jeweils alle Hamilton-Kreise in diesen Graphen? Zeichne sie in dein Heft. | {{:aufgabe.png?nolink |}} (8) Findest du jeweils alle Hamilton-Kreise in diesen Graphen? Zeichne sie in dein Heft. |
| <sub>//Basiert auf: Grund (2018): ZPG-Material IMP. und Magenheim et al. (2009): Informatik macchiato - Cartoon-Informatikkurs für Schüler und Studenten.//</sub> | <sub>//Basiert auf: Grund (2018): ZPG-Material IMP. und Magenheim et al. (2009): Informatik macchiato - Cartoon-Informatikkurs für Schüler und Studenten.//</sub> |
| |
| {{simplefilelist>:faecher:informatik:oberstufe:graphen:graphen:*}} | {{filelisting>:faecher:informatik:oberstufe:graphen:graphen:*}} |