Yönəldilmiş qraf nədir və onun xüsusiyyətləri nələrdir?

Yönəldilmiş qraf, vertexlər (düyünlər) və kənarların (oxların) olduğu və hər bir oxun istiqamətə malik olduğu qrafdır.

Xüsusiyyətlər:

• Yönəldilmiş oxlar: Ox boyunca hərəkət yalnız bir istiqamətdə mümkündür, bu da ox ilə göstərilir.
• Vertexin dərəcəsi: Yönəldilmiş qraf üçün giriş dərəcəsi (vertexdə bitən oxların sayı) və çıxış dərəcəsi (vertexdən başlayan oxların sayı) müəyyən edilir.
• Yollar və döngələr: Yol, düzgün istiqamətdə əlaqələndirilmiş vertexlər ardıcıllığıdır. Döngə, eyni vertexdə başlayıb bitən yoldur. Yönəldilmiş qrafda yönəldilmiş döngələr ola bilər.
• Qoşulma: Zəif qoşulma (oxların istiqamətləri nəzərə alınmadan, qraf qeyri-yönlü kimi qoşulmuşdur) və güclü qoşulma (hər iki vertex A və B üçün, A-dan B-yə və B-dən A-yə yönəldilmiş yol mövcuddur) ayırd edilir.
• Təqdimat: Onlar qonşuluq siyahısı və ya qonşuluq matrisləri ilə təqdim edilə bilər, burada yönəldilmiş qraf üçün matris ümumiyyətlə simmetrik deyil.

Qonşuluq siyahısı ilə təqdimat nümunəsi:

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

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

Qonşuluq matrisləri ilə təqdimat nümunəsi:

# Qraf 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-dən çıxan ox yoxdur
]