Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:einfuehrung:start [09.11.2022 17:29] – Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:einfuehrung:start [09.11.2022 19:50] – Frank Schiebel
@@ Zeile 17: / Zeile 17: @@
   * Entscheide, ob es eine derartige Rundtour gibt. Gib die Rundtour gegebenenfalls an.
   * Entscheide, ob es möglich ist, eine einzige Strecke zu fahren, bei der jede Route genau einmal bedient wird. Gib an, von welchen Häfen aus dies möglich ist.
-  * (**) Kannst du angeben, unter welchen Voraussetzungen es eine Rundtour (Starthafen = Zielhafen) gibt, die alle Routen genau einmal abfährt?
+  * Kannst du angeben, unter welchen Voraussetzungen es eine Rundtour (Starthafen = Zielhafen) gibt, die alle Routen genau einmal abfährt?
 ++++ Lösungen |
@@ Zeile 44: / Zeile 44: @@
 ++++
-Zur Modellierung kommt also ein Modell zum Einsatz, welches die **Häfen** und die **Verbindungen zwischen den Häfen** umfassen muss. Allgemeiner kann man davon sprechen, dass man Knoten modellieren möchte, deren Verbindung mit Hilfe von Kanten dargestellt werden.
+Zur Modellierung kommt also ein Modell zum Einsatz, welches die **Häfen** und die **Verbindungen zwischen den Häfen** umfassen muss. Allgemeiner kann man davon sprechen, dass man **Knoten** modellieren möchte, deren Verbindungen mit Hilfe von **Kanten** dargestellt werden.
 Für unser Archipel sieht das so aus:
-{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:graph01.drawio.png |}}
+{{  :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:archipel.drawio.png  |}}
+Die Anordnung der Elemente auf der Zeichenfläche spielt dabei überhaupt keine Rolle, solange die Kanten und ihre Verbindungen gleich bleiben, modellieren wir dasselbe Archipel:
+{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:graph02.drawio.png |}}
+===== Definition:  Graph =====
+<WRAP center round important 90%>
+Ein **Graph** ist ein Gebilde, das aus **Knoten** und **Kanten** besteht. Jede Kante verbindet zwei Knoten oder einen Knoten mit sich selbst. Von einem Knoten können eine, mehrere oder keine Kanten ausgehen.
+Formal ist ein Graph also ein 2-Tupel, das aus einer Knotenmenge und einer Kantenmenge besteht und man schreibt:
+Graph ''G = (V,E)'' mit ''V'': Knotenmenge und ''E'': Kantenmenge
+</WRAP>
+{{ graph.drawio.png?400|}}
+Die Buchstaben sind aus den englischen Begriffen abgeleitet: V ist die Menge von Knoten (Vertices) und E die Menge der Kanten  (Edges).
+Das Bild rechts veranschaulicht die Begriffe, man erkennt dort auch, wie man die Kanten darstellen kann, indem man die verbundenen Knoten in runden Klammern  durch ein Komma getrennt angibt. In der Menge der Kanten fehlt (d,b), weil der Knoten d nicht mit dem Knoten b verbunden ist.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+Zeichne den folgenden Graphen: ''G=(V,E)'' mit ''V = {29,8,1,16,42,3}'' und ''E = {(8,42),(8,1),(16,8),(8,29),(1,16),(42,3),(29,42),(3,29)}''
+===== Weitere Begriffe =====
+==== Knotengrad ====
+<WRAP center round important 90%>
+Jeder Knoten hat die Eigenschaft "**Grad** des Knotens"
+Der Grad eines Knotens entspricht der Anzahl der Kantenenden, die mit dem Knoten verbunden sind.((Bei "gerichteten" Graphen muss man ein- und ausgehenden Grad unterscheiden, das kommt dann zu gegebener Zeit, fürs erste ist diese Definition ausreichend.))
+</WRAP>
+**Beispiele:**
+{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:grad01.png?400|}}
+<code>
+grad(C) = 2
+grad(A) = 3
+grad(4) = 3
+grad(1) = 4
+</code>
+===== Wege in Graphen =====
+{{tag> def:graph}}