Нахождение минимального пути в нагруженном графе.

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

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

Лекция № 10. Сети и потоки в сетях. Задача о максимальном потоке и минимальном сечении. Задача декомпозиции (разрезания) графа.

Условия, определяющие чертёж оригинала.

Если проецировать оригинал на плоскость прямолинейными лучами и условиться о положении наблюдателя то не трудно заметить, что получаемое изображение оригинала будет определяться двумя условиями:

1) При данном положении плоскости и направлении проецирования вид получаемого изображения будет зависеть от положения оригинала относительно плоскости проекции. (Например наши точки могут быть спроецированы в одну точку или как изображение точек А2 и В2);

2) При данном относительном положении плоскости проекции и оригинала вид изображения будет определятся, направлением проецирования при этом проецирование осуществляется параллельными лучами в заданном направлении.

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

Определение. Путь в нагруженном графе из вершины vi в vj , где vi ` vj, называется минимальным, если он имеет минимальную длину среди всех путей из вершины v i в vj.

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

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

2) Если v1 v2 … vk – минимальный путь, то для любых номеров i, j таких, что 1d i d j d k, путь vi v … v также является минимальным.

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

Определение. Назовём орграф нагруженным, если на множестве дуг определена некоторая функция , которую часто называют весовой функцией.

Тем самым и нагруженном орграфе каждой дуге поставлено в соответствие некоторое действительное число . Значение будем называть длиной дуги .

Для любого пути нагруженного орграфа обозначим через сумму длин входящих в дуг, при этом каждая дуга учитывается столько раз, сколько она входит в путь. Величину будем называть длиной пути в нагруженном орграфе. Ранее так называлось количество дуг в пути . В связи с этим заметим, что если длины дуг выбраны равными 1, товыражает введенную ранее длину пути в ненагруженном орграфе. Следовательно, любой ненагруженный орграф можно считать нагруженным с длинами дуг, равными 1. Аналогично определяется и нагруженный граф, а также длина маршрута в нем.

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

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

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

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

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

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

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

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

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

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

1djdn

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

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

1djdn

Используя это утверждение можно найти таблицу значений величин 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, определить минимальный путь в нагруженном орграфе из вершины v1 в любую достижимую вершину vj, причем из всех возможных путей он выделяет путь с наименьшим числом дуг.

Рассмотрим теперь задачу поиска минимальных путей (маршрутов) в нагруженном орграфе (графе). При этом для определенности рассуждения будем проводить для орграфа (для графа они аналогичны).

Пусть - нагруженный орграф, , . Введем величины , где , ..., , , ,... Для каждых фиксированных и величина равна длине минимального пути среди путем из в , содержащих не более дуг; если же таких путей нет, то =. Кроме того, если произвольную вершину считать путем из в нулевой длины, то величины можно ввести также и для , при этом