Описание тега minimum-cut

Описание тега Вопросы с тегом
A problem in computer science related to graph theory
0 ответов

В этой сети потока существует ребро, такое, что уменьшение пропускной способности ребра уменьшит максимальный поток

Я ответил на следующий вопрос: "В каких потоковых сетях есть преимущество, при котором уменьшение его пропускной способности приведет к уменьшению максимального потока". С ответом "в каждой потоковой сети" мне сказали, что это неправильный ответ. Ка…
02 мар '19 в 17:07
1 ответ

Ищем алгоритмы: минимальный разрез для получения двудольного графа

Учитывая неориентированный взвешенный граф (или один связанный компонент большего непересекающегося графа), который обычно будет содержать множество нечетных и четных циклов, я ищу алгоритмы для удаления наименьшего возможного числа ребер, необходим…
28 фев '17 в 11:21
1 ответ

Разделите граф на непересекающиеся множества одинакового размера с минимальным разрезом

Существует ли какой-либо алгоритм или код, который делит узлы графа на два или более непересекающихся множества, которые удовлетворяют следующим условиям: во-первых, удаляются только ребра. во-вторых, ребра взвешены, и те, которые будут удалены, дол…
09 окт '16 в 14:56
1 ответ

Минимальный разрез между двумя произвольными вершинами, заданный в качестве входных данных для неориентированного невзвешенного графа

У меня есть ненаправленный взвешенный граф, и мне нужно найти минимальный разрез, который разделяет два набора вершин. Я могу изменить свою настройку, чтобы уменьшить проблему, чтобы найти минимальный разрез, который разделяет две заданные вершины. …
31 мар '16 в 05:28
1 ответ

Минимальное сокращение по Karger MinCut Java Большая ошибка ввода

Я работаю и пытаюсь это исправить некоторое время. На самом деле прошло довольно много недель, но у меня закончились возможные решения или модификации. Таким образом, алгоритм является рандомизированным алгоритмом минимального разреза Каргера, и моя…
20 сен '13 в 19:29
1 ответ

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

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

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

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

Найти все ребра в min-cut

Пусть (G,s,t,{c}) - сеть потоков, и пусть F - множество всех ребер e, для которых существует хотя бы один минимальный разрез (A,B), такой что e идет от A к B. Дайте алгоритм полиномиального времени, который находит все ребра в F. ПРИМЕЧАНИЕ: Пока я …
31 янв '14 в 01:39
0 ответов

Сетевой поток: поиск краев каждого минимального разреза

Какова минимальная пропускная способность этой сети с учетом потоковой сети с источником и приемником? Сколько минимальных срезов может иметь сеть потоков? Возможно ли, чтобы набор ребер E был при всей минимальной пропускной способности?
04 дек '17 в 22:30
2 ответа

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

Основанные на графике методы использовались для проблем сегментации медицинских изображений. Каждый пиксель (воксель в 3D) на изображении представлен узлом на графике, а ребра соединяют соседние узлы. Кроме того, добавлены два узла, а именно источни…
27 авг '15 в 03:34
2 ответа

Найдите минимальный набор вершин в группе обеспечения доступности баз данных, которая разъединяет определенную долю путей

Задача задается следующим образом: с учетом DAG и числа 0 < p ≤ 1вернуть минимальный набор вершин, который разъединяет по крайней мере p-разделение путей от источника (т. е. без входящих дуг) до приемника (т. е. без исходящих дуг). За p = 1пробле…
21 сен '15 в 10:56
1 ответ

Рандомизированный Min-Cut, алгоритм Каргера

Я реализую алгоритм Каргера. Из того, что я понимаю, число ребер между двумя последними узлами не всегда является минимальным срезом. У меня возникли проблемы с пониманием, как мне на самом деле сократить минимальные значения этого алгоритма. Я прод…
09 май '14 в 03:13
1 ответ

Вырезать набор графика, Boost Graph Library

Я изо всех сил пытался понять, как это сделать. Я заинтересован в том, чтобы быстро найти вырезанный набор графика. Я знаю, что BGL поддерживает поиск набора срезов путем итерации по аргументам colorMap, поддерживаемым, например, edmonds_karp_max_fl…
02 ноя '14 в 08:35
0 ответов

Двустороннее сопоставление с ограничениями

При самостоятельном изучении заметки Джеффа Эриксона о приложениях maxflow доступны здесь http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/23-maxflowapps.pdf Я столкнулся с этой проблемой, которая поставила меня в тупик Сенат факультета решил…
05 ноя '13 в 14:44
1 ответ

Нахождение минимального разреза в графе с помощью алгоритма Крускала?

Мы уже видели, что покрывающие деревья и срезы тесно связаны. Вот еще одна связь. Давайте удалим последнее ребро, которое алгоритм Крускала добавляет в связующее дерево; это разбивает дерево на две составляющие, таким образом определяя разрез (S,S) …
06 июл '12 в 19:35
1 ответ

Независимое время, чтобы обеспечить минимальное сокращение графика, по крайней мере, одно испытание успешно

Я только что закончил с первым модулем в курсе специализации algo в Coursera. Был экзаменационный вопрос, который я не мог понять. Я сдал этот экзамен, поэтому нет смысла его сдавать. Из любопытства я хочу изучить принципы этого вопроса. Вопрос был …
25 авг '17 в 03:11
0 ответов

График порезы и удаление краев

Я пытаюсь понять какой-то код из отличной библиотеки Graph Cut Владимира Колмогорова, и у меня есть вопрос, касающийся построения графиков. Скажем, у меня есть система бинарных переменных, и мне нужно представить следующие сокращения расходов E(0, 0…
11 авг '15 в 07:37
1 ответ

Максимальный поток Min Cut

Итак, я выяснил, что максимальный поток равен 10, что означает, что минимальный срез также равен 10, однако как мне нарисовать минимальный срез 10 на этом изображении?
04 май '16 в 18:46
1 ответ

Нахождение минимального значения графа с помощью алгоритма Крускала

Я новичок, и я пытаюсь найти минимальный срез графа, используя алгоритм Крускала в Java. Я попал туда, где я могу прочитать входные данные и создать vertexCount^2 числа MST со случайными весами для ребер. Все, что мне осталось сделать, это выяснить …
11 окт '15 в 15:26
0 ответов

St Cut для неориентированного взвешенного графика

Недавно я заинтересовался этой теорией графов. Я наткнулся на разрез для ориентированного графа. В Интернете я узнал, что минимальное сокращение равно максимальному потоку, и существуют стандартные алгоритмы, которые могут решить минимальное сокраще…
01 мар '19 в 18:03