Вопросы с тегом «max-flow-min-cut»

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

15
Супер Марио течет в НП?

Одним из классических расширений проблемы максимального потока является проблема «максимального потока во времени»: вам дается орграф, два узла которого различаются как источник и приемник, где каждая дуга имеет два параметра, - единичное время и задержка. Вы также дали горизонт времени . Цель...

14
Количество срезов графа без использования алгоритма Каргера

Мы знаем, что алгоритм mincut Каргера может быть использован, чтобы доказать (неконструктивно), что максимальное число возможных срезов, которые может иметь граф, равно (n2)(n2)n \choose 2 . Мне было интересно, можем ли мы как-то доказать эту идентичность, дав биективное (довольно инъективное)...

13
Второй самый маленький

Что-нибудь известно о втором наименьшем - -резе в сети потока? Или, в общем, об этой проблеме:sssTTt Вход: сеть и число , все в двоичном виде. Выход: наименьшее - вырезать.NNNККkККksssTTt - й наименьший - разреза любые - вырезать, например , что существует ровно - порезы , чьи мощностиККksssTTt( S,...

9
Увеличение способности максимизировать минимальное сокращение

Рассмотрим граф со всеми ребрами, имеющими единичную емкость. Можно найти минимальное сокращение за полиномиальное время. Предположим, мне разрешено увеличивать емкость любых ребер до бесконечности (эквивалентно объединению узлов по обе стороны ребра). Каков оптимальный способ выбора оптимального...