Багдарган граф жана анын өзгөчөлүктөрү эмнелер?

Бойондог граф — бул граф, анында түйүндөрдүн (вёрховдун) жана бурулуштардын (сүрөттөрдүн) жыйындысы бар, жана ар бир сүрөттүн багыты бар.

Өзгөчөлүктөрү:

• Багытталган бурулуштар: Бурулуш аркылуу кыймыл бир гана багытта мүмкүн, ал сүрөт менен көрсөтүлгөн.
• Вёрхтун даражасы: Бойондог граф үчүн кирүү даражасы (вёрхттө аяктап жаткан бурулуштардын саны) жана чыгуу даражасы (вёрхтөн башталган бурулуштардын саны) аныкталат.
• Жолдор жана циклер: Жол — бул туура багытта байланышкан вёрхттөрдүн тизмеси. Цикл — бул ошол эле вёрхттөн баштап аяктоо. Бойондог графтар багытталган циклерди камтышы мүмкүн.
• Байланыштык: Ашыкча байлангандык (бурулушдардын багыттарын эске албастан, граф эмес багытталган байланыштуу) жана күчтүү байлангандык (ар бир эки вёрхт A жана B үчүн, Aдан Bга жана Bдан Aга багытталган жол бар) айырмаланат.
• Өрнөк: Алар тизмелер же матрицалар аркылуу көрсөтүлүшү мүмкүн, жана бойондог граф үчүн матрица адатта симметриялык эмес.

Тизмелер менен көрсөтүүнүн мисалы:

# Граф G = (V, E), анда V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

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

Матрица менен көрсөтүүнүн мисалы:

# Граф G = (V, E), анда V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matrisa = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # 2ден чыгуу жок
]