🎓 Ui, fast schon Prüfungszeit? Hier geht's zur Mathe-Prüfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Graph

Bild

Viele Probleme kannst du mithilfe von Graphen modellieren.

Wenn du ein Problem geeignet als Graph modelliert hast, kannst du die Standard-Algorithmen der Graphentheorie darauf anwenden und so die Lösung des Problems berechnen.

Ein Beispiel: Du modellierst das Straßennetz deiner Heimatstadt als einen Graphen. Dann brauchst du nur noch den Kürzeste-Wege-Algorithmus anzuwenden, wenn du von A nach B navigieren willst.

Ein Graph ist anschaulich dargestellt so etwas:

Bild

Formal gesehen besteht ein Graph aus einer endlichen, nichtleeren Menge VV von Knoten (die Kringel in der Darstellung) und einer Menge EE von Kanten (die Pfeile in der Darstellung).

Eine Kante ist eindeutig angegeben durch ihren Startknoten und ihren Endknoten. Damit lässt sich die Kante als Paar (u,v)(u, v) von zwei Knoten uu (dem Startknoten) und vv (dem Endknoten) angeben.

Der Graph aus der Abbildung besteht also aus der Knotenmenge V={0,1,2,3,4}V = \{0{,}1,2{,}3,4\} und der Kantenmenge E={(0,1),(0,2),(1,2),(2,0),(3,0)}E = \{ (0{,}1), (0{,}2), (1{,}2), (2{,}0), (3{,}0)\}.

Formal gesehen ist ein Graph ein Paar G=(V,E)G = (V,E), wobei VVeine endliche, nichtleere Menge von Knoten und E  V×VE ~\subseteq~ V\times V die Menge der Kanten ist. Die Kanten sind Paare von je zwei Knoten; die Menge der Kanten EE ist also eine Teilmenge des kartesischen Produkts V×VV \times V und damit eine Relation auf der Menge VV.

Diese Relation kannst du in Worten etwa mit "ist durch eine dorthin gerichtete Kante verbunden mit" ausdrücken.

Pfad, Weg

Wenn du in einem Graphen von einem Knoten uu entlang der Kanten zu einem Knoten vv gelangst, beschreitest du einen Pfad (oder Kantenzug). Achte darauf, dass du dabei die Kanten in Pfeilrichtung durchläufst.

Definition

Ein Pfad ist eine endliche Folge von Kanten (u0,v0)...(un1,vn1)(u_0, v_0) ... (u_{n-1},v_{n-1}), wobei jeweils vi1=ui  (i=1 ... n1)v_{i-1} = u_i ~ ~ (i = 1~ ... ~n-1) gilt. Die Kanten eines Pfades hängen also zusammen. Endknoten einer Kante ist jeweils Startknoten der folgenden Kante.

Die Anzahl nn der Kanten eines Pfades ist die Länge des Pfades.

Zum Beispiel ist p0=(3,0)(0,1)(1,2)(2,0)(0,1)p_0 = (3{,}0)(0{,}1)(1{,}2)(2{,}0)(0{,}1) ein Pfad der Länge 5 in dem oben gezeigten Graphen.

Definition

Ein Pfad heißt einfacher Pfad, wenn er keine Kante mehrfach durchläuft. Der Pfad p0p_0 ist kein einfacher Pfad, denn er durchläuft die Kante (0,1) mehrfach. Wenn du die letzte Kante von p0p_0 weglässt, erhältst du einen einfachen Pfad p1p_1.

Ein Pfad heißt Weg, wenn er keinen Knoten mehrfach durchläuft. Dies ist erfüllt, wenn alle uiu_i untereinander und alle vjv_j untereinander verschieden sind. Der Pfad p1p_1 ist zwar ein einfacher Pfad, aber kein Weg. Denn die Knoten vjv_j sind nicht alle untereinander verschieden, der Knoten 0 tritt zweimal auf. Wenn du die letzte Kante von p1p_1 weglässt, erhältst du einen Weg p2p_2.

Ein Pfad heißt Zyklus, wenn er geschlossen ist, wenn also sein Start- und Endknoten übereinstimmen.

Ein Zyklus, der ein Weg ist, heißt Kreis. Zum Beispiel ist der Pfad p3=(1,2)(2,0)(0,1)p_3 = (1{,}2)(2{,}0)(0{,}1) ein Kreis. Denn Start- und Endknoten stimmen überein, und alle uiu_i und alle vjv_j sind untereinander verschieden.

Baum

In der Informatik spielen Bäume eine herausragende Rolle. Denn viele Daten lassen sich als hierarchische Struktur modellieren, also als eine Struktur, die sich von einem Punkt aus verzweigt. Eine solche Struktur wird als Baum bezeichnet.

Definition

Ein (gerichteter) Graph ist ein Baum, wenn

  • er genau einen Knoten enthält, zu dem keine Kante hinführt,

  • zu jedem anderen Knoten genau eine Kante hinführt und

  • er keinen Kreis enthält.

Der folgende Graph ist ein Baum. Die Kanten sind von oben nach unten gerichtet.

Dagegen sind die folgenden Graphen keine Bäume, denn sie erfüllen jeweils nur zwei der oben angegebenen Bedingungen.


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?