Yönlendirilmiş grafik nedir ve temel özellikleri nelerdir?

Yönlendirilmiş bir grafik (veya digraf), bir küme düğüm (kökler) ve bu düğümleri bağlayan yönlendirilmiş kenarlardan (yaylar) oluşan bir veri yapısıdır. Her yay, başlangıç ve bitiş düğümünü gösteren bir yön içerir.

Ana özellikler:

• Düğümler (Nodes / Vertices): Noktalarla temsil edilen grafik öğeleri. Nesneleri, durumları veya aşamaları gösterebilirler.
• Yaylar (Edges / Arcs): Düğümler arasındaki bağlantılar. Yönlendirilmiş grafikte, yay bir düğümden diğerine geçişi gösterir. (u, v) şeklinde sıralı bir çift olarak gösterilir, burada u başlangıç düğümüdür ve v bitiş düğümüdür.
• Yönlendirme: Bir yönlendirilmiş grafiği yönlendirilmemiş grafikten ayıran temel özellik. Hareket sadece yay yönünde mümkündür. A'dan B'ye olan bir yay, B'den A'ya hareket anlamına gelmez, eğer B'den A'ya ayrı bir yay yoksa.
• Döngüler (Loops): Kendisiyle bağlantılı yaylar (v, v).
• Çoklu yaylar (Multiple Edges): Aynı yönde aynı düğüm çifti arasında birden fazla yay. Basit yönlendirilmiş grafikte, çoklu yaylara izin verilmez.
• Yalıtılmış düğümler: Giriş veya çıkış yayları olmayan düğümler.
• Düğüm derecesi:
  • Giriş derecesi (In-degree): Bir düğüme giriş yapan yayların sayısı.
  • Çıkış derecesi (Out-degree): Bir düğümden çıkan yayların sayısı.

QA'da uygulamalar:

• Sonlu otomata testleri için durum grafikleri.
• Kod analizi ve test vakası oluşturma için kontrol akış grafikleri.
• Sistemlerde bağımlılıkların modellenmesi (örneğin, servisler veya modüller arasındaki bağımlılıklar).
• Katı sıralı eylem dizileriyle kullanım senaryolarının test edilmesi.