Определения и основные понятия

Напомним, что 1). сеть – это связный ориентированный граф без петель и циклов; 2) вход – вершина сети, у которой , а выход – вершина сети , у которой ; 3) каждая дуга сети ориентирована от входа к выходу, то есть лежит на некотором пути от входа к выходу.

Определение 1. Вершину сети, не являющуюся входом или выходом будем называть промежуточной.

Определение 2. Пропускная способность – это неотрицательная функция (нагрузка) , заданная на множестве дуг сети .

Пусть - множество дуг, входящих в вершину и - множество дуг, выходящих из вершины . Далее без ограничения общности будем считать, что сеть имеет единственный вход и единственный выход .

Определение 3. Потоком называется такая числовая функция , что:

1). ; 2). ;

3). для любой промежуточной вершины .

Последнее условие называется условием неразрывности потока . Оно означает, что «сколько втекает в промежуточную вершину, столько из нее и вытекает».

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

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

Обозначим множество дуг с началом в и концом в .

Определение 6. Пусть ,и Ø. Назовем потоком из в величину . В случае величину назовем потоком из .

Таким образом, - поток из входа .

Замечание 1. Условие неразрывности имеет вид: для любой промежуточной вершины .

Определение 7. Разрезом сети называется разбиение множества вершин сети на два таких подмножества и , что:

1) Ø,

2) ,

3) вход , а выход .

Множество называется входным, а – выходным. Далее

Определение 8. Дуга называется разрезанной разрезом .

Множество всех разрезанных дуг обозначается .

Определение 9. Величину назовем потоком через разрез .

Замечание 2. Если , и , то .

Определение 10. Пропускной способностью разреза называется сумма пропускных способностей дуг этого разреза:

Определение 11. Разрез минимальной пропускной способности называется минимальным.

Определение 12. Дуга называется насыщенной, если .

Очевидно, что для ненасыщенной дуги .

Теорема 1. Для любого разреза справедливо равенство.

Доказательство проведем индукцией по мощности входного множества. При имеем, что и в силу замечания 1.

Пусть утверждение справедливо для всех и входное множество разреза имеетмощность (соответствующее выходное множествоимеет вид ). Рассмотрим разрез , где (следовательно, ) и . Тогда

. С другой стороны,

Отсюда следует, что

Здесь последнее равенство справедливо в силу замечания 1. Поскольку , то по предположению индукции , и, следовательно, . Теорема доказана.

Теорема 2. Мощность любого потока не превосходит пропускной способности любого разреза : .

Доказательство. Поскольку , то в силу теоремы 1 .

Теорема доказана.

Следствие. Если для потока и разреза справедливо равенство то – максимальный поток, а – минимальный разрез.

Доказательство очевидно.

Замечание 2. Если то все дуги разреза - насыщенные и . Действительно, если дуга ненасыщенная, то , и, следовательно, . Если же , то

.

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