Kreczmar – Dzień 4

Omówienie zadań 2006-07-23
Dzień 4

1. Rysio budowniczy

Sprawdzić czy dany na wejściu graf jest planarny.

Złożoność: O(n)
Klasa: algorytmy grafowe

G(V, E)
|E|<=3*|V|-6

Podgrafy Kurakowskiego (odsyłam na wikipedie).

Wszystkie mosty możemy usunąć.

Zmieniamy graf za pomocą DFS na palmę (?). Wszystkie rozgałęzienia DFS traktujemy jako liście. Pamiętamy też drogi powrotu. Następnie zmieniamy numeracje (od korzenia do liści). Następnie używamy DFS po raz kolejny żeby podzielić graf na segmenty. Segment to zbiór ścieżek z drogą powrotną, tworzący cykl. Dla każdego wierzchołka trzymamy najgłębszy element powrotu. Umieszczamy kolejno segmenty. Za każdym razem sprawdzamy czy umieszczony segment koliduje z poprzednimi. Jeśli tak, to umieszczamy drogę powrotną po drugiej stronie. Krawędzie można umieszczać metodą zachłanną, ale nie jest to metoda najoptymalniejsza.

Algorytm Hopcroft i Tarjan (1974)
(wykładowca odsyła do googli)

2. Trójkąty

Dany jest zbiór punktów. Znajdź trójkąt o największym polu, którego wierzchołki są punktami.

Złożoność: O(n*lgn)

Sprawdzenie wszystkich możliwości zajmie O(n^3), co jest zbyt duże dla danych w teście. Pierwszym krokiem do optymalniejszego rozwiązania problemu, jest obliczenie wypukłej otoczki. Dalej bierzemy tylko punkty na otoczce. Jeśli będziemy rozpatrywali dla wszystkich punktów trójkąt spamiętując od którego punktu należy zaczynać, otrzymamy rozwiązanie o złożoności O(n^2).

Algorytm liniowy, na początku wygląda tak samo jak w kwadratówce. Trik polega na tym, że przesuwamy wszystkie punkty zgodnie ze wskazówkami zegara, tak żeby zwiększać pole. Jeśli nie jest to możliwe przesuwamy 2 punkt.
(nie wiadomo dlaczego miałoby to działać)

Leave a Comment

Name:
E-mail:
URI:
Enter this code: