Как преобразовать неориентированный граф в ориентированный граф, в котором каждый узел имеет не более K родителей?

Question

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

Answer 1

Хорошо, при условии, что я понял проблему, хороший алгоритм для ее решения - Кун-Мункрес (https://en.wikipedia.org/wiki/Hungarian_algorithm).

) Для каждого ребра вы хотите связать один из двух узлов (тот, которыйДля каждого узла у вас есть максимально возможная ассоциация K.

Таким образом, ваш биграф находится на одной стороне (скажем, слева), на краях исходного графа, а на другой (скажем, справа).сторона) K раз каждый узел + один узел-приемник на ребро. Узлы-приемники соответствуют потере ребра.

Затем вы помещаете ребра в свой биграф (не путайте с ребрами вашей задачи)Вы ставите ребро стоимости 0 для всех соединений вашего исходного графа и ребро стоимости 1 от любого левого узла до его узла приемника.

Затем вы используете алгоритм Куна-Мункреса, чтобы минимизировать ассоциацию.