# из фундаментальных

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

Индекс
Элементарные функции Линейные уравнения Нелинейные уравнения Случайные числа