Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:repraesentation:start [30.11.2022 21:03] – [Repräsentation von Graphen] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:repraesentation:start [30.11.2022 21:07] (aktuell) – Frank Schiebel
@@ Zeile 2: / Zeile 2: @@
   * [[.einstieg:start|Einstieg: Zwei Beispiele]]
-===== Einstieg: Modellierung mit Graphen =====
+  * Erarbeitung: Darstellung als [[.matrix:start|Adjazenzmatrix]] oder als [[.liste:Start|Adjazenzliste]]
+  * [[.uebungen1:start|Übungen]]
+  * [[.effizienz:start|Effizienzanalyse]]
-==== Situation 1 ====
-Modelliert werden sollen die Beziehung zwischen Personen, in diesem Beispiel festgelegt durch den Umstand, ob eine Person die Handynummer einer anderen Person kennt. In der Liste sieht man, wer welche Nummern gespeichert hat.
-{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:handy.png |}}
-==== Situation 2 (Traveling Salesman Problem) ====
-{{:faecher:informatik:oberstufe:graphen:zpg:repraesentation:karte.png |}}
-Ein Geschäftsmann aus Frankfurt muss Kunden in Berlin, Nürnberg und München beraten. Er möchte seine Rundreise so planen, dass er jeden Ort nur genau einmal besucht und die Gesamtfahrstrecke dabei möglichst klein bleibt. Dazu hat er die Entfernungen (in km) in einer Tabelle aufgeschrieben:
-{{:faecher:informatik:oberstufe:graphen:zpg:repraesentation:tabelle.png|}}
-~~CLEARFIX~~
-==== Aufgaben ====
-{{:aufgabe.png?nolink  |}}
-=== (A1) ===
-Beide Situationen sollen als Graph modelliert werden.
-  * Entscheide für beide Situationen, ob es sich um einen gerichteten oder ungerichteten Graphen handelt.
-  * Entscheide für beiden Situationen, ob es sich um einen gewichteten oder einen ungewichteten Graphen handelt.
-++++ Lösung |
-  * Situation 1: gerichteter, ungewichteter Graph
-  * Situation 2: ungerichteter, gewichteter Graph
-++++
-----
-{{:aufgabe.png?nolink  |}}
-=== (A2) ===
-Zeichne die Graphen für beide Situationen.
-++++ Lösung: |
-{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:lsg_telefon.png?400 |}}
-{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:lsg_staedte.png?400 |}}
-++++
-====== Begriffe ======
-Graphen können auf zwei Arten so dargestellt werden, dass sie von Rechnersystemen effizient verarbeitet werden können.
-  - Als **Adjazenzliste**
-  - Als **Adjazenzmatrix**
-<WRAP center round tip 90%>
-//Adjazenz// bedeutet in diesem Zusammenhang "//Nachbarschaft//".
-Wenn zwei Knoten über eine Kante miteinander verbunden sind, heißen diese Nachbarknoten, sie sind benachbart oder auch "adjazent".
-</WRAP>
-===== Erarbeitung =====
-  * {{:aufgabe.png?nolink  |}} (3A) Gruppe A: Bearbeite bitte diese Seite: [[.:matrix:start|Adjazenzmatrix]]
-  * {{:aufgabe.png?nolink  |}} (3B) Gruppe B:Bearbeite bitte diese Seite: [[.:liste:start|Adjazenzliste]]
-===== Übungen =====
-{{:aufgabe.png?nolink  |}}
-=== (A4)  ===
-Stelle folgende als Adjazenzmatrix oder Adjazenzliste gegebenen Graphen dar.
-{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:auswahl_412.png |}}
-++++ Lösung  |
-{{ :faecher:informatik:oberstufe:graphen:zpg:repraesentation:auswahl_413.png |}}
-++++
-----
-{{:aufgabe.png?nolink  |}}
-=== (A5)  ===
-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.
-++++