Yönəldilmiş qraf nədir və onun əsas xüsusiyyətləri hansılardır?

Yönəldilmiş qraf (və ya digraf) verilənlər quruluşudur və bu, bir çox düyün (nöqtələr) və bu düyünləri birləşdirən yönəldilmiş kənarların (yayların) toplusundan ibarətdir. Hər yayın istiqaməti var və bu, hansı düyünün başlanğıc və hansı düyünün son olduğunu göstərir.

Əsas xüsusiyyətlər:

• Düyünlər (Nodes / Vertices): Qrafın elementləri, nöqtələrlə təmsil olunur. Onlar obyektləri, vəziyyətləri və ya mərhələləri göstərə bilər.
• Yaylar (Edges / Arcs): Düyünlər arasında əlaqələr. Yönəldilmiş qrafda, yay bir düyündən digərinə keçidi göstərir. Bu, (u, v) ardıcıl cütü ilə göstərilir, burada u başlanğıc düyünü, v isə son düyünü göstərir.
• İstiqamət: Yönəldilmiş qrafı qeyri-yönəldilmişdən ayıran əsas xüsusiyyət. Hərəkət yalnız yay istiqamətində mümkündür. A-dan B-yə olan yay, B-dən A-yə hərəkət etməyi təmin etmir, əgər B-dən A-yə ayrıca yay yoxdursa.
• Dairələr (Loops): Öz-özünə bağlanan yaylar (v, v).
• Çoxsaylı yaylar (Multiple Edges): Eyni istiqamətdə eyni cüt düyünü birləşdirən bir neçə yay. Sadə yönəldilmiş qraflarda çoxsaylı yaylara icazə verilmir.
• İzolyasiya olunmuş düyünlər: Giriş və çıxış yayları olmayan düyünlər.
• Düyün dərəcəsi:
  • Giriş dərəcəsi (In-degree): Bir düyünə daxil olan yayların sayı.
  • Çıxış dərəcəsi (Out-degree): Bir düyündən çıxan yayların sayı.

QA-da tətbiqlər:

• Sonlu avtomatların sınağı üçün vəziyyət qrafikləri.
• Kodun analizi və test halları yaratmaq üçün idarə axını qrafikləri.
• Sistemlərdə asılılıqların modelləşdirilməsi (məsələn, xidmətlər və ya modullar arasındakı asılılıqlar).
• Qəti ardıcıllıqlarla istifadə ssenarilərinin sınağı.