Жадный алгоритм в задачах о покрытии/Задачи/vertex-cover

Ссылки сюда (11) →

Для известного 2-приближенного алгоритма для задачи о вершинном покрытии привести пример графа, для которого «этот алгоритм с паросочетаниями» строит покрытие с числом вершин

Решение (Целых Влада, 974 гр.): пример графа изображен на рисунке. Минимальное вершинное покрытие состоит из 2 вершин - B и D. Ленивый алгоритм может построить покрытие из 2*2=4 вершин, сначала добавив в покрытие вершины A,B, а потом D,E.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.