Kas yra orientuotas grafas ir kokios yra jo pagrindinės savybės?

Orientuotas grafas (arba diagrāfs) — tai datu struktūra, sudaryta iš viršūnių (mazgų) ir orientuotų kraštinių (briaunų), jungiančių šias viršūnes. Kiekviena briauna turi kryptį, nurodančią, kuri viršūnė yra pradžia, o kuri — pabaiga.

Pagrindinės savybės:

• Viršūnės (Node / Vertex): Grafiko elementai, vaizduojami taškais. Gali žymėti objektus, būsenas ar etapus.
• Kraštinės (Edge / Arc): Ryšiai tarp viršūnių. Orientuotame grafike kraštinė turi kryptį, nurodančią perėjimą iš vienos viršūnės į kitą. Žymima tvarkinga pora (u, v), kur u — pradžios viršūnė, v — pabaigos viršūnė.
• Kryptis: Esminis bruožas, skiriantis orientuotą grafiką nuo neorientuoto. Perėjimas galimas tik pagal kraštinės kryptį. Kraštinė iš A į B nereiškia galimybės pereiti iš B į A, jei nėra atskiros kraštinės iš B į A.
• Sukryžiai (Loops): Kraštinė, jungiantį viršūnę su pačia savimi (v, v).
• Daugkartinės kraštinės (Multiple Edges): Kelios kraštinės, jungiančios tą pačią porą viršūnių tame pačiame krypties. Paprastame orientuotame grafike daugkartinės kraštinės nėra leidžiamos.
• Izoliuotos viršūnės: Viršūnės be įeinančių ir išeinančių kraštinių.
• Viršūnės laipsnis:
  • Įeinančių kraštinių skaičius (In-degree): Kiek įeinančių kraštinių turi viršūnė.
  • Išeinančių kraštinių skaičius (Out-degree): Kiek išeinančių kraštinių turi viršūnė.

Taikymas QA:

• Būsenų grafai galutinių automatų testavimui.
• Valdymo srautų grafai kodo analizei ir testų atvejų kūrimui.
• Priklausomybių modeliavimas sistemose (pvz., priklausomybės tarp paslaugų ar modulių).
• Naudojimo scenarijų testavimas su griežta veiksmų seka.