Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
<big>Цыганова Светлана, 974 гр.</big>
 
−
 
 
Студент предложил для задачи [[Vertex cover]] приближенный алгоритм с точностью ½:
 
Студент предложил для задачи [[Vertex cover]] приближенный алгоритм с точностью ½:
 
* найти в графе дерево (методом поиска в глубину),
 
* найти в графе дерево (методом поиска в глубину),
Строка 8: Строка 6:
 
Прав ли он? Докажите или опровергните.
 
Прав ли он? Докажите или опровергните.
  
−
'''Решение'''
+
[[Category:Проблемные задачи]]
−
 
+
−
Допустим, что наш граф - цепь, вершиной является конец цепи. Рассмотрим на примере - допустим, есть цепь 1-2-3-4-5-6-7. Пусть корнем является вершина №1. Поиск в глубину найдет дерево 1-2-3-4-5-6-7. Если выкинуть из него листья, кроме корневого, то получится дерево 1-2-3-4-5-6. В таком случае студент объявляет, что вершинное покрытие имеет 6 вершин. Так как речь идет о точности, то студент ищет минимальное вершинное покрытие (а не просто вершинное покрытие, как указано в задаче).  В минимальном вершинном покрытии 3 вершины - 2,4,6. Таким образом, нужная точность не достигается (отличие ответа алгоритма от настоящего в 2 раза, а не в ½, даже если округлить результат в нужную сторону: 5 вершин лежит в пределах указанной точности, а 6 - уже нет.)
+
−
 
+
−
Таким образом студент не прав.
+
−
 
+
−
 
+
−
[[Category:На проверку]]
+

Текущая версия на 17:08, 19 мая 2015

Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:

  • найти в графе дерево (методом поиска в глубину),
  • выкинуть из него листья (кроме корневого узла).
  • а оставшееся объявить вершинным покрытием.

Прав ли он? Докажите или опровергните.

Источник — «https://discopal.ispras.ru/index.php?title=Жадный_алгоритм_в_задачах_о_покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2&oldid=3998»