Анисимов/Песочница — различия между версиями

Версия 05:52, 19 декабря 2013

Сначала докажем, что построенное таким образом множество вершин является вершинным покрытием.

Полное покрывающее дерево является вершинным покрытием, т.к. содержит все вершины. Допустим, что удалив листья из него покрытие станет не полным. Это возможно, если существовало ребро между какими-либо двумя листьями. Но это невозможно при построении покрывающего дерева поиском в глубину, т.к. для неориентированного графа он не даёт перекрёстных рёбер. Таким образом после удаления листьев полученное множестве является покрытием.

Теперь докажем, что полученное покрытие больше оптимального не более чем в два раза.