|
На практике часто возникают задачи определения максимального количества товара, которое может быть перевезено от производителя потребителю. Аналогичными являются задачи определения максимальной пропускной способности системы автомагистралей, определения максимального количества нефти или газа, передаваемых по трубопроводам, информации, пропускаемой по компьютерной или телефонной сети. Формально эти проблемы сводятся к задаче построения максимального потока в сети. Для их решения необходимо ввести несколько понятий.
Пусть задана сеть S = (N, U) с множеством вершин N и множеством дуг U.
Определение. Дуга ueU, соединяющая вершины i N,j N сети S, называется допустимой дугой, если она обладает одним из следующих свойств:
1) направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности:
и = (i, j), (u) < с(и);
2) направление дуги противоположного направлению потока, и величина потока отлична от нуля:
u=(j,i), (u)>0.
Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, — уменьшающими.
Определение. Увеличивающей цепью, соединяющей вход и выход сети, называется простая цепь, все дуги которой являются
допустимыми.
Алгоритм построения максимального потока включает следующую последовательность:
1) задание начального значения потока. Удобно задавать нулевое начальное значение;
2) построение увеличивающей цепи от входа к выходу сети. Если такой цепи нет, то максимальный поток построен, и его величина в противном случае переходят к пункту 3;
3) увеличение вдоль построенной цепи значения потока на максимально возможную величину , при этом по каждой увеличивающей дуге поток увеличивается на , а по каждой уменьшающей дуге уменьшается.
Возврат к пункту 2.
Специалистам часто приходится изучать возможности сетей с незаданной жестко фиксированной ориентации, например, автомагистралей с двухсторонним движением с отсутствием сплошной разделительной полосы. Использование неориентированных сетей позволяет увеличить значение максимальных потоков по ним.
Построить максимальный поток в этом случае можно по следующему алгоритму:
1) заменить каждое ребро сети, не выходящее из источника и не входящее в сток, двумя противоположно направленными дугами, имеющими ту же пропускную способность, что и заменяемое ребро;
2) перейти к алгоритму построения максимального потока для ориентированной сети.
|
