Анисимов/Песочница
Материал из DISCOPAL
Версия от 05:52, 19 декабря 2013; Denis Anisimov (обсуждение | вклад) (Новая страница: «Сначала докажем, что построенное таким образом множество вершин является вершинным пок…»)
Сначала докажем, что построенное таким образом множество вершин является вершинным покрытием.
Полное покрывающее дерево является вершинным покрытием, т.к. содержит все вершины. Допустим, что удалив листья из него покрытие станет не полным. Это возможно, если существовало ребро между какими-либо двумя листьями. Но это невозможно при построении покрывающего дерева поиском в глубину, т.к. для неориентированного графа он не даёт перекрёстных рёбер. Таким образом после удаления листьев полученное множестве является покрытием.
Теперь докажем, что полученное покрытие больше оптимального не более чем в два раза.
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.