Yönlendirilmiş grafik nedir ve özellikleri nelerdir?

Yönlendirilmiş bir grafik, bir küme düğüm (düğüm) ve bir küme kenar (oklar) içeren bir grafiktir ve her ok bir yön taşır.

Özellikler:

• Yönlendirilmiş kenarlar: Kenar boyunca hareket yalnızca bir yönde mümkündür, bu da bir ok ile gösterilir.
• Düğüm derecesi: Yönlendirilmiş grafiklerde, giriş derecesi (düğümde biten kenarların sayısı) ve çıkış derecesi (düğümden başlayan kenarların sayısı) tanımlanır.
• Yollar ve döngüler: Bir yol, doğru yönde bağlanan düğümler dizisidir. Bir döngü, aynı düğümde başlayıp biten bir yoldur. Yönlendirilmiş grafikler yönlendirilmiş döngüler içerebilir.
• Bağlılık: Zayıf bağlılık (kenarların yönleri göz ardı edilerek, grafik yönsüz bağlıdır) ve güçlü bağlılık (her iki düğüm A ve B için, A'dan B'ye ve B'den A'ya yönlendirilmiş bir yol vardır) arasında ayrım yapılır.
• Temsil: Komşuluk listeleri veya komşuluk matrisleri ile temsil edilebilir, burada yönlendirilmiş grafik için matris genellikle simetrik değildir.

Komşuluk listesi kullanılarak temsil örneği:

# Grafik G = (V, E), burada V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

grafik = {
    0: [1],
    1: [2],
    2: [0]
}

Komşuluk matrisi kullanılarak temsil örneği:

# Grafik G = (V, E), burada V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matris = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # 2'den çıkış yapan kenar yok
]