Проблема изоморфизма графов. Пригоден ли алгоритм Спарроу?

[sqribner48]

Можно ли использовать алгоритм Спарроу расчета автоморфно эквивалентных классов вершин для определения изоморфизма графов?
(напомню, что две подобные по Харари вершины называются автоморфно эквивалентными).
Недавно нашел две интересные работы по определению автоморфно эквивалентных классов вершин графов:
<1.> Malcolm K. Sparrow, A linear algorithm for computing automorphic equivalence classes: the numerical signatures approach, Social Networks, Volume 15, Issue 2, June 1993, Pages 151-170, ISSN 0378-8733.
Статью можно скачать по ссылке, любезно предоставленной Aritaborian,
здесь
<2.> Southwell R. Finding Symmetries in Graphs. Ph.D. thesis. University of York, UK, 2006.
109 p.
Диссертацию можно скачать по ссылке: https://richardsouthwell.files.wordpress.com/2010/08/msc.pdf

К сожалению, я не знаток английского языка, но используя переводчик, я вроде бы понял
следующее:
1. В статье Спарроу был предложен и обоснован итерационный алгоритм для определения автоморфно эквивалентных классов вершин. На каждой $n$-ой итерации для каждой
$i$ -той вершины алгоритм генерирует число $S_{i,n}$, называемое числовой сигнатурой $n$ -го порядка. При генерации используется число $\pi$.
2. На $n$-ой итерации числовая сигнатура вершины $v_i$ вычисляется по следующему выражению:

$$S_{i,n}= (|N^k[v_i]|+ \sqrt\pi) \prod_{v_j \in N[v_i]} (\pi + S_{j,n-1}),$$

Где $N^k[v_i]$ -- окрестность $k$ –го порядка вершины $v_i$ (т.е. множество вершин, находящихся на расстоянии
$\le k$; $N[v_i]$ -- множество вершин, смежных с вершиной $v_i$; $S_{j,n-1}$ -- сигнатура $j$-той вершины, полученная на $(n-1)$-той итерации; $|A|$ -- как обычно, число элементов множества $A$.
3. После завершения вычисления числовых сигнатур всех вершин производится их сравнение. Вершины с одинаковым значением сигнатуры вводятся в один класс.
4. Алгоритм очень прост в реализации и имеет линейную по числу $m$ ребер временную сложность, (т.е. $0(m)$ ) и пригоден как для простых неориентированных графов, так и для ориентированных графов и графов с параллельными ребрами.

(Оффтоп)

Сделал программу в Mathematica:

algSparrowL[adl_,k_,T_]:=Module[{n,deg,newS,degx,sp,s,p,Nk,niv},
    n=Length[adl];p=Pi; s=Table[0,{i,1,n}];deg=Table[0,{i,1,n}];
    Nk=Table[0,{i,1,n}];newS=Table[0,{i,1,n}];
    Do[ m=adl[[i]];deg[[i]]=Length[m];
      Nk[[i]]=Length[Neighborhood[adl, i, k]]-1;
      s[[i]]=Nk[[i]],{i,1,n}];
    Do[
      Do[sp = Nk[[i]] + Sqrt[p]; niv = deg[[i]];
        Do[ u = adl[[i,j]];sp = sp*((p + s[[u]])),                                      
          {j,1, niv}];
        newS[[i]] = sp//N,                                         
        {i,1,n}];
      Do[s[[i]] = newS[[i]],{i,1,n}];Print[s],                                       
      {t,1,T}];s ]

Здесь $adl$ -- список смежностей, $k$ -- глубина сигнатуры, $T$ -- количество итераций,
$deg$ -- список степеней вершин, $s$ -- список числовых сигнатур, $t$ – номер итерации,
$j$ -- номер вершины смежной с $i$ –той вершиной. Neighborhood – стандартная функция.
Проверил для всех 5-ти графов, рассмотренных в статье.
Вроде работает как показано в статье. Однако есть еще некоторые сомнения (выражение (3) в статье) .

Вот возникшие у меня вопросы:
1. Правильно ли я понял (перевел) алгоритм Спарроу?
Была использована как статья Спарроу, так и диссертация Саутвелла (на стр. 53, 54 описание алгоритма)
2. Можно ли использовать алгоритм Спарроу расчета автоморфно эквивалентных классов вершин для определения изоморфизма графов?
При этом, для определения изоморфизма двух графов можно рассмотреть три следующих метода:
а) для каждого графа по отдельности вычисляются числовые сигнатуры вершин и затем производится их сравнение;
б) графы объединяются в один (операция объединения по Харари), затем вычисляются числовые сигнатуры вершин и сравниваются;
в) графы объединяются в один, добавляется одна вершина и новые ребра, соединяющие ее со всеми вершинами обоих графов; затем вычисляются числовые сигнатуры вершин и сравниваются.
P.S. Я понимаю, что статья Спарроу была написана в 1993 году и если бы его алгоритм помог решить проблему GI , то это наверно было бы сделано. Значит там «что-то не так».
Вот поэтому то я и прошу помощи у математиков форума чтобы разобраться в этих вопросах.

[sqribner48]

В моем первом сообщении по этой теме один из вопросов, заданных мной, был вопрос:
"Правильно ли я понял (перевел) алгоритм Спарроу?"
К сожалению, из-за сложности английского текста статьи Спароу я не совсем правильно перевел и поэтому не совсем правильно понял алгоритм расчета автоморфно эквивалентных классов вершин. В этом также был «виноват» отрывок диссертации Ричарда Саутвэлла, в котором алгоритм Спарроу был описан так:

Цитата:

Sparrow’s algorithm can be applied to a graph $G$, on a vertex set $\{v_1, v_2, \dots, v_n\}$
as follows:
0) Select an appropriately large value of $T \in N^+$, this $T$ is the number of
iterations for which the algorithm will perform the update procedure, certainly
$T = |G|$ is sufficiently large and often small values such as
$T = 2$ or $T = 3$ will
be sufficient for the algorithm to find all the automorphically equivalent vertices.
1) Attribute to each vertex, $v_i \in G$ a function \delta^t(v_i), representing the value of the so called ’numerical signature’ on $v_i$ at the tth iteration of the method. Set $\delta^0(v_i) = deg(v_i), \; \forall v_i \in G.$
2) Then for $t$ from 1 to $T$ we, simultaneously, perform the update operation

$$\delta^{t+1}(v_i) = (|N^k(v_i)| + \sqrt \pi) \prod _{ u \in N(v_i)}(\pi + \delta^t(u)), \; \forall v_i \in G.$$

3) We check to see if $\delta^T (v_i) = \delta^T (v_j)$ for all pairs of vertices $ v_i, v_j ∈ G : v_i =v_j$.
Whenever this is the case we have that the vertex pair $\{v_i, v_j\}$ are automorphically equivalent.

(Оффтоп)

К тому же, в приложении диссертации Саутвэлл привел свою реализацию алгоритма Спарроу в системе Maple:

> #Sparrows algorithm:basic
> sparrow:=proc(GG,nn,T):
> S:=array(1..nn):
> deg:=array(1..nn):
> for x from 1 to nn do
> degx:=0:
> for y from 1 to nn do
> degx:=degx+GG[x,y]:
> end do:
> S[x]:=degx:
> deg[x]:=degx:
> end do:
>
> for t from 1 to T do
> for x from 1 to nn do:
> sp:=evalf(deg[x]+Pi^0.5):
> for y from 1 to nn do
> if GG[x,y]=1 then
> sp:=(sp*(Pi+S[y])):
> end if:
> end do:
> newS[x]:=evalf(sp):
> end do:
>
> for x from 1 to nn do
> S[x]:=newS[x]:
> end do:
> end do:
> return(S):
> end proc:

Таким образом, фактически в своем первом сообщении я привел алгоритм Спарроу в модификации Саутвэлла. Именно этот алгоритм я и реализовал в системе Mathematica и привел его в своем первом сообщении.
Как я указывал, алгоритм в модификации Саутвэлла показал хорошие результаты по декомпозиции вершин тестовых графов на автоморфно эквивалентные классы.
Однако, у меня еще оставались некоторые сомнения по тексту статьи Спарроу.
К счастью, эти сомнения были почти полностью рассеяны с помощью ЗУ форума:
Dan B-Yallay и venco, которые быстро и красиво перевели (в разделе: «Помогите с английским переводом терминов») интересующие меня места из статьи Спарроу.
За это приношу им свою благодарность!

(Оффтоп)

Вот этот ключевой для понимания кусок текста:

Цитата:

For the algorithm to discriminate successfully between nodes on the basis of cyclical structures we need to build this refinement into the computation of signatures. This is accomplished by updating a binary copy of the adjacency matrix in such a way that the jth column at time
t(n) shows which nodes have contributed to node j’s nth order signature. This is equivalent to keeping track of the nodes reachable by paths of length <n from node j.
Then, when calculating the nth order signatures, first calculate the number of contributing nodes (the size of the nth order neighborhood). Call it SPAN. And incorporate SPAN into the signature
calculation in some suitably complex way - for example:

$$S_{i,n}=(SPAN +\sqrt \pi) \prod^k(\pi + S_{k,n-1}), \quad (3)$$

здесь, как было ранее показано, $k$ -- номер вершины $v_k$, смежной с вершиной $v_j$.
Отсюда я полагаю, что произведение производится по всем вершинам, смежным с вершиной $v_i$, а SPAN есть размер окружения $n$–го порядка вершины $v_i$.

С учетом вышеизложенного, выкладываю правильный алгоритм Спарроу.
1. Сначала всем вершинам $v_i \in V(G)$ графа $G$ присваиваются начальные (нулевые) значения числовых сигнатур $S_{i,0}$, равные степеням вершин $deg(v_i)$, то есть
$S_{i,0}= deg(v_i), \; \forall v_i \in V(G)$
2. На первой итерации числовые сигнатуры 1-го порядка вершин вычисляются по следующим выражениям:

$$S_{i,1}= (deg(v_i) + \sqrt\pi) \prod_{v_j \in N[v_i]} (\pi + S_{j,0}),\; \forall v_i \in G $$

где $N[v_i]$ -- множество вершин, смежных с вершиной $v_i$.
3. На $k$-ой итерации $(1 < k \le n)$ числовые сигнатуры $k$-го порядка вершин вычисляются по следующим выражениям:

$$S_{i,k}= (|N^k[v_i]|+ \sqrt\pi) \prod_{v_j \in N[v_i]} (\pi + S_{j,k-1}),\; \forall v_i \in G $$

Где $N^k[v_i]$ -- окрестность $k$–го порядка вершины $v_i$ (т.е. множество вершин, находящихся на расстоянии $\le k$ от вершины $v_i$; $N[v_i]$ -- множество вершин, смежных с вершиной $v_i$; $n$-- общее количество выполняемых итераций.
4. После завершения вычисления числовых сигнатур (необходимого) $n$-го порядка всех вершин производится их сравнение. Вершины с одинаковым значением сигнатуры вводятся в один класс. Процесс вычисления автоморфно эквивалентных классов реализуется в отдельной процедуре. Эту процедуру также можно выполнять и после выполнения каждой $k$--той итерации.
Алгоритмы расчета числовых сигнатур и определения автоморфно эквивалентных классов были мной реализованы в системе Mathematica в виде функций algSparrowL и AutMorphClasses.
Проверка на тестовых графах из статьи Спароу показала их высокую работоспособность. При этом следует отметить, что искомое разложение вершин графов на автоморфно эквивалентные классы происходило значительно быстрее чем в примерах, приведенных в статье.

Можно считать, что ответ на свой первый вопрос я получил.
Остался мой второй вопрос о пригодности алгоритма Спарроу.
Ясно что при этом здесь речь идет не просто о пригодности алгоритма по расчету автоморфно эквивалентных классов.

(Оффтоп)

Хотя в статье были указаны некоторые недостатки алгоритма и его ограничения по видам графов на которых алгоритм правильно работает.
Так, в статье было прямо указано, что алгоритм не работает на distance-regular but not distance-transitive графах.
Один из таких графов (граф AVLF) был впервые приведен в статье:
Adelson-Velskii, G. M.; Veisfeiler, B. Ju.; Leman, A. A.; Faradzev, I. A. (1969), "An example of a graph which has no transitive group of automorphisms", Doklady Akademii Nauk SSSR 185: 975–976.

В интернете также нашел: The only graph of this type with degree three is the 126-vertex Tutte 12-cage. The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph.

Проверка показала, что у графа Шрикханде и графа AVLF для любого $k \ge 2$ окрестности
$k$–го порядка всех вершин имеют одинаковые значения.
Именно поэтому алгоритм Спарроу на таких графах не работает.
В статье также указывалось на возможные ошибки из-за округления иррациональных чисел, преодолеть которые можно используя 15-значную арифметику с плавающей запятой.

Вторая сложность, возникающая при работе алгоритма на графах с большим числом вершин - это резкое увеличение величин числовых сигнатур, которая может привести к предельно допустимой разрядности чисел. Для преодоления этой трудности в статье было предложено на каждом шаге алгоритма пропорционально уменьшать все получаемые величины размера окрестностей.

[Fate'sMathematics]

sqribner48 А Вы уверены, что с помощью предложенных Вами 3-х вариантов можно определить изоморфизм графов?
Особенно сомнительным мне кажется первый вариант.
Во 2-м и 3-м вариантах в два раза увеличивается число вершин - повышается сложность.
И вообще, разве можно по автоморфно-эквивалентным классам определить изоморфизм?

[sqribner48]

Fate'sMathematics

Fate'sMathematics в сообщении #1011704 писал(а):

А Вы уверены, что с помощью предложенных Вами 3-х вариантов можно определить изоморфизм графов?

Я ни в чем не уверен. В отличие от уважаемого bin, который в теме: «Полиномиальный алгоритм изоморфизма графов» предложил рассмотреть его статью, я просто задал два вопроса. При этом, главная цель была – вместе с другими участниками разобраться в них.
Первый вопрос касался правильности понимания (перевода) алгоритма Спарроу. Ответ на этот вопрос был получен. Остался второй вопрос. Причем этот вопрос не следует воспринимать слишком прямолинейно, как это написано в заголовке. Написать так я был вынужден из-за краткости заголовка. Во втором вопросе я предложил рассмотреть возможность использования автоморфно эквивалентных классов (далее везде АЭ классов) вершин, полученных с помощью алгоритма Спарроу, для определения изоморфизма двух графов тремя методами:
а) для каждого графа по отдельности вычисляются числовые сигнатуры вершин и затем производится их сравнение;
б) производится объединение графов, затем вычисляются числовые сигнатуры вершин и сравниваются;
в) графы объединяются в один, добавляется одна вершина и новые ребра, соединяющие ее со всеми вершинами обоих графов; затем вычисляются числовые сигнатуры вершин и сравниваются.
Вариант (а)

Fate'sMathematics в сообщении #1011704 писал(а):

Особенно сомнительным мне кажется первый вариант.

Ну что ж, Ваше сомнение мне понятно. Вариант (а) фактически сводится к стандартному определению изоморфизма двух графов через определение и сравнение их инвариантов.
Однако, АЭ классы вершин графа не являются его инвариантом. (С учетом именно этого факта и был предложен вариант (б), когда оба графа объединялись в один и нужда в инвариантах отпадала). В этом случае естественно возникают следующие вопросы:
1. Когда можно использовать АЭ классы вершин двух графов для определения их изоморфизма?
2. Можно ли на основе АЭ классов вершин графа построить инвариант?
3. Можно ли получить инвариант графа из набора его числовых сигнатур 1-го, 2-го и $n$-го порядков, полученных по алгоритму Спарроу?
Ответ на 1-й вопрос известен. Ясно, что после выполнения канонической перенумерации вершин графов, будут получены одинаковые разложения вершин графов на АЭ классы.
В работе:
М.Н. Назаров. Альтернативные подходы к описанию классов Изоморфных графов. Прикладная дискретная математика, 2014, №3(25), с. 86-97.
был найден полный инвариант $I[G]$ графа $G$ (названный линейной нотацией абстрактного графа [G] ), получаемый за полиномиальное время из набора АЭ классов вершин. Однако, перед определением $I[G]$ граф должен представлен в канонической форме, т.е. вершины графа должны быть упорядочены в соответствии с макси-кодом графа.
По второму вопросу. Каждый АЭ класс вершин определяется количеством вершин этого класса и значением числовой сигнатуры, по которому и были отобраны вершины этого класса. Ясно, что по определению класса не может быть двух разных классов с равными значениями числовых сигнатур. Таким образом, если каждому АЭ классу поставить в соответствие двухэлементный список -- (сигнатура, число вершин класса), а затем собрать их в один список и отсортировать эти списки в порядке возрастания сигнатур, то полученный список будет инвариантом графа. Очевидно, такие инварианты можно построить для любого уровня сигнатур графа и этот набор также будет инвариантом.
Будут ли такие инварианты и полными пока неясно. Хотя это мне представляется сомнительным.
Поскольку числовые сигнатуры тесно связаны со степенями вершин, то по-видимому предложенные инварианты могут иметь те же недостатки, что и упорядоченный список степеней вершин! Целесообразно протестировать эти инварианты на графах, для которых инвариант - список степеней вершин дает отрицательные результаты.
Вариант (б)
Вариант б) как раз и был предложен, чтобы избежать использования инвариантов графов.
В этом случае возникает вопрос: «существуют ли неизоморфные графы с одинаковыми наборами АЭ классов?» Наличие таких графов требуется доказать теоретически или найти контрпример.
Предлагаю Fate'sMathematics или кому-нибудь другому участнику форума попробовать свои силы по решению этой задачи.

Вариант (в)

Fate'sMathematics в сообщении #1011704 писал(а):

Во 2-м и 3-м вариантах в два раза увеличивается число вершин - повышается сложность.

Увеличение числа вершин – не помеха. Однако вынужден признать, что для простых неориентированных графов 3-й вариант в) может оказаться малопригодным для определения АЭ классов и, следовательно, будет не пригоден для определения изоморфизма. Это объясняется тем, что после добавления вершины и ребер, любая пара вершин будет соединена путем длиной 2.
Но надо проверить хотя бы на нескольких примерах.
Попробуйте сами протестировать и предлагайте Ваши варианты.
P.S. Я сам тоже попробую и выложу если что-то будет.

[sqribner48]

Вчера не заметил ошибки, а потом уже было невозможно отредактировать.
Вот так было написано:

sqribner48 в сообщении #1011798 писал(а):

Ясно, что после выполнения канонической перенумерации вершин графов, будут получены одинаковые разложения вершин графов на АЭ классы.

Пропущено два слова. А должно быть:
Ясно, что после выполнения канонической перенумерации вершин двух изоморфных графов, будут получены одинаковые разложения вершин графов на АЭ классы.

[Fate'sMathematics]

sqribner48­
В своем предыдущем сообщении Вы, кажетс­я, написали: «Поскольку числовые сигнату­ры тесно связаны со степенями вершин….."
Но тогда, наверно самыми неудобными ­ для определения изоморфизма посредство­м сравнения автоморфно - эквивалентных­ классов вершин будут однородные и ­строго регулярные графы.

[sqribner48]

Протестировал алгоритм на сильно регулярных графах, взятых с известного сайта Теда Спенса (Ted Spence) по ссылке http://www.maths.gla.ac.uk/~es/index.php
Напомню, что $k$ - регулярный (регулярный степени $k$) граф $G$ является сильно регулярным, если существуют целые $\lambda$ и $\mu$ такие, что:
- Любые две смежные вершины имеют $\lambda$ общих соседей.
- Любые две несмежные вершин имеют $\mu$ общих соседей.
Графы такого вида иногда обозначаются как $srg(n, k,\lambda,\mu)$. Величины $n, k, \lambda,\mu$ являются параметрами сильно регулярных графов, которые определяют их основные свойства.
Были рассмотрены следующие классы сильно регулярных графов:
- с 16 вершинами степени 6 и $\lambda = 2, \; \mu = 2, \; srg(16, 6, 2, 2)$
- с 25 вершинами степени 12 и $\lambda = 5, \; \mu = 6, \; srg (25, 12, 5, 6)$
- с 26 вершинами степени 10 и $\lambda = 3, \; \mu = 4,\; srg (26, 10, 3, 4)$
Также были рассмотрены отдельные графы нескольких других классов с количеством вершин 6, 9,10,12,15.
Результаты оказались плачевными.
Для всех рассмотренных графов с помощью алгоритма Спарроу не удалось выполнить декомпозицию вершин на АЭ классы вершин. Все вершины любого из рассмотренных графов на любой стадии вычислений попадали в один АЭ класс и имели одинаковые значения числовых сигнатур.
Начиная со 2-го порядка величины всех сигнатур не изменялись.
Это объясняется тем, что для любого графа $G$ окрестности 1-го порядка были равны степеням вершин, т.е.
$N(v_i) = deg(v_i), \; \forall v_i \in G$, а окрестности 2-го и более высоких порядков имели одинаковые значения, равные числу вершин графа, уменьшенному на 1, то есть

$$N^j(v_i) = n-1, \; 2 \le j \le n, \; \forall v_i \in G.$$

Более того, для всех неизоморфных графов одного класса (т.е. графов с одинаковыми параметрами) значения числовых сигнатур любого порядка имели одинаковые значения.
Таким образом, определение изоморфизма сильно регулярных графов с одинаковыми параметрами при помощи алгоритма Спарроу по варианту а) невозможно.

Далее я буду тестировать алгоритм на несимметричных (жестких) графах, на неизоморфных коспектральных графах, а также на других, сложных для определения изоморфизма, графах описанных в литературе.

[sqribner48]

Большое спасибо maxal
за помощь при корректировке моего предыдущего поста.
Протестировал алгоритм Спарроу на асимметричных (жестких) графах. Напомню, что

Цитата:

Тожде́ственный граф (асимметри́чный граф) — это граф, группа автоморфизмов которого состоит из одного единственного тождественного автоморфизма.

Рассматривались все 8 асимметри́чных графов с 6 вершинами и 16 асимметри́чных графов с 7 вершинами. Использовались следующие первоисточники:
1. Mirko Liepovic. The strongly asymmetric graphs of order 6 and 7.
Publications de l’Institute mathematique, Nouvelle serie tome 54(68), 1993, pp. 25—28.
2. Dragos Cvetkovic, Milenko Petric. A table of connected graphs on six vertices. Discrete Mathematics, 50 (1984) pp. 37-49.

На графах этого вида алгоритм Спарроу показал отличные результаты. Для всех графов была выполнена полная декомпозиция вершин (т.е. количество АЭ классов равно числу вершин и каждый АЭ класс имеет одну вершину). Следовательно, каждый граф имел свой уникальный набор АЭ классов вершин и соответствующих им значений числовых сигнатур.

Более того, во всех числовых сигнатурах рассмотренных асимметричных графов не было найдено ни одной пары равных числовых сигнатур.
Таким образом, для всех протестированных асимметричных графов алгоритм Спарроу по варианту (а) пригоден для определения (не)изоморфизма асимметричных графов.

Фактически, с помощью алгоритма Спарроу вершины асимметричного графа могут быть упорядочены в соответствии с их числовыми сигнатурами, что может быть использовано для получения полного инварианта $I[G]$ графа $G$ (без получения его макси-кода), описанного в статье :

Цитата:

М.Н. Назаров. Альтернативные подходы к описанию классов Изоморфных графов. Прикладная дискретная математика, 2014, №3(25), с. 86-97.

(Оффтоп)

Следует отметить, что шестой по счету граф, представленный на сайте Тождественный граф-Википедия не является асимметричным графом.

[Fate'sMathematics]

sqribner48­
Судя по вашему предпоследнему посту, ч­уда не произошло. Алгоритм Спарроу не ­может выполнить декомпозицию вершин силь­но однородных графов и, следовательно, ­не пригоден для определения их изоморфиз­ма. Про асимметричные графы вы написали.­ Там алгоритм Спарроу работает вроде хо­рошо. А как обстоят дела с графами други­х видов?

[sqribner48]

Протестировал алгоритм Спарроу на парах коспектральных, но неизоморфных графов.
В качестве первоисточника использовались:
1. C. D. Godsil, D. A. Holton and B. D. McKay, The spectrum of a graph, Combinatorial Mathematics V, Lecture Notes in Mathematics, 622 (Springer-Verlag, Berlin, 1977) 91-117
2. D. Cvetkovic, P. Rowlinson, S. Simic. Eigenspaces of graphs. Encyclopedia of mathematics and its applications. Cambridge university press
3. Andries E. Brouwer, Willem H. Haemers. Spectra of graphs(2011).
Также использовались и некоторые другие источники.
Наиболее большой оказалась коллекция коспектральных графов из 1-го источника. Там были рассмотрены следующие виды коспектральных графов:
1. Cospectral graphs
2. Cospectral connected graphs
3. Cospectral graphs with cospectral complements
4. Cospectral forests
5. Cospectral trees
6. Cospectral trees with cospectral complements
7. Cospectral trees with cospectral line graphs
8. Cospectral trees with cospectral complements, cospectral line graphs, cospectral complements of line graphs, cospectral line graphs of complements and cospectral distance matrice
9. Cospectral regular graph
10. Graphs cospectral but not isomorphic to their own complements
11. A family of four cospectral graphs of which (a) and (b) are complements of each other, while (c) and (d) are self-complementary.
12. Two cospectral regular graphs, the first transitive, the second not

Только по первому источнику были рассмотрены 12 вышеуказанных видов коспектральных графов по паре графов каждого вида (по две пары графов 9-го и 11-го видов) .
Сравнивались пары графов. На большинстве рассмотренных графов (кроме регулярных графов) алгоритм Спарроу показал хорошие результаты. Четко выполнялась декомпозиция вершин; для этого всегда было достаточно 2-х или 3-х итераций. Для большинства пар наборы числовых сигнатур были разными, разными были также количества АЭ классов и число их элементов. Таким образом, графы в паре определялись как неизоморфные.
Неприятным исключением оказались пары графов 11-го вида. Здесь в каждой паре графы имели одинаковые наборы числовых сигнатур и одинаковые декомпозиции множества вершин. Структурные инварианты, определяемые как упорядоченный список пар вида (значение сигнатуры, количество вершин класса с этой сигнатурой) также были одинаковы для разных графов каждой пары.
Детали:

(Оффтоп)

Граф 11a список смежностей:

$$\{\{2,7,8,9\},\{1,3,5,7,9\},\{2,4,6,8,9\},\{3,5,6,9\},\{2,4,6\},\{3,4,5,7\},\{1,2,6,8\},\{1,3,7\},\{1,2,3,4\}\}$$

Граф 11b список смежностей:

$$\{\{2,6,8,9\},\{1,3,7,8,9\},\{2,4,5,6,9\},\{3,5,7,9\},\{3,4,6\},\{1,3,5,7\},\{2,4,6,8\},\{1,2,7\},\{1,2,3,4\}\}$$

Для графов 11a 11b получили одинаковое распределение сигнатур по вершинам:

$ \{1.2924 \times 10^{78}, 7.51828 \times 10^{96}, 7.51828 \times 10^{96}, 1.2924 \times 10^{78}, 3.61739 \times 10^{61}, $
$3.90898 \times 10^{76},3.90898 \times 10^{76},3.61739 \times 10^{61},6.95288 \times 10^{84}\} $
И одинаковое распределение вершин по АЭ классам:

$$\{\{1,4\},\{2,3\},\{5,8\},\{6,7\},\{9\}\}$$

Структурный инвариант – упорядоченный список пар вида (значение сигнатуры, количество вершин класса с этой сигнатурой):

$$\{\{3.61739 \times 10^{61},2\}, \{3.90898 \times 10^{76}, 2\}, \{1.2924 \times 10^{78},2\}, \{6.95288 \times 10^{84},1\}, \{7.51828 \times 10^{96}, 2\}\},$$

один и тот же для разных графов.

Для графов 11c и 11d получились те же самые результаты, отличие в мелких несущественных деталях.
Граф 11c список смежностей:

$$\{\{2,7,8,9\},\{1,3,5,7\},\{2,4,6,8\},\{3,5,6,9\},\{2,4,6\},\{3,4,5,7,9\},\{1,2,6,8,9\},\{1,3,7\},\{1,4,6,7\}\}$$

Граф 11d список смежностей:

$$\{\{2,6,8,9\},\{1,3,7,8\},\{2,4,5,6\},\{3,5,7,9\},\{3,4,6\},\{1,3,5,7,9\},\{2,4,6,8,9\},\{1,2,7\},\{1,4,6,7\}\}$$

Для графов 11c 11d получили одинаковое распределение сигнатур по вершинам:

$ \{3.90898 \times 10^{76}, 3.90898 \times 10^{76}, 3.90898 \times 10^{76}, 3.90898 \times 10^{76},$
$ 3.61739 \times 10^{61}, 7.51828 \times 10^{96}, 7.51828 \times 10^{96}, 3.61739 \times 10^{61}, 6.95288 \times 10^{84}\} $

И одинаковое распределение вершин по АЭ классам:

$$\{\{1,4\},\{2,3\},\{5,8\},\{6,7\},\{9\}\}$$

Один и тот же для обоих графов структурный инвариант

$$\{\{3.61739 \times 10^{61},2\}, \{3.90898 \times 10^{76}, 2\}, \{1.2924 \times 10^{78},2\}, \{6.95288 \times 10^{84},1\}, \{7.51828 \times 10^{96}, 2\}\}$$

Для разных пар получили одинаковые значения числовых сигнатур, одинаковые распределения вершин по АЭ классам и одинаковые структурные инварианты. Разница только в том, распределения сигнатур по вершинам немного отличаются друг от друга.

Такой плохой результат по-видимому объясняется тем, что графы 11a и 11b являются взаимно дополнительными друг другу, а графы 11c и 11d являются самодополнительными.
Во всяком случае, это требует более детального рассмотрения.
Для графов из других источников были получены хорошие результаты. Графы в каждой паре определялись как неизоморфные.

[sqribner48]

Протестировал алгоритм Спарроу на графах, приведенных в книге:
А.А. Зыкова. Основы теории гарфов -- М.: Вузовская книга, 2004 --- 664 с.:ил.

Все эти графы являются сложными для распознавания изоморфизма с использованием известных инвариантов:
1. Вектора степеней - рис. 1.2.2.
2. Многочленного инварианта $F(G)$ , инварианта Г$(G)$ -- рис. 1.5.1.
3. Инварианта из многочленов $F(G)$ и $E(G)$ -- рис. 1.5.2.
4. Инвариантов $A(G),\,B(G),\,S(G)$ -- рис. 1.5.3.

На всех вышеуказанных тестовых примерах алгоритм Спарроу показал отличные результаты. Была выполнена правильная декомпозиция вершин графов, (совпадающая с результатами определения автоморфизмов, произведенных стандартными средствами Mathematica).
Все пары неизоморфных графов были правильно распознаны как неизоморфные.

Мне кажется, что надо немного вернуться назад к истокам, т.е. к исходному тексту статьи Спарроу и рассмотреть теоретические аспекты -- доказательство правильности алгоритма, особенности его реализации и возможные ошибки (рассмотренные автором статьи).
У меня вызывают сомнение результаты тестирования алгоритма на двух парах коспектральных графов:
$G11a, \,G11b$ и $G11c, \,G11d$.
Дело в том, что в статье:
M. G. Everett, S. Borgatti. Calculating role similarities: an algorithm that helps determine the orbits of a graph. Social Networks 10 (1988) 77-91
было написано:

Цитата:

Fontet (1975) proved that finding the orbits solves the graph isomorphism problem.

К сожалению статью:
Fontet M. Automorphismes des graphes et planarité. Journées Algorithmique 1975 (Ecole Norm. Sup., Paris) Soc. Math. France: 73-90.
получить не удалось.
Поэтому и сомневаюсь, а вдруг эти пары графов изоморфные?
Прошу участников форума, у которых есть Wolfram Mathematica более новых, чем у меня моделей, протестировать на изоморфизм две пары графов; ниже приведены их списки смежностей:

Граф G11a
 {{2,7,8,9},{1,3,5,7,9},{2,4,6,8,9},{3,5,6,9},{2,4,6},{3,4,5,7},{1,2,6,8},{1,3,7},{1,2,3,4}};
Граф G11b
{{2,6,8,9},{1,3,7,8,9},{2,4,5,6,9},{3,5,7,9},{3,4,6},{1,3,5,7},{2,4,6,8},{1,2,7},{1,2,3,4}};

Граф G11c
{{2,7,8,9},{1,3,5,7},{2,4,6,8},{3,5,6,9},{2,4,6},{3,4,5,7,9},{1,2,6,8,9},{1,3,7},{1,4,6,7}}; 
Граф G11d
{{2,6,8,9},{1,3,7,8},{2,4,5,6},{3,5,7,9},{3,4,6},{1,3,5,7,9},{2,4,6,8,9},{1,2,7},{1,4,6,7}};

[whitefox]

А Вы не сравнивали свою программу с программой nauty Брендана Маккей (Brendan McKay)?

[sqribner48]

Уважаемый whitefox
Как я могу сравнивать самую лучшую на данный момент программу nauty с моей, набросанной на коленке, программой (две функции) в Wolfram Mathematica?
Моя "программа" предназначена всего лишь для проверки моего предположения о возможности использования алгоритма расчета АЭ классов вершин для определения изоморфизма графов. И все. Я просто пытаюсь разобраться вместе с участниками форума в этом вопросе.
К сожалению, моя тема пока мало кого заинтересовала кроме Fate'sMathematics, который меня критикует без каких-либо конструктивных предложений.
Может быть моя тема малоинтересна, а может участники форума просто опасаются писать в такой скользкой и опасной теме, как изоморфизм графов.
Вы -- второй, да еще и ЗУ форума, откликнувшийся в моей теме. Большое Вам спасибо.
Буду рад любой Вашей критике и предложениям.
P.S. О программе nauty мне, разумеется, было хорошо известно.
Недавно я даже скачал одну очень интересную статью:
Павлов Д.А. Каноническая нумерация графов и библиотека nauty. Компьютерные инструменты в образовании, 2009, №5, 27—34.,
в которой был детально рассмотрен алгоритм этой программы.
Если Вам это нужно, могу скинуть файл с этой статьей.

[whitefox]

sqribner48 в сообщении #1017067 писал(а):

Моя "программа" предназначена всего лишь для проверки моего предположения о возможности использования алгоритма расчета АЭ классов вершин для определения изоморфизма графов. И все.

Любой алгоритм автоморфного разбиения графа на классы подобных вершин полиномиально эквивалентен алгоритму проверки изоморфизма графов. Об этом подробнее можно прочитать в статье известного российского специалиста по изоморфизму графов И.Н. Пономаренко Проблема изоморфизма графов: Алгоритмические аспекты (записки к лекциям). В Сети есть и видио самих этих лекций.

Вот несколько цитат из этой статьи:

И.Н. Пономаренко писал(а):

Теорема 1.11 Проблемы ISO и APART полиномиально эквивалентны.

И.Н. Пономаренко писал(а):

$ISO(G1,G2)$: для графов $G1$ и $G2$ определить верно ли, что $G1\cong G2.$

И.Н. Пономаренко писал(а):

$APART(G)$: найти автоморфное разбиение графа $G.$

P.S. Предложенная Вами статья у меня есть, спасибо.

[sqribner48]

whitefox

whitefox в сообщении #1017121 писал(а):

Любой алгоритм автоморфного разбиения графа на классы подобных вершин полиномиально эквивалентен алгоритму проверки изоморфизма графов.

Большое спасибо.

whitefox в сообщении #1017121 писал(а):

Об этом подробнее можно прочитать в статье известного российского специалиста по изоморфизму графов И.Н. Пономаренко Проблема изоморфизма графов: Алгоритмические аспекты (записки к лекциям).

Эта статья у меня есть, но я, видимо, пропустил этот замечательный факт из-за ненадобности. Буду иметь в виду.
Об этом же говорится и в известной статье: Ronald C. Read, Derek G. Corneil. The Graph Isomorphism Disease. Journal of Graph Theory, Vol. 1 (1977) 339-363,
которую мне вчера удалось скачать.

(Оффтоп)

Спасибо Aritaborian'у за его мастер-класс по скачиванию литературы.

Поэтому мне тем более непонятны результаты моего тестирования на двух, (указанных в моих предыдущих постах), парах коспектральных графов.
Надо в этом разобраться.