Repräsentation von Graphen

Wie könnte man Graphen repräsentieren?

(1A) Gruppe A: Betrachte den Graphen rechts. Wie könnte man diesen Graphen in einer Tabelle darstellen? Notiere deine Ideen und probiere sie aus!

(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?

Bei ungerichteten Graphen sind alle verbundenen Knoten adjazent (siehe Abbildung rechts). Bei einem gerichteten Graphen hingegen nur die, die durch …

(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.

Quelle: Stefan Eling: https://www.hanisauland.de/wissen/spezial/politik/europaeische-union/europaeische-union-kapitel-1.html (10.10.2022).

Zwei mögliche Repräsentationen

(3A) Wenn du in der Gruppe A bist, bearbeite bitte diese Seite: Adjazenzmatrix

(3B) Wenn du in der Gruppe B bist, bearbeite bitte diese Seite: 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/

(4)

Reflexionsfragen

Diskutiere die Vor- und Nachteile beider Repräsentationsformen. Erstelle dazu eine Tabelle wie diese:

Adjazenzmatrix	Adjazenzlisten
Vorteile	- …	- …
Nachteile	- …	- …

Implementation

[n/a: No match]