Полиномиальный алгоритм изоморфизма графов

[whitefox]

Представляю обещанный анализ процедуры P1.

Первая же фраза в описании алгоритма вызывает недоумение:

Цитата:

Let graphs G,G′ are isomorphic.

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

Мысленно заменим "изоморфные" на "простые связные" и продолжим наш анализ.

Пусть $\tilde{k}_i$ означает отсортированную в неубывающем порядке $i$-ю строку матрицы $\mathrm{A^{-1}}.$
Очевидно, что вектор $\tilde{k}$ является инвариантом подобия, то есть если вершины $u$ и $v$ подобны, то вектора $\tilde{k}_u$ и $\tilde{k}_v$ равны.

Пусть $\tilde{K}$ означает матрицу $\mathrm{A^{-1}}$ каждая строка которой отсортирована в неубывающем порядка, а затем сами строки отсортированы в лексикографическом порядке.
Очевидно, что матрица $\tilde{K}$ является инвариантом графа, то есть если графы $G$ и $H$ изоморфны, то матрицы $\tilde{K}_G$ и $\tilde{K}_H$ равны.

Допустим, что процедуре P1 работает правильно. Тогда она проверяет подобна ли вершина $i$ графа $G$ вершине $j$ графа $G'.$ И если они подобны, то выдаёт изморфизм $\alpha$ графа $G$ на граф $G'$ такой, что $\alpha(i)=j.$ А если не подобны выдаёт пустое множество.
Исходя из этого, мы можем, без всякой потери общности, ограничиться рассмотрением только таких графов $G$ и $G'$ для которых $\tilde{K}_G=\tilde{K}_{G'}.$

Пусть $\tilde{\mathfrak{U}}$ и $\tilde{\mathfrak{U}}'$ означает разбиение множества $V$ и $V'$, соответственно, на классы псевдоподобных вершин, индуцированное инвариантом подобия $\tilde{k}.$ То есть вершины $u$ и $v$ графа $G$ принадлежат одному классу псевдоподобия, если и только если $\tilde{k}_u=\tilde{k}_v.$

Так как $\tilde{K}_G=\tilde{K}_{G'}$, то разбиения $\tilde{\mathfrak{U}}$ и $\tilde{\mathfrak{U}}'$ аналогичны. В том смысле, что имеют одинаковое число классов псевдоподобия, одинаковые наборы инвариантов подобия, и одинаковые мощности соответствующих классов (с равными $\tilde{k}$).
Пусть $\tilde{\mathfrak{U}}_i$ означает разбиение $\tilde{\mathfrak{U}}$ у которого вершина $i$ индивидуализирована, то есть выделена в отдельный класс единичной мощности.

Построим двудольный граф $\tilde{H}=(V,V',\tilde{U})$, где $V$ множество вершин графа $G$, $V'$ множество вершин графа $G'$, $\tilde{U}$ множество рёбер графа $\tilde{H}$, такое что вершина $p\in V$ соединена с вершиной $q\in V'$, если и только если $\tilde{k}_p=\tilde{k}_q.$

Пусть $\tilde{H}_{ij}=(V,V',\tilde{U}_{ij})$ означает граф $\tilde{H}$ в котором вершины $i\in V$ и $j\in V'$ индивидуализированы, то есть выделены в отдельные классы единичной мощности, а из всех рёбер, инцидентных данным вершинам, оставлено только ребро $(i,j).$

Выберем вершину $i\in V$ и вершину $j\in V'.$
Без потери общности можно считать, что $\tilde{k}_i=\tilde{k}_j.$ В противном случае вершины $i$ и $j$ не подобны, и правильно работающая процедура P1 выдаст пустое множество.

Вектор $\tilde{k}_i$ определяет разбиение $\mathfrak{U}$ множества $V$, объединяя в один класс такие вершины $u,v\in V$, что $k_{iu}=k_{iv}.$
Аналогично вектор $\tilde{k}_j$ определяет разбиение $\mathfrak{U'}$ множества $V'$, условием -- вершины $u,v\in V'$ принадлежат одному классу разбиения $\mathfrak{U'}$ тогда и только тогда, когда $k_{ju}=k_{jv}.$
Очевидно, что разбиение $\mathfrak{U}$ является более грубым по сравнению с разбиением $\tilde{\mathfrak{U}}_i$. То есть один класс разбиения $\mathfrak{U}$ может состоять из нескольких классов разбиения $\tilde{\mathfrak{U}}_i$. Аналогично разбиение $\mathfrak{U'}$ является более грубым по сравнению с разбиением $\tilde{\mathfrak{U}}'_j.$

Так как $\tilde{k}_i=\tilde{k}_j$, то разбиение $\mathfrak{U}$ аналогично разбиению $\mathfrak{U'}$, в том смысле что у них совпадает число классов, множество различных элементов вектора $\tilde{k}_i$ совпадает с множеством различных элементов вектора $\tilde{k}_j$, и равны мощности соответствующих классов.

Выполним шаг 1) процедуры P1, то есть построим двудольный граф $H_{ij}$ по правилам описанным в статье.
Очевидно, что множество $\tilde{U}_{ij}$ рёбер графа $\tilde{H}_{ij}$ является подмножеством множества $U_{ij}$ рёбер графа $H_{ij}.$

Приступим к выполнению шага 2) процедуры Р1.
На этом шаге выполняется цикл по всем рёбрам графа $H_{ij}$ (фактически итерации будут выполняться только по тем рёбрам которые ещё небыли удалены на предыдущих итерациях).

Так как порядок выбора рёбер не указан, то можем выбрать любой.
Поэтому разобьём шаг 2) на два этапа:

на первом выбираем рёбра принадлежащие множеству $U_{ij}\diagdown\tilde{U}_{ij}$
на втором принадлежащие множеству $\tilde{U}_{ij}$.

То есть на первом этапе будут проверяться рёбра соединяющие заведомо не подобные вершины, так как их инварианты подобия $\tilde{k}$ различны.
Правильно работающая процедура Р1 будет такие рёбра из исходного графа $H_{ij}$ удалять.
Таким образом по окончании первого этапа наш граф $H_{ij}$ будет совпадать с графом $\tilde{H}_{ij}$.
То есть уже на 1) шаге процедуры Р1 мы можем вместо графа $H_{ij}$ взять граф $\tilde{H}_{ij}$, без всякой потери общности.

Замечаем, что на втором этапе шага 2) процедуры Р1 выполняется условие $\tilde{H}_{ij}\cap H_{pq}=\tilde{H}_{ij}\cap \tilde{H}_{pq}.$
Поэтому и на шаге 2) процедуры Р1 мы можем вместо графов $H_{pq}$ использовать графы $\tilde{H}_{pq}$, без всякой потери общности.

Замечаем, что на втором этапе шага 2) процедуры Р1 функция Т() всегда находит трансверсаль. То есть по окончании шага 2) мы получим некоторую трансверсаль которая, как мы надеемся, представляет изоморфизм графа $G$ на граф $G'.$

На шаге 3) найденный "изоморфизм" выдаётся на-гора.

Видим, что процедура Р1 фактически работает не с графом $\tilde{H}_{ij}$, а с разбиениями $\tilde{\mathfrak{U}}_i$ и $\tilde{\mathfrak{U}}'_j.$

Её можно записать так:
1) на входе получаем псевдоподобные вершины $i\in V$ и $j\in V'$ (то есть $\tilde{k}_i=\tilde{k}_j$)
2) для каждой индивидуализированной вершины $u$ разбиения $\tilde{\mathfrak{U}}$ (то есть вершины принадлежащей классу псевдоподобия единичной мощности) добавляем к изначально пустому отображению $map$ пару $(u,v)$, где $v$ -- вершина разбиения $\tilde{\mathfrak{U}}'$ соответствующая вершине $u$ (такая вершина обязательно имеется, причём ровно одна, так как разбиение $\tilde{\mathfrak{U}}'$ аналогично разбиению $\tilde{\mathfrak{U}}$)
3) если вершины $i$ и $j$ ещё не индивидуализированы, то индивидуализируем их и добавляем к отображению $map$ пару $(i,j)$
4) если все вершины разбиения $\tilde{\mathfrak{U}}$ уже индивидуализированы, то выдаём отображение $map$ и останавливаемся
5) выбираем не индивидуализированную вершину $u$ разбиения $\tilde{\mathfrak{U}}$
выбираем не индивидуализированную вершину $v$ из класс псевдоподобия разбиения $\tilde{\mathfrak{U}}'$, соответствующего классу псевдоподобия вершины $u$
добавляем к отображению $map$ пару $(u,v)$
6) если разбиение $\tilde{\mathfrak{U}}$ имеет ещё не обработанные индивидуализированные вершины (одна такая вершина может появиться на предыдущем шаге когда мощность класса псевдоподобия вершины $u$ равна двум), то соответствующие пары добавляем к отображению $map$
7) возвращаемся на шаг 4).

Это очень плохой алгоритм.
Ранее в этой теме он уже разбирался и был отвергнут.
Именно для замены этого алгоритма Вами был предложен Алгоритм 1, который работает абсолютно правильно на графах у которых разбиение $\tilde{\mathfrak{U}}$ множества вершин на классы псевдоподобия совпадает с автоморфным разбиением.
Вот его-то (Алгоритм 1) и нужно использовать в процедуре Р1.

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

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

[bin]

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

2bin
Насколько я понял, для правильной работы процедуры P1 совершенно необходима приведённая Вами верхняя оценка величин $k_{ij}$

Цитата:

$$ \begin{cases} \begin{array}{cc} 1\text{<}k_{ij}<2 & if \: i=j,\\ 0<k_{ij}<1 & otherwise.\end{array}\end{cases}(2)$$

Не могли бы Вы поподробнее изложить её вывод?

Это с очевидностью следует из ряда Неймана для обратной матрицы, представленного на p.2 (в низу), версии 4 препринта. Куда уж поподробнее?

-- Ср июл 11, 2012 23:47:27 --

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

Первая же фраза в описании алгоритма вызывает недоумение:Цитата:Let graphs G,G′ are isomorphic.Означает ли это, что данный алгоритм проверки изоморфизма к не изоморфным графам не применим?

Нет. Не означает. Это еще не описание, а введение, вводные замечания, а строгое описание приведено на p.6 в псевдокоде, кот. так и подписан "Algorithm 1."
На остальное смогу ответить позже, очень сожалею из-за нехватки времени.

[ogaman]

Как я понял, предложенный алгоритм "вырос" из химической тематики. Каким образом задаются графы оптических изомеров?

[whitefox]

bin в сообщении #594577 писал(а):

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

2bin
Насколько я понял, для правильной работы процедуры P1 совершенно необходима приведённая Вами верхняя оценка величин $k_{ij}$

Цитата:

$$ \begin{cases} \begin{array}{cc} 1\text{<}k_{ij}<2 & if \: i=j,\\ 0<k_{ij}<1 & otherwise.\end{array}\end{cases}(2)$$

Не могли бы Вы поподробнее изложить её вывод?

Это с очевидностью следует из ряда Неймана для обратной матрицы, представленного на p.2 (в низу), версии 4 препринта. Куда уж поподробнее?

Приведённый анализ процедуры Р1 показывает, что она никоим образом не зависит от указанного свойства.
Поэтому требование о строгом его доказательстве снимается.

bin в сообщении #594577 писал(а):

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

Первая же фраза в описании алгоритма вызывает недоумение:Цитата:Let graphs G,G′ are isomorphic.Означает ли это, что данный алгоритм проверки изоморфизма к не изоморфным графам не применим?

Нет. Не означает. Это еще не описание, а введение, вводные замечания, а строгое описание приведено на p.6 в псевдокоде, кот. так и подписан "Algorithm 1."

Вопрос был риторическим.

[bin]

ogaman в сообщении #594640 писал(а):

Как я понял, предложенный алгоритм "вырос" из химической тематики. Каким образом задаются графы оптических изомеров?

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

[ogaman]

bin в сообщении #594877 писал(а):

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

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

[bin]

ogaman в сообщении #595129 писал(а):

bin в сообщении #594877 писал(а):

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

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

Сожалею, но не сохранил этих ссылок. В химии много интересных задач, на все времени не хватает

[bin]

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

Мысленно заменим "изоморфные" на "простые связные" и продолжим наш анализ.

Где в статье я говорю, что графы простые? Что Вы понимаете под этим термином? То же, что Харари на стр.197 (Теория графов, М.: УРСС, 2003)? И далее Вы продолжаете подменять мои условия своими. Эквивалентны ли эти подмены? Приходиться долго думать. Но по факту получается, что Вы опровергаете не мой, а свой алгоритм, и ссылку дали на свое прочтение. Да, я тогда согласился, но придется вернуться. Однако я смогу сделать это позже, т.к. сейчас мне дали идею, как упростить и улучшить алгоритм и доказательство. М.б., если будет новый алгоритм, то опровергать Ваше опровержение старого будет ненужно. Но в любом случае, благодарен за Вашу критику и жду продолжения:

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

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

М.б. это продолжение ("в следующий раз") поможет новому алгоритму.

[whitefox]

bin в сообщении #596067 писал(а):

Где в статье я говорю, что графы простые? Что Вы понимаете под этим термином? То же, что Харари на стр.197 (Теория графов, М.: УРСС, 2003)?

Под термином "простой граф" я понимаю общепринятое, в настоящее время, определение:

WikipediA писал(а):

A graph is a simple graph if it has no multiple edges or loops

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

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

В своей статье Вы, действительно не используете термин "простой" граф. Вы делаете единственное допущение:

Цитата:

Further, without loss of generality of the task, we will consider undirected connected
graphs without loops

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

-- 17 июл 2012, 07:31 --

bin в сообщении #596067 писал(а):

М.б. это продолжение ("в следующий раз") поможет новому алгоритму.

Свои аргументы я, фактически, уже изложил выше.
А именно:

1. Ваш алгоритм эквивалентен "сибирскому" алгоритму, то есть графы по Вашему алгоритму изоморфны тогда и только тогда, когда они изоморфны по "сибирскому" алгоритму.

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

[bin]

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

Под термином "простой граф" я понимаю общепринятое, в настоящее время, определение:

WikipediA писал(а):

A graph is a simple graph if it has no multiple edges or loops

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

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

Ok! Спасибо за разъяснение. Просто у некоторых авторов были другие определения. Да, именно про такие графы в статье идет речь. Отмечу, что из несвязного графа, можно сделать связный добавив вершину, которая связана со всеми остальными. А ориентированный можно обратить в неориентированный с помощью "гаджетов" (добавлением подграфов). Т.о. общность не теряем.

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

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

1) Это утверждение нужно строго доказать. Пока же мы с Вами обменялись только соображениями: я привел доводы (в частности, в цитируемой статье, с которой Вы ознакомились), а Вы привели свои доводы. Но Вашими доводами можно так же "доказать", что все 4 моих алгоритма (из 4 опубликованных версий статьи) эквивалентны, а это не так: для них не верно, что графы по одному алгоритму изоморфны тогда и только тогда, когда они изоморфны по другому. Для нетривиальных алгоритмов док-во эквивалентности очень затруднительно.
2) Я много раз перечитывал "сибирские статьи" (и одно время переписывался с одним из авторов), но так и не понял, что за класс такой "ОС-графы", на которых работают их алгоритмы. Вы, видимо, поняли. Объясните, пожалуйста

[whitefox]

bin в сообщении #596419 писал(а):

Это утверждение нужно строго доказать.

Последуйте рекомендации Лакатоса, попытайтесь доказать утверждение противоречащее Вашему. Если получится - это избавит Вас от заблуждений.

Подсказка: рассмотрите матрицы используемые Вами и "сибиряками".

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

Вы оперируете матрицей $\mathrm{D}-\mathrm{M}$, где $\mathrm{D}=\operatorname{diag}(d_{1}+1,d_{2}+1,\dots,d_{n}+1)$
Они используют матрицу $\mathrm{D_0}+\mathrm{M}$, где $\mathrm{D_0}=\operatorname{diag}(d_{1}+d,d_{2}+d,\dots,d_{n}+d)$, $d=\max(d_1,d_2,\dots,d_n)$

bin в сообщении #596419 писал(а):

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

Вот определение, данное одним из авторов:

А.В. Пролубников писал(а):

Граф называется
определяемым спектром (ОС-графом), если ему изо-
морфен любой граф с таким же спектром матрицы,
представляющей граф. Спектр матрицы графа так
же называют спектром графа.

Авторами введён ещё один класс на котором применим их алгоритм - ОС2, включающий в себя первый.

Имхо, их алгоритм (а потому и Ваш) применим к ещё более широкому классу графов.

[bin]

1) Вы сделали утверждение - Вам его и доказывать, а не мне и не Лакатосу Подсказка: в 4х алгоритмах исхожу из одних и тех же матриц, но все эти алгоритмы не эквивалентны.

2) Спасибо, я читал это определение. ИМХО оно не дает границ применимости алгоритма. С тем же успехом можно определить класс Х, на котором алгоритм работает. Графы, на которых алгоритм не работает к классу Х не относятся. Ср. "алгоритм для класса планарных графов". BTW про спектры в статье я ничего не говорю.

[whitefox]

bin в сообщении #596673 писал(а):

Вы сделали утверждение - Вам его и доказывать, а не мне и не Лакатосу

Желаете и дальше пребывать в заблуждении? Воля Ваша.
Хотя бы попытались. Всё-таки Лакатос это Ваш авторитет.
А своё доказательство пока оставлю при себе, вдруг пригодится для какой-нибудь публикации.

bin в сообщении #596673 писал(а):

Спасибо, я читал это определение. ИМХО оно не дает границ применимости алгоритма.

В яблочко.
Именно в отсутствии легко-вычислимых границ применимости алгоритма и заключается вся сложность проблемы изоморфизма графов.

[bin]

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

А своё доказательство пока оставлю при себе, вдруг пригодится для какой-нибудь публикации.

О чем будет публикация? О том, что один непризнанный алгоритм эквивалентен другому
И кто же такое опубликует? Спасибо, развеселили! Публикуйте здесь! Пользуйтесь случаем застолбить приоритет, а то кто другой Вас опередит (не только на этом форуме мою статью обсуждают)

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

Именно в отсутствии легко-вычислимых границ применимости алгоритма и заключается вся сложность проблемы изоморфизма графов.

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

[whitefox]

bin в сообщении #596688 писал(а):

О чем будет публикация? О том, что один непризнанный алгоритм эквивалентен другому

Отнюдь. Куда интереснее определить точную границу класса графов для которых применимы алгоритмы подобные Вашему. Мне этот класс представляется довольно широким, но насколько он широк?

bin в сообщении #596688 писал(а):

У эвристических алгоритмов - да, а у строго доказанных - четкие границы

Мою мысль Вы поняли правильно.