Описание тега ford-fulkerson

Вопросы с тегом
Алгоритм Форда-Фулкерсона - это алгоритм поиска максимального потока в потоковой сети. Он работает только с графами с целочисленной емкостью и имеет низкую производительность на графах с большими потоками.
1 ответ

Форд Фулкерсон из Cormen et al

Я изучаю алгоритм Форда-Фулкерсона из книги Кормена "Введение в алгоритмы 2-е издание". Это описано в псевдокоде для ориентированного графа G=(V, E) следующим образом, где f - поток, определенный на VxV FORD-FULKERSON(G, s, t) for each edge (u,v) in…
12 окт '11 в 13:46
1 ответ

Обновление графика в Форд-Фулкерсон

Я использую алгоритм Форда-Фулкерсона, но у меня возникли проблемы с обновлением графика после фазы увеличения. Моя структура данных не делает это легким, я думаю. Для представления графика я использую это: private Map<Vertex, ArrayList<Edge&g…
30 ноя '14 в 11:23
0 ответов

Почему Эдмонд Карпс быстрее, чем Форд-Фулкерсон?

Почему выбор кратчайшего пути дополнения каждый раз вместо произвольного пути дополнения делает алгоритм Эдмонда Карпса быстрее, чем Ford-Fulkerson
14 янв '15 в 20:50
1 ответ

Использование ford fulkerson для размещения N сотрудников на M должностях с ролями

Я пытаюсь решить математическую задачу, используя Форд-Фулкерсон, но у меня есть некоторые проблемы. Это проблема I have a list of employees (Jack, John, Al, ...). I have a list of roles (R1, R2, R3, ...). I have a list of working positions (W1, W2,…
08 авг '14 в 08:10
2 ответа

Алгоритм Форда-Фулкерсона на графе с двусторонними ребрами

У меня возникли проблемы с пониманием алгоритма Форда-Фулкерсона для определения максимального потока, и я надеялся на некоторую помощь. Если мы посмотрим на следующий график с источником A и стоком F, где емкости ребер указаны на каждом ребре. Вы з…
11 фев '19 в 00:52
0 ответов

Как вы находите максимальный поток на орграфе, где возможности могут быть отрицательными?

Ford-Fulkerson и Edmonds-Karp et. и др. начните с нулевого потока и увеличивайте его до тех пор, пока он не может быть увеличен. В случае положительных способностей; однако начальный нулевой поток гарантированно будет как законным потоком, так и пот…
13 сен '13 в 16:43
1 ответ

Неровность Форда-Фулкерсона (множественные вершины против обратного потока)

До сих пор я работал с графами, вершины которых имеют только одно направленное ребро между ними. Для всех примеров, которые я использовал для проверки своей реализации, был получен правильный ответ. Однако, когда я использую график, содержащий верши…
10 дек '12 в 08:31
1 ответ

Экземпляр Ford Fulkerson нарушает собственность

Каким-то образом я создал этот график, который, кажется, нарушает одно из свойств, заключающееся в том, что значение потока ограничено верхним пределом пропускной способности min cut.Вот график: Максимальный поток, который находит алгоритм, равен 7.…
02 ноя '13 в 20:49
1 ответ

Максимальный поток Линейный алгоритм времени, Найти правильный поток

Итак, позвольте мне объяснить вопрос: Вам дан график. Вы найдете максимальный поток. Но оказывается, что у края, e_i, была неправильная способность. Это был один меньше. К сожалению, поток был максимизирован на старой мощности. Вычислите новый макси…
17 сен '13 в 00:00
0 ответов

Адаптация решателя Ford-Fulkerson для включения минимального веса

Я реализовал решение с использованием Ford-Fulkerson для решения проблемы распределения Скажем, система, в которой есть несколько человек, желающих принять участие в нескольких мероприятиях. У каждого человека есть список действий, которые он хочет …
28 фев '14 в 05:23
2 ответа

Алгоритм Форда-Фулкерсона и теорема о максимальном расходе

Привет, у меня проблемы с изучением алгоритма Форда-Фулкерсона с помощью теоремы о максимальном потоке. Согласно теореме, максимальный расход должен быть таким же, как и общий вес режущих кромок. Однако просмотр видео https://www.youtube.com/watch?v…
02 дек '18 в 12:32
0 ответов

Алгоритм максимального потока, увеличивающий путь

1) Истина или ложь: мы всегда можем найти последовательность потока, увеличивающего st-пути в алгоритме Форда-Фулкерсона, так что мы достигаем максимального потока за полиномиальное число итераций. 2) Истина или ложь: мы всегда можем найти последова…
18 дек '18 в 11:35
1 ответ

Эффективно рассчитать максимальный расход после добавления нового ребра в алгоритм Форда Фулкерсона?

Предположим, что максимальный поток для G был вычислен с использованием Ford-Fulkerson, и к E. добавлено новое ребро с единичной емкостью. Каким образом можно эффективно обновить максимальный поток. (t не значение потока, который должен быть обновле…
08 дек '16 в 15:57
1 ответ

Найти преимущество, используя алгоритм Форда Фулкерсона?

Я пытаюсь реализовать алгоритм Форд Фулкерсона в C++. Однако у меня проблемы с моим find_edge функция. Когда я вызываю эту функцию в my_alg, он выбирает правильный край, а затем поток увеличивается в my_alg, Он выбирает правый край и увеличивает его…
06 янв '12 в 18:30
1 ответ

Выбор расширенного пути в алгоритме ford fulkerson

Если в остаточной сети имеется много расширенных путей для данной сети потоков, какой путь я должен выбрать в первую очередь, чтобы найти пропускную способность?
08 июл '16 в 05:56
1 ответ

Анализ времени работы алгоритма Форда Фулкерсона, который находит максимальный поток в сети

Я знаю, что время работы ford fulkerson в общем случае составляет O(f*(n+m)), где f * - максимальный поток в сети, а n, m - количество вершин и ребер в сети, однако что если все граничные емкости ограничены постоянной C, как это повлияет на время ра…
08 апр '14 в 08:35
1 ответ

Максимальный поток - обнаружение, если данный край обнаружен в некотором минимальном срезе

Учитывая сеть G=(V,E), максимальный поток f и ребро e в E, мне нужно найти алгоритм efficeint, чтобы определить, есть ли какое-то минимальное сокращение, которое содержит e. Другой вопрос: если я обнаружил, что e содержится в некотором минимальном р…
07 июн '13 в 13:01
1 ответ

Увеличьте поток, изменив только один край после Ford-Fulkerson

Предположим, что я запустил алгоритм Форда-Фулкерсона на графике G = (V,E), и в результате получился максимальный поток fmax, который связан с минимальным сечением Xmin. Я заинтересован в максимально возможном увеличении потока за счет увеличения пр…
29 май '13 в 01:11
2 ответа

Нахождение минимального сечения сети потока

Я пытаюсь найти минимальное сокращение следующей сети Я использую следующий алгоритм: Запустите алгоритм Форда-Фулкерсона и рассмотрите окончательный остаточный граф. Найдите множество вершин, которые достижимы из источника в остаточном графе. Все р…
10 сен '17 в 23:01
1 ответ

Найти максимальный поток в любой сети по заданному алгоритму

Вы можете помочь мне решить следующую проблему?: Предположим, у нас есть алгоритм для решения проблемы максимального потока в сети потока, в которой степень каждого узла не превышает 2. Мне нужно показать, как использовать этот алгоритм для решения …
23 май '16 в 17:14