faecher:informatik:oberstufe:graphen:zpg:repraesentation:uebungen1:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.

===== Übungen =====

{{:aufgabe.png?nolink  |}}
=== (A1)  ===

In der Abbildung siehst du die Mitgliedsstaaten der EU. Manche der Staaten sind aufgrund gemeinsamer Grenzen adjazent. Erstelle einen Graphen der dieses Nachbarschaftsverhältnis wiedergibt.

{{ .:eurokarte.png?600 |}}((Quelle: https://de.wikipedia.org/wiki/Datei:EU_Member_states_and_Candidate_countries_map.svg. Lizenziert unter [[https://creativecommons.org/licenses/by-sa/3.0/deed.de |Creative-Commons-Lizenz "Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert"]]))


{{:aufgabe.png?nolink  |}}
=== (A2)  ===
Stelle folgende als Adjazenzmatrix oder Adjazenzliste gegebenen Graphen dar.

{{ ..:auswahl_412.png |}}

++++ Lösung  |
{{ ..:auswahl_413.png |}}

++++
----
{{:aufgabe.png?nolink  |}}
=== (A3)  ===

Betrachte die Dateien graph1.csv und graph2.csv im Unterordner beispielgraphen/05_repraesentation des Graphen-Testers in einem Texteditor. Untersuche, wie die Graphen hier gespeichert sind.

++++ Lösung |
Beide Dateien beginnen mit einigen Basisinformationen über den Graphen, dann kommt der eigentliche Graph. graph1.csv enthält eine Adjazenzliste, graph2.csv eine Adjazenzmatrix. In beiden Formaten ist für jeden Knoten eine Zeile gespeichert. Neben den Kanten des Knoten ist noch die Position des Knotens abgespeichert. Die erste Zahl ist die x-Koordinate, die zweite Zahl die y-Koordinate. Das ist notwendig, um den Graphen zeichnen zu können, für die Algorithmen nicht. graph1.csv ist ein ungewichteter Graph. Daher sind nur die Nummern der Knoten angegeben, wohin die Kanten führen. Bei graph2.csv handelt es sich um einen gewichteten Graph. Daher sind die Matrixeinträge die Gewichte der Kanten.

++++