Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2 — различия между версиями
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
'''Решение''' | '''Решение''' | ||
| − | Допустим, что наш граф - цепь, вершиной является конец цепи. Рассмотрим на примере - допустим, есть цепь 1-2-3-4-5-6-7. Пусть корнем является вершина №1. Поиск в глубину найдет дерево 1-2-3-4-5-6-7. Если выкинуть из него листья, кроме корневого, то получится дерево 1-2-3-4-5-6. В таком случае студент объявляет, что вершинное покрытие имеет 6 вершин. | + | Допустим, что наш граф - цепь, вершиной является конец цепи. Рассмотрим на примере - допустим, есть цепь 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 - уже нет.) |
Таким образом студент не прав. | Таким образом студент не прав. | ||
Версия 11:54, 27 ноября 2014
Цыганова Светлана, 974 гр.
Студент предложил для задачи Vertex cover приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в глубину),
- выкинуть из него листья (кроме корневого узла).
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
Решение
Допустим, что наш граф - цепь, вершиной является конец цепи. Рассмотрим на примере - допустим, есть цепь 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 - уже нет.)
Таким образом студент не прав.