Was ist ein gerichteter Graph und was sind seine Eigenschaften?

Ein gerichteter Graph ist ein Graph, der eine Menge von Knoten (Ecken) und eine Menge von Kanten (Bögen) hat, wobei jeder Bogen eine Richtung hat.

Eigenschaften:

• Gerichtete Kanten: Das Bewegen entlang des Bogens ist nur in eine Richtung möglich, die durch einen Pfeil angezeigt wird.
• Knoten-Grad: Für einen gerichteten Graphen werden der Eingangsgrad (Anzahl der Kanten, die am Knoten enden) und der Ausgangsgrad (Anzahl der Kanten, die am Knoten beginnen) definiert.
• Wege und Zyklen: Ein Weg ist eine Sequenz von Knoten, die durch Kanten in richtiger Richtung verbunden sind. Ein Zyklus ist ein Weg, der am selben Knoten beginnt und endet. Gerichtete Graphen können gerichtete Zyklen enthalten.
• Konnektivität: Es wird zwischen schwacher Konnektivität (unter Ignorieren der Richtungen der Kanten, ist der Graph ungerichtet verbunden) und starker Konnektivität (für beliebige zwei Knoten A und B existiert ein gerichteter Weg von A nach B und von B nach A) unterschieden.
• Darstellung: Sie können durch Nachbarschaftslisten oder Adjazenzmatrizen dargestellt werden, wobei die Matrix für einen gerichteten Graphen im Allgemeinen nicht symmetrisch ist.

Beispiel für die Darstellung mit Nachbarschaftsliste:

# Graph G = (V, E), wobei V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

graph = {
    0: [1],
    1: [2],
    2: [0]
}

Beispiel für die Darstellung mit Adjazenzmatrix:

# Graph G = (V, E), wobei V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matrix = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # keine ausgehenden Kanten von 2
]