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

[sqribner48]

Проанализируем свойства двух пар коспектральных графов $G11_a, G11_b,G11_c,G11_d$
Все эти графы имеют одинаковые диаметры $diam(G11_a)=diam(G11_b)=diam(G11_c)=3$.
Одинаковую вершинную $ \varkappa $ и реберную $\lambda $ связность:

$$ \varkappa(G11_a)= \varkappa(G11_b)= \varkappa(G11_c)= \varkappa(G11_d)= 3,$$

$$ \lambda(G11_a)= \lambda (G11_b)=\lambda (G11_c)= \lambda (G11_d)= 3.$$

Все эти графы имеют одинаковую степенную последовательность вершин (отсортированную в порядке неубывания) $\{5,5,4,4,4,4,4,3,3\}$.
И одинаковую последовательность эксцентриситетов вершин (отсортированную в порядке возрастания) $\{2,2,2,2,2,2,2,3,3\}$
Эти графы имеют очень близкие друг к другу отсортированные списки следующих параметров - DegreesOf2Neighborhood, NumberOf2Paths и Distances, полученных стандартными функциями Mathematica.
Напомню, что здесь
$DegreesOf2Neighborhood[g,v]$ - есть функция, которая возвращает упорядоченный список степеней вершин в графе $g$, которые находятся на расстоянии 2 от вершины $v$.
$NumberOf2Paths[g,v]$ возвращает упорядоченный список, который состоит из числа путей длины 2 от вершины $v$ до остальных вершин графа.
$Distances[g, v]$ возвращает расстояния от вершины $v$ до всех вершин графа в неубывающем порядке.
Вот эти списки для графов $G11a, G11b$:

(Оффтоп)

parameterGraph[G11_a];
 DegreesOf2Neighborhood
{{3,4,4,4,4,4,5,5},
{3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5}}

 NumberOf2Paths
{{1,1,1,2,2,3,3},
{1,1,1,2,2,3,3},
{1,1,1,2,2,2,3,4},
{1,1,1,2,2,2,3,4},
{1,1,2,2,3,3,3,5},
{1,1,2,2,3,3,3,5},
{1,1,1,1,1,2,2,3,4},
{1,1,1,1,1,2,2,3,4},
{1,1,2,2,2,2,2,2,4}}

 Distances
{{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,2,2,2,2,3},
{0,1,1,1,2,2,2,2,3}}

parameterGraph[G11_b];
 DegreesOf2Neighborhood
{{3,4,4,4,4,4,5,5},
{3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5}}

 NumberOf2Paths
{{1,1,2,2,3,3,4},
{1,1,2,2,3,3,4},
{1,1,1,1,2,2,2,3},
{1,1,1,1,2,2,2,3},
{1,1,1,1,2,3,3,4},
{1,1,1,1,2,3,3,4},
{1,1,1,2,2,2,3,3,5},
{1,1,1,2,2,2,3,3,5},
{1,1,2,2,2,2,2,2,4}}

 Distances
{{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,2,2,2,2,3},
{0,1,1,1,2,2,2,2,3}}

Не трудно заметить, что списки DegreesOf2Neighborhood и Distances
для графов $G11_a, G11_b$ совпадают.
Для графов $G11_c,G11_d$ наблюдается аналогичная картина -- списки DegreesOf2Neighborhood и Distances для графов $G11_c$ и $G11_d$ совпадают

(Оффтоп)

parameterGraph[G11_c];
 DegreesOf2Neighborhood
{{3,4,4,4,4,4,5,5},
{3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5}}
 NumberOf2Paths
{{1,1,1,2,2,3,3},
{1,1,1,2,2,3,3},
{1,1,2,2,3,3,4},
{1,1,2,2,3,3,4},
{1,1,1,1,1,2,2,3,4},
{1,1,1,1,1,2,2,3,4},
{1,1,1,2,2,2,3,3,5},
{1,1,1,2,2,2,3,3,5},
{1,1,2,2,2,2,2,2,4}}
 Distances
{{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,2,2,2,2,3},
{0,1,1,1,2,2,2,2,3}}

parameterGraph[G11_d];
 DegreesOf2Neighborhood
{{3,4,4,4,4,4,5,5},
{3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5},
{3,3,4,4,4,4,4,5,5}}
 NumberOf2Paths
{{1,1,1,1,2,2,2,3},
{1,1,1,1,2,2,2,3},
{1,1,1,2,2,2,3,4},
{1,1,1,2,2,2,3,4},
{1,1,1,1,1,1,2,4,4},
{1,1,1,1,1,1,2,4,4},
{1,1,1,1,2,2,3,4,5},
{1,1,1,1,2,2,3,4,5},
{1,1,2,2,2,2,2,2,4}}
 Distances
{{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,1,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,1,2,2,2,2},
{0,1,1,1,2,2,2,2,3},
{0,1,1,1,2,2,2,2,3}}

Кроме того, в обоих случаях (для двух пар) величины окрестностей всех порядков одинаковы для всех вершин графов. Из этого следует, что перечисленные коспектральные графы очень неудобны для определения изоморфизма с помощью алгоритма Спарроу.
Однако, необходимо отметить, что стандартные средства Mathematica, использующие вышеуказанные функции, четко определяют неизоморфность графов в каждой паре. Тогда как алгоритм Спарроу ошибочно определяет графы в каждой такой паре как изоморфные.
В чем же причина такой плохой работы алгоритма Спарроу на некоторых графах?
Это объясняется следующей особенностью алгоритма Спарроу - начальные значения числовых сигнатур вершин принимаются равными степеням вершин.
Произведенные эксперименты с модифицированным алгоритмом Спарроу, в котором начальные значения числовых сигнатур вершин принимались равными числовым кодам от величины NumberOf2Paths, показали хорошие результаты. Графы определялись как неизоморфные.
Рассматривалась также и другая модификация алгоритма Спарроу, когда начальные значения числовых сигнатур каждой вершины принимались равными произведению степени вершины на код вершины от величины NumberOf2Paths.
При этом, код вершины определялся как десятичный логарифм от десятичного представления числа, полученного из последовательности NumberOf2Paths с помощью функции FromDigits.
Пример:
последовательность - $\{1,1,2,2,3,3,4\}$, число - $1122334$, код - $\log(1122334)$
Вторая модификация алгоритма Спарроу также показала хорошие результаты - графы парах определялись как неизоморфные.

Однако, как я уже говорил, с учетом выполненного анализа работы алгоритма Спарроу, необходимо вернуться назад и детально разобрать доказательство правильности его работы, рассмотреть потенциально возможные ошибки и способы их устранения, представленные в статье Спарроу.
А для этого опять понадобится сделать перевод некоторых кусков текста.

[sqribner48]

Уважаемый whitefox
указал правильное направление для наших дальнейших исследований по алгоритму Спарроу, когда написал:

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

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

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

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

Этот факт невозможно оспорить. Однако, в моей, процитированной выше, фразе речь шла не просто «о возможности использования алгоритма расчета АЭ классов вершин для определения изоморфизма графов», а о возможности использования алгоритма Спарроу расчета АЭ классов вершин. А это как говорят в Одессе: «Две большие разницы».
На такую мысль наводят и результаты тестирования алгоритма Спарроу на строго регулярных, на некоторых однородных графах и на двух парах коспектральных графов $G11_a, \; G11_b, \; G11_c, \; G11_d $. Далее для простоты обозначим их через $ G_{A}, \; G_{B}, \; G_{C}, \; G_{D}$ соответственно.
Долго не мог понять, почему для этих графов получились такие плачевные результаты.
Дело в том, что графы $G_{A}$ и $G_{B}$ являются дополнительными друг к другу. То есть, используя общепринятые обозначения для дополнения, можно написать $G_{B} = \bar G_{A} $
Хорошо известно (см., например, «Лекции по теории графов/Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, Гл. ред. Физ.-мат. Лит., 1990.—384 с.), что

Цитата:

Всякий автоморфизм графа $G$ является также автоморфизмом дополнительного графа $G$, т.е. $Aut(G) = Aut(\bar G)$

Но тогда графы $G_{A}$ и $G_{B}$ имеют одинаковые группы автоморфизмов, (т.е. $Aut(G_{A}) = Aut(G_{B})=Aut(\bar G_{A})$) и, следовательно, они имеют одинаковые автоморфные разбиения вершин. Видимо поэтому с помощью алгоритма Спарроу для графов $G_{A}$ и $G_{B}$ были получены одинаковые наборы автоморфно эквивалентных классов с равными значениями числовых сигнатур.
Ниже на рисунке представлены графы $G_{A}$ и $G_{B}$.

Эти графы имеют четко выраженную симметричную структуру и один (одинаковый для обоих графов) нетривиальный автоморфизм

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

Аналогичная картина имела место и для графов $G_{C}$ и $G_{D}$, диаграммы которых представлены ниже.

Нетрудно заметить, что эти самодополнительные графы также имеют симметричную структуру и почти совпадают с графами $G_{A}$ и $G_{B}$. Так графы $G_{A}$ и $G_{C}$ отличаются друг от друга только двумя ребрами и $Aut(G_{A}) = Aut(G_{C})$. Эти графы имеют один (одинаковый для обоих графов) нетривиальный автоморфизм

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

В свою очередь, графы $G_{B}$ и $G_{D}$ также отличаются друг от друга только двумя ребрами и $Aut(G_{B}) = Aut(G_{D})$. Они также имеют один (одинаковый для обоих графов) нетривиальный автоморфизм

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

Таким образом, совпадение автоморфно эквивалентных классов, полученных с помощью алгоритма Спарроу для графов $G_{A}$ и $G_{B}$ объясняется равенством их групп автоморфизмов из-за того, что эти графы являются дополнительными друг к другу.
Аналогичный результат для графов $G_{C}$ и $G_{D}$ объясняется случайным совпадением групп автоморфизмов графов $G_{A}$ и $G_{C}$ и графов $G_{B}$ и $G_{D}$. Случайным ли?
Для других коспектральных графов (не являющихся сильно однородными), как было ранее отмечено, были получены очень хорошие результаты.
Для других графов, не являющихся строго регулярными, также были получены хорошие результаты. Очень хорошие результаты были получены при тестировании асимметричных графов (100% правильных результатов). Хорошие результаты были получены и на деревьях.
Фактически алгоритм Спарроу был предложен автором для работы в социальных и криминальных сетях, которые в основном являются большими деревьями или графами с небольшим количеством циклов. Таким образом, с тестированием алгоритма Спарроу на графах разных видов вопрос решен.

Остается уточнить следующие аспекты, связанные с алгоритмом Спарроу определения автоморфно эквивалентных классов вершин:
1. Рассмотреть как связаны АЭ классы вершин, полученные алгоритмом Спарроу, с автоморфизмами графа (на практике).
2. Почему возможны неизоморфные графы с одинаковыми группами автоморфизмов?
3. Разобрать доказательства полиномиальной эквивалентности проблемы автоморфного разбиения и проблемы определения изоморфизма графов, представленные в статье Пономаренко и в статье R. C. Read и D. G. Corneil “The Graph Isomorphism Disease”.
4. Рассмотреть как связаны друг с другом автоморфное разбиение вершин графов с их автоморфизмами (в теории).
5. Рассмотреть доказательство правильности работы алгоритма Спарроу, приведенное в его статье.
6. Рассмотреть возможные ошибки, допускаемы при работе алгоритма Спарроу и способы их преодоления, предложенные в статье Спарроу.
Интересно также выполнить сравнение алгоритма Спарроу автоморфного разбиения вершин и алгоритма разбиения вершин в программе Nauty, предложенное whitefox

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

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

Определить в чем состоит их принципиальное различие, особенности, недостатки и достоинства.

[whitefox]

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

Этот факт невозможно оспорить. Однако, в моей, процитированной выше, фразе речь шла не просто «о возможности использования алгоритма расчета АЭ классов вершин для определения изоморфизма графов», а о возможности использования алгоритма Спарроу расчета АЭ классов вершин. А это как говорят в Одессе: «Две большие разницы».

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

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

Рассмотреть как связаны АЭ классы вершин, полученные алгоритмом Спарроу, с автоморфизмами графа (на практике).

Каждый класс разбиения, найденный алгоритмом Спарроу, является объединением нескольких орбит группы автоморфизмов графа. Но решить "на практике", для произвольного графа, входит ли в это объединение строго одна орбита либо несколько, видимо, ничуть не проще чем вычислить орбиты группы автоморфизмов графа непосредственно.

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

Почему возможны неизоморфные графы с одинаковыми группами автоморфизмов?

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

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

Рассмотреть как связаны друг с другом автоморфное разбиение вершин графов с их автоморфизмами (в теории).

Каждый класс автоморфного разбиения графа является некоторой орбитой группы автоморфизмов этого графа, и наоборот, всякая орбита группы автоморфизмов графа является некоторым классом его автоморфного разбиения.

[whitefox]

(Оффтоп)

Вот решил глянуть диссертацию по приведённой Вами ссылке:

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

Southwell R. Finding Symmetries in Graphs. Ph.D. thesis. University of York, UK, 2006.
109 p.
Диссертацию можно скачать по ссылке: https://richardsouthwell.files.wordpres ... 08/msc.pdf

Первое же определение вызвало недоумение:

Цитата:

Definition 1.1.1. An undirected graph, $G=(V,E),$ is defined as a set of elements known as vertices which form vertex set $V$ together with an edge set $E$ which consists of a list of unordered pairs of vertices.

"set which consists of a list" . Видимо, это нужно понимать как multiset, а совместно с "unordered pairs of vertices" это означает, что автор допускает в графе кратные рёбра и петли . А почему бы и нет? Вот только такую сущность обычно именуют multigraph.

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

P.S. А он хоть защитился?

[whitefox]

(Оффтоп)

А вот и пример недоумения индуцированного первым недоумением:

Цитата:

Definition 1.3.1. For a graph $G,$ with $v\in G,$ the neighbourhood of $v,\operatorname{Ne}(v),$ is the subgraph induced on the vertex set $\{u\in G\mid u\operatorname{adj} v\}.$ Elements of $\operatorname{Ne}(v)$ are referred to as the neighbours of $v.$

(На $v\in G$ и $u\in G$ не обращаем внимания, понимая под этим $v\in V(G)$ и $u\in V(G)$ соответственно.)

Является ли вершина $v$ своим собственным соседом по этому определению? Ответ зависит от решения первого недоумения. Если граф это простой граф, то нет. А если граф это мультиграф, то может да, а может нет (в зависимости от того имеется ли в мультиграфе петля из вершины $v$ в неё же).

А вот из следующего определения прямо следует, что никакая вершина не может быть своим собственным соседом (если потребовать чтобы $\operatorname{Ne}(\{v\})=\operatorname{Ne}(v)$):

Цитата:

Definition 1.3.2. For a subgraph $X\subseteq G$ we define the neighbourhood of the subgraph, $\operatorname{Ne}(X),$ to be the graph induced on the vertex set $\{u\in G-X\mid\exists w\in X:u\operatorname{adj}w\}.$

То есть под графом автор понимает, всё таки, простой граф, а не мультиграф. Но тогда Definition 1.1.1. грубо ошибочно. Впрочем, возможно, по его задумке равенство $\operatorname{Ne}(\{v\})=\operatorname{Ne}(v)$ не обязано выполняться. В общем, ребус на ребусе.

[whitefox]

Сравним алгоритм Спарроу с алгоритм стабилизации из уже упомянутой статьи Пономаренко (стр. 40).

Для определённости приведу несколько определений из этой статьи (а то тут один диссертант до того заморочил мне голову, что все правильные определения улетучились из неё напрочь ):

Цитата:

Пусть $V$ – конечное множество и $E$ – подмножество множества его двухэлементных подмножеств. Тогда пара $G=(V,E)$ называется (простым) графом c множеством вершин $V$ и множеством ребер $E.$ Будем говорить, что вершины $u$ и $v$ графа $G$ смежны, если последний содержит ребро $(u,v):=\{u,v\}.$

Цитата:

Степенью вершины $v$ называется число

$$d_G(v)=|N_G(v)|,$$

где $N_G(v)=\{u\in V:(v,u)\in E\}$ – множество соседей или окрестность этой вершины.

Цитата:

Пусть $G=(V,E)$ граф и $c$ – произвольная сюръективная функция из $V$ в начальный отрезок натурального ряда $I=\{1,\dots,m\},$ где $m\geqslant1.$ Будем интерпретировать эту функцию как раскраску вершин в цвета из множества $I;$ таким образом, вершина $v\in V$ имеет в этой раскраске цвет $c(v).$ Множество $c^{-1}(v)\subseteq V$ называется цветным классом, отвечающим цвету $c\in I.$ Под раскрашенным графом будем понимать пару $(G,c).$

Цитата:

Пусть $(G,c)$ – раскрашенный граф с цветными классами $V_1,\dots,V_m,$ где $m$ – максимальный цвет вершины. И пусть $d_i(v)=|N_G(v)\cap V_i|.$

Алгоритм стабилизации работает с раскрашенными графами. В начале все вершины с одинаковой степень окрашиваются в один цвет, а вершины с разной степенью — в разные цвета (для определённости цветной класс с меньшей степенью вершин красим в цвет с меньшим номером). Всего получаем $m$ различных цветных классов, и номер максимального цвета равен $m.$ А вот и сам алгоритм стабилизации:

Цитата:

Будем называть раскраску $c$ графа $G$ стабильной, если для любых двух цветов $i$ и $j$ число $d_i(v)$ не зависит от вершины $v\in V_j;$ в этом случае будем также говорить, что раскрашенный граф $G$ является стабильным. Заметим, что если $m=1,$ то стабильность означает просто, что граф $G$ регулярен. Следующий алгоритм по заданной раскраске $c$ графа $G$ строит новую стабильную раскраску $\bar c$ так, что каждый цветной класс исходной раскраски является объединением цветных классов новой раскраски.

1. для каждой вершины $v\in V$ найдём строку $s(v)=(c(v),d_1(v),\dots,d_m(v)),$
2. лексикографически упорядочим множество $\{s(v):v\in V\},$
3. найдём однозначно определённую раскраску $\bar c,$ для которой $\bar c(v)<\bar c(u),$ если $s(v)<s(u),$ и $\bar c(v)=\bar c(u),$ если $s(v)=s(u),$
4. если число цветов раскраски $\bar c$ больше числа цветов раскраски $c,$ то полагаем $c:=\bar c$ и переходим к шагу 1.

Легко видеть, что приведенный алгоритм стабилизации работает полиномиальное время от числа вершин графа.

Для связных графов справедливо следующее утверждение.
Утверждение. Пусть $S_i(v)$ обозначает числовую сигнатуру которую получит вершина $v$ на $i$-й итерации по алгоритму Спарроу. И пусть $c_i(v)$ обозначает цвет который получит вершина $v$ на $i$-й итерации по алгоритму стабилизации. Тогда:

$$(c_i(v)=c_i(u))\Rightarrow(S_i(v)=S_i(v))$$

обратное, в общем случае, не верно.

Алгоритм стабилизации, также, является основным в программе nauty.

[whitefox]

Спарроу отметил в своей статье один очень важный момент без учёта которого его алгоритм перестаёт быть корректным (и чего совершенно нет у "диссертанта"). А именно — из-за округления результатов вычислений с действительными числами, результат умножения трёх и более сомножителей зависит от порядка перемножения. Поэтому сомножители нужно предварительно упорядочивать, в противном случае на одних и тех же входах могу получиться разные сигнатуры, что, в свою очередь, может привести к отнесению подобных вершин к разным классам эквивалентности.

Как было показано выше, на связных графах алгоритм стабилизации точнее алгоритма Спарроу. А с учётом того, что сортировку необходимо выполнять в обоих алгоритмах, то возникает сомнение в превосходстве по скорости алгоритма Спароу над алгоритмом стабилизации.

[sqribner48]

Уважаемый whitefox
Cпасибо за проявленный Вами интерес к моей теме и Ваши ценные для меня замечания.
Читать Ваши сообщения необычайно приятно, интересно и полезно. Постараюсь ответить.
Итак, начнем по порядку.

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

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

Честно говоря я не знаю, что такое сабж.
Если Вы имели в виду название моей темы, то в целом Вы правы. Однако, тема была создана просто для того, чтобы разобраться в статье Спарроу и в его алгоритме определения автоморфно эквивалентных классов вершин (поскольку я совсем не знаю английского языка). Однако даже моих плохих знаний английского хватило, чтобы понять следующий факт – алгоритм Спарроу не работает на всех графах. В частности, он не работает на distance-regular but not distance-transitive графах (дистанционно регулярных, но не дистанционно транзитивных?).
Возможно, исходя из этого, мне следовало бы назвать мою тему как-нибудь по-другому.
Но я хотел дать более привлекательное и более яркое название.

Когда я писал, что необходимо:

Цитата:

«Рассмотреть как связаны АЭ классы вершин, полученные алгоритмом Спарроу, с автоморфизмами графа (на практике)»

я имел в виду рассмотреть работу алгоритма Спарроу на разных характерных графах (пустых, полных, цепях, циклах, звездах, колесах, деревьях), поскольку любой граф может иметь такие графы в качестве своего подграфа.
Такой подход вызван наличием множества не совсем понятных мне мест статьи, из-за моего скверного английского.
Много темных мест прояснили участники нашего форума Dan B-Yallay, venco, svv, 3D Homer за что им мое большое спасибо.
Однако, не смотря на это, остались несколько темных мест.
Чего стоит только трюк Спарроу с некоей гипотезой, которая вроде доказывает правильность работы алгоритма, а потом выясняется, что доказательство гипотезы не требуется, и без нее все хорошо.
Пожалуй это смахивает на фокус, если не сказать больше…
Вот английский текст этого фокуса:

(Оффтоп)

To build the appropriate theoretical basis for 2nd and higher order signatures we need a conjecture which, fortunately, we will not have to prove for the practical purposes of this paper.
Conjecture: That there exists a sequence - of transcendental numbers $\{\pi_i: i = 1,2,. . . , n\}$ which together do not satisfy any non-trivial polynomial with integer coefficients. (We might perhaps call such numbers mutually transcendental.) In other words, there does not exist a set of non-zero integer coefficients $\{c_j\}$, and sets of positive integer powers $\{p(j), q(j), r(j),\dots , \colon j = 1,2,\dots , m\}$ such that

$$ \sum^m_{j=1} c_j \pi^{p(j)}_1 \pi^{q(j)}_2 \pi^{r(j)}_3 \dots, \pi_k \dots =0$$

… The reason that the conjecture does not need to be proved here is that, for all practical computational purposes, transcendental numbers are not needed. Nor even irrational numbers: random numbers will do. It is only necessary to provide sufficient complexity to the process to eliminate numerical “flukes”. Floating point arithmetic, operating with 14 significant figures, coupled with the use of y1 random numbers in the place of the set $\{\pi_i: i = 1,2,. . . , n\}$, achieves the purpose perfectly well.

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

Каждый класс разбиения, найденный алгоритмом Спарроу, является объединением нескольких орбит группы автоморфизмов графа.

Не всегда. А почему Вы так решили?
Я еще раз проверил все протестированные мной графы. Кроме однородных и сильно регулярных графов проблем нет. Все разбиения соответствовали орбитам. Проблемы возникали только для однородных и сильно регулярных графов.
Для однородных графов действительно наблюдалось объединение орбит, а иногда и неправильные разбиения, а для сильно регулярных графов множество вершин вообще не разбивалось.

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

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

Почему возможны неизоморфные графы с одинаковыми группами автоморфизмов?

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

С одной стороны, вроде бы понятно, «что группа автоморфизмов не является полным инвариантом графа». Вы привели в качестве примера семейство графов с тривиальной группой автоморфизмов разного порядка. Но разве могут быть изоморфными группы с разным количеством элементов? Или я ошибаюсь?
Видимо все-таки в качестве примера надо брать семейство несимметричных графов с тривиальной группой автоморфизмов одного порядка. Таких графов есть довольно много. Я протестировал алгоритм Спарроу на несимметричных графах 6-го и 7-го порядков.

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

Цитата:

«Каждый класс автоморфного разбиения графа является некоторой орбитой группы автоморфизмов этого графа, и наоборот, всякая орбита группы автоморфизмов графа является некоторым классом его автоморфного разбиения».

Получается, что автоморфное разбиение графа все же определяется группой автоморфизмов этого графа – т.е. списком всех автоморфизмов (подстановок).
Прошу Вас разъяснить мне в чем я ошибаюсь.

По диссертации Саутвелла

(Оффтоп)

На диссертацию Саутвелла, как и на статью Спарроу, я вышел при чтении статьи
М.Н. Назаров. Альтернативные подходы к описанию классов Изоморфных графов. Прикладная дискретная математика, 2014, №3(25), с. 86-97. (о чем я писал в своих первых постах).
В тонкости диссертации я не вдавался.
Меня заинтересовало лишь описание алгоритма Спарроу.
Кстати в своей диссертации Саутвелл описал какой-то урезанный алгоритм Спарроу (чем оказал мне медвежью услугу в понимании алгоритма Спарроу).
Вы привели много нелепостей, сделанные Саутвеллом в своей диссертации.
А я нашел только одну. Вот привожу отрывок текста из диссертации, взятого со стр. 52.

Цитата:

A new method of finding automorphically equivalent vertices
I found a simple brute force method that could be used to find automorphically equivalent vertices by applying theorem 3.2.1. The theorem implies that, for $x, y \in G$, $x$ is automorphically equivalent to $y$ if and only if $G - x \cong G - y$.
Мой перевод:
Новый метод обнаружения автоморфно эквивалентных вершин
Я нашел простой метод грубой силы, который мог использоваться, чтобы найти автоморфно эквивалентные вершины, применяя теорему 3.2.1. Теорема подразумевает, что для $x, y \in G$, $x$ - автоморфно эквивалентна $y$ если и только если $G - x \cong G - y$.

Во втором предложении отрывка Саутвелл очень не прав.
Действительно, если $\alpha$ -автоморфизм графа $G$, то графы $G - u$ и $G - \alpha(u)$ изоморфны. Поэтому, если вершины $u$ и $v$ подобны, то $G - u \cong G - v$.
Обратное этому утверждение неверно. Контрпример можно найти в книге Харари «Теория графов» (параграф Симметрические графы рис. 14.9).
Это очень грубая ошибка. Если бы я был не я, а ……. то уже только за это я бы не допустил к его защите.
А ведь, далее, на основании своего неверного вывода Саутвелл разрабатывает алгоритм определения автоморфно эквивалентных классов вершин. И очень гордится этим!

[Xaositect]

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

Чего стоит только трюк Спарроу с некоей гипотезой, которая вроде доказывает правильность работы алгоритма, а потом выясняется, что доказательство гипотезы не требуется, и без нее все хорошо. Пожалуй это смахивает на фокус, если не сказать больше…

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

[sqribner48]

Xaositect
Спасибо. Вы просто супер. А я долго ломал голову, пытаясь это понять.
Не совсем понятно что он имел в виду когда писал:

Цитата:

Nor even irrational numbers: random numbers will
do. It is only necessary to provide sufficient complexity to the process
to eliminate numerical “flukes”.

В частности, как переводится Nor even.
А что Вы можете сказать по поводу группы $Aut$ как не полного инварианта.

[Xaositect]

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

А что Вы можете сказать по поводу группы $Aut$ как не полного инварианта.

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

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

И извините уж совсем за глупый вопрос:"сама вершина входит в орбиту этой вершины?" Вроде бы должна входить. Но у меня есть сомнения.

Естественно. $v = 1 \cdot v$.

[sqribner48]

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

[Xaositect]

Да, но автоморфизмов же может быть вплоть до $n!$.

(Оффтоп)

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

В частности, как переводится Nor even.

Я не уверен, что nor там правильно стоит, но я английсткий так хорошо не знаю. Обычно в таких случаях пишут not even

[whitefox]

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

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

Каждый класс разбиения, найденный алгоритмом Спарроу, является объединением нескольких орбит группы автоморфизмов графа.

Не всегда. А почему Вы так решили?

Под "несколькими" я не имел ввиду, что их обязательно должно быть больше одного, один это тоже "несколько", имхо.

А сам вывод следует из этого:

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

Утверждение. Пусть $S_i(v)$ обозначает числовую сигнатуру которую получит вершина $v$ на $i$-й итерации по алгоритму Спарроу. И пусть $c_i(v)$ обозначает цвет который получит вершина $v$ на $i$-й итерации по алгоритму стабилизации. Тогда:

$$(c_i(v)=c_i(u))\Rightarrow(S_i(v)=S_i(v))$$

обратное, в общем случае, не верно.

Всякий класс эквивалентности по Спарроу является объединением нескольких цветных классов в стабильной раскраске (один тоже считается за несколько), а каждый цветной класс, в свою очередь, является объединением нескольких орбит группы автоморфизмов (случай одной орбиты не исключён).

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

а иногда и неправильные разбиения

Если в программе нет багов, то неправильное разбиение (отнесение подобных вершин к разным классам) возможно только из-за не учтённого момента, на который указывал Спарроу, и который упустил "диссертант":

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

Спарроу отметил в своей статье один очень важный момент без учёта которого его алгоритм перестаёт быть корректным (и чего совершенно нет у "диссертанта"). А именно — из-за округления результатов вычислений с действительными числами, результат умножения трёх и более сомножителей зависит от порядка перемножения. Поэтому сомножители нужно предварительно упорядочивать, в противном случае на одних и тех же входах могу получиться разные сигнатуры, что, в свою очередь, может привести к отнесению подобных вершин к разным классам эквивалентности.

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

Но разве могут быть изоморфными группы с разным количеством элементов? Или я ошибаюсь?

Не ошибаетесь, не могут. Но это уже другой инвариант графа (и тоже не полный). Можно задать вопрос — будет ли полным инвариантом объединение указанных не полных инвариантов (то есть будут ли изоморфны графы одного порядка с изоморфными группами автоморфизмов)? Ответ дал Xaositect:

Xaositect в сообщении #1023294 писал(а):

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

Или не дал? Вот чё-то сам засомневался.

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

Получается, что автоморфное разбиение графа все же определяется группой автоморфизмов этого графа – т.е. списком всех автоморфизмов (подстановок).
Прошу Вас разъяснить мне в чем я ошибаюсь.

Дело в том, что сама группа автоморфизмов может быть очень большой (до $n!$ элементов), но для полного задания группы достаточно определить множество образующих, мощность которого в случае графа не превышает $(n-1).$ Имеется алгоритм построения множества образующих для группы автоморфизмов графа (вероятно, полиномиальный для почти всех графов, но экспоненциальный в общем). И полиномиальный алгоритм построения орбит группы автоморфизмов по множеству образующих. Саму группу при этом строить не обязательно, да и не всегда можно это сделать за полиномиальное время. Всё это есть в, упомянутой ранее, статье Пономаренко.

-- 04 июн 2015, 18:47 --

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

В частности, как переводится Nor even.

Эта фраза вырвана из контекста. Точный перевод можно сделать с учётом предыдущего предложения, в котором говорится о том, что для практических целей трансцендентные числа не нужны. И тогда перевод будет примерно таким: "Ни даже иррациональные числа — будет достаточно случайных чисел".

[sqribner48]

Уважаемые whitefox и Xaositect
Большое спасибо за Ваши разъяснения.

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

Дело в том, что сама группа автоморфизмов может быть очень большой (до $n!$ элементов), но для полного задания группы достаточно определить множество образующих, мощность которого в случае графа не превышает $(n-1).$ Имеется полиномиальный алгоритм построения множества образующих для группы автоморфизмов графа. И полиномиальный алгоритм построения орбит группы автоморфизмов по множеству образующих. Саму группу при этом строить не обязательно, да и не всегда можно это сделать за полиномиальное время.

Буду разбираться в этом. Чтобы не засорять тему, разрешите мне обратиться к Вам с вопросами (если таковые возникнут) в ЛС. Буду очень благодарен.
Впрочем в случае необходимости и по Вашим разрешениям сами вопросы и Ваши ответы на них могут быть перенесены в тему.

(Оффтоп)

Хотелось бы отметить следующее:

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

... для сильно регулярных графов множество вершин вообще не разбивалось.

Т.е. для некоторых сильно регулярных графов в результате работы алгоритма Спарроу очень быстренько получалась одна орбита. Аналогичные результаты (с одной орбитой) получались и с помощью длительной работы Mathematica и выводом довольно длинных списков автоморфизмов. Для других сильно регулярных графов (21 и более вершин) автоморфизмы даже не были получены.
Для 26-ти вершинного графа AVFL, указанного в статье Спарроу как контрпример, Mathematica нашла 10 орбит группы автоморфизмов, а алгоритм Спарроу всего одну.