Как мне доказать правильность моего жадного алгоритма для покрытия вершин на дереве?

Question

Задача покрытия вершин на деревьях заключается в следующем.

Вход: ациклический простой неориентированный граф G
Вывод: набор вершин W такой, что для каждого ребра uv, u ∈ W или v ∈ W. Мы хотим минимизировать размер W.

Мой жадный алгоритм - инициализировать W = ∅, затем, пока G не пусто, повторить следующие шаги. Пусть L - листовые вершины G. Пусть N(L) - множество вершин, смежных с некоторой вершиной из L. Обновление W = W ∪ N(L). Удалите вершины L ∪ N(L) и их инцидентные ребра из G.

Этот алгоритм работает во всех случаях, которые я пробовал до сих пор. Как мне доказать это правильно? Вот что у меня так далеко.

Предположим, что существует другое множество S, которое является оптимальным решением. В противовес, я хочу установить, что S не покрывает все ребра или что S совпадает с тем, которое получено моим жадным алгоритмом.

Answer 1

Это разумное начало, но я вижу две проблемы. Во-первых, оптимальное решение не может быть уникальным. Рассмотрим путь из четырех вершин a-b-c-d, который имеет три оптимальных решения: {a,c}, {b,c}, {b,d}, Во-вторых (и вы, вероятно, уже делаете это, но вы этого не сказали), необходимо учитывать, что дерево является корневым. В противном случае на графике a-b например, у нас есть L = {a,b} а также N(L) = {b,a}и созданная вершина W = {b,a}, что не является оптимальным. Обозначая a как корень, он по определению исключен из множества листьев.

Чтобы формально доказать правильность программы, включающей цикл, часто полезно использовать индукцию для установления инварианта цикла. Позвольте мне предложить два.

1. Для всех времен t (где время = число итераций цикла), пусть G(t) будет тем, что осталось от G в момент времени t, и пусть W(t) будет значением W в момент времени t. Для каждого покрытия вершин X группы G(t) множество W(t) ∪ X является покрытием вершин группы G(0), где 0 - время начала.

2. Для всех времен t существует оптимальное решение, которое содержит W(t) в качестве подмножества.

Пусть T будет временем окончания. Поскольку G(T) является пустым графом, X = valid является допустимым покрытием вершин G(T), поэтому инвариант #1 устанавливает, что W(T) является покрытием вершин G(0). Инвариант № 2 устанавливает, что W(T) содержится в каком-то оптимальном решении. Поскольку W(T) само является покрытием вершин, то само W(T) должно быть этим оптимальным решением.

Индуктивный шаг в доказательстве инварианта № 2 заключается в том, чтобы при задании оптимального решения, содержащего W(t-1), но не W(t), превратить его в другое оптимальное решение, содержащее W(t). Это включает в себя формализацию вашей интуиции, что всегда по меньшей мере столь же продуктивно брать соседа листа по листу.