Жадный алгоритм в задачах о покрытии/Задачи/ex-breath-tree-for-vertex-covering-1-2 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 6: | Строка 6: | ||
Прав ли он? Докажите или опровергните. | Прав ли он? Докажите или опровергните. | ||
| − | [[Category: | + | [[Category:На проверку]] |
| − | + | =Стенин Сергей группа 974= | |
| + | То, что предлагает студент, вообще может не дать вершинного покрытия. Покажем это на примере. Рассмотрим полный граф на 4 вершинах. Запустим обход в ширину на любой вершине. Она поместится в очередь. Потом извлекаем из очереди эту вершину и помещаем три остальных в эту очередь. При извлечении этих вершин из очереди ничего не происходит. Получается дерево с корнем на первом уровне и тремя потомками на втором уровне. Если выкинуть из него листья, то останется только одна вершина, которая, очевидно, вершинным покрытием не является вовсе. Так что студент не прав, ибо предложил некорректный алгоритм. | ||
Версия 19:48, 8 ноября 2014
Студент предложил для задачи вершинного покрытия приближенный алгоритм с точностью ½:
- найти в графе дерево (методом поиска в ширину),
- выкинуть из него листья,
- а оставшееся объявить вершинным покрытием.
Прав ли он? Докажите или опровергните.
Стенин Сергей группа 974
То, что предлагает студент, вообще может не дать вершинного покрытия. Покажем это на примере. Рассмотрим полный граф на 4 вершинах. Запустим обход в ширину на любой вершине. Она поместится в очередь. Потом извлекаем из очереди эту вершину и помещаем три остальных в эту очередь. При извлечении этих вершин из очереди ничего не происходит. Получается дерево с корнем на первом уровне и тремя потомками на втором уровне. Если выкинуть из него листья, то останется только одна вершина, которая, очевидно, вершинным покрытием не является вовсе. Так что студент не прав, ибо предложил некорректный алгоритм.