183623 (629883), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

1) вершины первой группы не имеют предшествующих, а вершины последней группы не имеют последующих;

2) вершины любой промежуточной группы не имеют предков;

3) вершины одной и той же группы дугами не соединяются.

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

Мысленно вычеркивают все вершины и дуги, из них выходящие. В получившемся графе найдется хотя бы одна вершина, в которую не входит ни одна дуга. Этой вершине присваивается следующий по порядку номер. Сама вершина (или несколько вершин) образует вторую группу. Описанную процедуру повторяют до тех пор, пока все вершины не будут упорядочены и разобраны по группам.

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

Пример. Упорядочить вершины графа и построить граф, изоморфный данному.

Решение. Просматривая граф, замечаем, что вершина xB_6B не имеет предшествующих, так как в нее не входит ни одна дуга. Эта вершина относится к первой группе. Подобных вершин в данном графе больше нет. Исключим из рассмотрения эту вершину и дуги, из них выходящие. На рис. 1.6 пометим их одной черточкой. В оставшемся графе снова ищем вершины, в которые не входит ни ода дуга. Таковыми будут xB_{4 B}и xB_7B. Эти вершины образуют вторую группу. Обозначим второе вычеркивание двумя черточками. И так далее. На рис. 1.7 представлен упорядоченный граф. Вертикальными линиями показаны группы разбиения и на них отложены вершины, принадлежащие соответствующим группам. Далее эти вершины соединены, как на исходном графе.

Рис.1.6 Рис.1.7

4. Постановка задачи о максимальном потоке. Основные определения

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

Сеть — это взвешенный граф без циклов и петель, ориентированный в одном направлении от вершины, называемой источником, к вершине, называемой стоком.

На рис. 1.8 представлена сеть. Истоком I является вершина 1, стоком S –вершина 6. Представим, что по ребрам (i,j) сети направляется некоторое вещество (ресурс, информация и т.п.). В скобках указаны пропускные способности ребер. Первое число- это пропускная способность в прямом направлении (от вершины i к вершине j) и второе – в противоположном направлении.

Пропускная способность - максимальное количество вещества rB_ijB, которое можно пропустить по ребру (i,j). Количество xB_{ij B}вещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру. Считается, что если есть поток из вершины i в вершину j, то

xB_ijB = - xB_{ji B} (1.1)

Если поток по ребру (i,j) меньше его пропускной способности, т.е. xB_{ij B}< rB_ijB, то ребро называют ненасыщенным, если xB_{ij B}= rB_ijB, - насыщенным. Совокупность X = {xB_ijB} потоков по всем ребрам называют потоком по сети или просто потоком.

Поток по ребру не может превысить его пропускной способности, т.е.

(1.2)

где n – количество вершин сети.

Приведем основное положение в теории потоков, которое называют условием сохранения потока: для любой вершины, кроме истока I и стока S, количество поступающего вещества в эту вершину, равно количеству вещества, вытекающего из нее. В промежуточных вершинах потоки не создаются и не исчезают.

Математическая запись этого ограничения с учетом формулы (1.1) следующая:

(1.3)

Отсюда вытекает, что общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.

(1.4)

где j – конечные вершины ребер, исходящих из I;

i – начальные вершины ребер, входящих в S.

Линейную функцию f называют мощностью потока на сети. Сформулируем задачу о максимальном потоке: найти множество XP^{* P}= {xB_ijPB^*P} потоков xB_ijPB ^*P по всем ребрам (i,j) сети, которое удовлетворяет условиям (1.1) - (1.3) и доставляет линейной функции (1.4) максимальное значение.

Как видно из формулировки, это типичная задача линейного программирования.

Обратимся к рис. 1.8, где изображена сеть. Для этой сети пропускную способность представим в виде матрицы, используя цифры в скобках. Здесь n = 6 и числа образуют квадратную матрицу шестого порядка (табл. 1.1). Если вершины k и l не соединены, то rB_{kl B}= rB _lkB = 0. Сформировать матрицу чисел xB_ijB – это значит задать поток на сети, т.е. найти nP^{2 P}чисел, удовлетворяющих условиям (1.1) – (1.3). Рассмотрим полный путь 1 – 2 – 5 – 6.

Пропускная способность этого пути не больше 1 ед. и ограничивается ребром (2, 5), которое лежит на этом пути. Поток по этому пути мощностью в 1 ед. будет допустимым, и условии (1.1) – (1.3) должны выполняться для всех вершин и ребер этого пути.

Таблица 1.1

Рис. 1.8

Например, возьмем вершину 2 и проверим условие (1.3):

xB_21B + xB_25B = (-xB_21B) + xB_25B = (-1) + 1 = 0.

5. Разрез на сети

Представим некоторую сеть. Разобьем множество вершин сети на два непересекающихся подмножества A и B так, чтобы исток I попал в подмножество A, а сток S попал в подмножество B. В результате такого разбиения появляются ребра (i, j), конечные точки которых оказываются в разных подмножествах.

Совокупность ребер (i, j), начальные точки которых принадлежат подмножеству A, а конечные точки – подмножеству B, называют разрезом сети и обозначают A/B.

На рис. 1.9 изображена некоторая сеть. Стрелки указывают положительное направление потока. На сети произведено два разреза: I и II. При разрезе I образовалось два подмножества вершин сети: подмножество A = {1, 2} и B = {3, 4, 5}, а ребрами, образующим разрез, стали (1, 3), (1, 4), (2, 4). При разрезе II образовались подмножества A = {1, 2, 3, 4} и B = {5} с образующими разрез ребрами (3, 5) и (4, 5).

Рис. 1.9

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

Если на сети задан поток X = {xB_ijB} и разрез (A/B), то величина , представляющая сумму потоков по всем ребрам разреза, называется потоком через разрез.

Для разреза I R(I) = rB_13B + rB_{14 B}+ rB_24B = 6 + 2 + 1 = 9. X(I) = xB_13B + xB_14B + xB_24B = 4 + 2 + 0 = 6. Для разреза II – R(II) = 9, X(II) = 6.

В общем случае, если на сети задан поток X = {xij} и произведен разрез (A/B), то хотя бы одно ребро любого полного пути, идущего из истока в сток, будет обязательно принадлежать разрезу (A/B). Напомним, что величина потока по любому полному пути не превышает пропускную способность каждого его ребра, а потому величина X суммарного потока, стремящегося из истока в сток, не может повысить пропускную способность любого разреза сети, т.е.

(1.5)

В теории потоков утверждается, что если удастся построить на сети поток XP^{* P}= {xB_ijPB^*P}, величина которого равна пропускной способности некоторого разреза (A/B), то этот поток будет максимальным, а разрез обладать минимальной пропускной способностью. Ниже приводится теорема о максимальном потоке, имеющая большое прикладное значение.

Теорема Форда - Фалкерсона. На любой сети сети максимльная величина потока из истока I в исток S равна максимальной пропускной способности разреза, отделяющего I от S.

6. Алгоритм решения задачи о максимальном потоке

В разделе 4 был проведен расчет мощности потока, но ничего не было сказано о том, будет ли этот поток максимальным. Чтобы ответить на этот вопрос, необходимо исследовать этот поток.

Пусть задан некоторый поток X = {xij}. Разобьем сеть таким образом, чтобы к подмножеству A отошли исток I и все те вершины i, которые достигаются из истока I хотя бы по одному пути, состоящему из ненасыщенных ребер; к подмножеству B отнесем вершины, которые нельзя достичь из истока по ненасыщенным ребрам. При таком разбиении возникают две ситуации:

1) сток ;

2) сток .

Рассмотрим случай 1. Если , то

Построенное разбиение является разрезом A/B. По условию разбиения для любой вершины существует путь из истока в i, состоящий из ненасыщенных ребер, а для любой вершины такого пути нет. Отсюда следует, что любое ребро (i,j) разреза A/B будет насыщенным (иначе j принадлежало бы A), т.е. xij = rij. Просуммируем все эти равенства по всем и всем и получим

(1.6)

В этом равенстве слева – величина X потока через разрез, справа – пропускная способность R разреза A/B. Из равенства (1.6) по теореме Форда - Фалкерсона следует, что поток X = {xij} является максимальным.

Рассмотрим случай 2. Если то существует путь из ненасыщенных ребер, ведущий из истока в сток. По ребрам этого пути можно пропустить дополнительный поток величиной , где минимум берется по всем ребрам, входящими в этот путь. Потоки xB_ijB по всем остальным ребрам остаются без изменения. В результате мощность суммарного потока возрастет на величину и это будет новый поток X = {xB_ijPB^1P}.

Характеристики

Список файлов курсовой работы