3.7. Взвешенные графы

Определение. Граф (орграф) называется взвешенным (нагруженным), если каждой дуге x соответствует некоторое действительное число s(x).

Значение s(x) называется весом. В качестве весов могут выступать длины дуг, пропускная способность, стоимость эксплуатации и т. д. Для любого пути p нагруженного графа обозначим через s(p) сумму весов, входящих в p дуг, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь. Величина s(p) называется длиной пути p. Ранее так называлось количество дуг в пути не нагруженного графа, что соответствует случаю когда все веса равны 1.

Определение. Путь в нагруженном графе из вершины v_i в v_j , где v_i ≠ v_j, называется минимальным, если он имеет минимальную длину среди всех путей из вершины v _i в v_j.

Приведем некоторые свойства минимальных путей в нагруженных графах.

1) Если для x X, s(x) > 0, то любой минимальный путь является простой цепью.

2) Если v₁ v₂ … v_k – минимальный путь, то для любых номеров i, j таких, что 1≤ i ≤ j ≤ k, путь v_i v … v также является минимальным.

3) Если vi … v_m v_j – минимальный путь среди путей из вершины v_i в v_j, содержащих не более k+1 дуг, то v_i … v_m – минимальный путь среди путей из вершины v_i в v_m, содержащих не более k дуг.

Рассмотрим задачу поиска минимальных путей в нагруженном орграфе. Для графа поиск минимальных путей производится аналогично.

Замечание. Поиск максимальных путей сводится к поиску минимальных путей заменой знаков весов на противоположные.

Пусть G(V, X) – нагруженный орграф, V={v₁, …, v_n}, n ≥ 2. Введем величины z , где i = 1, …, n, k = 1, 2, … Для каждых фиксированных i и k величина z равна длине минимального пути среди путей из вершины v₁ в v_i, содержащих не более k дуг. Если таких путей нет, то z = ∞.

Кроме того, если произвольную вершину v_i считать путем из v_i в v нулевой длины, то величины z можно ввести также и для k = 0.

Тогда z = 0, z = ∞, i = 2, … , n. (3.12)

Введем в рассмотрение квадратную матрицу C(G) порядка n с элементами

которая называется матрицей длин дуг нагруженного орграфа.

Утверждение. При i = 2, …, n, k ≥ 0 выполняется следующее равенство

z = min ( z + c ), (3.13)

1≤j≤n

а при i = 1, k ≥ 0 справедливо равенство

z = min [ 0, min( z + c )]. (3.14)

1≤j≤n

Используя это утверждение можно найти таблицу значений величин z ,

где i – номер строки таблицы ( i = 1, …, n ), k + 1 – номер столбца таблицы

( k = 0, …, n-1 ).

Заполнять таблицу начинают с первого столбца (k = 0). Согласно (3.12) z = 0,

z = … = z = ∞.

Затем определяют значения второго столбца (k = 1). По формуле (3.14) z = 0. Остальные элементы второго столбца вычисляются по формуле (3.13).

Затем аналогично определяют элементы третьего столбца (k = 2) и т. д.

Замечание. Таблицу можно “ удлинить “ до необходимого количества столбцов, а не ограничиваться n столбцами.

Рассмотрим алгоритм, позволяющий по матрице длин дуг и таблице величин z , определить минимальный путь в нагруженном орграфе из вершины v₁ в любую достижимую вершину v_j, причем из всех возможных путей он выделяет путь с наименьшим числом дуг.