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

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.