Nima uchun yo'naltirilgan grafik va uning asosiy xususiyatlari qanday?

Yönlendirilган граф (ёки диграф) — бу маълумотлар тузилмаси бўлиб, у ўзига хос тўпламдаги вершина (нодлар) ва уларни боғловчи йўналтирилган қирралар (аркилар)дан иборат. Ҳар бир қирра ўз йўналишига эга бўлиб, қайси вершина бошланғич, қайси — охирги бўлишини кўрсатади.

Асосий хусусиятлар:

• Вершиналар (Nodes / Vertices): графнинг элементлари, нуқталар билан ифодаланган. Улар объектлар, ҳолатлар ёки босқичлар бўлиши мумкин.
• Қирралар (Edges / Arcs): вершина ўртасидаги боғловчи боғлар. Йўналтирилган графда, қирра йўналиши бўлиб, у бир вершинадан бошқага ўтишни кўрсатади. Улар тартибланган жуп (u, v) шаклида кўрсатилади, бу ерда u — бошланғич вершина, v — охирги.
• Йўналиш: йўналтирилган графни йўналмагандан ажратиб турадиган асосий хусусият. Ҳаракат фақат қирра йўналиши бўйича амалга оширилади. Aдан Bга бўлган қирра, Bдан Aга ҳаракат қилиш имкониятини бермайди, агар алоҳида Bдан Aга қирра бўлмаса.
• Луплар (Loops): ўз-ўзидан боғланган қирра (v, v).
• Кўп марта қирралар (Multiple Edges): бир йўналишда бир парда вершина боғловчи бир неча қирралар. Оддий йўналтирилган графларда, кўп марта қирраларга рухсат берилмайди.
• Изолланган вершина: кирувчи ва чиқувчи қирраларсиз вершина.
• Вершина даражаси:
  • Кириш даражаси (In-degree): бир вершинага кирувчи қирралар сони.
  • Чиқиш даражаси (Out-degree): бир вершинадан чиқувчи қирралар сони.

QAда қўлланишлари:

• Ҳолатлар графи, чеклов автоматларини синаш учун.
• Код таҳлили ва тест ҳолатларини яратиш учун бошқарув тўғрисидаги графлар.
• тизимларда боғлиқликларни моделлаштириш (масалан, хизматлар ёки модуллар ўртасидаги боғлиқликлар).
• Қатъий амаллар тартибидаги сценарийларни синаш.