Описание тега network-flow
Сеть-поток или сеть потоков - это ориентированный граф с пропускной способностью для каждого ребра, который может распространять поток от источника к приемнику. Это один из самых мощных инструментов решения проблем в информатике, который используется для решения многих сетевых проблем, задач исследования операций и т. Д.
1
ответ
Как превратить мультиграф в простой ориентированный граф
Предположим, что существует сеть с несколькими ребрами, для любой пары вершин (u, v) граф содержит несколько направленных ребер от u до v и от v до u, каждый со своей емкостью и весом. Как я могу уменьшить этот мультиграф до простого ориентированног…
21 ноя '16 в 04:45
0
ответов
Назначение учеников в классе - поток в сети?
У меня есть одна комната, которая открыта несколько дней в неделю, каждый день в разные часы (7:00-14:42, ...) У меня несколько студентов, каждый из которых может посещать комнату в разные дни, в разные часы (у студентов может быть время посетить ко…
30 апр '18 в 12:31
1
ответ
Сопоставление максимальных весов с взвешенными вершинами
У меня есть двудольный граф с двумя наборами вершин A и B. Края не имеют весов. Однако вершинам в одном из наборов (скажем, в наборе B) назначены положительные веса (wb1,wb2...). Я хочу найти соответствие в этом двудольном графе, чтобы максимизирова…
02 янв '16 в 20:27
0
ответов
В этой сети потока существует ребро, такое, что уменьшение пропускной способности ребра уменьшит максимальный поток
Я ответил на следующий вопрос: "В каких потоковых сетях есть преимущество, при котором уменьшение его пропускной способности приведет к уменьшению максимального потока". С ответом "в каждой потоковой сети" мне сказали, что это неправильный ответ. Ка…
02 мар '19 в 17:07
2
ответа
Теорема об интегральности в максимальном потоке
Теорема об интегральности говорит нам, что если все емкости в сети потока являются целыми числами, то существует максимальный поток, где каждое значение является целым числом Но самая замечательная часть - это существование, а не каждый максимальный…
22 дек '13 в 18:57
0
ответов
Как вы находите максимальный поток на орграфе, где возможности могут быть отрицательными?
Ford-Fulkerson и Edmonds-Karp et. и др. начните с нулевого потока и увеличивайте его до тех пор, пока он не может быть увеличен. В случае положительных способностей; однако начальный нулевой поток гарантированно будет как законным потоком, так и пот…
13 сен '13 в 16:43
0
ответов
Edmond Karp максимальный поток с реальными мощностями
В оригинальном Ford-Fulkerson емкости допускаются только целыми числами. Но мне любопытно насчет Эдмонда-Карпа. Работает ли он с реальными значениями емкости в O(VE^2)? Я думаю, это все еще работает.
21 окт '17 в 07:50
1
ответ
Экземпляр Ford Fulkerson нарушает собственность
Каким-то образом я создал этот график, который, кажется, нарушает одно из свойств, заключающееся в том, что значение потока ограничено верхним пределом пропускной способности min cut.Вот график: Максимальный поток, который находит алгоритм, равен 7.…
02 ноя '13 в 20:49
2
ответа
Как уменьшить максимальный кардинальность двухстороннего соответствия для минимального покрытия пути?
Я прочитал эти два вопроса: ссылка1 ссылка2 а также эта википедия но я не могу понять, как решение проблемы максимального соответствия может быть использовано для решения минимального покрытия пути. Я знаю, что решение - это nm, где n - это число ве…
18 дек '14 в 13:35
1
ответ
Сетевой подход для максимизации количества заданий, которые могут быть запланированы
Мне любопытно использовать сетевой подход для решения этой проблемы. Надеюсь, что кто-то здесь может занять время, чтобы помочь мне построить подходящий и подходящий график для этой проблемы. Построенный график, когда он решен для максимального пото…
27 май '15 в 15:03
1
ответ
Оптимизация в Python: объект 'Var' не повторяется
Я надеюсь, что это не дубликат, но я не могу найти конкретного ответа на эту проблему. Я довольно новичок в Python, так что это может быть очевидно, но я не могу найти свою ошибку. Итак, проблема в том, что я использую gurobi для оптимизации модели …
09 фев '16 в 22:25
0
ответов
Алгоритм максимального потока Голдберга-Рао - почему некоторые дуги никогда не допустимы?
Я пытаюсь реализовать алгоритм максимального потока Голдберга-Рао, описанный в статье " Вне барьера разложения потока, 1988". В статье говорится, что мы ищем поток на допустимых дугах. The arc(vw) is admissible if distance(v) > distance(w) + leng…
25 дек '17 в 18:28
1
ответ
Этот код Седжвика правильный?
Я решаю проблему оптимизации, в которой, помимо прочего, я должен максимизировать потоки сетей. Я реализовал алгоритм максимизации потока на основе кода C++, основанный на следующем Java-коде, который приведен в книге Седжвика "Алгоритмы на Java, тр…
01 дек '14 в 01:33
3
ответа
Какой алгоритм я должен использовать, чтобы найти минимальный поток на орграфе, где существуют нижние, но не верхние границы потока?
Какой алгоритм я должен использовать, чтобы найти минимальный поток на орграфе, где есть нижние границы, но не верхние границы потока? Например, этот простой пример: В литературе это проблема минимальных затрат. Однако в моем случае стоимость такая …
03 сен '13 в 17:43
1
ответ
Поток сети: правда или ложь
In a directed graph with at most one edge between each pair of vertices, if we replace each directed edge by an undirected edge, the maximum flow value remains unchanged. Почему это ложно? Почему и как изменится поток? Спасибо.
06 ноя '15 в 11:34
1
ответ
Найти путь от источника к цели в остаточном графе графика сетевого потока за O(E) время
Мне дана сеть потоков G и их (ребро) Емкости и (ребро) потоки через каждое ребро, а также Поток F. Я хочу проверить, существует ли путь от источника к цели в остаточном графе, чтобы найти вне, если F является максимальным потоком или нет. Можно ли с…
19 фев '17 в 21:45
1
ответ
Головоломка на графике
Учитывая неориентированный граф G=(V,E), каждый узел i связан с числом объектов "Ci". На каждом шаге для каждого узла i объекты Ci делятся поровну между соседями i. После K шагов выведите количество объектов из пяти верхних узлов, у которых больше в…
14 окт '12 в 03:05
1
ответ
Подсчет количества различных срезов в ориентированном графе
Я пытаюсь найти количество различных срезов в ориентированном невзвешенном графике. В статье Перечень в графах с. 45 Я нашел хороший способ перечислить эти сокращения (раздел 7.3). Есть ли более быстрый или более простой алгоритм, который я могу исп…
01 дек '11 в 14:52
1
ответ
Максимальный поток на ненаправленном графике
Как я могу найти максимальный поток в этом неориентированном графике? Кто-нибудь может показать шаг?
20 апр '15 в 07:30
1
ответ
Кратчайший путь между тремя точками
На графике мне нужно найти кратчайший путь между двумя точками и по пути посетить одну контрольную точку. Также я могу посетить каждую вершину только один раз. Я предполагаю, что это как-то связано с сетевым потоком, но я понятия не имею, как это ре…
24 май '13 в 17:42