Wat is een gerichte graaf en wat zijn de kenmerken ervan?

Een gerichte graaf is een graaf die een verzameling knooppunten (vertices) en een verzameling randen (bogen) heeft, waarbij elke boog een richting heeft.

Kenmerken:

• Gerichte randen: Beweging langs de rand is alleen mogelijk in één richting, aangegeven door een pijl.
• Graaddoel: Voor een gerichte graaf worden de inkomende graad (het aantal randen dat eindigt in de knoop) en de uitgaande graad (het aantal randen dat begint in de knoop) gedefinieerd.
• Paden en cycli: Een pad is een reeks knooppunten verbonden door randen in de juiste richting. Een cyclus is een pad dat begint en eindigt in hetzelfde knooppunt. Gerichte grafen kunnen gerichte cycli bevatten.
• Verbinding: Men onderscheidt zwakke verbinding (de graaf is verbonden als ongerichte graaf, ongeacht de richtingen) en sterke verbinding (voor elk paar knooppunten A en B bestaat er een gerichte pad van A naar B en van B naar A).
• Representatie: Ze kunnen worden weergegeven met behulp van lijsten van buren of matrices van buren, waarbij de matrix voor een gerichte graaf over het algemeen niet-symmetrisch is.

Voorbeeld van representatie met behulp van een adjacency list:

# Graaf G = (V, E), waarbij V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Voorbeeld van representatie met behulp van een adjacency matrix:

# Graaf G = (V, E), waarbij 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]   # geen uitgaande randen van 2
]