Liczba wierzchołków obecnych we wszystkich maksymalnych dopasowaniach

Biorąc pod uwagę wykres , musimy znaleźć liczność największego zestawu wierzchołków, aby każdy z nich był obecny w każdym możliwym maksymalnym dopasowaniu. $G$

Czy istnieje rozwiązanie obok oczywistego usunięcia każdego wierzchołka i znalezienia maksymalnego dopasowania, aby zobaczyć, że zmniejsza się?

graph-theory graph-algorithms

— Hououin Kyouma
źródło

Nie rozumiem, jak to, co zasugerowałeś, jest nawet rozwiązaniem. (Rozważ trójkąt.)

$\:$

$\hspace{1.4 in}$

@ RickyDemer najpierw znajdujemy maksymalne dopasowanie na całym wykresie. Następnie usuwamy wierzchołek i ponownie znajdujemy maksymalne dopasowanie. Jeśli różnica wynosi 1, możemy powiedzieć, że ten wierzchołek występuje we wszystkich maksymalnych dopasowaniach.

— evil999man

Czy „znaleźć maksymalne dopasowanie” należy zastąpić „znaleźć maksymalne dopasowanie” czy „znaleźć wszystkie maksymalne dopasowania”?

$\;$

Myślę, że należy go zastąpić rozmiarem maksymalnego dopasowania.

— evil999man

@ Awesome ma rację. Zmienię moje pytanie.

— Hououin Kyouma,

Odpowiedzi:

Myślę, że chcesz rozkładu Edmonda-Gallai na swoim wykresie, który można obliczyć w czasie (patrz te uwagi ). $O(n^3)$

— Thomas Kalinowski
źródło

Potrzebuję tylko rozmiaru, a nie samych wierzchołków. Czy można to zrobić w O (n ^ 2)? I dzięki za artykuł

— Hououin Kyouma,

Czy twój wykres jest dwustronny? Ponieważ, jeśli tak jest: załóżmy, że jedna strona dwuczęściowa jest pozostawiona, a druga właściwa. Znajdź maksymalne dopasowanie i ustaw wszystkie dopasowane krawędzie od lewej do prawej oraz wszystkie niedopasowane krawędzie od prawej do lewej. Następnie wierzchołek można pominąć w maksymalnym dopasowaniu tylko wtedy, gdy spełniony jest jeden z trzech następujących (wzajemnie wykluczających się) warunków: $v$

$v$ jest już niedopasowane
$v$ można osiągnąć z niedopasowanego wierzchołka po jego stronie dwuczęściowego w wynikowym digrafie
$v$ może osiągnąć niedopasowany wierzchołek po swojej stronie dwuczęściowej w wynikowym wykreślniku.

Wykonując dwa wyszukiwania najpierw szerokości lub pierwszego głębokości, jeden w celu znalezienia części wykresu, do których można dotrzeć z niedopasowanych wierzchołków, i drugi w celu znalezienia części, które mogą osiągnąć niedopasowane wierzchołki, można znaleźć niezbędne wierzchołki w czasie liniowym, gdy tylko już mam pasujące.

Prawdopodobnie coś takiego będzie działało również w przypadku dwustronnej, wykorzystując naprzemienne wyszukiwanie ścieżki alternatywnej, ale szczegóły będą bardziej skomplikowane.

— David Eppstein
źródło

Jestem ciekawy, jak byś to zrobił na ogólnym wykresie. Czy możesz to wyjaśnić?

— evil999man

Gdybym to szczegółowo opracował, uwzględniłbym to w swojej odpowiedzi. Ale w zasadzie chcesz po prostu znaleźć wierzchołki, do których można dotrzeć, zmieniając ścieżki z nieosiągalnych wierzchołków, ponieważ są to te, które można pozostawić niedopasowane. Wyszukiwanie na przemian powinno być w zasadzie takie samo, jak w przypadku wyszukiwania dopasowania.

— David Eppstein,

Przepraszam za spóźniony komentarz. Mój wykres jest ogólny. Spróbuję przemyśleć metodę

— Hououin Kyouma,