Co je orientovaný graf a jaké jsou jeho hlavní charakteristiky?

Směrovaný graf (nebo digraf) je datová struktura skládající se z množiny vrcholů (uzlů) a množiny směrovaných hran (oblouků), které tyto vrcholy spojují. Každá hrana má směr, který ukazuje, který vrchol je počáteční a který koncový.

Hlavní vlastnosti:

• Vrcholy (Nodes / Vertices): Elementy grafu, zobrazené body. Mohou představovat objekty, stavy nebo fáze.
• Hrany (Edges / Arcs): Spojení mezi vrcholy. Ve směrovaném grafu má hrana směr, který ukazuje přechod z jednoho vrcholu na jiný. Jsou reprezentovány jako uspořádaný pár (u, v), kde u je počáteční vrchol a v je koncový.
• Směr: Klíčová vlastnost, která odlišuje směrovaný graf od nesměrovaného. Pohyb je možný pouze podél směru hrany. Hrana z A do B neznamená, že je možné se pohybovat z B do A, pokud neexistuje samostatná hrana z B do A.
• Smyčky (Loops): Hrany spojující vrchol se sebou samým (v, v).
• Vícenásobné hrany (Multiple Edges): Několik hran spojujících stejný pár vrcholů ve stejném směru. V jednoduchých směrovaných grafech nejsou vícenásobné hrany povoleny.
• Izolované vrcholy: Vrcholy bez vstupních a výstupních hran.
• Stupeň vrcholu:
  • Vstupní stupeň (In-degree): Počet hran vstupujících do vrcholu.
  • Výstupní stupeň (Out-degree): Počet hran vystupujících z vrcholu.

Použití v QA:

• Grafy stavů pro testování konečných automatů.
• Grafy toku řízení pro analýzu kódu a tvorbu testovacích případů.
• Modelování závislostí v systémech (například závislosti mezi službami nebo moduly).
• Testování scénářů použití s přísnými sekvencemi akcí.