Yo'naltirilgan grafik nima va uning xususiyatlari…

Yo'naltirilgan grafik — bu tugunlar (vertexlar) va ularning yo'nalishi bo'lgan qirralar (aralar) to'plamidan iborat bo'lgan graf bo'lib, har bir qirra yo'nalishga ega.

Xususiyatlar:

Yo'naltirilgan qirralar: Qirra bo'ylab harakat faqat bir yo'nalishda, ya'ni ko'rsatilgan o'q bilan mumkin.
Vertexning darajasi: Yo'naltirilgan graf uchun kirish darajasi (vertexda tugashadigan qirralar soni) va chiqish darajasi (vertexdan boshlanadigan qirralar soni) aniqlanadi.
Yo'llar va sikllar: Yo'l — bu to'g'ri yo'nalishda bog'langan vertexlar ketma-ketligi. Sikl — bu boshlanishi va tugashi bir xil vertex bo'lgan yo'ldir. Yo'naltirilgan graflar yo'naltirilgan sikllarni o'z ichiga olishi mumkin.
Bog'liqlik: Zaif bog'liqlik (qirralarning yo'nalishlarini inobatga olmasdan, graf notog'ri bog'langan) va kuchli bog'liqlik (har qanday A va B vertexlari uchun, A dan B ga va B dan A ga yo'nalgan yo'l mavjud) ajratiladi.
Taqdimoti: Ular ro'yxat yoki matritsa shaklida taqdim etilishi mumkin, bunda yo'naltirilgan graf uchun matritsa odatda simmetrik emas.

Ro'yxat yordamida taqdim etish misoli:

# Graf G = (V, E), bunda V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Matritsa yordamida taqdim etish misoli:

# Graf G = (V, E), bunda V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matritsa = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # 2 dan chiqadigan qirra yo'q
]

Yo'naltirilgan grafik nima va uning xususiyatlari qanday?