Методы решения сетевых задач

Построение максимального потока

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

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

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

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

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

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

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

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

Над каждой дугой указана ее пропускная способность и в скобках — величина потока по этой дуге.

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

Рис. 4.19

  • • дуга (5, 1) — увеличивающая, гак как она проходит по направлению потока и поток по ней меньше ее пропускной способности (6 < 9);
  • • дуга (1,2) — также увеличивающая дуга (3 < 6);
  • • дуга (2, 4) — уменьшающая, так как она а) проходит против движения потока; б) поток по ней 2 > 0;
  • • дуга (4, t) — увеличивающая (4 < 7).

Построим увеличивающую цепь для сети, представленной на рис. 4.20.

Рис. 4.20

Цепь (s, 3, 2, t) — увеличивающая, так как все ее дуги являются допустимыми увеличивающими дугами.

Определение максимального потока основано на увеличении потока вдоль увеличивающей цепи на величину Дф.

Алгоритм построения максимального потока включает следующую последовательность:

  • 1) задание начального значения потока. Удобно задавать нулевое начальное значение (У0 = 0);
  • 2) построение увеличивающей цепи от входа к выходу сети. Если такой цепи нет, то максимальный поток построен, и его величина

в противном случае переходят к пункту 3;

3) увеличение вдоль построенной цепи значения потока на максимально возможную величину Дф, при этом по каждой увеличивающей дуге поток увеличивается па Дф, а по каждой уменьшающей дуге уменьшается на Дф.

Возврат к пункту 2.

Пример 4.3. Определим максимальный поток для сети (см. рис. 4.19). Начальный поток в сети задан, следовательно, пункт 1 алгоритма выполнен.

1. Увеличим поток вдоль цепи (s, 1, 2, 4, t).

Вдоль дуги (5,1) поток можно увеличить на разницу между пропускной способностью этой дуги 9 и уже проходящим по ней потоком 6 (9 - 6 = 3).

Вдоль дуги (1,2) аналогичным образом поток можно увеличить на 3 (6 - 3).

Дуга (2, 4) является уменьшающей. Максимальная величина, на которую можно уменьшить поток по ней, равна 2, т.е. значению уже проходящего потока.

По дуге (4, t) поток можно увеличить на 3 (7 - 4).

Таким образом, максимальная величина Дер, на которую можно увеличить поток, составляет наименьшую из величин

при этом на каждой увеличивающей дуге поток увеличивается на эту величину, а по каждой уменьшающей — уменьшается.

Новое значение при построении максимального потока записано в скобках над дугой (рис. 4.21).

Рис. 4.21

После такого перераспределения значение потока увеличилось на 2 и стало равным V = 11 (8 + 3 = 6 + 5), а условие сохранения потока в вершинах сети по-прежнему выполняется. Заметим, что если увеличить поток не на 2, а на 3, то на дуге (4, 2) получим отрицательное значение -1 (2 - 3), что противоречит свойству неотрицательности потока.

2. Рассмотрим теперь цепь ($, 1, 2, t).

Эта цепь увеличивающая, так как все дуги — допустимые. Поток вдоль этой цепи можно увеличить на

Новое значение потока указано во вторых скобках на рис. 4.21.

Заметим, что если допустить увеличение потока на 5, то поток по дугам (5,1) и (1,2) превзойдет пропускную способность этих дуг.

3. Затем рассмотрим цепь (s, 3, 4, t)

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

Минимальный разрез АЛ, соответствующий этому потоку, содержит дуги {(1, 2); (1,4); (3,4)}, а его пропускная способность 6 + 3 + 4 = 13 соответствует величине максимального потока.

Из примера следует, что значение Дф, на которое увеличивается поток вдоль увеличивающей цепи, определяется следующим образом:

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

Построить максимальный поток в этом случае можно по следующему алгоритму:

  • 1) заменить каждое ребро сети, не выходящее из источника и не входящее в сток, двумя противоположно направленными дугами, имеющими каждая ту же пропускную способность, что и заменяемое ребро;
  • 2) перейти к алгоритму построения максимального потока для ориентированной сети.

Пример 4.4. Построим максимальный поток для ориентированной сети, представленной на рис. 4.22.

Начальное значение потока равно нулю V = 0. Увеличивающие цепи:

  • 1) (s, 1, 2, t), Дф = min (8, 4, 10) = 4;
  • 2) (s, 1, 3, 4, t), Дф = min (8 - 4, 3, 2, 9) = 2. Больше увеличивающих цепей построить нельзя.

Рис. 4.22

Пример 4.5. Построим максимальный поток для неориентированной сети с той же структурой (рис. 4.23).

Рис. 4.23

Заменяя ребра двумя противоположно направленными дугами, строим максимальный поток в неориентированной сети (рис. 4.24).

Увеличивающие цени:

  • 1) (s, 1,2, t),Acp = 4;
  • 2) (s, 1, 3, 4, t), Аср = 3;
  • 3) (5, 3, 2, 0, Аф = 2;
  • 4) (5, 3, 4, 0, Аф = 2.

Больше увеличивающих цепей не существует. Максимальный поток Утах = 7 + 4 = 9 + 2=11. Оптимальная ориентация сети показана па рис. 4.25.

Рис. 4.24

Рис. 4.25

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >