Существует ли алгоритм для поиска наилучшего набора пар вершин во взвешенном графе без повторения?

Question

Существует ли эффективный алгоритм поиска множества ребер со следующими свойствами в полном взвешенном графе с четным числом вершин.

• набор имеет наименьший максимальный вес края для любого набора, который соответствует другим возможным критериям
• каждая вершина связана ровно с одним ребром в наборе

Все веса положительны

d Я не могу думать о чем-то лучше, чем грубая сила, но я не распознаю это как NP с трудом.

Answer 1

Один из способов решения этой проблемы за полиномиальное время заключается в следующем:

1. Сортировка весов ребер по времени O (E log E)
2. Для каждого ребра присвойте емупсевдовес E '= 2 ^ {позиция в упорядочении} за ~ O (E) время
3. Найдите минимальное идеальное совпадение веса среди псевдосесов за время, близкое к O (V ^ 3) (в зависимости оталгоритм, который вы выберете, может быть медленнее или быстрее)

Это минимизирует наибольшее ребро, содержащееся в идеальном сопоставлении, которое именно то, что вы ищете в чем-то вроде O (V ^ 3)время.

Источники выполнения части 3 приведены ниже
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

с примером источника C ++, доступным по http://ciju.wordpress.com/2008/08/10/min-cost-perfect-matching/

Answer 2

попробуйте это (я только что обдумал это, поэтому у меня нет ни доказательства того, что он даст оптимальный ответ, ни того, будет ли он давать решение в каждом случае):

1. поиск самых тяжелых вершин V (A, B)
2. удалить вершину V из графа
3. если A подключен только к одной другой вершине T (A, C), затем удалите все остальные ребра, связанные с C, повторите шаг 3 с этими ребрами
4. если B подключен только к одной другой вершине S (B, D), затем удалите все остальные ребра, связанные с D, повторите шаг 4 с этими ребрами
5. повторить с шага # 1