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