Алгоритм решения проблемы кратчайших ребер?

Question

Вот проблема: Для графа из нескольких узлов каждый узел может подключаться только к одному из других узлов. Как минимизировать суммарные ребра этого графа? * Рис.1 1002 * Fig.2

Как указано выше, фиг.2 имеет более короткую длину, чем длина по фиг.1. Есть ли алгоритм для расчета кратчайшей длины всех ребер?

Answer 1

Проблема называется «идеальное соответствие минимального веса». Колмогоров В. - Блоссом В. Новая реализация алгоритм идеального соответствия минимальной стоимости представляет эффективный алгоритм. Реализация алгоритма на C ++ в статье доступна (извлечено из здесь ; ссылка, указанная в самой статье, больше не активна).

Беглый поиск в Google показал, что различные библиотеки обработки графиков (например, LEDA) включают алгоритм решения вашей проблемы в своем наборе инструментов.

Протест

Я не проверял реализацию цитируемой статьи и не знаю о правовом статусе ее использования.