Τι είναι ένα προσανατολισμένο γράφημα και ποια είναι τα βασικά χαρακτηριστικά του;

Ένα προσανατολισμένο γράφημα (ή digraph) είναι μια δομή δεδομένων που αποτελείται από ένα σύνολο κορυφών (κόμβων) και ένα σύνολο προσανατολισμένων ακμών (εξαρτημάτων) που συνδέουν αυτές τις κορυφές. Κάθε ακμή έχει μια κατεύθυνση που δείχνει ποια κορυφή είναι η αρχική και ποια η τελική.

Βασικά χαρακτηριστικά:

• Κορυφές (Nodes / Vertices): Στοιχεία του γραφήματος που αντιπροσωπεύονται από σημεία. Μπορούν να αντιπροσωπεύουν αντικείμενα, καταστάσεις ή στάδια.
• Ακμές (Edges / Arcs): Συνδέσεις μεταξύ κορυφών. Σε ένα προσανατολισμένο γράφημα, η ακμή έχει μια κατεύθυνση που δείχνει τη μετάβαση από μια κορυφή σε άλλη. Αναπαρίσταται ως ζεύγος (u, v), όπου u είναι η αρχική κορυφή και v η τελική.
• Κατεύθυνση: Χαρακτηριστικό που διαχωρίζει ένα προσανατολισμένο γράφημα από ένα μη προσανατολισμένο. Η κίνηση είναι δυνατή μόνο κατά μήκος της κατεύθυνσης της ακμής. Μια ακμή από A σε B δεν σημαίνει ότι μπορείς να μετακινηθείς από B σε A, εκτός αν υπάρχει ξεχωριστή ακμή από B σε A.
• Κύκλοι (Loops): Ακμές που συνδέουν μια κορυφή με τον εαυτό της (v, v).
• Πολλαπλές ακμές (Multiple Edges): Πολλές ακμές που συνδέουν το ίδιο ζεύγος κορυφών στην ίδια κατεύθυνση. Σε απλά προσανατολισμένα γραφήματα, οι πολλαπλές ακμές δεν επιτρέπονται.
• Απομονωμένες κορυφές: Κορυφές χωρίς εισερχόμενες ή εξερχόμενες ακμές.
• Βαθμός κορυφής:
  • Εισερχόμενος βαθμός (In-degree): Αριθμός ακμών που εισέρχονται σε μια κορυφή.
  • Εξερχόμενος βαθμός (Out-degree): Αριθμός ακμών που εξέρχονται από μια κορυφή.

Εφαρμογές σε QA:

• Γράφοι καταστάσεων για δοκιμές πεπερασμένων αυτομάτων.
• Γράφοι ροής ελέγχου για ανάλυση κώδικα και δημιουργία περιπτώσεων δοκιμής.
• Μοντελοποίηση εξαρτήσεων σε συστήματα (π.χ., εξαρτήσεις μεταξύ υπηρεσιών ή μονάδων).
• Δοκιμές σεναρίων χρήσης με αυστηρές ακολουθίες ενεργειών.