- •Часть 4. Элементы теории графов.
- • Понятия графа.
- • Способы задания графов.
- • Операции над графами.
- • Булевы матрицы и операции над ними.
- • Метод поиска в глубину.
- •Эйлеровы и гамильтоновы циклы.
- •Связность. Компоненты связности.
- •Матрица связности.
- •Транспортные сети.
- •Эйлеровы графы.
- •3. Для каждого из подмножеств уточняем оценки, вычитая из строчек и столбцов минимальные элементы и прибавляя вычтенные числа к предыдущей оценке:
- •Метод ветвей и границ.
- •Задача о потоках в сетях.
Задача о потоках в сетях.
Функция (x), определенная на множестве Х транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если :
1) для любой дуги xX величина (x), называемая потоком по дуге x, удовлетворяет условию ,
2) для любой промежуточной вершины сумма потоков по дугам, заходящим в равна сумме потоков по дугам, исходящим из .
Транспортной сетью называется орграф D=(V,X) с множеством врешин V={1,…,n} для которого выполняются условия:
1) существует одна и только одна вершина 1 называемая источником, таая, что D-1(1)= (т.е. ни одна дуга не заходит в 1);
2) существует одна и только одна вершина n, называемая стоком, такая, что D(n)= (т.е. из n не исходит ни одной дуги);
3) каждой дуге xX поставлено в соответствии целое число , называемое пропускной способностью дуги.
Величиной потока в транспортной сети D называется величина , равная сумме потоков по всем дугам, заходящим в n, или, что то же самое, - величина, равная сумме потоков по всем дугам, исходящим из 1.
Пусть - допустимый поток в транспортной сети D. Дуга xX называется насыщенной, если поток по ней равен ее пропускной способности, (x)=c(x). Поток называется полным, если любой путь в D из 1 в n содержит, по крайней мере, одну насыщенную дугу.
Поток называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D. Максимальный поток обязательно является полным.
Алгоритм построения полного потока:
Теорема Форда - Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.
Алгоритм нахождения максимального потока в сети:
1. Рисуем граф, совпадающий с исходным (граф приращений). На исходном графе пускаем нулевой поток.
2. Находим на графе приращений путь из начальной точки в конечную.
3. Если такого пути нет, то указанный на исходном графе поток является максимальным.
4. По найденному пути пропускаем максимально возможный поток, как на исходном графе, так и на графе приращений. На графе приращений на прямых дугах величину потока отнимаем, на обратных - прибавляем (обратные дуги при, необходимости добавляются искуственно). Идем к пункту 2.
Теорема Форда - Фалкерсона. Пусть D - транспортная сеть, - допустимый поток в этой сети V1 - множество вершин V таких, что длина минимального пути из в n в орграфе приращений равна нулю. Тогда, если 1V1, то - максимальный поток, величина которого равна .
Для заданной транспортной седи D и допустимого потока в этой сети орграф приращений I(D,) имеет те же вершины, что и сеть D. Каждой дуге x=(,)X транспортной сети D в орграфе приращений I(D,) соответствуют две дуги: x и x'=(,) - дуга, противоположная по направлению дуге x.
Припишем дугам x=(,)X, x'=(,) орграфа приращений I(D,) длину l:
то есть орграф I(D,) является нагруженным.