Czym jest graf skierowany i jakie są jego główne cechy?

Skierowany graf (lub digraf) to struktura danych składająca się z zbioru wierzchołków (węzłów) i zbioru skierowanych krawędzi (łuków), które łączą te wierzchołki. Każda krawędź ma kierunek wskazujący, który wierzchołek jest początkowy, a który końcowy.

Główne cechy:

• Wierzchołki (Nodes / Vertices): Elementy grafu reprezentowane przez punkty. Mogą oznaczać obiekty, stany lub etapy.
• Krawędzie (Edges / Arcs): Połączenia między wierzchołkami. W grafie skierowanym krawędź ma kierunek wskazujący przejście z jednego wierzchołka do drugiego. Są oznaczane jako uporządkowana para (u, v), gdzie u to wierzchołek początkowy, a v to końcowy.
• Kierunek: Kluczowa cecha odróżniająca graf skierowany od nieskierowanego. Przemieszczanie się jest możliwe tylko wzdłuż kierunku krawędzi. Krawędź z A do B nie oznacza możliwości przemieszczania się z B do A, chyba że istnieje osobna krawędź z B do A.
• Pętle (Loops): Krawędzie łączące wierzchołek z samym sobą (v, v).
• Wielokrotne krawędzie (Multiple Edges): Kilka krawędzi łączących tę samą parę wierzchołków w tym samym kierunku. W prostych grafach skierowanych wielokrotne krawędzie nie są dozwolone.
• Izolowane wierzchołki: Wierzchołki bez krawędzi wejściowych i wyjściowych.
• Stopień wierzchołka:
  • Stopień wejściowy (In-degree): Liczba krawędzi wchodzących do wierzchołka.
  • Stopień wyjściowy (Out-degree): Liczba krawędzi wychodzących z wierzchołka.

Zastosowania w QA:

• Grafy stanów do testowania automatów skończonych.
• Grafy przepływu sterowania do analizy kodu i tworzenia przypadków testowych.
• Modelowanie zależności w systemach (np. zależności między usługami lub modułami).
• Testowanie scenariuszy użytkowania z ściśle określonymi sekwencjami działań.