Izomorfizm Grafow I Inne Problemy Grafowe

Opis zajęć

Na tych warsztatach zajmiemy się badaniem następującego problemu: Czy dane dwa grafy są izomorficzne? Nie istnieje do tej pory żaden ogólny algorytm wielomianowy odpowiadający na to pytanie, przez co temat jest bardzo interesujący. Poznamy algorytmy wielomianowe badające izomorfizm takich grafów które posiadają różne dodatkowe własności, ułatwiające szukanie wspomnianego izomorfizmu (np. grafy planarne). Zobaczymy kilka przykładów szczególnych klas grafów dla których wiemy, że badanie izomorfizmu nie jest łatwiejsze niż problem ogólny (np. sprawdzenie czy izomorficzne są dwa grafy dwudzielne). Podejdziemy też do tego z innej strony i przekonamy się, że izomorfizm grafów jest w pewnym sensie "łatwy" - zobaczymy dlaczego większość informatyków twierdzi, że nie jest to problem NP-zupełny.

Program

  • Algorytmy wielomianowe rozwiązujące nasz problem dla różnych klas grafów (drzewa, kografy, …).
  • Algorytmy probabilistyczne - pierwszy algorytm typu Las Vegas (jak wyżej - izomorfizm grafów szczególnej postaci).
  • Kilka klas grafów dla których rozwiązanie problemu izomorfizmu grafów jest tak samo trudne, jak przypadek ogólny.
  • Dlaczego uważamy, że izomorfizm grafów nie jest NP-zupełny.

Wymagania

Zdecydowanie potrzebne będzie podstawowe obycie algorytmiczne, w miarę intuicyjne rozumienie pojęcia "złożoność obliczeniowa", no i podstawy teorii grafów. Program mamy bardzo szeroki - więc będzie można wybrać tylko część tematów, tak aby dostosować się do Waszych chęci - jeśli znacie podstawy algebry liniowej, czy teorii złożoności - to miło. (Jeśli nie, to też całkiem nieźle).

Literatura

I tak nie wierzę, że ktoś będzie szukał - ale jeśli tak, to przydałoby się jakieś wprowadzenie do algebry liniowej, wprowadzenie do teorii złożoności. O izomorfizmie grafów nie musicie czytać, przecież po to są te warsztaty, żeby się o tym czegoś dowiedzieć.

Zadanie kwalifikacyjne:

Rozwiązanie zadania to opis algorytmu wraz z ogólnymi wskazówkami "dlaczego to działa" - jeśli to nie jest oczywiste. Nie chodzi mi tutaj o formalny dowód - nie jest konieczny, wystarczy uzasadnienie w dwóch zdaniach. Jak będzie tego za mało (nie będę rozumiał dlaczego algorytm działa) to będę pytał, nie traci się za to punktów.

Dwa zadania, bardzo możliwe że wystarczy zrobienie jednego z nich - nie martwcie się więc, jeśli nie macie obu:

Zadanie 1:
Mamy dane dwa drzewa. Sprawdź czy drzewo pierwsze jest izomorficzne z dowolnym podgrafem indukowanym drzewa drugiego (innymi słowy: czy istnieje podgraf indukowany drzewa 2 izomorficzny z drzewem 1). Oczekuję złożoności nie gorszej niż $O(n^5)$ - ale jeśli macie cokolwiek wielomianowego to też nieźle.

Zadanie 2:
Dany jest graf - część jego krawędzi jest skierowana (silnie rozróżniamy tutaj krawędź nieskierowaną od dwóch krawędzi skierowanych - w jedną i drugą stronę). Tak zadany graf częściowo skierowany jest silnie spójny (z każdego wierzchołka można dojść do każdego innego). Ile co najwyżej możemy skierować krawędzi spośród tych nieskierowanych, aby graf pozostał silnie spójny? Oczekiwana złożoność: $O(|E|^2)$ lub lepsza.

Mój adres email: jaro3000 miau gmail.com

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License