Построение максимального потока в сетях с неориентированными дугами

Для построения максимального в сетях с неориентированными дугами поступают следующим образом:

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

· каждую неориентированную дугу с началом в источнике заменяют на ориентированную, выходящую из источника;

· каждую неориентированную дугу с концом в стоке заменяют на ориентированную, входящую в сток;

· применяют алгоритм построения максимального потока в сетях, изложенный в разделе 4.1.

Пример сети с неориентированными дугами (BD и EF) и соответствующей ей сети с ориентированными дугами:

Дата добавления: 2015-07-26; просмотров: 299; Нарушение авторских прав

Мы поможем в написании ваших работ!