Какво е ориентиран граф и какви са неговите характеристики?

Обърнат граф е граф, който има множество върхове (върхове) и множество ръбове (стрели), като всеки стрела има посока.

Характеристики:

• Обърнати ръбове: Движението по ръба е възможно само в една посока, посочена с стрелка.
• Степен на върха: За обърнат граф се определят входящата степен (броят на ръбовете, които завършват във върха) и изходящата степен (броят на ръбовете, които започват от върха).
• Пътища и цикли: Път е последователност от върхове, свързани с ръбове в правилната посока. Цикъл е път, който започва и завършва в един и същи връх. Обърнатите графи могат да съдържат обърнати цикли.
• Свързаност: Различават се слаба свързаност (игнорирайки посоките на ръбовете, графът е свързан като неориентиран) и силна свързаност (за всяка двойка върхове 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)}

matrica = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # няма изходящи ръбове от 2
]