Вершинное покрытие и деревья поиска: различия между версиями

Предположим, что v – вершина степени 2 в графе G, имеющая двух соседей u и w, не являющихся смежными друг с другом. Построим новый граф G’ следующим образом: удалим все вершины v, u и w и введем новую вершину v’, смежную со всеми оставшимися соседями вершин u и w в графе G. В таком случае говорится, что граф G’ был получен из графа G в результате свертки вершины v. Для технологии свертки был получен следующий результат.

'''Теорема 2. Пусть G’ – граф, полученный из графа G в результате свертки вершины v второй степени, два соседа которой не были смежными друг другу. Тогда граф G имеет вершинное покрытие из k вершин в том и только том случае, если G’ имеет вершинное покрытие из k-1 вершины.'''