Нагруженные графы. Расстояния в нагруженном графе

Определение: Граф G = (V, X) (орграф Д = (V, X)) называется нагруженным, если на множестве ребер (дуг) определена некоторая функция l: X → R , которую часто называют весовойфункцией.

Таким образом, в нагруженном графе (нагруженном орграфе) каждому ребру (дуге) x X поставлено в соответствие некоторое действительное число l(x).

Значение l(x) называется длинойребра (дуги) x или весом ребра (дуги) x.

Пример:

l( v₁, v₂)=3

l( v₂, v₃)=2

l( v₁, v₃)=7

Информацию о длинах дуг (ребер) нагруженного орграфа (графа) можно представить в виде матрицы длин дуг (ребер).

Определение: Матрицей длин дуг (ребер)орграфа Д (графа G) называется квадратная матрица порядка n С= [с_ij], у которой каждый элемент с_ij определяется следующим образом:

Определение: Пусть дан нагруженный граф G = (V, X) (орграф Д = (V, X)).

Рассмотрим некоторый маршрут (путь) из вершины v_i в вершину v_j. Обозначим его П, а сумму длин входящих в него ребер (дуг) обозначим l(П).

l(П) называется длиной маршрута (пути) П в нагруженном графе (орграфе) или весом маршрута (пути).

Пример: Пусть П – маршрут из v₁ в v₃.

П₁ = v₁ v₂ v₃ П₂ = v₁ v₃

l(П₁) = 3 + 2 = 5 l(П₂) = 7

Определение: Расстоянием в нагруженном графе (орграфе) (или взвешенным расстоянием) между вершинами v_i и v_j называется длина минимального маршрута (пути) из v_i в v_j.

Матрица взвешенных расстояний, взвешенные эксцентриситеты вершин, диаметр, радиус, центр нагруженного графа определяются аналогично определению данных понятий для ненагруженного графа.