Šta je usmeren graf i koje su njegove osobine?

Оријентисани граф је граф који има скуп врхова (чворова) и скуп ивица (стрелица), при чему свака стрелица има смер.

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

• Оријентисане ивице: Према ивици се може кретати само у једном смеру, означеном стрелицом.
• Степен врха: За оријентисани граф се дефинишу улазни степен (број ивица које се завршавају у врху) и излазни степен (број ивица које почињу у врху).
• Путеви и циклуси: Пут је низ врхова повезаних ивицама у исправном смеру. Циклус је пут који почиње и завршава се у истом врху. Оријентисани графови могу садржати оријентисане циклусе.
• Повезаност: Разликују се слаба повезаност (игноришући смер ивица, граф је као неоријентисани повезан) и јака повезаност (за свака два врха 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
]