Определение 2.1.7. Пусть , – сечение сети. Тогда число называется пропускной способностью сечения

Определение 2.1.8. Сечение с минимальной пропускной способностью называется минимальным сечением.

Определение 2.1.9. Величина (для нетривиального потока) называется мощностью потока , т. е. поток из истока в сеть.

Определение 2.1.10. Поток максимальной мощности в сети называется максимальным потоком.

Лемма 2.1.1. Для любого потока и любого сечения справедливо неравенство:

,

т. е. мощность любого потока не превосходит пропускной способности сечения.

Доказательство:

(, т. е. – множество промежуточных узлов);

.

Теорема 2.1.1 (о максимальном потоке в сети). Мощность максимального потока равна пропускной способности минимального сечения, т. е. .

Лемма 2.1.2. Если – поток, – сечение, и при этом , то – максимальный поток, а
– минимальное сечение.

Доказательство.

1) Из Леммы 2.1.1

– максимальный поток.

2) Из Леммы 2.1.1 . Т. к. , то – минимальное сечение.

Определение 2.1.11. Пусть поток в сети . Будем говорить, что ребро , ненасыщенно потоком, если .

Определение 2.1.12. Путем из истока в сток будем называть последовательность ребер вида:

Определение 2.1.13. Будем говорить, что путь ненасыщен относительно потока , если каждое ребро пути не насыщено относительно потока, т. е.

, .

Обозначим – путь из узла в узел . Будем говорить, что путь ненасыщен потоком , если , .

Дата добавления: 2014-01-07