Выберите ребра из взвешенного графа, чтобы каждая вершина была конечной точкой одного ребра, а сумма весов ребер минимизирована

Question

Для упрощения можно предположить, что граф G = (V, E) имеет 2N вершин, а ответ имеет N ребер.

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

Любые полиномиальные решения, а также доказательство сложности NP приветствуются.

Answer 1

Если вы хотите, чтобы каждая вершина была инцидентной точно одному ребру, то вам нужно найти идеальное соответствие.Но идеальное сопоставление не всегда существует даже для графа с четным числом вершин.

Вы можете увидеть пример в этот ответ .