Na stronie http://www.dharwadker.org/tevet/isomorphism/ znajduje się prezentacja algorytmu do określania, czy dwa wykresy są izomorficzne. Biorąc pod uwagę wiele „powiedzmy” interesujących twierdzeń A Dharwadkera, nie jestem skłonny w to uwierzyć.
W trakcie mojego dochodzenia stwierdziłem, że algorytm z pewnością da poprawną odpowiedź i powiem, że dwa wykresy nie są izomorficzne, chociaż w rzeczywistości są prawidłowe. Nie jest jednak jasne, czy algorytm konsekwentnie powie ci, czy dwa wykresy są w rzeczywistości izomorficzne. „Dowód” ich wyniku pozostawia coś do życzenia.
Nie znam jednak kontrprzykładu. Zanim zacznę pisać oprogramowanie do testowania algorytmu, pomyślałem, że zobaczę, czy ktoś już wie o kontrprzykładzie.
Ktoś poprosił o streszczenie algorytmu. Zrobię, co mogę tutaj, ale aby naprawdę to zrozumieć, powinieneś odwiedzić http://www.dharwadker.org/tevet/isomorphism/ .
Algorytm składa się z dwóch faz: fazy „podpisu” i fazy sortowania. Pierwsza faza „podpisu” (jest to mój termin określający ich proces; nazywają to generowaniem „macierzy znaków”) skutecznie sortuje wierzchołki do różnych klas równoważności. Druga faza najpierw porządkuje wierzchołki zgodnie z ich klasą równoważności, a następnie stosuje procedurę sortowania w ramach klas równoważności, aby ustalić izomorfizm między dwoma wykresami. Co ciekawe, nie twierdzą, że ustanowili kanoniczną formę wykresów - zamiast tego jeden wykres jest używany jako rodzaj szablonu dla drugiego.
Faza podpisu jest w rzeczywistości dość interesująca i nie oddałbym jej tutaj, próbując ją sparafrazować. Jeśli chcesz uzyskać dodatkowe informacje, polecam skorzystanie z linku, aby sprawdzić jego fazę podpisu. Wygenerowana „matryca znaków” z pewnością zachowuje wszystkie informacje o oryginalnym wykresie, a następnie ustanawia nieco więcej informacji. Po zebraniu podpisów ignorują oryginalną macierz, ponieważ podpisy zawierają całą informację o oryginalnej macierzy. Wystarczy powiedzieć, że podpis wykonuje pewną operację, która ma zastosowanie do każdej krawędzi związanej z wierzchołkiem, a następnie zbiera zbiór elementów dla wierzchołka, aby ustalić klasę równoważności dla wierzchołka.
Druga faza - faza sortowania - jest częścią wątpliwą. W szczególności spodziewałbym się, że jeśli ich proces zadziała, to opracowany przez Annę Lubiw algorytm zapewniający „podwójnie leksykalne porządkowanie macierzy” (patrz: http://dl.acm.org/citation.cfm?id=22189 ) działałoby również w celu zdefiniowania postaci kanonicznej dla wykresu.
Szczerze mówiąc, nie do końca rozumiem ich proces sortowania, chociaż myślę, że wykonują rozsądną robotę, opisując go. (Po prostu nie przepracowałem wszystkich szczegółów). Innymi słowy, coś może mi brakować. Nie jest jednak jasne, w jaki sposób ten proces może zrobić znacznie więcej niż przypadkowe znalezienie izomorfizmu. Pewnie, prawdopodobnie znajdą to z dużym prawdopodobieństwem, ale nie z gwarancją. Jeśli dwa wykresy nie są izomorficzne, proces sortowania nigdy go nie znajdzie, a proces poprawnie odrzuca wykresy.