Wat is een gerichte graaf en wat zijn de belangrijkste kenmerken ervan?

Een gerichte graaf (of digraaf) is een gegevensstructuur die bestaat uit een verzameling knooppunten (vertices) en een verzameling gerichte randen (bogen) die deze knooppunten verbinden. Elke rand heeft een richting die aangeeft welk knooppunt het beginpunt is en welk knooppunt het eindpunt.

Belangrijkste kenmerken:

• Knooppunten (Nodes / Vertices): Elementen van de graaf, weergegeven door punten. Ze kunnen objecten, toestanden of fasen vertegenwoordigen.
• Randen (Edges / Arcs): Verbindingen tussen knooppunten. In een gerichte graaf heeft de rand een richting die de overgang van het ene knooppunt naar het andere aangeeft. Ze worden weergegeven als een geordend paar (u, v), waarbij u het beginknooppunt is en v het eindknooppunt.
• Richting: Een kernkenmerk dat een gerichte graaf onderscheidt van een niet-gerichte. Beweging is alleen mogelijk langs de richting van de rand. Een rand van A naar B betekent niet dat je van B naar A kunt bewegen, tenzij er een aparte rand van B naar A bestaat.
• Lussen (Loops): Randen die een knooppunt met zichzelf verbinden (v, v).
• Meerdere randen (Multiple Edges): Meerdere randen die dezelfde paar knooppunten in dezelfde richting verbinden. In eenvoudige gerichte grafen zijn meerdere randen niet toegestaan.
• Geïsoleerde knooppunten: Knooppunten zonder inkomende of uitgaande randen.
• Knoopgraad:
  • In-graad (In-degree): Aantal randen die in een knooppunt binnenkomen.
  • Uit-graad (Out-degree): Aantal randen die uit een knooppunt vertrekken.

Toepassingen in QA:

• Toestandsgrafen voor het testen van eindige automaten.
• Stroomdiagrammen voor controleflow-analyse en het maken van testgevallen.
• Modellering van afhankelijkheden in systemen (bijvoorbeeld afhankelijkheden tussen services of modules).
• Testen van gebruiksscenario’s met strikte sequenties van acties.