У меня есть однонаправленный график, который выглядит как ниже. Я хочу найти минимальный набор покрытия в этом графе, где минимальный набор обозначает подмножество его вершин, так что для каждого ребра (u, v) графа, либо 'u', либо 'v 'находится в покрытии вершины.
В networkx реализован функциональный модуль под названием min_weighted_vertex_cover , который предположительно возвращает минимальный набор, но я думаю, что решения, возвращаемые функциями, не верны. Когда я использую функцию на приведенном выше графике, она дает результат в виде набора вершин в виде {{0, 1, 2, 4}, что явно неверно. Один из ответов - {3,0,2}, и с этим небольшим графиком я бы предположил, что модуль дал бы правильный ответ.
Я могу ошибаться в своем понимании функции, и если это так, может кто-нибудь подсказать, как я могу go реализовать минимальный набор покрытия?