Zlicz wszystkie nieizomorficzne wykresy o określonym rozmiarze

Chciałbym wyliczyć wszystkie niekierowane wykresy wielkości , ale potrzebuję tylko jednego wystąpienia każdej klasy izomorfizmu . Innymi słowy, chcę wyliczyć wszystkie nieizomorficzne (niekierowane) wykresy na wierzchołkach. W jaki sposób mogę to zrobić?$n$$n$

Dokładniej, chcę algorytmu, który wygeneruje sekwencję niekierowanych wykresów , z następującą właściwością: dla każdego niekierowanego wykresu na wierzchołkach istnieje indeks taki, że jest izomorficzny do . Chciałbym, aby algorytm był tak wydajny, jak to możliwe; innymi słowy, miarą, na której mi zależy, jest czas działania do wygenerowania i iteracji po tej liście wykresów. Drugi cel polega na tym, że byłoby miło, gdyby algorytm nie był zbyt skomplikowany do wdrożenia.$G_1,G_2,\dots,G_k$$G$$n$$i$$G$$G_i$

Zauważ, że muszę mieć co najmniej jeden wykres z każdej klasy izomorfizmu, ale jest OK, jeśli algorytm wytwarza więcej niż jedną instancję. W szczególności jest OK, jeśli sekwencja wyjściowa zawiera dwa wykresy izomorficzne, jeśli pomaga to w znalezieniu takiego algorytmu lub umożliwia wydajniejsze algorytmy, o ile obejmują wszystkie możliwe wykresy.

Moja aplikacja jest następująca: Mam program, który chcę przetestować na wszystkich wykresach wielkości . Wiem, że jeśli dwa wykresy są izomorficzne, mój program będzie działał tak samo na obu (będzie albo poprawny na obu, albo niepoprawny na obu), więc wystarczy wyliczyć przynajmniej jednego przedstawiciela z każdej klasy izomorficznej, a następnie przetestować program na tych wejściach. W mojej aplikacji jest dość małe.$n$$n$

Niektóre algorytmy kandydujące, które rozważałem:

• Mógłbym wyliczyć wszystkie możliwe macierze przylegania, tj. Wszystkie macierze symetryczne $n\times n$ 0-lub-1, które mają wszystkie zera na przekątnych. Wymaga to jednak wyliczenia $2^{n(n-1)/2}$ macierzy. Wiele z tych matryc będzie reprezentować grafy izomorficzne, więc wygląda na to, że marnuje dużo wysiłku.

• Mógłbym wyliczyć wszystkie możliwe macierze przylegania i dla każdej przetestować, czy jest on izomorficzny na którymkolwiek z wcześniej wygenerowanych wykresów; jeśli nie jest izomorficzny w stosunku do jakichkolwiek danych wyjściowych, wyślij go. To znacznie skróciłoby listę wyjściową, ale nadal wymaga co najmniej kroków obliczeniowych (nawet jeśli założymy, że sprawdzenie izomorfizmu wykresu jest super szybkie), więc według mojej metryki nie jest dużo lepsze.$2^{n(n-1)/2}$

• Możliwe jest wyliczenie podzbioru macierzy przylegania. W szczególności, jeśli jest wykresem n wierzchołków V = { v 1 , … , v n } , bez utraty ogólności, mogę założyć, że wierzchołki są ułożone w taki sposób, że deg v 1 ≤ deg v 2 ≤ ⋯ ≤ deg v $G$$n$$V=\{v_1,\dots,v_n\}$$\deg v_1 \le \deg v_2 \le \cdots \le \deg v_n$. Innymi słowy, każdy wykres jest izomorficzny do tego, w którym wierzchołki są ułożone w kolejności nie malejącej. Wystarczy więc wyliczyć tylko macierze przyległości, które mają tę właściwość. Nie wiem dokładnie, ile jest takich macierzy przylegania, ale jest ich znacznie mniej niż i można je policzyć o wiele mniej niż 2 n ( n - 1 ) / 2 kroków obliczenie. Jednak nadal pozostawia to wiele nadmiarowości: wiele klas izomorfizmu będzie nadal objętych wiele razy, więc wątpię, aby było to optymalne.$2^{n(n-1)/2}$$2^{n(n-1)/2}$

Czy możemy zrobić lepiej? Jeśli dobrze rozumiem, jest około klasy równoważności grafów nieizomorficznych. Czy możemy znaleźć algorytm, którego czas działania jest lepszy niż powyższe algorytmy? Jak blisko możemy dojść do ∼ 2 n ( n - 1 ) / 2 / n ! Dolna granica? Dbam przede wszystkim o podatność na małe n (powiedzmy n = 5 lub n = $2^{n(n-1)/2}/n!$$\sim 2^{n(n-1)/2}/n!$$n$$n=5$$n=8$lub tak; wystarczająco małe, aby można było uruchomić taki algorytm do końca), nie tyle o asymptotykach dla dużego .$n$

Powiązane: Konstruowanie nierównych macierzy binarnych (choć niestety wydaje się, że nie otrzymano prawidłowej odpowiedzi).

Prawdopodobnie najłatwiejszym sposobem wyliczenia wszystkich wykresów nieizomorficznych dla małych zliczeń wierzchołków jest pobranie ich z kolekcji Brendana McKaya . Algorytm wyliczenia jest opisany w pracy McKaya [1] i działa poprzez rozszerzanie nieizomorfów o wielkości n-1 na wszystkie możliwe sposoby i sprawdzanie, czy nowy wierzchołek był kanoniczny. Jest zaimplementowany jak gengw programie do sprawdzania izomorfizmu wykresu McKaya nauty.

[1]: BD McKay, Zastosowania techniki numerowanego znakowania , Congressus Numerantium, 40 (1983) 207-221.

Proponuję ulepszenie twojego trzeciego pomysłu: wypełnij macierz przylegania rząd po rzędzie, śledząc wierzchołki, które są równoważne pod względem stopnia i przyległości do wcześniej wypełnionych wierzchołków. Tak więc początkowo klasy równoważności będą się składać ze wszystkich węzłów o tym samym stopniu.
Gdy nowo wypełniony wierzchołek sąsiaduje tylko z niektórymi równoważnymi węzłami, każdy wybór prowadzi do reprezentantów z tych samych klas izomorfizmów. Rozważamy więc tylko przypisanie, w którym aktualnie wypełniony wierzchołek sąsiaduje z równoważnymi wierzchołkami o największej liczbie (i dzielimy klasę równoważności na dwa dla pozostałego procesu).

$n<6$
$(1,2)$$(3,4)$$n=6$

Naiwna implementacja tego algorytmu wpada w ślepe zaułki, gdzie okazuje się, że nie można wypełnić macierzy przyległości zgodnie z danym zestawem stopni i wcześniejszymi zadaniami. Warto wcześnie wykryć / odfiltrować je. Jakieś pomysły:

• Jeśli suma stopni jest nieparzysta, nigdy nie utworzą wykresu
• Wypełnij wpisy dla wierzchołków, które muszą być natychmiast połączone ze wszystkimi / żadnym z pozostałych wierzchołków.

Te dokumenty mogą być interesujące.

„O zwięzłej reprezentacji grafów”, Gyorgy Turan, Discrete Applied Mathematics, tom 8, wydanie 3, lipiec 1984, s. 289-294 http://www.sciencedirect.com/science/article/pii/0166218X84901264

„Zwięzłe przedstawienie ogólnych nieznakowanych wykresów”, Moni Naor, Discrete Applied Mathematics, tom 28, wydanie 3, wrzesień 1990, s. 303–307 http://www.sciencedirect.com/science/article/pii/0166218X9090011Z

Przedstawiają funkcje kodowania i dekodowania do kodowania wykresu oznaczonego wierzchołkiem, dzięki czemu dwa takie wykresy są odwzorowane na to samo słowo kodowe, tylko wtedy, gdy jeden wynika z permutacji etykiet wierzchołków drugiego.

Ponadto udowodniono, że funkcje kodowania i dekodowania są wydajne.

Pierwszy artykuł dotyczy grafów płaskich. W drugim artykule ograniczenie płaskości zostało usunięte.

EDYCJA: Ten dokument może być również odpowiedni:

Wykres Izomorfizm w czasie quasi-wielomianowym, Laszlo Babai, University of Chicago, Preprint on arXiv, 9 grudnia 2015 http://arxiv.org/pdf/1512.03547v1.pdf

Ogłoszenie przez Babai jego wyniku opublikowało wiadomość: https://www.sciencenews.org/article/new-alameterm-cracks-graph-problem

Ale może się mylę, łącząc pytanie PO z tymi trzema artykułami? OP chce wyliczyć grafy nieizomorficzne, ale nadal pomocne mogą być skuteczne metody określania, kiedy dwa wykresy są izomorficzne?

Istnieje dokument z początku lat dziewięćdziesiątych dotyczący dokładnie tego pytania:

Wydajne algorytmy do wyświetlania wykresów nieznakowanych autorstwa Leslie Goldberga.

Podejście to gwarantuje, że dokładnie jeden reprezentant każdej klasy izomorfizmu jest wyliczony i że istnieje jedynie opóźnienie wielomianowe między generowaniem dwóch kolejnych wykresów.

$n$