Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:graphen:graphen:einfuehrung [07.12.2021 20:27] – [Wege in Graphen] Mareike Nutz
+++ faecher:informatik:oberstufe:graphen:graphen:einfuehrung [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Einführung in die Datenstruktur Graphen ======
-===== "Auf den Spuren eines Handelsreisenden" =====
-Spielanleitung: [[https://www.youtube.com/watch?v=IDbbiNFjJeM]]
-----
-{{: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.
-===== Was ist ein Graph? =====
-{{ :faecher:informatik:oberstufe:graphen:graphen: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.
-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.
-{{: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)}''.
-==== Eigenschaften von Graphen ====
-**Multigraphen**
-Sind zwei Knoten durch mehrere Kanten verbunden, so spricht man von "Mehrfachkanten" und nennt die zugehörigen Graphen Multigraphen. Ein Graph ohne Mehrfachkanten wird als "einfacher Graph" bezeichnet.
-{{:aufgabe.png?nolink  |}} (2) Notiere, welche der folgenden Graphen Multigraphen sind.
-{{ :faecher:informatik:oberstufe:graphen:graphen:multi2.png?600 |}}
-<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:vollstaendigergraph.drawio.png?200|}}
-**Vollständigkeit**
-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.
-++++ Zu einfach? Knobelaufgabe!|
-Bestimme eine allgemeine Formel, um die Anzahl der Kanten in einem Graph mit //n// Knoten zu berechnen.
-++++
-----
-**Richtung**
-Die Kanten zwischen Knoten können eine Richtung haben, dann nennt man den Graph gerichtet. Die Richtung einer Kante wird durch eine Pfeilspitze am entsprechenden Ende angezeigt (siehe Abb. unten). Beispielsweise kann so die Fahrtrichtung einer Einbahnstraße angegeben werden.
-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.
-----
-{{ :faecher:informatik:oberstufe:graphen:graphen:gewichtetergraph.drawio.png?200|}}
-**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.
-{{: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 ====
-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:
-  * Einfache **Pfade**, auch Wege genannt, durchlaufen keine Kante mehrfach.
-  * Zyklische Pfade (**Zyklen**/Kreise) sind geschlossen. Das bedeutet, dass sie den gleichen Start- und Endknoten haben.
-Hier ist dies beispielhaft veranschaulicht:
-{{ :faecher:informatik:oberstufe:graphen:graphen:pfade.png?600 |}}
-<sub>Quelle: Magenheim et al. 2009, S.42)</sub>
-{{:aufgabe.png?nolink  |}} Zeichne einen Graphen mit folgendem Pfad:
-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  |}} 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.
-++++
-----
-<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:*}}