Описание тега max-flow
The maximum-flow problem, a problem in computer science over a flow network
2
ответа
Алгоритм Форда-Фулкерсона на графе с двусторонними ребрами
У меня возникли проблемы с пониманием алгоритма Форда-Фулкерсона для определения максимального потока, и я надеялся на некоторую помощь. Если мы посмотрим на следующий график с источником A и стоком F, где емкости ребер указаны на каждом ребре. Вы з…
11 фев '19 в 00:52
0
ответов
В этой сети потока существует ребро, такое, что уменьшение пропускной способности ребра уменьшит максимальный поток
Я ответил на следующий вопрос: "В каких потоковых сетях есть преимущество, при котором уменьшение его пропускной способности приведет к уменьшению максимального потока". С ответом "в каждой потоковой сети" мне сказали, что это неправильный ответ. Ка…
02 мар '19 в 17:07
1
ответ
Алгоритм Java MaxFlow, края, генерирующие проблемы
Я пытаюсь решить проблему максимального потока с графом, имеющим неограниченные весовые ребра, но у каждого узла есть емкость. Я решил проблему с помощью алгоритма Форда Фулкерсона и разделил каждый узел на входной и выходной узлы с емкостью, являющ…
23 фев '17 в 23:11
1
ответ
Как найти окончательное сохраненное количество в каждом приемнике в сети потока?
У меня есть сеть потока с одним источником и несколькими приемниками. Если я вытечу 1 галлон воды из источника, тогда вся вода разделится в узлах и, наконец, сохранится в разных раковинах. Здесь каждый вес ребра c(u,v) представляет коэффициент разде…
26 июн '17 в 18:24
0
ответов
Алгоритм Форда-Фулкерсона с "взвешенными" ребрами и минимальной / максимальной производительностью вершины
Мой вопрос похож на этот: Алгоритм Форда-Фулкерсона с "взвешенными" ребрами Тем не менее, я включаю минимальные и максимальные возможности для назначений. Мало того, что у ребер есть вес ("тренировка"), и что каждый ученик должен быть назначен, но и…
02 ноя '18 в 10:51
0
ответов
Каковы ограничения алгоритма MPM и алгоритма Push-relbel для максимального потока?
Я кодирую это и должен знать об ограничениях для этих двух разных алгоритмов: 1) Емкости должны быть целыми или нет? 2) График должен быть ациклическим или нет? Кто-нибудь может дать намек? Спасибо
23 сен '13 в 02:19
3
ответа
Максимальный поток в динамических графиках
Я ищу быстрый алгоритм для вычисления максимального потока в динамических графах (добавление / удаление узла со связанными ребрами к графу). т.е. у нас есть максимальный поток в G, теперь новый узел добавлен / удален со связанными ребрами, я не любл…
26 янв '12 в 10:09
1
ответ
Как я могу получить элементы антицепи в SPOJ-DIVREL?
Проблема: http://www.spoj.com/problems/DIVREL В вопросе нам просто нужно найти максимальное количество элементов, которые не кратны (делится на форму b) из заданного набора элементов. Если мы просто сделаем ребро от элемента до его кратного и постро…
25 май '14 в 18:23
1
ответ
Неровность Форда-Фулкерсона (множественные вершины против обратного потока)
До сих пор я работал с графами, вершины которых имеют только одно направленное ребро между ними. Для всех примеров, которые я использовал для проверки своей реализации, был получен правильный ответ. Однако, когда я использую график, содержащий верши…
10 дек '12 в 08:31
1
ответ
Поиск минимального потока с полной производительностью в потоковых графиках
Я изменил задачу о максимальных проблемах потока. Я должен найти минимальный поток, который удовлетворяет условию (где f - поток, а c - емкость): f(u,v) >= c(u,v) Таким образом, поток на каждом ребре - это, по крайней мере, емкость ребра. (Я пишу…
12 май '14 в 20:34
1
ответ
Создание графика производительности алгоритма максимального потока Эдмондса Карпа в Python
Прежде чем я углублюсь в вопрос, вот некоторая справочная информация о том, что у меня уже есть: - Сначала я создал матрицу ненаправленной матрицы смежности, основанную на городах по всей территории США, где веса ребер были рассчитанным расстоянием …
03 дек '12 в 04:27
0
ответов
Работает ли алгоритм диника для двунаправленного фронта?
Алгоритм Форда-Фулкерсона работает для двунаправленных ребер с небольшой модификацией. Но я уверен в алгоритме Диника. Этот алгоритм хорошо работает и для двунаправленных ребер?
26 июн '15 в 23:14
0
ответов
Получите минимальное сокращение при расчете максимального расхода с помощью push-relbel
Я пытаюсь получить минимальные сокращения после запуска алгоритма push relbel. Я взял алгоритм из https://www.geeksforgeeks.org/push-relabel-algorithm-set-2-implementation/ // C++ program to implement push-relabel algorithm for // getting maximum fl…
16 дек '18 в 09:55
0
ответов
Алгоритм максимального потока, увеличивающий путь
1) Истина или ложь: мы всегда можем найти последовательность потока, увеличивающего st-пути в алгоритме Форда-Фулкерсона, так что мы достигаем максимального потока за полиномиальное число итераций. 2) Истина или ложь: мы всегда можем найти последова…
18 дек '18 в 11:35
0
ответов
Python быстрая реализация ford fulkerson
Я использую реализацию Python в Википедии Форд Фулкерсон, чтобы найти максимальный поток. Однако это немного медленно, и я хотел бы иметь более быструю процедурную реализацию. Есть идеи?
12 дек '15 в 13:47
0
ответов
BOOST min-cut/max-flow на неориентированном графике с источником и целью
Могу ли я использовать любые алгоритмы от Boost на неориентированном графе, который должен иметь источник и цель (два узла, которые должны быть в отдельных разрезах). Preflow_relabel говорит, что для этого требуется ориентированный граф. Stoer_wagne…
19 ноя '18 в 06:41
1
ответ
Максимальное сокращение потока с перекрестными зависимостями
У меня есть n заданий, которые выполняются с использованием старой системы. Если я изменю их на новую систему, я получу двойную выгоду за эту работу. Некоторые пары заданий (i, j) имеют зависимости. Смена работы, но не ее зависимая пара стоит xij. З…
12 мар '14 в 02:51
1
ответ
Компьютерное зрение: настройка сегментации. График среза потенциалов
Я пытался научить себя некоторым простым алгоритмам компьютерного зрения и пытаюсь решить проблему, где у меня есть немного искаженное шумом изображение, и все, что я пытаюсь сделать, это отделить черный фон от переднего плана, который имеет некотор…
08 окт '14 в 15:31
0
ответов
Алгоритм максимального потока Голдберга-Рао - почему некоторые дуги никогда не допустимы?
Я пытаюсь реализовать алгоритм максимального потока Голдберга-Рао, описанный в статье " Вне барьера разложения потока, 1988". В статье говорится, что мы ищем поток на допустимых дугах. The arc(vw) is admissible if distance(v) > distance(w) + leng…
25 дек '17 в 18:28
1
ответ
Двухстороннее сопоставление с делимыми задачами
Я пытаюсь решить проблему с заданием, где делятся и задачи, и человеческие часы. например, у человека X есть 4 часа в день, он может выполнить 1/3 задачи A за 2 часа, 1/4 задачи B за 4 часа. Человек Y, имеющий 10 часов, может выполнить 1/5 задачи A …
14 сен '18 в 07:27