Qu'est-ce qu'un graphe orienté et quelles sont ses principales caractéristiques?

Un graphe orienté (ou digraphe) est une structure de données composée d’un ensemble de sommets (nœuds) et d’un ensemble d’arêtes orientées (arcs) reliant ces sommets. Chaque arête a une direction indiquant quel sommet est le point de départ et lequel est la destination.

Caractéristiques principales :

• Sommets (Nœuds / Vertices) : Éléments du graphe représentés par des points. Ils peuvent représenter des objets, des états ou des étapes.
• Arêtes (Edges / Arcs) : Connexions entre sommets. Dans un graphe orienté, l’arête a une direction indiquant la transition d’un sommet à un autre. Elles sont représentées par une paire ordonnée (u, v), où u est le sommet de départ et v le sommet d’arrivée.
• Orientation : Caractéristique clé distinguant un graphe orienté d’un non orienté. Le déplacement n’est possible que le long de la direction de l’arête. Une arête de A à B n’implique pas la possibilité de se déplacer de B à A, sauf s’il existe une arête séparée de B à A.
• Boucles (Loops) : Arêtes reliant un sommet à lui-même (v, v).
• Arêtes multiples (Multiple Edges) : Plusieurs arêtes reliant la même paire de sommets dans la même direction. Dans les graphes dirigés simples, les arêtes multiples ne sont pas autorisées.
• Sommets isolés : Sommets sans arêtes entrantes ni sortantes.
• Degré du sommet :
  • Degré entrant (In-degree) : Nombre d’arêtes entrantes dans un sommet.
  • Degré sortant (Out-degree) : Nombre d’arêtes sortantes d’un sommet.

Applications en QA :

• Graphes d’états pour tester des automates finis.
• Graphes de flux de contrôle pour l’analyse de code et la création de cas de test.
• Modélisation des dépendances dans les systèmes (par exemple, dépendances entre services ou modules).
• Test de scénarios d’utilisation avec des séquences strictes d’actions.