[Algorytmy]Minimalne pokrycie krawędziowe grafu dwudzielnego

[matinf]

Witajcie,

Mamy graf dwudzielny. Chcemy znaleźć w \(\displaystyle{ G}\) minimalne pokrycie krawędziowe. Tzn wyznaczyć podzbiór (minimalny) krawędzi taki że każdy wierzchołek jest incydentny z choć jedną z krawędzi.

Więc ja zaproponuję algorytm liniowy ze względu na sumę krawędzi i wierzchołków:

1. Policz stopnie wierzchołków.
2. Dla każdego wierzchołka stopnia jeden dodaj jedyną krawędź do szukanego zbioru zaktualizuj stopnie, usuń ten wierzchołek i krawędź. Na razie wszystko jest ok, bo tą krawędź musimy wziąć.
3. Wróć do kroku 2. o ile są jeszcze wierzchołki stopnia 1.
4. Teraz każdy wierzchołek ma stopień co najmniej 2. Więc każdy leży na pewnym cyklu. Istotne jest to, że są to cykle parzyste (W sensie liczby krawędzi). Takie cykle parzyste można pokryć krawędziowo w sposób optymalny (żaden wierzchołek nie jest dotykany przez więcej niż jedną krawędź). W tym celu muszę znaleźć cykle. Wystarczy podzielić graf na dwuspójne.
Następnie przejdziemy każdą dwuspójną i weźmiemy co drugą krawędź.


Czy to jest ok ? Może można prościej ?

[Afish]

4. Weź trójkąt — każdy wierzchołek ma stopień dokładnie \(\displaystyle{ 2}\), cykl ma trzy krawędzie.

[matinf]

Czy trójkąt może należeć do grafu dwudzielnego ?

[Afish]

A pardon, zapomniałem o tym warunku.

[matinf]

I co powiesz o tym algorytmie ?

[Afish]

Przede wszystkim jest napisany nieprecyzyjnie, przez co punkt drugi może dać zły wynik (dlaczego? rozważ „wężyk” bez rozwidleń między kilkoma wierzchołkami)
Poza tym wydaje się działać, ale być może to dlatego, że znam klasyczny algorytm do tego problemu. Kilka linków pozostawię do rozważenia:

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Edge_cover#Algorithms

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Hungarian_algorithm

[matinf]

Słuszna uwaga:
Drugie trzeba tak poprawić:
Używaj do tego kolejki. Zawsze sprawdzaj po ściągnięciu z kolejki czy przypadkiem dany węzeł nie jest już pokryty,