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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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]]
 

Версия 22:49, 25 декабря 2014

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