Найти покрытие вершин двудольного графа с очень важной вершиной

Question

Я знаю, что могу найти минимальное покрытие вершин двудольного графа, сначала найдя максимальное соответствие, а затем используя Теорема Кенига , чтобы превратить это соответствие в покрытие вершин того же порядка.

Однако полученный результат является лишь одним из множества допустимых покрытий вершин.На следующем графике {A, B}, {C, D} и {B, C} являются действительными покрытиями.Применение метода Konig дает покрытие {A, B}.

(A)=====(C)
       /
     /
   /
(B)=====(D)

Как бы вы проверили существование минимального покрытия вершин, которое включает данную важную вершину, скажем, вершину D?

Мое первое предположение - перевернуть график и найти другое минимальное покрытие вершин.В приведенном выше случае это дало бы {C, D}.Если ни одно из решений не содержит важную вершину, оно не является частью какого-либо минимального покрытия.Тем не менее, я не думал достаточно глубоко, чтобы действительно доказать это себе.

Answer 1

Я бы предложил следующий метод

1. Найдите размер минимального покрытия вершин (Пусть покрытие вершин будет $ C $)
2. Удалите «Очень важную вершину» и все ребра, покрытые одним и тем же (вершина будет $ v $)
3. Повторите процесс, и пусть покрытие новой вершины будет $ C '$

Если $ | C '+ V | = | C | $, то сообщите о минимальном покрытии вершин, иначе сообщите, что с данной вершиной не существует минимального покрытия вершин.

Полагаю, у вас тот же ответ, доказательство тоже в том же духе.

Новое покрытие вершин не может быть меньше, поскольку оно нарушит условие, что $ C $ является одним из минимальных покрытий вершин.

Также $ C '$ - минимальное покрытие, покрывающее остальную часть графика.

Если существует хотя бы одно минимальное покрытие вершин, включая вершину $ V $, то остальные вершины в этом наборе будут покрывать все вершины, кроме соседних с $ V $, но тогда это будет означать, что $ | C ' | $ не больше, чем $ | C | -1 $, поэтому, если сделать это неправильно, не будет минимального покрытия вершин, включая ребро VIP.

Answer 2

Вычислить начальное совпадение, используя венгерский алгоритм, давая меньший вес всем ребрам, заканчивающимся в этой вершине.