У меня есть неориентированный взвешенный граф с n узлами и m ребрами.На этом графике можно начать с узла и посетить все остальные узлы ровно один раз и вернуться к начальному узлу (это может быть не важно).Мне нужно выбрать n / 2 (n четное) ребер так, чтобы каждый узел был связан только одним ребром, а сумма ребер минимально возможна.Еще одна вещь должна быть удовлетворена, ребра не должны пересекаться между собой.
Я пробовал грубую силу, и она слишком медленная.Я не очень знаком с теорией графов, поэтому, возможно, существует какой-то алгоритм для этого.Я ищу подсказку (или веб-ссылку) к алгоритму, который решает эту проблему.