Покрытие вершин минимального веса в дереве со взвешенными вершинами

Question

Для дерева с ненаправленными ребрами, где вес вершины равен ее степени, найдите покрытие вершин минимального веса.

Вот что я думаю:

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

Это правильно, или я упускаю что-то очевидное?

Answer 1

Это правильно, или я упускаю что-то очевидное?

Две вершины, имеющие одно ребро;Например, ...

A -- B -- C

Weights:
B = 2;
A = 1;
C = 1

{ A, C } и { B } - оба взвешенных минимальных покрытия вершин по вашему определению.

Только { B } является стандартным минимальным покрытием вершин.

РЕДАКТИРОВАТЬ: ... лучший пример, показывающий другую причину:

A -- B -- C -- D

Weights:
B = 2;
C = 2;
A = 1;
D = 1

{ A, C }, { B, D }, { B, C } - все стандартные минимальные покрытия вершин.

Только { A, C } и { B, D } являются взвешенными минимальными покрытиями вершин по вашему определению.Интуитивно это объясняется тем, что покрытие вершин { B, C } подсчитывает ребро B -- C дважды.

---

Первый пример счетчика опровергает, что все взвешенные MVC (согласно вашему определению) являются стандартными MVC.Второй встречный пример опровергает, что все стандартные MVC являются взвешенными MVC.

После некоторого размышления ... вы правы в том, что взвешенный MVC для дерева - это любой VC со стоимостью, равной количеству ребер.

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

... в общем, набор всех взвешенных MVC - это набор всех VC, не содержащих соседей.Например, в дереве, где ни один из дочерних элементов не является родительским, набор листовых узлов также является допустимым взвешенным MVC.