Расширенные предельные сети.

Предельная сеть – сеть, состоящая из допустимых дуг.

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

Условие допустимости для прямой дуги: прямая дуга допустима до тех пор, пока поток по ней можно увеличить ().

Допустимость прямой дуги в сети обозначается знаком «+».

Условие допустимости обратной дуги: обратная дуга допустима до тех пор, пока поток по ней можно уменьшить (). Допустимость обратной дуги обозначается на исходной сети знаком «-».

Размерность потока строго большего нуля обозначает, что поток можно уменьшить до нуля, если , то дуга перестает существовать.

Дата добавления: 2015-07-15