====== Einführung: Graphen ======

===== Schiffsverbindungen =====

==== Ausgangssituation ====


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


{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:archipel.png?450|}}


Die Regionalregierung eines Archipels hat eine Fähre angeschafft, die die vier Inseln des Archipels verbinden soll. Dabei sollen die abgebildeten Fährrouten bedient werden. Idealerweise sollte das Schiff immer wieder eine Rundtour fahren, bei der jede Fährverbindung einmal bedient wird. 

  * Entscheide, ob es eine derartige Rundtour gibt. Gib die Rundtour gegebenenfalls an.
  * Entscheide, ob es möglich ist, eine einzige Strecke (≠ Rundtour) 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?

++++ Lösungen |
  * Nein, eine solche Rundtour gibt es nicht.
  * Ja, es ist möglich, eine Strecke zu fahren, bei der jede Verbindung genau ein mal bedient wird, und zwar von Ulahi und Aruna aus.
  * Jeder Hafen muss eine gerade Anzahl von Fährrouten haben und alle Fährrouten müssen untereinander verbunden sein. Entferne z.B. die Verbindung Aruna-Ulahi, dann kannst du eine solche Runde fahren.
++++

==== Modellierung ====

Um derartige Fragestellungen in informatischen Systemen modellieren zu können, müssen wir
uns nun ein paar Gedanken machen.

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

Welche der folgenden Informationen sind wichtig für die Suche nach Rundtouren:
  * Name der Inseln
  * Größe der Inseln
  * Entfernung zwischen den Häfen
  * Welche Inseln sind mit Fährrouten verbunden?
  * genauer Verlauf der Fahrtroute

++++ Lösung| 
Man muss lediglich wissen, welche Häfen es gibt, und welcher Hafen mit welchem anderen verbunden ist.
++++

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: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 ====

  * 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>**. Ein Graph, in dem man keinen Zyklus finden kann, heißt **<color #22b14c>zyklenfrei</color>**.
  * Ein geschlossener Weg heißt **<color #22b14c>Kreis</color>** ,  d.h. Start- und Zielknoten sind gleich und jeder Knoten wird maxmimal ein mal durchlaufen 


==== Zusammenhang ====


<WRAP center round important 90%>
Wenn es in einem Graphen von jedem Knoten zu einem anderen einen Weg gibt, heißt der Graph **zusammenhängend**.

Einen zusammenhängenden Teilgraphen nennt man **Zusammenhangskomponente**.
 
Zusammenhängende, azyklische Graphen sind **Bäume**.

</WRAP>

{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:auswahl_376.png |}}

==== Eulerzug ====

{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:euler1.png?100|}}

<WRAP center round important 50%>
Ein Kantenzug, in dem jede Kante genau einmal vorkommt, heißt **Eulerzug**.

In einem gegebenen Graph gibt es einen Eulerzug wenn  
  * Der Graph zusammenhängend ist **und**
  * **Entweder:** Alle Knoten geraden Grad haben **oder:** genau zwei Knoten ungeraden Grad haben.

</WRAP>


==== Geschlossener Eulerzug ====

{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:euler2.png?130|}}

<WRAP center round important 50%>
Ein **geschlossener Eulerzug** ist ein Zyklus, in dem jede Kante genau ein mal vorkommt.

Ein Graph besitzt einen geschlossenen Eulerzug, wenn 
  * Der Graph zusammenhängend ist **und**
  * Alle Knoten geraden Grad haben

</WRAP>


===== Weiterführende Fragen =====

{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:auswahl_377.png?220|}}

Ein **<color #22b14c>vollständiger Graph</color>** hat eine Verbindung von jedem Knoten zu jedem
anderen.

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

  * Zeichne einen vollständigen Graphen mit drei und einen mit vier Knoten.
  * Entscheide, ob die Graphen mit drei, vier oder fünf Knoten einen geschlossenen Euler-Zug haben.
  * Gib eine allgemeine Regel an, wann ein vollständiger Graph einen geschlossenen Eulerzug hat.

----



Für viele Anwendungen verwendet man **<color #22b14c>gerichtete Graphen</color>**, d.h. die
Kanten haben eine Richtung (z.B. bei einem Stadtplan mit Einbahnstraßen). Bei einem Euler-Zug darf man die Kanten dann nur in der vorgegebenen Richtung durchlaufen.

Jeder Knoten hat dann einen **Ausgangsgrad** (wie viele Kanten gehen von einem Knoten aus) und einen **Eingangsgrad** (wie viele Kanten führen zu einem Knoten hin).
{{ :faecher:informatik:oberstufe:graphen:zpg:einfuehrung:auswahl_378.png?200|}}
----
{{:aufgabe.png?nolink  |}}
=== (A5) ===

   * Entscheide, ob der abgebildete Graph einen geschlossenen Euler-Zug hat.
   * Gib eine allgemeine Regel an, wann ein gerichteter Graph einen geschlossenen Euler-Zug hat.

===== Dateien =====


{{simplefilelist>:faecher:informatik:oberstufe:graphen:zpg:einfuehrung:*}}

{{tag> def:graph}}