Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:einfuehrung:start [09.11.2022 17:43] – [Definition: Graph] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:einfuehrung:start [09.11.2022 20:08] – [Wege in Graphen] Frank Schiebel
@@ Zeile 48: / Zeile 48: @@
 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:
@@ Zeile 68: / Zeile 70: @@
 {{ 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 ====
+Wenn man sich über Wege in Graphen unterhalten möchte, muss man sprachlich einige Dinge sehr genau unterscheiden, damit keine Missverständnisse entstehen.
+  * Mit dem Begriff **<color #22b14c>Kantenzug</color>** bezeichnen wir einen Pfad durch den Graphen, bei dem Knoten/Kanten auch **mehrfach** durchlaufen werden dürfen.
+  * Mit dem Begriff **<color #22b14c>Weg</color>** bezeichnen wir einen Pfad durch den Graphen, bei dem jeder Knoten höchstens ein Mal durchlaufen wird.
+  * Startet ein Kantenzug oder Weg am selben Knoten wie er endet, **sind** also **Start- und Endknoten identisch**, bezeichnet man den Kantenzug/der Weg als **<color #22b14c>geschlossen</color>**.
+  * Ein **geschlossener Kantenzug** heißt **<color #22b14c>Zyklus</color>**
+{{tag> def:graph}}