Теорема Форда-Фалкерсона

@no swear · Регистрация: 01.07.2016

Author24 — интернет-сервис помощи студентам

Здравствуйте всем, не получается разобраться с этой теоремой. Не понятно в одном моменте, в теореме сказано что
1. Поток f максимален.
2. В G_f не существует пути s⇝t.
3. |f|=c(S,T) для некоторого разреза (S,T) сети G.

<S, T> - пара множеств вершин разреза

1 и 3 понятно а вот 2'ой не очень ясно, говорится что остаточном графе максимальный поток существует тогда когда не существует дополняющего пути.
А по определению дополняющего пути это путь (u₁, u₂, u₃, ..., u_k) в остаточной сети, где u₁ = s, u_k = t (s - исток, t - сток), с_f(u_i, u_{i + 1} > 0)
Что это значит? Что такое дополняющий путь

@salam · 17.02.2019, 00:38

путь, вдоль которого можно пропустить положительное число потока.

@no swear · 17.02.2019, 11:05 **[ТС]**

salam, Спасибо за ответ, нашел в Кормене про дополняющий путь, доп путь это путь по которому можно пропустить ещё какое то количество потока

Как вы говорите положительное число потока

Новые блоги и статьи Все статьи Все блоги /
Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .	Lazarus. Таблица с объединением ячеек. Massaraksh7 21.03.2025 Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .	Async/await в Swift: Асинхронное программирование в iOS mobDevWorks 20.03.2025 Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .	Колмогоровская сложность: Приёмы упрощения кода ArchitectMsa 20.03.2025 Наверное, каждый программист хотя бы раз сталкивался с кодом, который напоминает запутанный лабиринт — чем дальше в него погружаешься, тем сложнее найти выход. И когда мы говорим о сложности кода, мы. . .	PostgreSQL в Kubernetes: Подготовка кластера и настройка Mr. Docker 20.03.2025 Когда доходит до контейнеризации баз данных и особенно таких требовательных к ресурсам системах как PostgreSQL, многие команды до сих пор колеблются, прежде чем перенести их в контейнерную. . .
C++26: Индексирование пакетов и метапрограммирование bytestream 20.03.2025 Эволюция C++ продолжается стремительными темпами – каждый новый стандарт приносит функциональность, о которой мы мечтали годами. Звучит слишком громко? Если вы когда-либо боролись с вариадическими. . .	Состояние гонки в C#: подводные камни многопоточного программирования UnmanagedCoder 20.03.2025 Что такое состояние гонки? Это ситуация, когда результат программы непредсказуемо меняется в зависимости от порядка выполнения потоков. Проще говоря, два или более потока пытаются одновременно. . .	Next.js для разработки React: преимущества серверного рендеринга Reangularity 20.03.2025 Next. js решает классическую проблему React-приложений: медленную первоначальную загрузку и плохую индексацию поисковиками. Вместо того чтобы заставлять браузер пользователя выполнять всю работу по. . .	JUnit или TestNG: Выбираем Java-фреймворк для тестирования Javaican 20.03.2025 История тестовых фреймворков в Java началась в конце 90-х, когда Кент Бек и Эрих Гамма разработали JUnit - инструмент, который перевернул представление разработчиков о модульном тестировании. JUnit. . .	Разбиваем монолит на два микросервиса и реализуем CI/CD ArchitectMsa 20.03.2025 Когда команда растет, а функциональность монолита расширяется, поддерживать и развивать такую систему становится все труднее. Разработчики начинают тратить много времени на разбор сложных. . .

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943

	Теорема Форда-Фалкерсона 16.02.2019, 19:56. Показов 631. Ответов 2 Метки нет (Все метки) Здравствуйте всем, не получается разобраться с этой теоремой. Не понятно в одном моменте, в теореме сказано что 1. Поток f максимален. 2. В G_f не существует пути s⇝t. 3. \|f\|=c(S,T) для некоторого разреза (S,T) сети G. <S, T> - пара множеств вершин разреза 1 и 3 понятно а вот 2'ой не очень ясно, говорится что остаточном графе максимальный поток существует тогда когда не существует дополняющего пути. А по определению дополняющего пути это путь (u₁, u₂, u₃, ..., u_k) в остаточной сети, где u₁ = s, u_k = t (s - исток, t - сток), с_f(u_i, u_{i + 1} > 0) Что это значит? Что такое дополняющий путь 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	17.02.2019, 00:38
	путь, вдоль которого можно пропустить положительное число потока. 1

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943
	17.02.2019, 11:05 [ТС]
	salam, Спасибо за ответ, нашел в Кормене про дополняющий путь, доп путь это путь по которому можно пропустить ещё какое то количество потока Как вы говорите положительное число потока 0

Опции темы