Czy ktoś zna przeciwny przykład algorytmu grafowego izomorfizmu Dharwadkera-Teveta?

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.

Dla graphA.txt:

25
 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1
 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1
 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0
 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1
 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0
 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1
 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1
 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0
 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1
 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0
 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0
 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0
 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1
 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1
 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1
 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0

i graphB.txt:

25
 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0
 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0
 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1
 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0
 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1
 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1
 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1
 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0
 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1
 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1
 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0
 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1
 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0
 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0
 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0
 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1
 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1
 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1
 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1
 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0
 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0

który jest uzyskiwany graphA.txtprzez zastosowanie (losowej) permutacji

 22 9 24 11 15 8 5 18 13 14 2 10 23 0 3 17 4 16 6 19 7 21 12 1 20

program C ++ isororphism.cppz rysunku 6.3. Program C ++ dla algorytmu grafowego izomorfizmu w http://www.dharwadker.org/tevet/isomorphism/ zapewnia następujące dane wyjściowe:

The Graph Isomorphism Algorithm
by Ashay Dharwadker and John-Tagore Tevet
http://www.dharwadker.org/tevet/isomorphism/
Copyright (c) 2009
Computing the Sign Matrix of Graph A...
Computing the Sign Matrix of Graph B...
Graph A and Graph B have the same sign frequency vectors in lexicographic order but cannot be isomorphic.
See result.txt for details.

Możemy więc założyć, że jest to przeciwny przykład dla algorytmu grafowego izomorfizmu grafu Dharwadkera-Teveta.

Problemem jest, jak sugeruje Prowincja Billa

4.1 Propozycja. Jeśli wykresy i są izomorficzne, algorytm znajduje izomorfizm.G $G_A$$G_B$

Zarzut prowincji Billa polega na tym, że dowód Propozycji 4.1. nie używa żadnej specjalnej właściwości macierzy znaków, która nie miałaby również zastosowania do macierzy sąsiedztwa. Dokładniej, następujący krok w dowodzie jest błędny:

Dla hipotezy indukcyjnej, załóżmy, że wiersze z i zostały idealnie dopasowane przez wewnętrzny 3.4 tak, że etykiety wierzchołków dla rzędów z są i etykiety wierzchołków do rzędów z są odpowiednio.A B 1 , . . . , T A v 1 , . . . , V T 1 , . . . , t $1, ..., t$$A$$B$$1, ..., t$$A$$v_1, ..., v_t$$1, ..., t$$B$$φ(v_1) = v'_1, ..., φ(v_t) = v'_t$

ponieważ nawet jeśli wiersze zostały idealnie dopasowane, nie oznacza to, że etykiety wierzchołków pasują do etykiet podanych przez dowolny izomorfizm .$φ$

Ponieważ zidentyfikowano dziurę w dowodzie poprawności, powyższy kontrprzykład powinien wystarczyć do obalenia twierdzonej poprawności proponowanego algorytmu.

Podziękowania Kontrprzykład jest pierwszą z 8 par wykresu od

http://funkybee.narod.ru/graphs.htm

Aby manipulować wykresami, użyłem i zmodyfikowałem kod źródłowy z ScrewBoxR1160.tar znalezionego na

https://people.mpi-inf.mpg.de/~pascal/software/

Aby zrozumieć lukę w dowodzie poprawności, bardzo pomocny był komentarz Andrása Salamona na temat Weisfeiler-Lehman, podobnie jak wyjaśnienia z

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

Motywację do wykorzystania tego pytania jako okazji do zapoznania się z nauty / Traces i praktycznymi aspektami izomorfizmu grafów zapewnił vzn. Korzyści płynące z nauki korzystania z najnowocześniejszych programów do izomorfizmów graficznych sprawiły, że warto poświęcić trochę czasu na znalezienie kontrprzykładu (który, jak wierzyłem, istnieje).