Функции от множеств

Введем обозначения:

· Пусть , тогда для множества .

· Пусть , тогда для множеств .

Свойства функций от множеств:

· Если , то .

· Если , то .

· Если , то .

Свойства потока на множествах узлов:

· для любых ;

· для любого .

Определение 2.1.3. Узел называется истоком сети , если для любого нетривиального потока выполнено: .

Определение 2.1.4. Узел называется стоком сети , если для любого нетривиального потока выполнено: .

В дальнейшем будем предполагать, что в сети имеется единственный исток и единственный сток (т. е. любой поток в сети вытекает из истока и втекает в сток). Тогда, в силу кососимметричности потока, для всех выполняется

(2.1)

Определение 2.1.5. Узлы , такие что , и выполняется условие (2.1), называются промежуточными узлами.

Пример 2.1.2 (промежуточных узлов, см. рис. 2.1).

.

Определение 2.1.6. Пара множеств называется сечением сети , если выполнено: , , .

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