Жадный алгоритм в задачах о покрытии/Задачи/ex-depth-tree-for-vertex-covering-1-2 — различия между версиями
StasFomin (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | <big>Цыганова Светлана, 974 гр.</big> | ||
| + | |||
Студент предложил для задачи [[Vertex cover]] приближенный алгоритм с точностью ½: | Студент предложил для задачи [[Vertex cover]] приближенный алгоритм с точностью ½: | ||
* найти в графе дерево (методом поиска в глубину), | * найти в графе дерево (методом поиска в глубину), | ||
| Строка 6: | Строка 8: | ||
Прав ли он? Докажите или опровергните. | Прав ли он? Докажите или опровергните. | ||
| − | [[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:На проверку]] | ||
Версия 11:43, 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 - уже нет.)
Таким образом студент не прав.