из фундаментальных
из фундаментальных фактов теории потоков в сетях является классическая теорема о максимальном потоке и минимальном разрезе. Разрезом называют множество дуг, удаление которых из сети приводит к “разрыву” всех путей, ведущих из s в t. Пропускная способность разреза - это суммарная пропускная способность дуг, его составляющих. Разрез с минимальной пропускной способностью называют минимальным разрезом.
Теорема (Форд и Фалкерсон). Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего s и t, причем существует поток, достигающий этого значения.
Теорема устанавливает эквивалентность задач нахождения максимального потока и минимального разреза, однако не определяет метода их поиска.
Пример. Показана сеть, источник - вершина 1, сток - вершина 6, в круглых скобках у дуг указаны их пропускные способности. Минимальный разрез - дуги (1, 2) и (3, 4), следовательно, согласно теореме максимальный поток равен 4. Разрез определен путем простого
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
