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

[whitefox]

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

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

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

[whitefox]

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

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

Зря сомневался.
Вот пример парочки не изоморфных графов восьмого порядка с одинаковой группой автоморфизмов (тривиальной):

(Оффтоп)

0 1 1 1 1 1 0 0
1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
1 0 0 0 0 0 1 0
0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0

0 1 1 1 1 1 0 0
1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0
1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1
0 0 0 0 0 0 1 0

[sqribner48]

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

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

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

Зря сомневался.

(Оффтоп)

Это известный нам "диссертант" запутал?

В одном из своих предыдущих постов я писал о результатах тестирования неизоморфных асимметрических графов (с тривиальной группой автоморфизмов) одного порядка. Было протестировано 8 таких графов с 6 вершинами и 16 таких графов с 7 вершинами. И несмотря на то, что у этих графов были одинаковые группы автоморфизмов, алгоритм Спарроу четко определил все эти графы как неизоморфные (так как не нашлось ни одной пары одинаковых наборов числовых сигнатур)!
Так что, предложенный Вами пример, меня не удивил, а лишь дополнил мои результаты.
Спасибо Вам за него.
А нет ли у Вас примера двух неизоморфных графов с нетривиальными группами автоморфизмов (взаимно дополнительные друг к другу графы не в счет)?

[whitefox]

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

А нет ли у Вас примера двух неизоморфных графов с нетривиальными группами автоморфизмов

Такой пример построить не сложно. Возьмём два неизоморфных графа $G_1$ и $G_2$ с тривиальной группой автоморфизмов каждый. И возьмём граф $G_3$ с нетривиальной группой автоморфизмов и его копию $G'_3$. И пусть множества вершин всех четырёх графов попарно не пересекаются. Тогда графы $G_{13}=G_1\cup G_3$ и $G_{23}=G_2\cup G'_3$ неизоморфны, а их группы автоморфизмов изоморфны.

[sqribner48]

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

Такой пример построить не сложно.

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

[whitefox]

Графы $G_{13}$ и $G_{23}$ легко превратить в связные графы без мостов и шарниров. Для этого нужно просто добавить к каждому по паре вершин, и соединить последние со всеми прочими вершинами.

[sqribner48]

whitefox

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

Графы $G_{13}$ и $G_{23}$ легко превратить в связные графы без мостов и шарниров. Для этого нужно просто добавить к каждому по паре вершин, и соединить последние со всеми прочими вершинами.

Это конструкция графа $G_{12}$ (в выражении (7)) статьи Пономаренко (стр. 13). ?
Тогда для графа $G_{13}$ после добавления вершин $x_1, \, x_2$ и ребер имеем

$$V_{13}= V_1 \cup V_3 \cup \{x_1,x_2\},\; E_{13} = E_1 \cup E_3 \cup \{(x_1,x_2)\}\cup \{(x_1,v) \colon v \in V_1\} \cup \{(x_2,v) \colon v \in V_2\}.$$

Аналогично для графа $G_{23}$ после добавления вершин $y_1, \, y_2$ и ребер будем иметь

$$V_{23}= V_2 \cup V_3 \cup \{y_1,y_2\},\; E_{23} = E_2 \cup E_3 \cup \{(y_1,y_2)\}\cup \{(y_1,u) \colon u \in V_3\} \cup \{(y_2,u) \colon u \in V_4\}.$$

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

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

При этом, для определения изоморфизма двух графов можно рассмотреть три следующих метода:
а) для каждого графа по отдельности вычисляются числовые сигнатуры вершин и затем производится их сравнение;
б) графы объединяются в один (операция объединения по Харари), затем вычисляются числовые сигнатуры вершин и сравниваются;
в) графы объединяются в один, добавляется одна вершина и новые ребра, соединяющие ее со всеми вершинами обоих графов; затем вычисляются числовые сигнатуры вершин и сравниваются.

За что подвергся резкой, но не конструктивной и совершенно бездоказательной критике Fate'sMathematics

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

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

Однако, затем whitefox
напомнил, что проблема изоморфизма графов полиномиально эквивалентна проблеме автоморфного разбиения вершин графа.
Действительно, как показано в статье Матона - R. Mathon. A note on the 6raph isomorphism counting problem. Information processing letters., 1979, vol.8, issue 3, pp. 131—132 и в статье R. C. Read, D. G. Corneil. “The Graph Isomorphism Disease" определение изоморфизма графов $G_1$ и $G_2$ фактически сводится к определению автоморфного разбиения графа $G_3 =G_1 \cup G_2$. Причем две вершины $v \in G_1$ и $u \in G_2$ будут «изоморфно подобными» т.е.
$u =\alpha (v)$ (где $\alpha$ изоморфизм между графами $G_1$ и $G_2$) тогда и только тогда, когда обе эти вершины, будут принадлежать одной ячейке автоморфного разбиения $G_3$.
Таким образом, предложенный мной метод (б), в котором «графы объединяются в один (операция объединения по Харари), затем вычисляются числовые сигнатуры вершин и сравниваются» имеет теоретическое обоснование.
При этом следует учесть замечание whitefox ,что этот метод пригоден лишь для связных графов.
Как я уже ранее отмечал, предложенный мной метод (в) оказался не верным. Поэтому вместо него можно использовать подход, предложенный в вышеуказанной статье Пономаренко.
Согласно этому подходу для определения изоморфизма двух графов $G_1$ и $G_2$ предлагается построить следующую конструкцию:
1. Создать граф $G_3 =G_1 \cup G_2$;
2. Добавить две вершины $x_1$ и $x_2$;
3. Соединить вершины $x_1$ и $x_2$ ребром;
4. Соединить ребрами вершину $x_1$ со всеми вершинами $G_1$, а вершину $x_2$ соединить ребрами со всеми вершинами $G_2$.
Как было показано в вышеупомянутой статье Пономаренко, такая конструкция пригодна для определения изоморфизма любых графов. Причем графы $G_1$ и $G_2$ будут изоморфны тогда и только тогда, когда вершины $x_1$ и $x_2$ будут принадлежать одной ячейке автоморфного разбиения вершин графа $G_3$.
Ну вот, теоретические основы для определения изоморфизма посредством автоморфного разбиения есть и все измышления Fate'sMathematics оказались ложными.
Осталось только полностью довершить разбор алгоритма Спарроу определения автоморфно эквивалентных классов вершин, начатый мной, whitefox и Xaositect в предыдущих постах.

[whitefox]

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

Это конструкция графа $G_{12}$ (в выражении (7)) статьи Пономаренко (стр. 13).?

Похоже, но нет.

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

Тогда для графа $G_{13}$ после добавления вершин $x_1, \, x_2$ и ребер имеем

$$V_{13}= V_1 \cup V_3 \cup \{x_1,x_2\},\; E_{13} = E_1 \cup E_3 \cup \{(x_1,x_2)\}\cup \{(x_1,v) \colon v \in V_1\} \cup \{(x_2,v) \colon v \in V_2\}.$$

Аналогично для графа $G_{23}$ после добавления вершин $y_1, \, y_2$ и ребер будем иметь

$$V_{23}= V_2 \cup V_3 \cup \{y_1,y_2\},\; E_{23} = E_2 \cup E_3 \cup \{(y_1,y_2)\}\cup \{(y_1,u) \colon u \in V_3\} \cup \{(y_2,u) \colon u \in V_4\}.$$

Правильно?

Не совсем так.

$$V_{13}= V_1 \cup V_3 \cup \{x_1,x_2\},\; E_{13} = E_1 \cup E_3 \cup \{(x_1,v) \mid v \in V_1 \cup V_3\} \cup \{(x_2,v) \mid v \in V_1 \cup V_3\}$$

$$V_{23}= V_2 \cup V'_3 \cup \{y_1,y_2\},\; E_{23} = E_2 \cup E'_3 \cup \{(y_1,v) \mid v \in V_2 \cup V'_3\} \cup \{(y_2,v) \mid v \in V_2 \cup V'_3\}$$

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

Но согласитесь, это тоже не совсем обычные, а искусственно сконструированные графы.

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

[nazarov_m]

В целом задача о построении разбиения на классы автоморфизма для вершин (APART) является полиномиально эквивалентной задаче об изоморфизме (ISO).

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

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

Ну а что касается моей статьи "Альтернативные подходы к описанию классов изоморфных графов " в ПДМе, то
1) Для решения задачи об изоморфизме инвариант $I[G]$ не пригоден. Вычисление искомого $I[G]$ эквивалентно задаче ISO.
2) Использовать на практике $I[G]$ можно примерно также как и обычные канонические формы графов Canon(G). Т.е. предварительное вычисление $I[G]$ с последующим хранением в памяти.
3) В самой статье имеется ошибка со сдвигом нумерации в иллюстрациях. Фактически иллюстрации соответствуют индексам вершин, которые заданы в два шага:
Определение 1: Пусть макси-коду графа $G$ соответствует некоторый порядок следования вершин $\alpha$ . Тогда назовем номером класса автоморфизма вершин $\overline{v}$ натуральное число $N(\overline{v})$, которое равно : $ N(\overline{v}) = \! \min\limits_{i: \, \alpha(i) \in \overline{v} } \! \! i$
Определение 2: Введем индексы классов автоморфизма вершин $I(\overline{v})$ индуктивно:

1. $N(\overline{v}) = \min\limits_{\overline{u}} N(\overline{u}) \, \Rightarrow \, I(\overline{v}) = 1$ - базис индукции;
   
2. $ \left. \begin{matrix} & (N(\overline{v}) > N(\overline{u})) \, \wedge \\ & (\forall u^{*}\! \!\neq \!\! u \, \, N(\overline{v}) > N(\overline{u^{*}}) \Rightarrow N(\overline{u}) > N(\overline{u^{*}})) \end{matrix} \right\rbrace \Rightarrow I(\overline{v}) = I(\overline{u}) + 1 $ - индуктивный переход.

4) Достаточно скоро выйдет новая статья на эту тему с подробным описанием всех алгоритмов и исправлением всех обнаруженных багов.

[sqribner48]

Уважаемый nazarov_m
Спасибо за проявленный интерес к моей теме. Ваше внимание мне особенно приятно, так как именно Ваша статья дала первоначальный «толчок» для создания темы, поскольку в ней были ссылки на статью Спарроу и на диссертацию Саутвелла.

nazarov_m в сообщении #1027252 писал(а):

В целом задача о построении разбиения на классы автоморфизма для вершин (APART) является полиномиально эквивалентной задаче об изоморфизме (ISO).

На это мне впервые указал whitefox, за что я ему искренне благодарен.

nazarov_m в сообщении #1027252 писал(а):

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

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

nazarov_m в сообщении #1027252 писал(а):

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

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

(Оффтоп)

В диссертации я нашел одну очень важную ошибку. Вот привожу отрывок текста из диссертации, взятого со стр. 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$.

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

nazarov_m в сообщении #1027252 писал(а):

Ну а что касается моей статьи "Альтернативные подходы к описанию классов изоморфных графов " в ПДМе, то
1) Для решения задачи об изоморфизме инвариант $I[G]$ не пригоден. Вычисление искомого $I[G]$ эквивалентно задаче ISO.

Я это знаю и про это я не писал. Я написал лишь, что:

Цитата:

Фактически, с помощью алгоритма Спарроу вершины асимметричного графа могут быть упорядочены в соответствии с их числовыми сигнатурами, что может быть использовано для получения полного инварианта $I[G]$ графа $G$ (без получения его макси-кода), описанного в статье М.Н. Назарова. Альтернативные подходы к описанию классов Изоморфных графов. Прикладная дискретная математика, 2014, №3(25), с. 86-97.

Уважаемый nazarov_m. Еще раз спасибо за Ваши замечания по теме. С нетерпением буду ждать Вашу новую статью.

[nazarov_m]

Цитата:

На это мне впервые указал whitefox, за что я ему искренне благодарен.

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

Насчёт инварианта $ I[G] $, то "заказ" на эту конструкцию поступил от знакомых химиков. По умолчанию они для хранения молекул используют канонические формы графов (см. например стандарт SMILES). Но вот появилось желание получить альтернативу, у которой в явном виде будут все классы автоморфизма (вершин и рёбер) непосредственно интегрированы в сам инвариант. В этом случае сразу видны все симметрии молекулы, и не нужно каждый раз решать задачу APART.

Собственно чтобы инвариант $ I[G] $ можно было получить для произвольно больших графов достаточно дать описание для некоторых простых классов графов, а также построить базис операций полиномиальной сложности для $ I[G] $.
Тут важно отметить, что если такой базис существует для маркированных инвариантов $ I^{*}[G] $, то это будет означать что задача об изоморфизме решается за полиномиальное время. Так что скорее всего если и можно построить искомый базис операций полиномиальной сложности, то только для чистых инвариантов $ I[G] $ без меток. Ну а собственно химикам достаточно набора операций, который бы работал с почти всеми графами и покрывал бы по возможности все известные молекулярные графы.

[Yuri Gendelman]

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

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

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

Обратите внимание на титульный лист диссертации:

Цитата:

Finding Symmetries in Graphs
Richard Southwell
Dissertation submitted for the MSc in Mathematics with Modern Applications,
August 2006

Это не PhD, а MSc.

[whitefox]

Yuri Gendelman

(Оффтоп)

Спасибо.
Как-то сразу показалось, что сия работа на PhD ну никак не тянет.

[sqribner48]

(Оффтоп)

Долго не мог завершить тему из-за острой нехватки времени.

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

Типы ошибок
Полезно суммировать все типы отказов, которые могут возникнуть при использовании метода числовых сигнатур при определении автоморфно эквивалентных классов.
(a) Тип I: Размещение автоморфно эквивалентных узлов в различных классах.
(b) Тип II: Размещение автоморфно различных узлов в том же самом классе в результате случайного совпадения числовых сигнатур.
(c) Тип III: Размещение автоморфно различных узлов в том же самом классе в результате генерации идентичных многочленов от разных структур.
(d) Тип IV: Размещение автоморфно различных узлов в том же самом классе в результате дефицита самого метода.
Ошибки первого рода никогда не должны происходить, при нормальной работе компьютера.
Ошибка первого рода у меня произошла всего один раз при вводе ошибочных данных.

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

Ошибок III типа можно избежать полностью при использовании различных коэффициентов составления в каждой последовательной стадии. Практически такие ошибки не возникают, даже при неоднократном использовании тех же самых коэффициентов.

Ошибки IV типа, кажется, редки. Кроме случаев особенно построенных графов (таких как граф AVLF) метод неизменно приводит к соответствующему разложению.

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

Второй такой «камень» привожу в авторском тексте:

Цитата:

«Но остерегайтесь экспоненциального роста в числовых сигнатурах, которые произойдут при расчете больших сетей. Если вещественным числам позволить стать слишком большими, то они достигнут некоторого верхнего допустимого предела, определенного для языка программирования и компилятора.
В этом случае многие такие числа могут принять одинаковое максимально допустимое значение. Избегайте этого, отказываясь от части целого числа каждой сигнатуры в каждой стадии расчета. Это сохранит значения всех сигнатур в диапазоне (0, 1).»

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

С учетом вышеописанных модификаций структура алгоритма Спарроу выглядит так:
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]} (\gamma_{i,j} + S_{j,0}),\; \forall v_i \in G, $$

где $N[v_i]$ -- множество вершин, смежных с вершиной $v_i$;
$\gamma_{i,j}$ -- коэффициенты составления(разные иррациональные числа типа $\pi$, $e$ или случайные числа в диапазоне от 0 до 1) которые или могут быть постоянными, или изменяться при изменении номера вершины $v_i$.
3. На $k$-ой итерации $(1 < k \le n)$ числовые сигнатуры $k$-го порядка вершин вычисляются по следующим выражениям:

$$S_{i,k}= (|N^k[v_i]|+ \sqrt\pi) \prod_{j \in N[v_i]} (\gamma_{i,j} + 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$-- общее количество выполняемых итераций; $\gamma_{i,j}$ -- коэффициенты составления (разные иррациональные числа типа $\pi$, $e$ или случайные числа в диапазоне от 0 до 1), которые или могут быть постоянными, или изменяться от стадии к стадии, или изменяться при изменении номера вершины $v_i$ и номера $j$ стадии.
4. После завершения вычисления числовых сигнатур (необходимого) $n$-го порядка всех вершин производится их сравнение. Вершины с одинаковым значением сигнатуры вводятся в один класс. Процесс вычисления автоморфно эквивалентных классов реализуется в отдельной процедуре. Эту процедуру также можно выполнять и после выполнения каждой $k$--той итерации.

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