Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
ествуют пути из хi в хj и из хj в хi.
Пример.
2. Матричное задание графа. Упорядочение вершин
При большом числе вершин и дуг/ребер изображение графа теряет наглядность. В этих случаях для задания графов и работы с ними используют матрицы.
. Граф без петель, имеющий n вершин и m дуг/ребер можно задать матрицей инциденций, строки которой соответствуют вершинам, а столбцы - дугам. Элементы матрицы, размерности nm, определяются по формуле
+1, если дуга uj входит в вершину xi,
Для неориентированного графа вместо -1 ставится 1.
Пример.
. Граф можно матрицей смежности вершин, строки и столбцы которой соответствуют вершинам графа. Элементы матрицы Sij равны числу дуг/ребер, идущих из хi в хj. Матрица смежности для неориентированного графа будет симметричной.
Пример.
Аналогично может быть задана матрица смежности дуг/ребер.
Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.
Если существует путь из хi в хj, то вершина хi называется предшествующей вершине хj, а хj - последующей хi.
Упорядочение вершин связного графа без контуров означает разбиение его вершин на группы так, чтобы:
) вершины 1-й группы не имели предшествующих, а вершины последней - последующих;
) вершины любой другой группы не имели предшествующих в следующей группе;
) вершины одной и той же группы не соединялись с дугами.
Графический способ упорядочения вершин (алгоритм Фалкерсона).
1. Находятся вершины графа, в которые не входит ни одна дуга. Такие вершины образуют 1-ю группу.
. Вершины и выходящие из них дуги установленной группы исключаются из дальней- шего рассмотрения.
. Устанавливается следующая группа вершин, в которые не входит ни одна дуга.
. Если процесс упорядочения не окончен, то переход п. 2.
. В полученном графе, изоморфном исходному, перенумеровываются вершины.
3. Сети и потоки на сетях. Постановка задачи о максимальном потоке
Сеть - конечный взвешенный связный орграф без контуров и петель, ориентированный в одном общем направлении от вершины I (исток, вход) к вершине S (сток, выход).
Для наглядности представим, что по ребрам от истока к стоку направляется некоторое вещество (груз, ресурс, информация и т.п.).
Максимальное количество rij вещества, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае rij ? rji. Если вершины не соединены, rij = 0. Т.к. нет петель, то rii = 0. Пропускную способность можно задать квадратной матрицей.
Количество хij вещества, проходящего по ребру (i, j) в единицу времени, называется потоком по ребру (i, j). Предполагается, что если из хi в хj направляется поток хij , то из xj в xi направляется поток (-хij)
xij = - xji . (1)
Поток по каждому ребру не превышает его пропускную способность
xij rij (i = ; j = ) . (2)
Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё
(i I, S ). (3)
Совокупность Х = потоков по всем рёбрам сети называют потоком по сети. Общее количество вещества вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.
F = xIj = xiS. (4)
Функцию F называют мощностью потока.
Если на сети задан поток Х = , то ребро (i,j) называется насыщенным, если поток xij по нему совпадает с его пропускной способностью rij (xij = rij) , и ненасыщенным, если xij < rij .
Задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность Х* = {x*ij} потоков x*ij по всем рёбрам сети, которая удовлетворяет условиям (1) - (3) и максимизирует линейную функцию (4) . Это типичная ЗЛП.
Замечание. Не всякие n2 чисел могут задавать поток по сети. Только такие n2 чисел xij задают поток, которые удовлетворяют условиям (1) - (3) .
Пример.
4. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
Пусть дана некоторая сеть. Разобьём множество вершин сети на два непересекающихся множества А и В так, чтобы исток I попал в А, а сток S - в В. В этом случае на сети задан разрез. Совокупность ребер (i,j), начальные вершины которых принадлежат А, а конечные - В, называется разрезом сети (А/B).
Пропускной способностью разреза называют сумму пропускных способностей всех рёбер разреза R (A/B) = rij.
Сумма всех потоков xij по всем рёбрам разреза называется потоком через разрез
X(A/B) = xij.
Теорема Форда-Фалкерсона: на любой сети максимальная величина потока равна минимальной пропускной способности разреза.
Теорема позволяет определить максимальный поток для относительно простых сетей. В общем случае используют следующий алгоритм.
Алгоритм решения задачи о максимальном потоке.
1.Построить начальный поток Х = (чем больше величина выбранного потока, тем быстрее решается задача).
.На основе заданной сети строится новая сеть:
а) каждая дуга, для которой остаётся в новой сети с первоначальной rij;
б) каждая дуга для которой заменяется на две:
одна дуга того же направления с пропускной способностью rij-;
вторая дуга противоположенного направления с пропускной способностью .
. Если в новой сети можно найти ненулевой поток из I в S, то этот поток прибавляет-ся к начальному. В результате получается новый поток и переходят к п. 2.
Если же в новой сети отсутствуют ненулевые потоки из I в S, то максимальный поток сети построен.
Пример.
5. Элемент