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 ?
[Algorytmy]Minimalne pokrycie krawędziowe grafu dwudzielnego
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
[Algorytmy]Minimalne pokrycie krawędziowe grafu dwudzielnego
Ostatnio zmieniony 9 gru 2015, o 06:57 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy]Minimalne pokrycie krawędziowe grafu dwudzielnego
4. Weź trójkąt — każdy wierzchołek ma stopień dokładnie \(\displaystyle{ 2}\), cykl ma trzy krawędzie.
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy]Minimalne pokrycie krawędziowe grafu dwudzielnego
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:
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
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
[Algorytmy]Minimalne pokrycie krawędziowe grafu dwudzielnego
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,
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,