Skojarzenie doskonałe w odpowiednim grafie

[kowal199306]

Dane mamy następujące zadanie:

Są 2 kajaki, n osób oraz zbiór par, które chcą razem przepłynąć się kajakiem (jedna osoba może chcieć się przepłynąć kolejno z wieloma osobami). Zastosować algorytm znajdujący skojarzenie doskonałe do wyznaczenia rozkładu jazdy kajaków, tak aby zminimalizować ilość kursów pojedynczych kajaków. Należy przy tym spełnić życzenia wszystkich osób.

No i pierwszym nasuwającym się pomysłem jest jest budowa grafu w następujący sposób: bierzemy ludzi jako wierzchołki a krawędzie dajemy pomiędzy tymi wierzchołkami, które odowiadają osobom, które chcą razem przepłynąć się kajakami. W takim grafie znajdujemy skojarzenie doskonałe, wybieramy 2 krawędzie (czyli 4 osoby do 2 kajaków) i usuwamy je z grafó oraz dodajemy do rozkładu jazdy. Następnie znowu wyznaczamy skojarzenie itd.

Okazuje sie jednak, że to naiwne rozwiązanie jest błędne, a oto kontrprzykład:

Pięć osób: a,b,c,d,e i pary które chcą się razem przepłynąć:
ab,ac,ad,ae,bd,be,cd

Czyli graf ma 5 wierzchołków, 7 krawędzi.
1. maksymalne skojarzenie: ae,cd -> płyną równolegle
zostają ab,ac,ad,bd,be
2. maksymalne skojarzenie: ac,be -> płyną równolegle
zostają ab,ad,bd
i te 3 pary płyną pojedynczo

A lepiej ożna tak:
ab,cd
ad,be
ae,bd
ac


Należy zatem szukać skojarzenia w innym grafie - niestety nie wiem jakim...

Jedyne co mi wiadomo, to z grafu G (ten opisany wyżej) można otrzymać go za pomocą jakichś dwóch elementarnych operacji, ale nie mam pojęcia jakich - próbowałem drzew rozpinających itp. (może coś przeoczyłem?) Stąd moja prośba o pomoc w rozwiązaniu powyższego problemu. Generalnie dążymy do:


G -> G' -> G''

i w grafie G'' szukamy skojarzenia. Takie wskazówki dostałem.

Pozdrawiam.

[Mruczek]

Napisałeś w treści zadania, że pewne osoby chcą kolejno przepłynąć z innymi. Mam nadzieję, że nie chodzi o to, że podana kolejność par musi być zachowana dla konkretnych osób, w swoim rozwiązaniu nie zachowywałeś tej kolejności. Dlatego zakładam, że żadna kolejność par nie jest ważna.

Zbudujmy graf nieskierowany z par które mają razem przepływać tzn niech wierzchołkami grafu będą pary, a krawędziami połączmy te pary, które są rozłączne (nie mają wspólnego elementu). Wtedy krawędź oznacza, że wierzchołki (pary) połączone tą krawędzią mogą płynąć razem w dwóch łódkach. Szukamy w tym grafie maksymalnego skojarzenia - otrzymamy zbiór krawędzi, czyli par par osób które płyną razem w dwóch łódkach. Wierzchołki nie wybrane do skojarzenia płyną pojedynczo.
Nie zawsze znajdę skojarzenie doskonałe, bo może ono nie istnieć, jak np. w podanym przez Ciebie przykładzie.
Dla Twojego przykładu graf będzie złożony z 7 wierzchołków: ab, ac, ad, ae, bd, be, cd i 5 krawędzi:
ab - cd, cd - be, ac - be, ac - bd, ad - be, ae - cd, ae - bd. Maksymalne skojarzenie w tym grafie to ab - cd, ad - be, ae - bd, pozostaje wierzchołek: ac, czyli się zgadza.
Algorytm wyszukujący maksymalne skojarzenie jest np. tutaj: