Існують значні класи практичних завдань, які вирішити за допомогою розглянутих графів неможливо. Схема доріг і площ міста зображується за допомогою плоского графа. Але якщо цією схемою потрібно скористатися з метою проїзду по місту, а рух на окремих вулицях односторонній. Тоді можуть допомогти зорієнтуватися стрілки, розташовані прямо на ребрах.
Ребро графа називається орієнтованим, якщо одну з його вершин вважати початком, а іншу кінцем цього ребра.
Граф у якого всі ребра орієнтовані, називається орієнтованим графом.
Ребра орієнтованого графа мають певні фіксовані початок і кінець і називаються дугами. Vi Vj ¹ Vj Vi
Полустепені входу вершини орієнтованого графа називається число ребер, для яких ця вершина є кінцем. Позначається: deg + (V)
Полустепені виходу вершини орієнтованого графа називається число ребер, для яких ця вершина є початком. Позначається: deg - (V)
У орграфе маршрут є орієнтованим і називається шляхом.
Жодне ребро шляху не повинно зустрічатися двічі і напрямок кожної дуги повинен співпадати з напрямом шляху.
Шлях - це впорядкована послідовність ребер орієнтованого графа, в якій кінець попереднього ребра збігається з початком наступного і все ребра єдині.
# 8204; # 8204; # 8204; # 8204; # 8204; # 8204; | # 8204; АТ | = 3
Якщо в орієнтованому графі не можна «пройти» від вершини до іншої вершини, то відстань між ними називають нескінченним.
Вершина орієнтованого графа називається витоком. якщо в неї не входить жодна дуга, тобто d + (v) = 0.
Вершина орієнтованого графа називається стоком. з неї не виходить жодної дуги, тобто d- (v) = 0.
Матриця суміжності - це квадратна матриця розмірністю n * n, (де n-число вершин графа), однозначно представляє його структуру.
A =, i, j = 1,2. n, а кожен елемент матриці визначається наступним чином:
aij = 1, якщо ∃ дуга (Vi, Vj),
aij = 0, якщо немає дуги (Vi, Vj).
Відділення знаходиться на перехресті стоки і шпальти ставиться 1 або 0 в залежності від того. чи є дуга, що йде з мітки рядки в мітку стовпчика.
Рядки матриці інцидентності відповідають вершинам, а стовпці - ребрах або дуг.
Матриця інцидентності орієнтованого графа G - це матриця B = (bij) розміру n × m така, що
Нехай Vi і Vj - вершини орграфа G. Вершина Viдостіжіма з Vj. якщо існує (Vi, y)-шлях. Будь-яка вершина досяжна сама з себе. Вершини Vi і Vj сильно пов'язані, якщо вони досяжні одна з іншої.
Наприклад, для графа, зображеного на малюнку 25.2, вершини V2 і V3 сильно пов'язані, вершини V1 і V4 сильно пов'язані, вершина V6 досяжна з V1. але вершина V1 недосяжна з V6.
Компонентою сильної зв'язності графа G називається його сильно зв'язний підграф, який не є власним подграфом ніякого іншого сильно зв'язного подграфа графа орієнтованого G.
Граф, зображений на малюнку. 25.3 має три компоненти сильної зв'язності. Вони обведені пунктирними лініями.
Зауважимо, що існують дуги, які не належать жодній з компонент сильної зв'язності.
Досяжність в графі описується матрицею досяжності R = [rij], i, j = 1, 2. n, де n - число вершин графа, а кожен елемент визначається наступним чином:
rij = 1, якщо вершина хj досяжна з хi,
rij = 0, в іншому випадку.
Матриця контрдостіжімості Q = [qij], i, j = 1, 2. n, де n - число вершин графа, визначається наступним чином:
qij = 1, якщо з вершини xj можна досягти вершину xi,
qij = 0, в іншому випадку.
Матриця сильної зв'язності орієнтованого графа D - квадратна матриця S (D) = [sij] порядку n. елементи якої рівні