Informatik 11

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Graphen ======
<WRAP center round info 80%>
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).

</WRAP>

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

<HTML>
<div style="clear: both"></div>
</HTML>

==== Aufgabe 3 ====
Nennen Sie je zwei Anwendungsbeispiele, die als gerichtete, ungerichtete oder gewichtete Graphen dargestellt werden können.