Chciałbym zapytać, czy jest na to już opublikowany wynik:
Bierzemy wszystkie możliwe różne ścieżki między każdą parą węzłów dwóch połączonych regularnych (o powiedzmy stopnia , i liczby węzłów ) wykresów i zapisujemy ich długości. Oczywiście ta liczba odrębnych ścieżek ma charakter wykładniczy. Moje pytanie brzmi: jeśli posortujemy długości i porównamy je (listy uzyskane z dwóch wykresów) i są one dokładnie takie same, czy możemy powiedzieć, że dwa wykresy są izomorficzne?n
Oczywiście, nawet jeśli jest to wynik, nie możemy go użyć do odpowiedzi na wykres Izomorfizm, ponieważ liczba różnych ścieżek jest wykładnicza, jak powiedziano
Przez różne ścieżki rozumiem oczywiście ścieżki mające co najmniej jeden inny węzeł.
Dziękuję z góry za pomoc.
Odpowiedzi:
Uważam, że odpowiedź na twoje pytanie brzmi „nie”, ponieważ równoważny warunek oznaczałby wielomianowe rozwiązanie GI.
W przypadku macierz przyległości wykresu należy zauważyć, że liczba ścieżek od do długości wynosi (przy dozwolonym powtórzeniu wierzchołków i krawędzi). Na dwóch wykresach i (z sąsiedztwa macierzy i ) i , gdy sortowane elementy i , a następnie w celu bycia izomorficzna jest to konieczny warunek, że listy są identyczne dla wszystkich .G i j k ( A k ) i , j G 1 G 2 A 1 A 2 k ≥ 1 A k 1 A k 2 G 1 G 2 kZA sol ja jot k (Ak)i,j G1 G2 A1 A2 k≥1 Ak1 Ak2 G1 G2 k
Uważam, że twoje przypuszczenie jest równoważne z:
Jeżeli sortowane wykaz elementów i są identyczne dla do (górna granica w najdłuższej ścieżce z wierzchołków niepowtarzającego), a następnie i są izomorficzne. A d 2 k = 1 n - 1 G 1 G 2Ak1 Ad2 k=1 n−1 G1 G2
Aby rozwiązać GI, wystarczy wykonać mnożenia macierzy (i trochę więcej czasu na sortowanie i porównywanie elementów). Zajmie to mniej niż czasu.n × n n 2 n 4n−1 n×n n2 n4
Przyznaję dwie możliwe wady w mojej argumentacji. Po pierwsze, jest całkowicie możliwe, że GI ma algorytm wielomianowy i że właśnie go odkryliśmy, właśnie teraz (brawo, jesteśmy sławni!). Uważam to za bardzo mało prawdopodobne. Po drugie (i o wiele bardziej prawdopodobne) to, co zaproponowałem, nie jest w rzeczywistości równoznaczne z twoją hipotezą.
Końcowa myśl. Czy wypróbowałeś to dla wszystkich, powiedzmy, 3-regularnych wykresów dla rozmiaru około 8? Sądzę, że jeśli twoje przypuszczenie jest fałszywe, powinien istnieć przeciwny przykład na 3-regularnych wykresach o dość małym rozmiarze.
źródło
Ponieważ porównujesz tylko długości ścieżek (a tymczasem zapominasz, jaką parę węzłów odpowiadają, jeśli dobrze cię rozumiem), myślę, że bardzo podobne wykresy powinny zapewnić kontrprzykład: w końcu po prostu liczysz liczba ścieżek o stałej długości i niezależnie od wierzchołków, które łączą. Na przykład myślę, że te wykresy są kontrprzykładem: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif i http://www.mathe2.uni-bayreuth.de/ markus / REGGRAPHS / GIF / 06_3_3-1.gif
Jeśli się nie mylę (liczenie ścieżek jest uciążliwe), oba mają po 9 ścieżek o długości 1, 18 ścieżek o długości 2, 48 ścieżek o długości 3, 30 ścieżek o długości 4 i 36 ścieżek o długości 5
źródło
źródło