Rozwiązania można oglądać między 13.00 a 14.00 w 5790. Można też próbować w innych terminach, ale nie ma gwarancji, że będę u siebie w pokoju.

Zadanie 1.

Część A

W rozwiązaniach pojawiły się dwa podejścia.

Zacznę od nieco bardziej naturalnego. Dla do wejściowego grafu G=(V,E) będziemy budować graf nad zbiorem jego wierzchołków V(G) powiększonym o superźródło s i superujście t. Niech d(v) oznacza różnicę między liczbą krawędzi wychodzących z v a liczbą krawędzi wchodzących do v (w wejściowym grafie).

Wstawiamy następujące krawędzie:

W tym grafie szukamy maksymalnego przepływu o minimalnym koszcie między s a t. Nieskończone przepustowości gwarantują, że zawsze znajdziemy przepływ, który nasyca zarówno krawędzie wychodzące z s, jak i te wchodzące do t (nasycenie jednych jest równoważne nasyceniu drugich). Używane przez nas algorytmy dla sieci o przepustowościach całkowitoliczbowych znajdują całkowitoliczbowe przepływy.

Aby otrzymać wynik, patrzymy na przepływy po krawędziach między wierzchołkami w V(G) i dla każdej krawędzi jej krotność w wynikowym multizbiorze jest wyznaczona przez przepływ po tej krawędzi. Wynik jest poprawny (z warunków na przepływ) oraz optymalny (bo z dowolnego rozwiązania da się uzyskać przepływ).

Możemy ograniczyć wartość maksymalnego przepływu w sieci przez O(|E|) (istnieją również sieci, w których ta wartość jest osiągana). Używamy algorytmu do znajdowania maksymalnego przepływu o minimalnym koszcie (O(|f*|(n2 + m))), zatem cały algorytm działa w czasie O(|E||V|2).

Inne możliwe podejście jest takie, że najpierw znajdujemy najkrótszą ścieżkę między każdą parą wierzchołków, względem wagi w, a następnie korzystamy z konstrukcji podobnej do powyższej, przy czym wstawiamy nieco inne krawędzie (różnica występuje w 3. podpunkcie):

W efekcie dostajemy sieć bez cykli. Gdy użyjemy algorytmu z wykładu, ostateczna złożoność pozostaje taka sama.

Kryteria oceny

Najczęstsze błędy to: Jeśli w rozwiązaniu była sama poprawna konstrukcja sieci (a dalej, np. niepoprawny algorytm), stawiałem 1 punkt.

Część B

Pokażę, że ten problem jest NP-trudny.

Zredukuję do tego problemu problem cyklu Hamiltona w grafie skierowanym. Dla podanego grafu G=(V,E), tworzymy instancję naszego problemu. Składa się ona z grafu o |V| wierzchołkach, który nie zawiera krawędzi, oraz funkcji w danej:

Jasne jest, że do wyniku musimy wziąć co najmniej n krawędzi, zatem minimalna waga to n. Jeśli dostaliśmy rozwiązanie o takim koszcie, to odpowiada ono cyklowi Hamiltona w oryginalnym grafie (graf Eulerowski ma co najmniej n krawędzi, zatem użyliśmy jedynie krawędzi z oryginalnego grafu). Z drugiej strony, cykl Hamiltona wprost wyznacza rozwiązanie o wadze n.

Pozostaje pokazać, że redukcja działa w czasie wielomianowym. W zasadzie jest to jasne, przy czym zakładamy tu, że reprezentacja grafu na |V| wierzchołkach wymaga co najmniej |V| bitów informacji.

Gdyby istniało rozwiązanie wielomianowe dla tego problemu, to istniałoby również rozwiązanie wielomianowe dla dowolnego problemu z klasy NP. Jest to sprzeczne z założeniem , że P ≠ NP, więc rozwiązanie wielomianowe nie może istnieć.

Kryteria oceny

W większości przypadków rozwiązanie było albo w pełni poprawne, albo nie dawało się prosto zmodyfikować do poprawnego, przez co przeważające oceny to 0 lub 4 punkty. W szczególności nie odejmowałem punktów za nienapisanie, że opisywana redukcja działa w czasie wielomianowym.

Zadanie 2.

Rozwiązanie (szkic)

Na początku każdy okręg dzielimy na dwa łuki, które stanowią górną i dolną połówkę okręgu. Dla tego zbioru łuków używamy algorytmu analogicznego do algorytmu znajdowania wszystkich przecięć w podanym zbiorze odcinków. W miotle trzymamy zbiór łuków, które aktualnie ją przecinają, posortowanych względem współrzędnej przecięcia. Kolejność łuków na miotle zmienia się jedynie w momencie przecięcia dwóch łuków. Trzeba jednak pamiętać, że gdy łuki są styczne, przecięcie nie doprowadzi do zamiany ich kolejności.

Kryteria oceny

Nie było wymagane opisanie kolejności przetważania zdarzeń o takiej samej współrzędnej.