Zlicz wszystkie nieizomorficzne wykresy o określonym rozmiarze

30

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 wierzchołków , bez utraty ogólności, mogę założyć, że wierzchołki są ułożone w taki sposób, że $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ż 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 Dolna granica? Dbam przede wszystkim o podatność na małe (powiedzmy lub $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).

— DW
źródło

1

AFAIK, nawet liczba wykresów wielkości

do izomorfizmu jest znana, więc myślę, że to mało prawdopodobne, że istnieje (nie brute-force) algorytm. Jeśli chodzi o algorytmy kandydujące, pamiętaj, że nie znamy algorytmu wielomianowego do sprawdzania izomorfizmu grafowego (afaik), więc każdy algorytm, który powinien działać w

powinien unikać konieczności sprawdzania izomorfizmu ( często / głupio). (Również

.)

n

$n$

O (| output |)

$O(|\text{output}|)$

| output | = Ω (n \cdot | classes |)

$|\text{output}| = \Omega(n \cdot |\text{classes}|)$

— Raphael

@Raphael, (1) Wiem, że nie znamy dokładnej liczby wykresów wielkości

aż do izomorfizmu, ale ten problem niekoniecznie wymaga wiedzy (np. Z powodu tego, że jestem w porządku z powtórzeniami). Nie wiem, dlaczego to sugeruje, że jest mało prawdopodobne, aby istniał lepszy algorytm niż ten, który podałem. (2) Tak, wiem, że nie jest znany algorytm wielomianowy dla izomorfizmu grafowego, ale będziemy rozmawiać o wartościach

takich jak

tutaj, więc istniejące algorytmy będą prawdopodobnie szybkie - a zresztą wspomniałem tylko algorytm kandydujący do odrzucenia go, więc i tak jest dyskusyjny.

n

$n$

n

$n$

n = 6

$n=6$

— DW

W przypadku

co najwyżej 6 uważam, że po wybraniu liczby wierzchołków i liczby krawędzi i uporządkowaniu etykiet wierzchołków bez zmniejszania według stopnia, jak sugerujesz, będzie bardzo mało możliwych klas izomorfizmu. W tym momencie może okazać się wykonalne posortowanie pozostałych przypadków za pomocą kontroli izomorfizmu brutalnej siły przy użyciu np. NAUTY lub BLISS.

n

$n$

— Simon

19

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.

— David Eisenstat
źródło

Mam problem. Biorę wykres wielkości n-1i rozciągam go o wierzchołek na wszystkie możliwe sposoby, jak pan powiedział. Następnie sprawdzam, czy wierzchołek ma etykietę kanoniczną, powiedzmy 1(wierzchołek kanoniczny ?!). Co jednak, jeśli wykres jest tylko izomorficzny w stosunku do formy kanonicznej, a wierzchołek ma inną etykietę? Próbowałem sprawdzić automorfizmy, aby sprawdzić, czy wierzchołek z etykietą 1znajduje się na tej samej orbicie, ale potem dwukrotnie kończę z wykresem na mojej liście. Papier tak naprawdę mi nie pomaga. Ponadto kod źródłowy geng jest nieczytelny z powodu wszystkich tych binarnych optymalizacji i prawie żadnych komentarzy.

— Alex

1

@Alex Zdecydowanie chcesz wersji czeku, która określa, czy nowy wierzchołek znajduje się na tej samej orbicie co 1. Czy możesz podać przykład, w którym daje to dwa wykresy izomorficzne? Może to byłoby lepsze jako nowe pytanie.

— David Eisenstat,

Okej, bardzo Ci dziękuję! Wydaje mi się, że w takim przypadku „rozszerzenie na wszystkie możliwe sposoby” musi w jakiś sposób rozważyć automorfizmy wykresu z n-1wierzchołkami? np. n = 3, a mój poprzedni wykres to P2. Wówczas dwa przypadki, w których łączę trzeci wierzchołek z jednym z poprzednich wierzchołków, będą oczywiście skutkować tym samym wykresem P3. Czy mógłbyś szybko wyjaśnić, jak właściwie „rozszerzyć na wszystkie możliwe sposoby”, czy powinienem zadać to jako kolejne pytanie? (Czasem też nie jestem pewien, co się dzieje, ponieważ mój program musi znaleźć nieizomorfizmy specjalnego typu wykresu, co komplikuje sprawę)

— Alex

@Alex Tak, wydaje się, że samo rozszerzenie musi być kanoniczne. Prawdopodobnie warte nowego pytania, ponieważ nie pamiętam, jak to działa z mojej głowy.

— David Eisenstat,

1

Strona domowa Nauty

— Guy Coder,

4

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.

— FrankW
źródło

3

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?

— Szymon, Szymek
źródło

Doceniam tę myśl, ale obawiam się, że nie pytam, jak ustalić, czy dwa wykresy są izomorficzne. Naprawdę pytam, jak wyliczyć grafy nieizomorficzne. Obawiam się, że opisywanie algorytmów do testowania, czy dwa wykresy są izomorficzne, naprawdę mi nie pomaga - dziękuję za próbę!

— DW

Turan i Naor (we wspomnianych wyżej artykułach) konstruują funkcje opisanego typu, tj. Które odwzorowują wykres na kanoniczny reprezentant klasy równoważności, do której należy ten wykres. Gdybyś mógł wymienić tych przedstawicieli kanonicznych, wydaje się, że to rozwiązałoby twój problem.

— Simon

Babai wycofał roszczenie dotyczące quasipolynomial runtime . Najwyraźniej wystąpił błąd w analizie.

— Raphael

1

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$

— Pascal Welke
źródło