Граф G имеет минимальное покрытие вершин размером |V| - 1 тогда и только тогда, когда G полна. Это правда?

Question

Граф G имеет минимальное покрытие вершин размером |V| - 1 тогда и только тогда, когда G полна. Это правда?

Сетка может быть примером полной G. Где каждый узел связан с каждым другим узлом. Поэтому минимальный размер покрытия вершины для такого графа не должен быть равен 1.

0

algorithm vertex-cover

Источник

user4327275 12 сен '17 в 14:08

1 ответ

Другие вопросы по тегам algorithm vertex-cover

user2876504 12 сен '17 в 14:30 2017-09-12 14:30 · Answer 1 · 2017-09-12 14:30

Минимальное покрытие вершин - это множество вершин, каждое ребро которого касается вершины в наборе. Учитывая сетку (полный график) AB а также C, если у вас есть только один узел (скажем, A) как ваша попытка MVC, вы пропустите край (в этом случае край B-C).