Wiem, że dla nieważonego grafu dwustronnego mogę znaleźć minimalną osłonę wierzchołków, najpierw znajdując maksymalne dopasowanie i przekształcając ją w osłonę wierzchołków za pomocą Twierdzenia Königa. Czy istnieje modyfikacja, której można by użyć, gdyby węzły były ważone?
1
Chociaż rozwiązanie podane przez Shivę Kintali rozwiązuje twój problem, chciałbym tylko dodać szybką uwagę: twierdzenie Königa dotyczy kardynalności. Możesz dodać wagi, znajdując minimalne maksymalne dopasowanie dwustronne (istnieją algorytmy do tego z wagami krawędzi; zamiast tego łatwo używać wag węzłów), ale nadal uzyskasz minimalny koszt minimalnego pokrycia wierzchołków - co może nie być minimalny koszt ochrony wierzchołków (tj., który może składać się z większej liczby węzłów). Dopasowanie minimalnego kosztu bez ograniczeń / optymalizacji liczności byłoby po prostu puste (dla dodatnich wag)…
—
Magnus Lie Hetland