Материал: Потоки в сетях

Потоки в сетях

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИПММ

Кафедра Телематики при ЦНИИ РТК

Курсовая работа по Теории графов

по теме «Потоки в сетях»

Содержание

Задание

Описание математической модели

Особенности реализации

Распределение Пойа-1

Формирование связного ациклического графа

Алгоритм поиска потока минимальной стоимости

Алгоритм Фалкерсона

Алгоритм Беллмана - Форда

Алгоритм Дейкстры

Результаты работы программы

Заключение

Список использованной литературы

Задание

Сформировать связный ациклический граф случайным образом в соответствии с заданным распределением (Пойа-1).

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

В качестве величины потока брать значение, равное [2/3*max], где max - максимальный поток.

Матрицы пропускных способностей и стоимости сгенерировать случайным образом.

Реализовать алгоритмы Фалкерсона, Дейкстры и Беллмана - Форда.

Описание математической модели

поток граф алгоритм матрица

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

Функция  называется потоком в сети , если:

. то есть поток через дугу неотрицателен и не превосходит пропускной способности дуги;

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

Число называется величиной потока f. Если  то дуга  называется насыщенной.

Пусть paзpeз, .

Всякий разрез определяется разбиением множества вершин V на два подмножества S и Т, так что , а в Р попадают все дуги, соединяющие S и Т. Тогда  , где - дуги от S к Т,  - дуги от Т к S.

Сумма потоков через дуги разреза Р обозначается F(P).

Сумма пропускных способностей дуг разреза Р называется пропускной способностью разреза и обозначается С(Р):

Аналогично, и  суммы потоков через соответствующие части разрезов.

Для задач с потоками, граф G(V,E) должен удовлетворять условиям:- связный граф без петель.

Существует один исток.

Существует один сток.

Каждой дуге поставлена в соответствие пропускная способность дуги.

Теорема Фалкерсона. Максимальный поток в сети равен минимальной пропускной способности разреза:

Ищем максимальный поток минимальной стоимости: если , то решения нет (Ѳ - величина потока, который хотим найти).

Если наоборот, то минимизируем сумму:

Модификация сети относительно данного потока:

Модифицирующая относительно данного потока сеть строится следующим образом:

 ( - множество модифицированных вершин)

 (- множество фиктивных дуг)

Если (u,v)  Е и , то ; при этом  (только для дуг, по которым проходит поток).

  ;  и . (Только для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети).

Для всех насыщенных дуг: ; полагают, что

Особенности реализации

Задача состоит в реализации вычисления потока минимальной стоимости для сформированного графа в соответствии с заданным распределением (Пойа-1). Вначале мной формируется связный граф в соответствии с распределением. Затем вычисляется максимальный поток, с помощью реализованного алгоритма Фалкерсона и, в конечном итоге, вычисляется поток минимальной стоимости, с помощью алгоритма Беллмана - Форда и Дейкстры.

Распределение Пойа-1

Распределение Пойа 1 - распределение случайной величины, принимающей целые неотрицательные значения, в соответствии с формулами:

Где n>0, b>0, r>0, c - целые числа. Параметр с может быть отрицательным, однако он должен удовлетворять условию b+ r+c(n-1) > 0.

Рис. 1 Пример Распределение Пойа 1 (Вадзинский Р.Н. Справочник по теории вероятности. Санкт-Петербург., 2001. с. 88)

Генерирование случайных чисел

(Вадзинский Р.Н. Справочник по теории вероятности. Санкт-Петербург., 2001. с. 88)

Алгоритм реализует стандартный способ имитации моделирования дискретных случайных величин. Вероятность p0 = P(X=0) вычисляется по формуле (1) ( оператор (*)). Функция α(х) вычисляется по формуле α(х) = (n - 1 - x)[b + (x-1)c]/{x[r+(n-x)c]} (оператор (**)).

Алгоритм реализован с учетом того, что степень вершины графа не может быть равной 0 или n, и что сумма всех степеней графа первоначально должна быть четной. В алгоритме проводится проверка, и если х=0, вершине присваивается степень 1, а максимальная степень изначально может быть только у одной (чаще всего средней вершины).

Реализация алгоритма

vector<int> Valency(vector<int>vertex)

int b = 3, c = 1, key = 0, sum = 0;r = 20, p0 = 1;(int i = 1; i <= n; i++) //генерирование р = ро= p0*(r + (i - 1)*c) / (b + r + (i - 1)*c);(int v = 0; v < n; v++)

{p = p0, be = (n+1)*100./(1.05+v);x = 0, rafiky = be;= (rand()%rafiky)/100.; = r - p;(r > 0)

{(x < n - 1)

{++;= p* (n - 1 - x)*(b + (x - 1)*c) / (x*(r + (n - x)*c));= r - p;

}

{[v] = (n-2);break;

}

}(x == n-1)

{ (!key) // чтобы был один максимум

{[v] = n-2;++;

}

}(x == 0)[v] = 1;if(x != 0 || x < n-2)

vertex[v] = x;

// проверка на четность

sum += vertex[v];

}(sum & 1)

{-= vertex[n/2];(!key)

{[n/2] = n-1;+= vertex[n/2];++;

}

{[n/2]=rand()%(n-2)+1;+= vertex[n/2];

}

}vertex;}

Рис. 3 График функции вероятности распределения Пойа 1 для 100 вершин.

Формирование связного ациклического графа в соответствии с распределением Пойа 1

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

Принцип построения графа:

Граф строится ориентированный.

Функцией FindMax() выбирается вершина с наибольшей степенью на данный момент из массива степеней вершин (если степени равны, то берется та, чей номер меньше). Эта вершина вычеркивается из списка возможных связей. Из оставшихся вершин, не связанных еще с данной, функцией FindMax() выбирается вершина с максимальной степенью (если степени равны, то берется та, чей номер больше). Далее между собой сравниваются номера, выбранных для связи вершин, чей номер больше - от той вершины и будет исходить дуга. После каждой связи степень соединенных вершин уменьшается на 1. Алгоритм повторяется, до тех пор, пока все степени вершин не обнулятся.

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

Функция FindMax()

Эта функция находит номер вершины с максимальной степенью, в массиве степеней вершин. При этом, можно контролировать поиск максимума: можно брать минимальный или максимальный номер если есть несколько вершин с максимальной степенью.

int FindMax (vector<int>vertex, bool MorD)

{k = 0;n = vertex.size();(!vertex.at(k)) k++;(int j = 0; j < n; j++)

{(vertex.at(j) && k != j)

{(vertex.at(k) < vertex.at(j))= j;(vertex.at(k) == vertex.at(j) && !MorD)

k = j;

}

}k;

}

Реализация алгоритма построения связного ацикличного графа:

vector<vector<int>> MakeGraph()

{n = 1;

cout << endl << "Введите количество вершин (число должно быть целым, из промежутка [2;200]): ";

while (n < 2 || n > 200)

{= Check(n);

if (n < 2)<< endl << "\tНеправильно задано количество вершин! Введенное число меньше 2!"

<< "\n\t\t\t\tПопробуйте еще раз!\2\n\n";(n > 200)<< endl << "\tНеправильно задано количество вершин! Введенное число больше 200!"

<< "\n\t\t\t\tПопробуйте еще раз!\2\n\n";

}<int>vertex(n);= Valency(vertex);<vector<int>>graph(n);indexMax = FindMax(vertex, 1);=0;(vertex.at(indexMax) > 0)

{<int>temp = vertex;[indexMax] = 0;(int i = 0; i < graph.at(indexMax).size(); i++){(int j = 0; j < temp.size(); j++)

{(j == graph[indexMax][i] || j == -graph[indexMax][i])

{[j] = 0;;

}

}

}tS = 0;

for (int i = 0; i < temp.size(); i++) //проверка, не пустой ли темп

{(temp[i] == 0)++;

}(tS == temp.size()) //если пустой то делаем кратные связи

{= vertex;[indexMax] = 0;

}indexDn = FindMax(temp, 0);(indexMax > indexDn)(indexMax, indexDn);.at(indexMax).push_back(indexDn);graph.at(indexDn).push_back(-indexMax);.at(indexMax)--;.at(indexDn)--;= FindMax(vertex, 1);}<vector<int>>graphMatr(n, vector<int>(n));

for (int i = 0; i < graph.size(); i++) //легко переделать в матрицу смежности

{(int j = 0; j < graph.at(i).size(); j++)

{l = rand()%2;(graph[i][j] > 0)[i][graph[i][j]] = 1;

}h = 0;(int e = 0; e < i; e++)(graphMatr[e][i])

{=1;;

}

(i > 0 && !h)

{= rand()%i;[h][i] = rand() % 19 - 8;

}

}

Алгоритм поиска потока минимальной стоимости

Для нахождения минимальной стоимости заданного потока следует воспользоваться следующим алгоритмом:

Находим максимально возможный поток по теореме Фалкерсона, за исходный поток берем 2/3 максимального потока;

Находим минимальный путь из истока в сток сети в матрице стоимостей с помощью алгоритма Беллмана-Форда, в зависимости от чисел в матрице весов;

Пропускаем по найденному пути максимальный возможный поток для этого пути;

Из ребер матрицы пропускных способностей вычитаем величину потока, то есть устанавливаем остаточную пропускную способность этих ребер;

Для каждого обнуленного ребра в матрице пропускных способностей обнуляем ребро в матрице стоимостей;

Если текущий пропущенный поток меньше заданного переходим к шагу 1.

Реализация алгоритма:

void pot_min_st(vector<vector<int>> propSpos, vector<vector<int>> price, vector<int> s, vector<int> t, int max)

{n = propSpos.size(), maxB = max;;minPath, ti, tj, temp;temps, tempt;<vector<int>> rezult(n, vector<int>(n));<vector<int>> priceEtalon(price);<int> minP;(max)

{= Deykstra(price, s[0], t[0]);= 0;= 0;(int i = 0; i < s.size(); i++)(int j = 0; j < t.size(); j++)(min(minPath, Deykstra(price, s[i], t[j])) != minPath)

{= Deykstra(price, s[i], t[j]);= i;= j;

}= MakePath(price, minPath, s[ti], t[tj]);= propSpos[*minP.begin()][*++minP.begin()];(list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{++;(min(propSpos[*it][*jt], temp) != temp)= propSpos[*it][*jt];

}(temp > max) temp = max;

cout << endl << "Пускаем поток (" << temp << ")" << " по пути ";

ti = 0;<int>::iterator it;(it = minP.begin(); it != minP.end(); it++, ti++)

{<< *it + 1;(ti < minP.size()-1)

cout << "-";

}= 0;<< ". Стоимость данного потока ";

for (list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{++;+= price[*it][*jt] * temp;[*it][*jt] -= temp;[*it][*jt] += temp;(!propSpos[*jt][*it] && propSpos[*it][*jt])

{[*jt][*it] += temp;[*jt][*it] = -price[*it][*jt];

}(!propSpos[*it][*jt] && !rezult[*jt][*it])[*it][*jt] = 0;

}<< ti << endl;(max - temp)<< "Оставшийся поток равен " << max - temp << endl;

Save(price, "Промежуточная матрица стоимости");(propSpos, "Промежуточная матрица пропускной способности");

for (int i = 0; i < n; i++)(int j = i; j < n; j++)(price[i][j] < 0)[i][j] = 0;-= temp;

}rez = 0;(int i = 0; i < n; i++)(int j = i; j < n; j++)(rezult[i][j])+= rezult[i][j] * priceEtalon[i][j];

cout << endl << "Минимальная стоимость потока " << maxB << " равна " << rez;<< endl << "Все промежуточные матрицы стоимости и потоков сохранены в файл graph.txt";(rezult.size() < 25)(rezult, "\n\t\tНовая матрица потоков");<< endl << "Новая матрица потоков сохранена в файл graph.txt\n" << endl;

}

Алгоритм Фалкерсона

Алгоритм Форда - Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v)=0 для всех u,v ϵ V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

Пускаем через найденный путь (он называется увеличивающим путём) максимально возможный поток:

На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .

Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему - уменьшаем на .