Разрез на сети

Максимальный поток определяется с помощью одного из основных понятий теории сетей – разреза.

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

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

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

Пропускной способностью или величиной разреза называется величина , которая определяется следующей формулой:

. (6.1)

Потоком через разрез называется величина , которая определяется следующей формулой:

. (6.2)

Пример 5.1. Рассмотрим сеть с заданными пропускными способностями дуг, которые записаны в круглых скобках, рис. 5.1.

Рис. 5.1

Построим на сети некоторый поток, величину которого по каждой дуге будем записывать без скобок:

путь : , значит, по этому пути пропускаем поток в 2 единицы;

путь : , значит, по этому пути пропускаем поток в 3 единицы;

путь : , значит, по этому пути пропускаем поток в 1 единицу.

Проведем на этой сети разрез , при котором вершины разбиты, например, на подмножества и . Тогда сам разрез, рис. 5.2, состоит из дуг: , , т.е.

.

Рис. 5.2

Пропускная способность данного разреза равна

(ед.),

а поток через этот разрез составляет:

(ед.).

,