ебер.
Орграф D називається навантаженим , якщо на множині дуг Х визначена вагова функція - довжина дуги хГЋХ.
Шлях називається
мінімальним в навантаженому графі або орграфе, якщо він має мінімальну довжину шляху.
Матриця суміжності (графа, орграфа): А = [a ij ], V = {v 1 ..., v n },
X = {x 1 ..., x m }
В·
Матриця інцидентності : B = [b ij ]
(орграфа D)
В·
(графа G)
В·
Матриця досяжності T = [t ij ]
В·
Матриця зв'язності S = [s ij ]
(орграфа D)
(графа G)
Дерево - зв'язний граф без циклів
Остовне дерево графа (ОД) - будь-який зв'язний підграф зв'язного графа, що містить всі вершини і є деревом.
Мінімальна кістяк (МОД) - кістяк навантаженого графа з мінімальною сумою довжин дуг, що містяться в ньому.
Цикломатичне число зв'язного графа G (число циклів в базисі циклів графа), де n - кількість вершин, m - кількість ребер в графі .
Орієнтований граф
Назвемо ребра графа:
В
1. Характеристика графа
Орієнтований псевдографом D = (V, X).
V = {V0, V1, V2, V3, V4, V5}; X = {X0, X1, X2, X3, X4, X5, X6, X7}
X0 = , X1 = , X2 = , X3 = , X4 = , X5 = , X6 = , X7 =
. Спеціальні вершини і ребра
X7 - петля, X1, ...
