Я пытаюсь найти количество различных разрезов s-t в ориентированном невзвешенном графе. В статье Перечисление в графиках стр. . 45 Я нашел хороший способ перечислить эти разрезы (раздел 7.3). Есть ли более быстрый или простой алгоритм, который я...

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

Я пытаюсь решить следующую проблему , но мой алгоритм работает слишком медленно. Это потому, что я использую алгоритм Эдмондса-Карпа , чтобы найти максимальный поток что в применении к двудольным графам также дает максимальное соответствие. Время...

Я не могу понять, как найти циркуляционный поток в сети с нижними границами (не требованиями). Я нашел следующие документы с описанием проблемы и стратегиями решения: https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf...

Нам задан сетевой поток, а также максимальный поток в сети. Ребро будет называться возрастающим ребром , если увеличение его пропускной способности на произвольное положительное число также увеличит максимальный поток. Представьте алгоритм,...

Я понимаю, что Алгоритм Форда-Фулкерсона может найти максимальный поток, который может течь от источника ( s ) к приемнику ( t ) в потоковой сети. Но существует ли алгоритм, который находит все возможные наборы путей, обеспечивающие максимальный...

У меня есть небольшая ошибка в понимании алгоритма Диника о том, как он использует остаточную сеть. так что алгоритм, насколько я понимаю, следующий 1- запустить bfs в остаточной сети и назначить уровни узлам в зависимости от расстояния от...

Я пытаюсь реализовать проблему потока дуги, когда у меня есть набор дуг в массиве. Каждая дуга представляет собой настраиваемую структуру данных, состоящую из узлов от / до. Я хочу добавить ограничение, в котором я включаю только дуги, идущие от...