![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теорема Форда-Фалкерсона ⇐ ПредыдущаяСтр 3 из 3
В 1955 г. Форд и Фалкерсон доказали следующую теорему о максимальном потоке и минимальном разрезе. Теорема. Максимальная величина потока Доказательство. Докажем сначала, что величина любого потока не превосходит пропускной способности любого разреза:
где значения коэффициентов
5 1 6 4
Рис. 2. Возможные расположения концов произвольной дуги
1°. 2°. 3°. 4°. 5°. 6°. Для дуг шестого типа в сумму (3) добавим и вычтем Перепишем уравнение (3) в виде
откуда для любого потока и любого разреза
Отсюда следует, что максимальное значение потока в сети равно минимальному значению пропускных способностей разрезов этой сети:
|