Кто-нибудь знает контр-пример алгоритма изоморфизма графа Дарвадера-Тевета?

На сайте http://www.dharwadker.org/tevet/isomorphism/ представлен алгоритм определения изоморфности двух графов. Учитывая ряд, скажем так, «интересных» утверждений А. Дхарвадкера, я не склонен верить в это.

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

Однако я не знаю контрпример. Прежде чем приступить к написанию программного обеспечения для тестирования алгоритма, я подумал, что увижу, знает ли кто-нибудь уже контр-пример.

Кто-то запросил краткий обзор алгоритма. Я сделаю то, что могу, но чтобы по-настоящему понять это, вам следует посетить http://www.dharwadker.org/tevet/isomorphism/ .

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

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

Второй этап - этап сортировки - является сомнительной частью. В частности, я ожидаю, что если их процесс сработает, то алгоритм, разработанный Анной Любив для обеспечения «вдвойне лексического упорядочения матриц» (см .: http://dl.acm.org/citation.cfm?id=22189 ). также будет работать, чтобы определить каноническую форму для графа.

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

Для graphA.txt:

25
 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1
 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1
 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0
 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1
 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0
 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1
 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1
 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0
 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1
 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0
 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0
 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0
 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1
 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1
 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1
 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0

и graphB.txt:

25
 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0
 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0
 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1
 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0
 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1
 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1
 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1
 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0
 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1
 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1
 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0
 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1
 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0
 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0
 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0
 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1
 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1
 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1
 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1
 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0
 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0

который получается graphA.txtпутем применения (случайной) перестановки

 22 9 24 11 15 8 5 18 13 14 2 10 23 0 3 17 4 16 6 19 7 21 12 1 20

программа C ++ isororphism.cppиз рисунка 6.3. Программа на C ++ для алгоритма изоморфизма графов в http://www.dharwadker.org/tevet/isomorphism/ выдает следующий результат:

The Graph Isomorphism Algorithm
by Ashay Dharwadker and John-Tagore Tevet
http://www.dharwadker.org/tevet/isomorphism/
Copyright (c) 2009
Computing the Sign Matrix of Graph A...
Computing the Sign Matrix of Graph B...
Graph A and Graph B have the same sign frequency vectors in lexicographic order but cannot be isomorphic.
See result.txt for details.

Таким образом, мы можем предположить, что это контрпример к алгоритму изоморфизма графа Дарвадера-Тевета.

Как предполагает Билл Провинция, проблема заключается в

4.1. Предложение. Если графы и изоморфны, то алгоритм находит изоморфизм.$G_A$$G_B$

Возражение Билла Провинса состоит в том, что доказательство предложения 4.1. не использует никаких специальных свойств матрицы знаков, которые также не применяются к матрице смежности. Точнее, следующий шаг в доказательстве неверен:

Для гипотезы индукции предположим, что строки в и были полностью согласованы с помощью процедуры 3.4, так что метки вершин для строк в равны и метки вершин для строк в имеют вид соответственно.$1, ..., t$$A$$B$$1, ..., t$$A$$v_1, ..., v_t$$1, ..., t$$B$$φ(v_1) = v'_1, ..., φ(v_t) = v'_t$

потому что даже если строки были идеально согласованы, из этого не следует, что метки вершин совпадают с метками, заданными любым изоморфизмом .$φ$

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

Благодарности Контр-пример является первой из восьмой пары графов из

http://funkybee.narod.ru/graphs.htm

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

https://people.mpi-inf.mpg.de/~pascal/software/

Чтобы понять дыру в доказательстве правильности, был очень полезен комментарий Андраса Саламона о Вейсфейлере-Лемане, а также объяснения от

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

Мотивация использовать этот вопрос как возможность познакомиться с nauty / Traces и практическими аспектами изоморфизма графов была предоставлена ​​vzn. Преимущество изучения того, как использовать современные программы для изоморфизмов графа, стоило потратить некоторое время на поиск контрпримера (который я твердо верил в существование).