• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytmy zaawansowane

VPS Starter Arubacloud
0 głosów
386 wizyt
pytanie zadane 28 czerwca 2020 w Algorytmy przez xdelvis Nowicjusz (120 p.)
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?

1 odpowiedź

0 głosów
odpowiedź 28 czerwca 2020 przez fedora Użytkownik (500 p.)

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.

Podobne pytania

0 głosów
0 odpowiedzi 218 wizyt
pytanie zadane 4 grudnia 2016 w C i C++ przez martix3 Użytkownik (690 p.)
0 głosów
0 odpowiedzi 92 wizyt
0 głosów
1 odpowiedź 158 wizyt
pytanie zadane 23 czerwca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,831 zapytań

141,772 odpowiedzi

320,818 komentarzy

62,160 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...