Построение максимального потока в сетях с неориентированными дугами
Для построения максимального в сетях с неориентированными дугами поступают следующим образом: · каждую неориентированную дугу (ребро) сети, не выходящую из источника и не входящую в сток, заменяют парой противоположно направленных дуг с той же пропускной способностью, что и заменяемое ребро; · каждую неориентированную дугу с началом в источнике заменяют на ориентированную, выходящую из источника; · каждую неориентированную дугу с концом в стоке заменяют на ориентированную, входящую в сток; · применяют алгоритм построения максимального потока в сетях, изложенный в разделе 4.1. Пример сети с неориентированными дугами (BD и EF) и соответствующей ей сети с ориентированными дугами:
|
