Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:liste [24.10.2022 08:49] – angelegt Mareike Nutz
+++ faecher:informatik:oberstufe:graphen:liste [30.11.2022 19:35] (aktuell) – Frank Schiebel
@@ Zeile 1: / Zeile 1: @@
-====== Adjazenzliste ======
+====== Adjazenzlisten ======
-Eine Adjazenzliste ist eine Liste, in der die Nachbarschaftsverhältnisse von Knoten eingetragen werden. Jede Zeile steht für einen Knoten. Wenn dieser mit dem Knoten der Spalte verbunden ist, die beiden Knoten also adjazent sind, wird eine 1 eingetragen, ansonsten eine 0. Unten das Beispiel vom gerichteten Graphen von gerade eben.
-{{ :faecher:informatik:oberstufe:graphen:matrixeinstieg.drawio.png?400 |}}
+Graphen können mithilfe von Adjazenzlisten, die die Nachbarschaftsverhältnisse der einzelnen Knoten enthalten, repräsentiert werden. Für jeden Knoten wird dazu eine Liste mit seinen adjazenten, also benachbarten Knoten erstellt. Unten das Beispiel vom gerichteten Graphen von gerade eben.
+Zur Erinnerung: Die Nachbarn eines Knotens sind dabei alle Knoten seiner ausgehenden Kanten.
-In einer richtigen Adjazenzmatrix fehlen die erste Spalte und Zeile mit den Namen der Knoten. Durch die Vorgehensweise ist dennoch bekannt, welche Knoten adjazent sind und welche nicht.
+{{ :faecher:informatik:oberstufe:graphen:listeeinstieg.drawio.png?400 |}}
-{{:aufgabe.png?nolink  |}} (1) Erstelle für den folgenden Graphen eine Adjazenzliste.
+Die einzelnen Listen können zum Beispiel in einem Array mit der Länge der Anzahl der Knoten gespeichert werden.
-{{:aufgabe.png?nolink  |}} (2) Erstelle aus der folgenden Adjazenzliste einen Graphen.
+----
+{{:aufgabe.png?nolink  |}}
+=== A1 ===
+Erstelle für den folgenden Graphen seine Adjazenzlisten.
+{{ :faecher:informatik:oberstufe:graphen:a3_1.drawio.png?300 |}}
+----
+{{:aufgabe.png?nolink  |}}
+=== A2 ===
+Erstelle aus den folgenden Adjazenzlisten einen Graphen.
+{{ :faecher:informatik:oberstufe:graphen:a3_2liste.drawio.png?150 |}}
+----
+{{:aufgabe.png?nolink  |}}
+=== A3 ===
+Überlege dir einen Graphen und einen Satz Adjazenzlisten für deinen Partner. Erkläre ihm dann anhand der Aufgaben 1 und 2, was Adjazenzlisten sind und wie sie zu verstehen sind. Anschließend lässt du ihn zur Übung deine beiden hier entwickelten Aufgaben lösen.
-{{:aufgabe.png?nolink  |}} (3) Überlege dir einen Graphen und eine Adjazenzliste für deinen Partner. Erkläre ihm dann anhand der Aufgaben 1 und 2, was eine Adjazenzliste ist und wie sie zu verstehen ist. Anschließend lässt du ihn zur Übung deine beiden hier entwickelten Aufgaben lösen.
-++++ Spoiler |
-Du bekommst im Gegenzug auch Aufgaben! :)
-++++
 {{simplefilelist>:faecher:informatik:oberstufe:graphen:*}}