Czym jest graf skierowany i jakie są jego cechy?

Graf skierowany to graf, który ma zbiór wierzchołków (węzłów) i zbiór krawędzi (łuków), z których każda ma kierunek.

Cechy:

• Krawędzie skierowane: Poruszanie się po krawędzi jest możliwe tylko w jednym kierunku, wskazanym przez strzałkę.
• Stopień wierzchołka: Dla grafu skierowanego definiuje się stopień wejściowy (liczba krawędzi kończących się w wierzchołku) i stopień wyjściowy (liczba krawędzi zaczynających się w wierzchołku).
• Ścieżki i cykle: Ścieżka to sekwencja wierzchołków połączonych krawędziami w odpowiednim kierunku. Cykl to ścieżka zaczynająca się i kończąca w tym samym wierzchołku. Grafy skierowane mogą zawierać cykle skierowane.
• Połączenia: Rozróżnia się słabą spójność (ignorując kierunki krawędzi, graf jest spójny jak nieskierowany) i silną spójność (dla dowolnych dwóch wierzchołków A i B istnieje skierowana ścieżka z A do B i z B do A).
• Reprezentacja: Mogą być reprezentowane za pomocą list sąsiedztwa lub macierzy sąsiedztwa, gdzie dla grafu skierowanego macierz zwykle nie jest symetryczna.

Przykład reprezentacji za pomocą listy sąsiedztwa:

# Graf G = (V, E), gdzie V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Przykład reprezentacji za pomocą macierzy sąsiedztwa:

# Graf G = (V, E), gdzie V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

macierz = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # brak krawędzi wychodzących z 2
]