Разрез, лемма о потоке через разрез — различия между версиями
(→Поток через разрез) |
|||
Строка 23: | Строка 23: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Минимальным разрезом''' называется разрез с минимально возможной пропускной способностью | + | '''Минимальным разрезом''' (англ. ''minimum cut'') называется разрез с минимально возможной пропускной способностью |
}} | }} | ||
Версия 11:02, 15 декабря 2015
Определение разреза
Определение: |
Поток через разрез
Определение: |
Пропускная способность разреза | обозначается и вычисляется по формуле: .
Определение: |
Поток в разрезе | обозначается и вычисляется по формуле: .
Определение: |
Минимальным разрезом (англ. minimum cut) называется разрез с минимально возможной пропускной способностью |
Лемма: |
Пусть — разрез в . Тогда . |
Доказательство: |
|
Лемма (закон слабой двойственности потока и разреза): |
Пусть — разрез в . Тогда . |
Доказательство: |
, из-за ограничений пропускных способностей . |
Лемма: |
Если , то поток — максимален, а разрез — минимален. |
Доказательство: |
Из закона слабой двойственности следует, что для любых двух разрезов и в сети , так как . Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения. Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети . |
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
- Википедия: Разрез графа
- Википедия: Разрез графа (англ.)