Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:adjazenz [04.11.2022 09:59] – [Übungen für beide Gruppen] Mareike Nutz
+++ faecher:informatik:oberstufe:graphen:adjazenz [30.11.2022 20:17] (aktuell) – gelöscht Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== Repräsentation von Graphen ======
-{{ :faecher:informatik:oberstufe:graphen:grapheinstieg.drawio.png?200|}}
-==== Wie könnte man Graphen repräsentieren? ====
-{{:aufgabe.png?nolink  |}} (1A) Gruppe A: Betrachte den Graphen rechts. Wie könnte man diesen Graphen in einer Tabelle darstellen? Notiere deine Ideen und probiere sie aus!
-{{:aufgabe.png?nolink  |}} (1B) Gruppe B: Betrachte den Graphen rechts. Wie könnte man diesen Graphen in einer Liste darstellen? Notiere deine Ideen und probiere sie aus!
-==== Adjazenz - Was ist das? ====
-<blockquote>Wenn zwei Knoten über eine Kante miteinander verbunden sind, heißen diese Nachbarknoten, sie sind benachbart oder auch "adjazent".</blockquote>
-Bei ungerichteten Graphen sind alle verbundenen Knoten adjazent (siehe Abbildung rechts). Bei einem gerichteten Graphen hingegen nur die, die durch ...
-{{:aufgabe.png?nolink  |}}(2) In der Abbildung siehst du die Mitgliedsstaaten der EU. Manche der Staaten sind aufgrund gemeinsamer Grenzen adjazent. Erstelle einen Graphen einen Graphen der dieses Nachbarschaftsverhältnis wiedergibt.
-{{ :faecher:informatik:oberstufe:graphen:eu_mitgliedsstaaten.png?550 |}}
-<sub>//Quelle: Stefan Eling: https://www.hanisauland.de/wissen/spezial/politik/europaeische-union/europaeische-union-kapitel-1.html (10.10.2022).//</sub>
-==== Zwei mögliche Repräsentationen ====
-{{:aufgabe.png?nolink  |}} (3A) Wenn du in der Gruppe A bist, bearbeite bitte diese Seite: [[.:matrix|Adjazenzmatrix]]
-{{:aufgabe.png?nolink  |}} (3B) Wenn du in der Gruppe B bist, bearbeite bitte diese Seite: [[.:liste|Adjazenzliste]]
-==== Übungen für beide Gruppen ====
-Es folgen verschiedene Aufgaben. Um deine Lösungen zu überprüfen, kannst du folgendes Tool verwenden: [[https://graphonline.ru/de/]]
-++++ Kurzanleitung |
-  - **Graph -> Matrix:** Graph über ''Knoten hinzufügen'' und ''Knoten verbinden'' erstellen. Unter ''Graph>Adjazenzmatrix'' die Matrix anzeigen lassen.
-  - **Listen -> Graph:** [[https://graphonline.ru/de/create_graph_by_edge_list]] (Anleitung angegeben).
-  - **Matrix -> Graph:** Matrix eingeben unter ''Graph>Adjazenzmatrix'' oder [[https://graphonline.ru/de/create_graph_by_matrix]].
-  - **Graph -> Listen:** Leider nicht möglich! Selber denken! :)
-++++
-{{:aufgabe.png?nolink  |}} (4) Bisher haben wir uns nur gerichtete Graphen angeschaut. Nun wollen wir auch einen Blick auf die Repräsentationsformen von ungerichteten Graphen werfen.
-{{ :faecher:informatik:oberstufe:graphen:a4.drawio.png?500 |}}
-  * Betrachte die beiden Graphen und überführe sie in Adjazenlisten und -matrizen.
-  * Vergleiche die Adjazenzmatrizen von ungerichteten und gerichteten (aus Aufgabe 3) Graphen. Was fällt dir auf?
-++++ Das sollte euch aufgefallen sein! |
-Bei ungerichteten Graphen ist die Adjazenzmatrix symmetrisch zu ihrer Diagonalen.
-++++
-  * Vergleiche die Adjazenzmatrizen der beiden Graphen aus dieser Aufgabe. Was fällt dir auf?
-++++ Das sollte euch aufgefallen sein! |
-Die Matrizen sind identisch!
-<blockquote>Man sagt, zwei Graphen sind isomorph, wenn die Anzahl an Knoten und Kanten und deren Nachbarschaftsverhältnisse übereinstimmen. In ihrer Darstellung können die Graphen aber abweichen, also beispielsweise verzerrt oder verschoben sein. Beweisen lässt sich die Isomorphie zweier Graphem anhand identischer Adjazenzmatrizen.</blockquote>
-++++
-{{:aufgabe.png?nolink  |}} (5) gewichtet/ungewichtet
-{{:aufgabe.png?nolink  |}} (6) Kante/Knoten entfernen/einfügen
-{{:aufgabe.png?nolink  |}} (7) vollständiger Graph/Multigraph
-  * Wie sieht die Adjazenzmatrix eines vollständigen Graphen aus?
-  * Wie die eines Multigraphen?
-{{:aufgabe.png?nolink  |}} (8) Verschiedenes
-  * Wie könnte man eine Schlinge (Kante von einem Knoten zu sich selbst) darstellen?
-  * Woran kann man die Ordnung eines Knotens in einer Matrix und in den Listen erkennen?
-  * Woran erkennt man einen isolierten Knoten?
-++++ Das sollte euch aufgefallen sein! |
-Die Matrizen sind identisch!
-<blockquote>Man sagt, zwei Graphen sind isomorph, wenn die Anzahl an Knoten und Kanten und deren Nachbarschaftsverhältnisse übereinstimmen. In ihrer Darstellung können die Graphen aber abweichen, also beispielsweise verzerrt oder verschoben sein. Beweisen lässt sich die Isomorphie zweier Graphem anhand identischer Adjazenzmatrizen.</blockquote>
-++++
-====Effizienz- und Laufzeitanalyse====
-Die verschiedenen Repräsentationen der Graphen haben Vor- und Nachteile. Man kann z.B. den benötigten Speicherplatz und die Laufzeit für Zugriffsoperationen auf den Graphen bewerten.
-Dabei muss man Anwendungen unterscheiden, bei denen relativ **dünne** Graphen auftreten, und Anwendungen, bei denen der Graph (nahezu) **vollständig** ist. Repräsentiert der Graph z.B. eine Karte mit Straßen und Kreuzungen, gehen von jedem Knoten (= Kreuzung) nur wenige Kanten (= Straßen) ab. Mehr als 4-5 Straßen gehen üblicherweise nicht von einer Kreuzung aus. Diese Zahl ändert sich auch nicht, wenn die Anzahl der Knoten steigt. Der Graph ist also sehr dünn. Betrachtet man einen vollständigen Graphen, steigt bei einer Erhöhung der der Knotenzahl damit auch die Zahl der Kanten pro Knoten.
-===Effizienzanalyse (Speicherplatz)===
-Angenommen es geht um einen ungerichteten und gewichteten Graphen. Dann muss folgendes gespeichert werden:
-  * ''Adjazenzliste'': Zwei Zahlen (Nummer des Nachbarknoten, Entfernung) werden gespeichert.
-  * ''Adjazenzmatrix'': Eine Zahl (Entfernung) wird in jeder Zelle gespeichert (0 für keine Kante).
-{{:aufgabe.png?nolink  |}} (x) Ermittle anhand der Tabelle den Speicherbedarf für einen dünnen Graphen mit vier Kanten pro Knoten und einen vollständigen. Die Berechnung für fünf und mehr Knoten hilft dir dabei. Entscheide begründet welche Repräsentationsform im Sinne des Speicherbedarfs effizienter ist.
-^  Anzahl der Knoten  ^  dünner Graph (4 Kanten pro Knoten)                     ^^  vollständiger Graph                    ^^
-^  :::                ^  Adjazenzlisten                      ^  Adjazenzmatrix   ^  Adjazenzlisten       ^  Adjazenzmatrix  ^
-|  5                  |  5*4*2 = 40 Zahlen                   |  5*5 = 25 Zahlen  |  5*4*2 = 40 Zahlen    |  25 Zahlen       |
-|  6                  |                                      |                   |                       |                  |
-|  7                  |                                      |                   |                       |                  |
-|  8                  |                                      |                   |                       |                  |
-|  9                  |                                      |                   |                       |                  |
-|  n                  |                                      |                   |                       |                  |
-++++ Tipp |
-Knoten * Kanten * ?
-++++
-===Laufzeitanalyse===
-Wir betrachten wieder eine ungerichteten, gewichteten Graphen. Die Laufzeit einzelner Operationen hängt von der Art der Implementierung ab.
-  * Adjazenzliste: Ein Array enthält für jeden Knoten eine einfach verkettete Liste der Kanten.
-  * Adjazenzmatrix: Zweidimensionales Array.
-{{:aufgabe.png?nolink  |}} (x) Ermittle anhand der Tabelle die Laufzeiten für verschiedene Operationen auf einem dünnen Graphen mit vier Kanten pro Knoten und einem vollständigen. Entscheide begründet welche Repräsentationsform im Sinne der Laufzeit effizienter ist.
-^  Operation                    ^  dünner Graph (4 Kanten pro Knoten)                    |^  vollständiger Graph                    ||
-| :::                           ^  Adjazenzlisten                      ^  Adjazenzmatrix  ^  Adjazenzlisten       ^  Adjazenzmatrix  ^
-|  Länge einer Kante?           |  O(1)                                |  O(1)            |  O(n)                 |  O(1)            |
-|  Ausgangsgrad eines Knotens?  |                                      |                  |                       |                  |
-|  Einfügen Kante               |                                      |                  |                       |                  |
-|  Einfügen Knoten              |                                      |                  |                       |                  |
-|  Löschen Kante                |                                      |                  |                       |                  |
-|  Löschen Knoten               |                                      |                  |                       |                  |
-<sup>(Quelle: Verändert nach: ZPG Informatik, Schaller 2020)</sup>
-==== Reflexionsfragen ====
-{{:aufgabe.png?nolink  |}} (x) Diskutiere die Vor- und Nachteile beider Repräsentationsformen. Erstelle dazu eine Tabelle wie diese:
-|            ^ Adjazenzmatrix  ^ Adjazenzlisten  ^
-^ Vorteile   | - ...           | - ...           |
-^ Nachteile  | - ...           | - ...           |
-Implementation
-{{simplefilelist>:faecher:informatik:oberstufe:graphen:adjazenz:*}}