Я изучаю анализ алгоритмов. В настоящее время я читаю об алгоритмах Network Flow . Я рассматриваю применение Network Flow алгоритмов для поиска bipartite matchings минимальной стоимости. Пусть G с соответствующим потоком сети G'...

Я рассматриваю возможность использования cvxopt для решения некоторых задач оптимизации нелинейного сетевого потока. Чтобы понять основы, я пробую это с очень простой тестовой сетью всего с 4 вершинами и 5 ребрами. Моя сеть выглядит как это ....

Я решаю классическую проблему сетевого потока с помощью CPLEX (используя Java). Он содержит ограничение Ax = b (A - матрица инцидентности узла и дуги, x - переменная решения для потоков ссылок, а b - заданные правые части). Меня интересуют теневые...

Пусть G=(V,A,s,t,U) — поточная сеть. Предположим, мы получили максимальный поток. Существует ли быстрый алгоритм для поиска всех ребер, находящихся в некотором минимальном разрезе? Я знаю, что если x является максимальным потоком, то мы можем...

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

Мне даны потоки-сеть G и их (реберные) емкости и (реберные) потоки через каждое ребро, а также поток F. Я хочу проверить, существует ли путь от источника к цели в остаточном графе, чтобы найти вне зависимости от того, является ли F максимальным...

Итак, я работаю над проблемой сетевого потока и должен иметь возможность удалить правую половину моего двудольного графа, чтобы иметь дело с несколькими графами одновременно. Вот как у меня настроены классы узлов и краев: class Node { public:...

Дан граф с n вершинами, непрямой, взвешенный, без отрицательных циклов и двумя узлами s,t — найти путь из s в t, в котором самое тяжелое ребро на пути имеет наименьший вес между всеми путями из s в t. одно решение, о котором я подумал, запустить...

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

предположим, что нам дано m экзаменов E = {E1, E2, ..., Em} и набор инструментов из I = {I1, I2, ..., In}, и для каждого исследования Ej требуется подмножество Rj из I. каждый экзамен приносит прибыль Pj $, а стоимость каждого инструмента - Cj $. мы...

Мне трудно понять следующую лемму из CLRS: Пусть G — поточная сеть, s и t — узлы источника и стока, f — предпоток из s в t, а h — функция высоты на G. Тогда в остаточном графе G ф . Почему это?

Каким-то образом я создал этот график, который, кажется, нарушает одно из свойств: значение потока ограничено сверху пропускной способностью минимального разреза. Вот график: Максимальный поток, который находит алгоритм, равен 7. (отправка 3...