Жадный алгоритм в задачах о покрытии/Задачи/vertex-cover — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Celyh (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
<m> \ge 2 \cdot OPT</m> | <m> \ge 2 \cdot OPT</m> | ||
| − | [[Category: | + | [[Category:На проверку]] |
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
| + | |||
| + | |||
| + | Решение (Целых Влада, 974 гр.): пример графа изображен на рисунке. Минимальное вершинное покрытие состоит из 2 вершин - B и D. Ленивый алгоритм может построить покрытие из 2*2=4 вершин, сначала добавив в покрытие вершины A,B, а потом D,E. | ||
| + | |||
| + | |||
| + | [[File:Vertex-cover.png]] | ||
Версия 17:20, 25 октября 2014
Для известного 2-приближенного алгоритма для задачи о вершинном покрытии привести пример графа, для которого «этот алгоритм с паросочетаниями» строит покрытие с числом вершин
Решение (Целых Влада, 974 гр.): пример графа изображен на рисунке. Минимальное вершинное покрытие состоит из 2 вершин - B и D. Ленивый алгоритм может построить покрытие из 2*2=4 вершин, сначала добавив в покрытие вершины A,B, а потом D,E.
