Пусть G (U u V, E) - взвешенный ориентированный двудольный граф (т.е. U и V - два набора узлов двудольного графа, а E содержит направленные взвешенные ребра из U в V или из V в U). Вот пример:
В этом случае:
U = {A,B,C}
V = {D,E,F}
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)}
Определение: DirectionalMatching (я сформулировал этот термин только для того, чтобы сделать все более ясным): набор направленных ребер, которые могут делиться начальными или конечными вершинами. То есть, если U- > V и U '- > V' оба относятся к DirectionalMatching, то V/= U 'и V'/= U, но может быть, что U = U 'или V = V'.
Мой вопрос: Как эффективно найти DirectionalMatching, как определено выше, для двудольного ориентированного взвешенного графика, который максимизирует сумму весов его ребер?
Эффективно я имею в виду полиномиальную сложность или быстрее, я уже знаю, как реализовать наивный подход грубой силы.
В приведенном выше примере максимальное взвешенное управление направлением: {F- > A, C- > E, B- > D} со значением 13.
Официально демонстрируя эквивалентность этой проблемы любой другой хорошо известной проблеме теории графов, было бы также полезно.
Спасибо!
Примечание 1: Этот вопрос основан на Максимально взвешенном двудольном сопоставлении _with_ направленных ребер, но с дополнительной релаксацией, которая разрешена для ребер в сопоставлении для совместного использования источника или адресата. Поскольку эта релаксация имеет большое значение, я создал независимый вопрос.
Примечание 2: Это максимальный вес. Мощность (количество ребер присутствует), а количество вершин, покрываемых совпадением, не имеет значения для правильного результата. Учитывается только максимальный вес.
Примечание 2: Во время моего исследования, чтобы решить проблему, я нашел эту статью, я думаю, что было бы полезно, если другие попытаются найти решение: Чередование циклов и путей в красном цвете мультиграфы: обзор
Примечание 3: В случае, если это помогает, вы можете также думать о графике как о эквивалентном двухстороннем цветном неориентированном двудольном мультиграфе. Затем формулировка проблемы включала бы: Найти множество ребер без чередующихся по цвету путей или циклов с максимальной суммой веса.
Примечание 4: Я подозреваю, что проблема может быть NP-жесткой, но я не так разбираюсь в сокращениях, поэтому мне еще не удалось это доказать.
Еще один пример:
Представьте, что вы имели
4 вершины: {u1, u2} {v1, v2}
4 ребра: {u1->v1, u1->v2, u2->v1, v2->u2}
Тогда, независимо от их веса, u1->v2 и v2->u2 не могут находиться в одном и том же методе DirectionalMatching, не могут v2->u2 и u2->v1. Однако u1->v1 и u1->v2 могут, и поэтому могут u1->v1 и u2->v1.
