Ce este un graf orientat și care sunt caracteristicile sale principale?

Un graf orientat (sau digraf) este o structură de date formată dintr-un set de vârfuri (noduri) și un set de arce orientate care leagă aceste vârfuri. Fiecare arc are o direcție care indică care vârf este cel inițial și care cel final.

Caracteristici principale:

• Vârfuri (Noduri / Vertices): Elemente ale grafului reprezentate prin puncte. Pot reprezenta obiecte, stări sau etape.
• Arce (Edges / Arcs): Conexiuni între vârfuri. Într-un graf orientat, arcul are o direcție care indică trecerea de la un vârf la altul. Sunt reprezentate ca un cuplu ordonat (u, v), unde u este vârful inițial și v cel final.
• Direcție: Caracteristică cheie care diferențiază un graf orientat de unul neorientat. Mișcarea este posibilă doar de-a lungul direcției arcului. Un arc de la A la B nu implică posibilitatea de a te deplasa de la B la A, dacă nu există un arc separat de la B la A.
• Cârcei (Loops): Arce care leagă un vârf de sine însuși (v, v).
• Arce multiple (Multiple Edges): Mai multe arce care leagă aceeași pereche de vârfuri în aceeași direcție. În grafurile simple orientate, arcele multiple nu sunt permise.
• Vârfuri izolate: Vârfuri fără arce de intrare sau ieșire.
• Gradul vârfului:
  • Gradul de intrare (In-degree): Numărul de arce care intră într-un vârf.
  • Gradul de ieșire (Out-degree): Numărul de arce care ies dintr-un vârf.

Aplicații în QA:

• Grafuri de stări pentru testarea automatelor finite.
• Grafuri de flux de control pentru analiza codului și crearea cazurilor de test.
• Modelarea dependențelor în sisteme (de exemplu, dependențe între servicii sau module).
• Testarea scenariilor de utilizare cu secvențe stricte de acțiuni.