Материал: Граф и его элементы

Понятия транспортной сети

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(ei), называемое пропускной способностью дуги, и существует:

- ровно одна вершина Vo = S, в которую не заходит ни одна дуга, называемая источником или началом сети;

- ровно одна вершина Vn=t, из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга e=(Vi,Vj) называется насыщенной потоком f, если f(Vi, Vj) = c(Vi, Vj)=c(e) (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

Понятие увеличивающая дуга, цепь, разрез

Рассмотрим данные понятия на примере:

Разрезом L сети S(N, U) называется множество насыщенных дуг, отделяющих источник s от стока t.

Пусть задана сеть S=(N, U) с множеством вершин N и множеством дуг U.

Определение: дуга u є U, соединяющая вершины i є N, j є N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:

а) направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:

u=(i, j), (u)<c(u) (1)

б) направление дуги противоположного направлению потока, и величина потока отлична от нуля:

u=(j, i), (u)>0 (2)

Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, - уменьшающими.

Увеличивающей цепью, соединяющей вход и выход сети, называется простая цепь, все дуги которой являются допустимыми.

Пример 1: построим увеличивающую цепь для сети S=(N, U), представленной на рисунке 10.

Рисунок 10 - увеличивающая цепь

Над каждой дугой указана ее пропускная способность, в скобках - поток по этой дуге.

Цепь (s, 1, 2, 4, t) является увеличивающей, так как все дуги - допустимые:

- дуга (s, 1) - увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности:

5 < 10;

- дуга (1,2) - также увеличивающая дуга: 12 < 15;

- дуга (2,4) - уменьшающая, так как она проходит против потока и поток по ней 3 > 0;

- дуга (4, t) - увеличивающая: 1 < 4.

Алгоритм Флойда-Уоршелл

Алгоритм Флойда является одним из методов поиска кратчайших путей в графе. В отличии от алгоритма Дейкстры, который позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины, метод Флойда позволяет найти длины всех кратчайших путей в графе.

Прежде чем представлять алгоритмы, необходимо ввести некоторые обозначения. Перенумеруем вершины исходного графа целыми числами от 1 до N. Обозначим через di,jm длину кратчайшего пути из вершинм i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа. (Напомним, что промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами.) Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=?. Из данного определения величин di,jm следует, что величина di,j0, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе). для любой вершины i положим di,im= 0. Отметим далее, что величина di,jmпредставляет длину кратчайшего пути между вершинами i и j.

Обозначим через Dm матрицу размера NxN, элемент (i, j) которой совпадает с di,jm. Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D0. Наша цель состоит в определении матрицы DN, представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.

В алгоритме Флойда в качестве исходной выступает матрица D0. Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрицав D2 и т. д. Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны:

1) кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

2) кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

3) кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин.

Поскольку по предположению исходный граф не может содержать контуров отрицательной длины, один из двух путей -- путь, совпадающий с представленным в пункте 3, или путь, являющийся объединением путей из пунктов 1 и 2 -- должен быть кратчайшим путем из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых m вершин. Таким образом,

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}, (3)

где di,jm - элемент матрицы Dm, di,jm-1 - элементы матрицы Dm-1 найденой на предыдущем шаге алгоритма.

Из соотношения видно, что для вычисления элементов матрицы Dm необходимо располагать лишь элементами матрицы Dm-1. Более того, соответствующие вычисления могут быть проведены без обращения к исходному графу. Теперь мм в состоянии датьформальное описание алгоритма Флойда для нахождения на графе кратчайших путей между всеми парами вершин.

Алгоритм:

1) перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ?. Кроме того, положить значения диагонального элемента di,iравным 0;

2) для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1элементы Dm;

3) алгоритм заканчивается получением матрицы всех кратчайших путей DN, N - число вершин графа. Для определения по известным элементам матрицы Dm-1 элементов матрицы Dm в алгоритме Флойда применяется рекурсивное соотношение указанное в формуле (3).

Постановка задачи

Найти путь наименьшей длины между вершинами 1 и 8. Построить коммуникационную сеть минимальной длины, используя Алгоритм Флойда-Уоршелл.

Рисунок 11 - Граф задачи с весом ребер

Решение задачи аналитическим методом

Обозначим через di,jm длину кратчайшего пути из вершины i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа.

На основании исходных данных формируем матрицу длин кратчайших дуг D0 (Таблица 1), каждый элемент которой равен длине кратчайшей дуги между вершинами i и j. Если такой дуги нет, положим значение элемента равным ?.

Таблица 1- Матрица D0

Представим матрицу D1 (Таблица 2). включив в нее рассчитанные элементы из приложения A.

Таблица 2- Матрица D1

Представим матрицу D2 (Таблица 3). включив в нее рассчитанные элементы из приложения.

Таблица 3 - Матрица D2

Представим матрицу D3 (Таблица 4). включив в нее рассчитанные элементы из приложения.

Таблица 4 - Матрица D3

Представим матрицу D4 (Таблица 5). включив в нее рассчитанные элементы из приложения.