Разрез, лемма о потоке через разрез
Эта статья находится в разработке!
Определение разреза
Определение: |
1) 2) 3) | -разрезом в сети называется пара множеств , удоволетворяющих условиям:
Поток через разрез
Определение: |
Пропускная способность разреза | обозначается и вычисляется по формуле: .
Определение: |
Поток в разрезе | обозначается и вычисляется по формуле: .
Лемма: |
Пусть - разрез в . Тогда . |
Доказательство: |
1-е равенство выполняется, так как суммы не пересекаются ( );2-е равенство выполняется из-за антисимметричности ( );3-е равенство выполняется, как и 1-е, из-за непересекающихся сумм; 4-е равенство выполняется из-за сохранения потока. |
Лемма (закон слабой двойственности потока и разреза): |
Пусть - разрез в . Тогда . |
Доказательство: |
, из-за органичений пропускных способностей ( ). |
Лемма: |
Если , то поток - максимален, а разрез - минимален. |
Доказательство: |
Из закона слабой двойственности следует, что для любых двух разрезов и в сети (так как ). Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения. Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети . |