Čo je orientovaný graf a aké sú jeho hlavné charakteristiky?

Smerovaný graf (alebo digraf) je dátová štruktúra pozostávajúca z množiny vrcholov (uzlov) a množiny smerovaných hrán (oblúkov), ktoré tieto vrcholy spájajú. Každá hrana má smer, ktorý ukazuje, ktorý vrchol je počiatočný a ktorý koncový.

Hlavné vlastnosti:

• Vrcholy (Nodes / Vertices): Elementy grafu, zobrazené bodmi. Môžu predstavovať objekty, stavy alebo fázy.
• Hrany (Edges / Arcs): Prepojenia medzi vrcholmi. V smerovanom grafe má hrana smer, ktorý ukazuje prechod z jedného vrcholu na druhý. Sú reprezentované ako usporiadaný pár (u, v), kde u je počiatočný vrchol a v je koncový.
• Smer: Kľúčová vlastnosť, ktorá odlišuje smerovaný graf od nesmerovaného. Pohyb je možný iba pozdĺž smeru hrany. Hrana z A do B neznamená, že sa možno pohybovať z B do A, ak neexistuje samostatná hrana z B do A.
• Smyčky (Loops): Hrany, ktoré spájajú vrchol so sebou samým (v, v).
• Viacnásobné hrany (Multiple Edges): Viacero hrán spájajúcich ten istý pár vrcholov v rovnakom smere. V jednoduchých smerovaných grafoch nie sú viacnásobné hrany povolené.
• Izolované vrcholy: Vrcholy bez vstupných a výstupných hrán.
• Stupeň vrcholu:
  • Vstupný stupeň (In-degree): Počet hrán, ktoré vstupujú do vrcholu.
  • Výstupný stupeň (Out-degree): Počet hrán, ktoré vystupujú z vrcholu.

Použitie v QA:

• Grafy stavov na testovanie konečných automatov.
• Grafy toku riadenia na analýzu kódu a tvorbu testovacích prípadov.
• Modelovanie závislostí v systémoch (napríklad závislosti medzi službami alebo modulmi).
• Testovanie scenárov použitia so striktnými sekvenciami akcií.