Algorytmy zaawansowane

Question

Cześć, mam do wymyślenia algorytm liniowy:

w  grafie G, zbiór krawędzi jest wielokrotnością liczby 3 i ten zbiór podzielono na 3 skojarzenia. Jak skonstruować podział zbioru krawędzi na 3 równoliczne skojarzenia?

Może trzeba użyć ścieżek rozszerzających albo kolorowań? Ktoś może wie?

Answer 1

Hej,

nie wiem czy dobrze zinterpretowałem polecenie. Chodzi o taki podział krawędzi na trzy zbiory M1, M2, M3, że ich liczebności są równe, iloczyn dwóch dowolnych M1, M2, M3 jest zbiorem pustym oraz suma wszystkich jest zbiorem E? A także, że każdy z tych zbiorów jest skojarzeniem?

Jeśli tak to pierwszym założeniem powinno być, że żaden wierzchołek nie posiada stopnia większego niż 3, bo wtedy takie rozdzielenie jest niemożliwe.

Następnie wymyśliłem taki pseudokod polegający na iteracji po wierzchołkach i przydzielaniu klas {1,2,3} krawędziom, które odchodzą od tych wierzchołków. Klasy symbolizują przynależność do zbiorów M1, M2, M3:

1. Dla każdego wierzchołka v należącego do V:
   1. możliwości := lista sładająca się z elementów {1,2,3} o długości stopnia wierzchołka v pomniejszonego o liczbę krawędzi, które mają już przydzieloną klasę.
   2. z każdego elementu listy możliwości usuń te cyfry, które są już klasami odchodzących wierzchołków
   3. Dla każdej nieoznakowanej krawędzi e łącząca wierzchołek v z w:
      1. sprawdź klasy krawędzi odchodzących od wierzchołka w i usuń je z korespondującego elementu listy możliwości
      2. jeśli jakieś elementy listy możliwości mają moc 1 to przypisz im tę klasę oraz usuń ją z wszystkich elementów listy możliwości.
   4. Jeśli jest 1 element z mocą 2 to przypisz mu klasę, która nie pojawia się w drugim sąsiedzie (ponieważ taka sytuacja może mieć miejsce tylko gdy stopień v = 2).
   5. Gdy nie da się tego dokonać lub elementy są dwa to przypisz im dowolną kombinację

Pewnie da się go jakoś uprościć, ale to pierwsze co przyszło mi na myśl. Jeśli to nie to, albo algorytm nie działa dla jakiegoś grafu to postaram się naprawić błąd.