====== Graphen ======
Graphen bestehen aus **Knoten** und **Kanten**. Kanten verbinden jeweils zwei Knoten. Kanten können **gerichtet** sein (d.h. sie können nur in einer Richtung durchlaufen werden, ähnlich wie eine Einbahnstraße) oder **ungerichtet** und sie können **Gewichte** besitzen (z.B. Länge einer Strecke). Die Gewichte werden an den Kanten notiert. Graphen, deren Kanten keine Gewichte besitzen, heißen **ungewichtet** (auch: **unbewertet**). \\ \\
**Folgen von Kanten**, die zwei Knoten verbinden heißen **Pfad**. Ein Pfad, dessen Anfangs- und Endknoten übereinstimmt heißt **geschlossener Pfad**. Ein Knoten A heißt von einem anderen Knoten B aus **erreichbar**, wenn es von B nach A einen Pfad gibt. **Ein geschlossener Pfad**, der **keine Kante zweimal** enthält, heißt **Zyklus**. Ein Graph, der **mindestens einen Zyklus** besitzt, heißt **zyklisch**. \\ \\
Ein **ungerichteter** Graph heißt **zusammenhängend**, wenn von jedem Knoten zu jedem anderen ein Pfad existiert. \\ \\
Ein **gerichteter Graph** heißt
* **stark zusammenhängend**, wenn von jedem Knoten zu jedem anderen ein Pfad existiert \\ (damit ist natürlich insbesondere gemeint, dass die Kanten in der vorgegebenen Richtung durchlaufen werden),
* **schwach zusammenhängend**, wenn er als ungerichteter Graph zusammenhängend wäre und
* ansonsten **unzusammenhängend** (auch bei ungerichteten Graphen).
==== Beispiel 1 ====
{{ :graphen:pasted:20211106-152145.png?300}}
Dieser Graph ist gewichtet (die Kantengewichte geben die Straßen-Distanz in Kilometern an), ungerichtet, zyklisch und nicht zusammenhängend. \\ \\
Knoten wie Helgoland in Beispiel 3, die zu keinem anderen Knoten eine Kante besitzen, heißen **isoliert**.
==== Aufgabe 1 ====
Beschreibe die folgenden Graphen mit möglichst vielen der obigen Fachwörter.
^a)^b)^c)^d)^e)^
| {{:graphen:pasted:20211106-143849.png?80}} | {{:graphen:pasted:20211106-144133.png?80}} | {{:graphen:pasted:20211106-144416.png?120}} | {{:graphen:pasted:20211106-144620.png?80}} | {{:graphen:pasted:20211106-145043.png?80}} |
[[.aufgabe1loesung:start|Lösung]]
{{ :graphen:pasted:20230915-111022.png?300}}
==== Aufgabe 2 ====
Derselbe Graph kann auf unterschiedliche Weise als Diagramm dargestellt werden. Welche der Diagramme im Bild rechts stellen denselben Graph dar? \\ \\
[[.aufgabe2loesung:start|Lösung]]
==== Aufgabe 3 ====
Nennen Sie je zwei Anwendungsbeispiele, die als gerichtete, ungerichtete oder gewichtete Graphen dargestellt werden können.