Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:graphen:einfuehrung [13.12.2021 10:29] – Mareike Nutz
+++ faecher:informatik:oberstufe:graphen:graphen:einfuehrung [12.01.2023 13:53] (aktuell) – [Wege in Graphen] sron
@@ Zeile 8: / Zeile 8: @@
 ===== 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.
@@ Zeile 26: / Zeile 26: @@
 {{ :faecher:informatik:oberstufe:graphen:graphen:multigraphen.drawio.png?900 |}}
+----
+{{ :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 haben die Knoten folgende Grade:
+^ Knoten  ^ Grad  ^
+|    a    |   2    |
+|    b    |   1    |
+|    c    |   4    |
+|    d    |   2    |
+|    e    |   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 34: / Zeile 50: @@
 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 52: / Zeile 68: @@
 **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  |}} (4) 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.
+----
+**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 =====
@@ Zeile 63: / Zeile 89: @@
 Hier ist dies beispielhaft veranschaulicht:
-{{:aufgabe.png?nolink  |}} (5) 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.
+{{ :faecher:informatik:oberstufe:graphen:graphen:zyklen.drawio.png?800 |}}
+{{: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  |}} (6) 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.
 {{ :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>
@@ Zeile 77: / Zeile 105: @@
 {{:aufgabe.png?nolink  |}}
-=== Übergreifende Aufgabe ===
+==== (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. 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 Elemente von Graphen im Spiel zu finden sind und welche Eigenschaften diese Graphen haben.
+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.
@@ Zeile 84: / Zeile 112: @@
 {{:aufgabe.png?nolink  |}}
-==== (7) Zusatzaufgabe: TSP ====
+==== (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.
@@ Zeile 96: / Zeile 124: @@
   * Zeichne einen gewichteten Graphen. Suche alle Hamiltonkreise und ermittle die kürzeste Route. Wie nennt sich dieser Algorithmus?
 ++++ Zu einfach? Zusatz-Zusatzaufgabe! |
-iefern beide Algorithmen immer das bestmögliche Ergebnis? Erkläre deine Antwort.
+Liefern beide Algorithmen immer das bestmögliche Ergebnis? Erkläre deine Antwort.
 ++++