Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:graphen:graphen:einfuehrung [07.12.2021 20:26] – [Wege in Graphen] Mareike Nutz
+++ faecher:informatik:oberstufe:graphen:graphen:einfuehrung [18.03.2022 11:31] – Mareike Nutz
@@ Zeile 5: / Zeile 5: @@
-----
-{{:aufgabe.png?nolink  |}}
-=== Übergreifende Aufgabe ===
-Im Spiel "Auf den Spuren eines Handelsreisenden" habt ihr in jedem Level auf Verschiedenen Beispielen von der gespielt. Im Folgenden erfährst du, was die Datenstruktur Graph genau ist, welche Eigenschaften Graphen haben sowie welche Wege auf Graphen gegangen werden können. Beschreibe, welche Eigenschaften die Graphen im Spiel haben.
@@ Zeile 17: / Zeile 13: @@
 Formal schreibt man:
 <blockquote>Graph ''G = (V,E)'' mit ''V'': Knotenmenge und ''E'': Kantenmenge</blockquote>
-Das bedeutet so viel wie: "Ein Graph ''G'' ist ein Tupel ''(V,E)'', wobei ''V'' die Menge von Knoten und ''E'' die Menge von Kanten des Graphen bezeichnet." Das Bild von einem Beispielgraphen rechts veranschaulicht dies.
+Das bedeutet so viel wie: "Ein Graph ''G'' ist ein Tupel ''(V,E)'', wobei ''V'' die Menge von Knoten (//Vertices//) und ''E'' die Menge von Kanten (//Edges//) des Graphen bezeichnet." Das Bild von einem Beispielgraphen rechts veranschaulicht dies.
 {{:aufgabe.png?nolink  |}} (1) Zeichne den folgenden Graphen: ''V = {29,8,1,16,42,3}'' und ''E = {(8,42),(8,1),(16,8),(8,29),(1,16),(42,3),(29,42),(3,29)}''.
@@ Zeile 28: / Zeile 24: @@
 {{:aufgabe.png?nolink  |}} (2) Notiere, welche der folgenden Graphen Multigraphen sind.
-{{ :faecher:informatik:oberstufe:graphen:graphen:multi2.png?600 |}}
+{{ :faecher:informatik:oberstufe:graphen:graphen:multigraphen.drawio.png?900 |}}
-<sup>https://lehrerfortbildung-bw.de/u_matnatech/imp/gym/bp2016/fb1/6_m2_aug/2_kopiervorlagen/2_multi/multi2.png</sup>
+----
+{{ :faecher:informatik:oberstufe:graphen:graphen:knotengrad.drawio.png?200|}}
+**Knotengrad**
+Der Grad eines Knotens (Knotengrad) ist die Anzahl der Kanten, die in diesem Knoten zusammentreffen. Im Graph rechts hat der Knoten **a** den Grad 2, der Knoten **b** den Grad 1, **c** den Grad 4, **d** den Grad 2 und der Knoten **e** den Grad 3.
+{{:aufgabe.png?nolink  |}} (3) Ermittle den Grad aller Knoten des sechsten Levels aus dem Spiel "Auf den Spuren eines Handelsreisenden".
+{{:faecher:informatik:oberstufe:graphen:graphen:l6_gelb.png?500|}}
 ----
@@ Zeile 38: / Zeile 43: @@
 Ein Graph heißt vollständig, wenn jeder Knoten mit jedem anderen Knoten des Graphs durch eine Kante verbunden ist. Rechts ist ein Beispiel für einen vollständigen Knoten zu sehen.
-{{:aufgabe.png?nolink  |}} (3) Finde heraus, wie viele Kanten ein vollständiger Graph mit 3, 7 und mit 8 Knoten hat.
+{{:aufgabe.png?nolink  |}} (4) Finde heraus, wie viele Kanten ein vollständiger Graph mit 3, 7 und mit 8 Knoten hat.
 ++++ Zu einfach? Knobelaufgabe!|
 Bestimme eine allgemeine Formel, um die Anzahl der Kanten in einem Graph mit //n// Knoten zu berechnen.
@@ Zeile 50: / Zeile 55: @@
 Sind bei den Kanten keine Richtungen angegeben, nennt man den Graphen ungerichtet. Die Kante wird durch eine Linie dargestellt (siehe Abb. unten).
 {{ :faecher:informatik:oberstufe:graphen:graphen:un_gerichtetergraph.drawio.png?500 |}}
-{{:aufgabe.png?nolink  |}} (4) Beschreibe je ein Anwendungsbeispiel, in dem man einen ungerichteten und einen gerichteten Graphen verwendet.
 ----
@@ Zeile 62: / Zeile 65: @@
 {{: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.
-==== Wege in Graphen ====
+----
+**Zusammenhängende Graphen**
+Ein Graph heißt zusammenhängend, wenn man entlang der Kanten von jedem Knoten zu einem anderen gelangen kann. Der Graph **G** auf der rechten Seite ist nicht zusammenhängend. Von Knoten **a** kann der Knoten **e** nicht erreicht werden.
+{{:aufgabe.png?nolink  |}} (6) Ergänze den Graphen G, sodass er zusammenhängend ist.
+{{ :faecher:informatik:oberstufe:graphen:graphen:zusammenhaengender.drawio.png?500 |}}
+===== Wege in Graphen =====
 Einen Weg durch einen Graphen nennt man Pfad. Das ist eine endliche Folge von Kanten, die man durchlaufen muss, um von einem Startknoten zu einem Endknoten zu gelangen. Dabei gibt es zwei verschiedene Arten von Pfaden:
@@ Zeile 69: / Zeile 82: @@
 Hier ist dies beispielhaft veranschaulicht:
-{{ :faecher:informatik:oberstufe:graphen:graphen:pfade.png?600 |}}
+{{ :faecher:informatik:oberstufe:graphen:graphen:zyklen.drawio.png?800 |}}
-<sub>Quelle: Magenheim et al. 2009, S.42)</sub>
-{{:aufgabe.png?nolink  |}} Zeichne einen Graphen mit folgendem Pfad:
+{{: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.
-{{:aufgabe.png?nolink  |}} Finde 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.
 {{ :faecher:informatik:oberstufe:graphen:graphen:hamilton_ueb1.png?600 |}}
 <sup>Quelle: https://lehrerfortbildung-bw.de/u_matnatech/imp/gym/bp2016/fb1/6_m2_aug/2_kopiervorlagen/3_hamilton/1_uebung/hamilton_ueb1.png</sup>
 ++++ Zu einfach? Knobelaufgabe!|
-Bestimme eine allgemeine Formel, um die Anzahl der möglichen Hamilton-Kreise in einem Graph mit //n// Knoten zu berechnen.
+Bestimme eine allgemeine Formel, um die Anzahl der möglichen Hamilton-Kreise in einem vollständigen Graphen mit //n// Knoten zu berechnen.
 ++++
 ----
+{{:aufgabe.png?nolink  |}}
+==== (9) Graphen in "Auf den Spuren eines Handelsreisenden" ====
+Im Spiel "Auf den Spuren eines Handelsreisenden" habt ihr in jedem Level auf verschiedenen Beispielen von Graphen gespielt. Auf dieser Seite habt ihr erfahren, was die Datenstruktur Graph genau ist, welche Eigenschaften Graphen haben sowie welche Wege auf Graphen gegangen werden können. Beschreibe, welche Elemente von Graphen im Spiel zu finden sind und welche Eigenschaften diese Graphen haben.
+----
+{{:aufgabe.png?nolink  |}}
+==== (10) Zusatzaufgabe: TSP ====
+Herr Schnell muss Waren ausliefern. Er startet bei seiner Spedition in A, muss dann jede der Städte B,C und D genau einmal anfahren und wieder zur Spedition in A zurückkehren. Die Entfernungen sind in der Tabelle (in km) angegeben.
+^     ^  A   ^  B    ^  C    ^  D    ^
+^  A  |  0   |  98   |  58   |  54   |
+^  B  |  98  |  0    |  56   |  161  |
+^  C  |  58  |  56   |  0    |  125  |
+^  D  |  54  |  161  |  125  |  0    |
+  * Er möchte auf seiner Tour jeweils in die nächstgelegene, noch nicht besuchte Stadt fahren und am Ende nach A zurückkehren. Gib den Pfad und die Länge seines Weges an. Wie nennt sich der Algorithmus, den Herr Schnell verwendet?
+  * Zeichne einen gewichteten Graphen. Suche alle Hamiltonkreise und ermittle die kürzeste Route. Wie nennt sich dieser Algorithmus?
+++++ Zu einfach? Zusatz-Zusatzaufgabe! |
+Liefern beide Algorithmen immer das bestmögliche Ergebnis? Erkläre deine Antwort.
+++++
+<sup>(Quelle: Grund 2018)</sup>
+----
 <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:*}}