რა არის მიმართულებული გრაფი და რა არის მისი ძირითადი მახასიათებლები?

მიმართულებული გრაფი (ან დიგრაფი) არის მონაცემთა სტრუქტურა, რომელიც შედგება კვანძების (ნაკადების) და ამ კვანძებს დაკავშირებული მიმართულებული კიდეების (ხაზების)გან. თითოეულ ხაზს აქვს მიმართულება, რომელიც მიუთითებს, რომელი კვანძი არის საწყისი და რომელი — საბოლოო.

ძირითადი მახასიათებლები:

• კვანძები (Nodes / Vertices): გრაფის ელემენტები, რომლებიც წარმოდგენილია წერტილებით. მათ შეიძლება წარმოადგენდნენ ობიექტებს, მდგომარეობებს ან ეტაპებს.
• ხაზები (Edges / Arcs): კვანძებს შორის კავშირები. მიმართულებულ გრაფში, ხაზი აქვს მიმართულება, რომელიც მიუთითებს ერთ კვანძიდან მეორეზე გადასვლას. მათ წარმოაჩენენ როგორც წესრიგით დაწყვილებული (u, v), სადაც u არის საწყისი კვანძი, ხოლო v — საბოლოო.
• მიმართულება: ძირითადი მახასიათებელი, რომელიც განასხვავებს მიმართულებულ გრაფს არასამართებულიდან. მოძრაობა შესაძლებელია მხოლოდ ხაზის მიმართულებით. ხაზი A-დან B-მდე არ ნიშნავს, რომ B-დან A-მდე გადაადგილება შესაძლებელია, თუ არ არსებობს ცალკე ხაზი B-დან A-მდე.
• ლუპები (Loops): ხაზები, რომლებიც კვანძს უკავშირდება თავისით (v, v).
• მრავლობითი ხაზები (Multiple Edges): რამდენიმე ხაზი, რომლებიც ერთსა და იმავე წყვილ კვანძს უკავშირდება ერთსა და იმავე მიმართულებით. მარტივ მიმართულებულ გრაფებში, მრავალჯერადი ხაზები არ არის დაშვებული.
• გამოყოფილი კვანძები: კვანძები, რომლებსაც არ აქვთ შესასვლელი და გასასვლელი ხაზები.
• კვანძის ხარისხი:
  • შესასვლელი ხარისხი (In-degree): ხაზების რაოდენობა, რომლებიც შედიან კვანძში.
  • გასასვლელი ხარისხი (Out-degree): ხაზების რაოდენობა, რომლებიც გამოდიან კვანძიდან.

QA-ში გამოყენება:

• მდგომარეობის გრაფები, რათა გამოიცადოს საბოლოო ავტომატები.
• კონტროლის ნაკადის გრაფები, კოდის ანალიზისთვის და ტესტის შემთხვევების შექმნისთვის.
• სისტემებში დამოკიდებულებების მოდელირება (მაგალითად, სერვისებსა და მოდულებს შორის დამოკიდებულებები).
• გამოყენების სცენარების ტესტირება მკაცრი სექვენციებით მოქმედებების.