Графи равшан ва хусусиятҳои асосии он чӣ гуна аст?

Графи рондашуда (ёки диграф) структураи маълумот мебошад, ки аз маҷмӯи нуқтаҳо (чорчӯбаҳо) ва маҷмӯи қирраҳои рондашуда (юлҳо) иборат аст, ки ин нуқтаҳоро мепайвандад. Ҳар як юл дорои самт аст, ки нишон медиҳад, ки кадом нуқта ибтидоӣ ва кадом охирӣ мебошад.

Хусусиятҳои асосӣ:

• Нуқтаҳо (Nodes / Vertices): унсурҳои граф, ки бо нуқтаҳо нишон дода шудаанд. Онҳо метавонанд объектҳо, ҳолатҳо ё марҳилаҳоро нишон диҳанд.
• Юлҳо (Edges / Arcs): пайвандҳо байни нуқтаҳо. Дар графи рондашуда, юл дорои самт аст, ки нишон медиҳад, ки гузариш аз як нуқта ба дигар. Инҳо ҳамчун ҷуфтҳои тартибдодашуда (u, v) нишон дода мешаванд, ки дар он u нуқтаи ибтидоӣ ва v нуқтаи охирӣ мебошад.
• Самт: хусусияти калидӣ, ки графи рондашударо аз графи бе самт фарқ мекунад. ҳаракат танҳо дар самти юл имконпазир аст. Юли аз A ба B маънои онро надорад, ки метавон аз B ба A ҳаракат кард, агар юл махсус аз B ба A вуҷуд надошта бошад.
• Даҳонҳо (Loops): юлҳое, ки нуқтаро бо худ пайваст мекунанд (v, v).
• Множество юлҳо (Multiple Edges): чанд юл, ки як ҷуфти нуқтаро дар ҳамон самт пайваст мекунанд. Дар графҳои оддӣ, юлҳои зиёд иҷозат дода намешаванд.
• Нуқтаҳои ҷудошуда: нуқтаҳое, ки юлҳои воридотӣ ва баромадӣ надоранд.
• Дараҷаи нуқта:
  • Дараҷаи воридотӣ (In-degree): шумораи юлҳое, ки ба нуқта ворид мешаванд.
  • Дараҷаи баромадӣ (Out-degree): шумораи юлҳое, ки аз нуқта баромад мекунанд.

Барномаҳо дар QA:

• Графҳои ҳолат барои санҷиши автоматҳоҳои маҳдуд.
• Графҳои ҷараёни назорат барои таҳлили код ва эҷоди ҳолатҳои санҷишӣ.
• Моделсозии вобастагиҳо дар системаҳо (масалан, вобастагиҳо байни хизматрасониҳо ё модулҳо).
• Санҷиши сценарийҳои истифода бо пайдарпайии қатъии амалҳо.