Какво е насочен граф и какви са основните му характеристики?

Посока граф (или диграф) е структура од податоци која се состои од множество на врвови (јазли) и множество на насочени ребра (арки) што ги поврзуваат овие врвови. Секое ребро има насока што покажува кој врв е почетен и кој е краен.

Главни карактеристики:

• Врвови (Nodes / Vertices): Елементи на графот претставени со точки. Могат да претставуваат објекти, состојби или фази.
• Ребра (Edges / Arcs): Врски меѓу врвовите. Во насочен граф, реброто има насока што покажува премин од еден врв на друг. Тие се претставени како уредена пар (u, v), каде u е почетниот врв, а v е крајниот.
• Насоченост: Клучна карактеристика што го разликува насочениот граф од ненасочениот. Движењето е можно само по насоката на реброто. Ребро од A до B не значи дека може да се движи од B до A, освен ако постои посебно ребро од B до A.
• Лупови (Loops): Ребра што ги поврзуваат врвот со itself (v, v).
• Многу ребра (Multiple Edges): Неколку ребра што ги поврзуваат истите парови врвови во истата насока. Во едноставните насочени графови, многу ребра не се дозволени.
• Изолирани врвови: Врвови без влезни и излезни ребра.
• Степен на врвот:
  • Влезен степен (In-degree): Бројот на ребра што влегуваат во врвот.
  • Излезен степен (Out-degree): Бројот на ребра што излегуваат од врвот.

Апликации во QA:

• Графови на состојби за тестирање на конечни автомати.
• Графови на текови на контрола за анализа на код и креирање на тест случаи.
• Моделирање на зависности во системите (на пример, зависности меѓу сервиси или модули).
• Тестирање на сценарија за користење со строги секвенци на акции.