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

[bin]

Ранее Вы написали:

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

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

Еще раз: не в этом заключается проблема! Нпр., мой изначальный алгоритм (опубликованный в Изв. РАН) самоочевидно охватывает все графы, как и знаменитая nauty, т.к. это алгоритмы с возвратом. На выборке в 95 млн. графов я увидел, что экспоненты от числа вершин нет. Что несколько возвратов, а потом идет лавина, дискриминирующая вершины. Но как обосновать это теоретически? М.б. невозможно. Для nauty в сибирских статьях указаны несложные примеры, когда реализуется наихудший экспоненциальный случай. Для моего изначального алгоритма такого случая пока не найдено. Думаю, что и не найдется. Проблема в этом. BTW изначальный алгоритм решает те же СЛУ, но с очевидностью корректен для всех графов

[whitefox]

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

Для моего изначального алгоритма такого случая пока не найдено. Думаю, что и не найдется.

В том-то и дело, что найдется. Нужно искать пару изоморфных графов с различными инвариантами $\tilde{K}$

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

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

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

И, пожалуйста, не требуйте от меня представить эти графы явно. Мне жалко времени на их поиск, но они определёно существуют так как инвариант $\tilde{K}$ не является полным.

[bin]

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

Нужно искать пару изоморфных графов с различными инвариантами

У изоморфных графов значения любого инварианта равны (см. определение инварианта графа). М.б. Вы хотели сказать: Нужно искать пару неизоморфных графов с равными инвариантами? В любом случае, на 95 млн. графов для моего алгоритма с возвратом для ${n}$-вершинного графа наблюдается: через малое число итераций ${m}$ (${m}<<{n}$, при достаточно большом ${n}$) все вершины приобретают разные веса, т.е. дискриминируются, что означает единственное на данной ветке дерева решений соответствие (т.е. перебор прекращается). Т.о. полного перебора не происходит, и ветки $({n}-{m})!$ отсекаются. При этом, если ${m}$ и растет с ростом ${n}$, то очень слабо, явной зависимости ${m}$ от класса графа обнаружено не было. (И это при том, что инвариант, как Вы справедливо заметили, неполный!)

-- Чт июл 19, 2012 22:46:29 --

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

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

Учитывая вышесказанное, не смею требовать от кого-либо такого поиска, который с почти полной вероятностью обречен на неуспех!

-- Чт июл 19, 2012 22:52:58 --

Дело в другом. First impression я уже высказал, но продолжаю балдеть от Вашей методологии. Недавно Вы написали:

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

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

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

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

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

Т.е. никакого содержательного обсуждения с Вашей стороны, но тогда и остальные участники свои доказательства оставят при себе (в том числе и я). А значит, все молча проявят пристальное внимание и … ничего. А к чему проявлять пристальное внимание, если я оставлю при себе исправленный алгоритм? К черновику?

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

В итоге имеем ситуацию, когда никто ничего не говорит и никого не слышит (а что слушать, если все молчат?), никто ничего не знает (кроме того, что сам придумал). А зачем тогда форум? И зачем здесь время тратить?

-- Чт июл 19, 2012 23:16:53 --

PS

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

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

Любой алгоритм с возвратом (backtracking) всегда дает правильный ответ, но иногда м.б. ценой полного перебора

[sup]

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

Учитывая вышесказанное, не смею требовать от кого-либо такого поиска, который с почти полной вероятностью обречен на неуспех!

Если я правильно понял о чем идет речь, то искать не долго.
Для регулярных графов матрица $\mathrm{A^{-1}}$ это просто полином от матрицы смежности $M$, однозначно определяемый минимальным многочленом для $M$.

Поэтому, стоит поискать среди сильно-регулярных графов с одинаковыми параметрами. Для них выполнены соотношения
($J$ - матрица, все элементы которой равны 1)
$MJ = kJ$
$M^2 +aM +bE = cJ$
А потому, матрица $A^{-1}$ - суть линейная комбинация $M$ и $J$
После сортировки все индивидуальные особенности $M$ исчезают.
Такие неизоморфные графы существуют см. например http://en.wikipedia.org/wiki/Shrikhande_graph (Shrikhande graph & rook's graph).
Об этом, кстати, уже давно говорилось, что свойства $A^{-1}$ и $M$ очень близки (точнее не только $M$, но и степеней $M^k$). Для регулярных графов это следствие теоремы Кэли-Гамильтона.

[whitefox]

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

У изоморфных графов значения любого инварианта равны (см. определение инварианта графа). М.б. Вы хотели сказать: Нужно искать пару неизоморфных графов с равными инвариантами?

Да Вы правы, оговорился.

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

Любой алгоритм с возвратом (backtracking) всегда дает правильный ответ, но иногда м.б. ценой полного перебора

Но Вы-то свой алгоритм позиционируете как полиномиальный.

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

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

Продолжайте балдеть дальше, а отказываюсь общаться с Вами в таком ключе.

[bin]

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

Но Вы-то свой алгоритм позиционируете как полиномиальный.

Не путайте! Речь шла о другом моем алгоритме, который был позиционирован, как алгоритм с возвратом. Другое дело, что возвратов он делает очень мало, об этом и речь.

-- Пт июл 20, 2012 13:27:02 --

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

Продолжайте балдеть дальше, а отказываюсь общаться с Вами в таком ключе.

Не понравилось слово "балдею"? Охотно беру его назад, заменив словом "удивляюсь". Ok? Хотелось бы услышать по сути, предложенной Вами методологии обсуждения, столь удивившей меня.

-- Пт июл 20, 2012 13:41:11 --

sup в сообщении #597130 писал(а):

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

Учитывая вышесказанное, не смею требовать от кого-либо такого поиска, который с почти полной вероятностью обречен на неуспех!

Если я правильно понял о чем идет речь, то искать не долго.
Для регулярных графов матрица $\mathrm{A^{-1}}$ это просто полином от матрицы смежности $M$, однозначно определяемый минимальным многочленом для $M$.

Поэтому, стоит поискать среди сильно-регулярных графов с одинаковыми параметрами. Для них выполнены соотношения
($J$ - матрица, все элементы которой равны 1)
$MJ = kJ$
$M^2 +aM +bE = cJ$
А потому, матрица $A^{-1}$ - суть линейная комбинация $M$ и $J$
После сортировки все индивидуальные особенности $M$ исчезают.
Такие неизоморфные графы существуют см. например http://en.wikipedia.org/wiki/Shrikhande_graph (Shrikhande graph & rook's graph).
Об этом, кстати, уже давно говорилось, что свойства $A^{-1}$ и $M$ очень близки (точнее не только $M$, но и степеней $M^k$). Для регулярных графов это следствие теоремы Кэли-Гамильтона.

Спасибо за совет. Я обязательно испытаю этот граф (м.б. я его уже его пробовал - сходу не вспомню, испытывалось много сильно-регулярных графов). Однако, не думаю, что найдется нумерация, при которой мой алгоритм с возвратом (NB! Здесь речь о нем, а не о тех, что в препринте) потребует полный перебор всех его вершин: "После сортировки все индивидуальные особенности $M$ исчезают"- но алгоритм работает несколько иначе...

[whitefox]

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

Не путайте! Речь шла о другом моем алгоритме, который был позиционирован, как алгоритм с возвратом. Другое дело, что возвратов он делает очень мало, об этом и речь.

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

(Оффтоп)

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

(Оффтоп)

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

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

Удивляюсь Вашему удивлению, что-то не припомню чтобы мной предлагались бы какие-либо методологии.

Единственное моё предложение Вам было - самостоятельно поискать опровержение собственного утверждения. Но это не моя методология, а столь почитаемого Вами Лакатоса.

[bin]

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

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

1) Но он решает те же СЛУ, значит, по Вашей логике, он эквивалентен другим моим алгоритмам и сибирским алгоритмам 2) А откуда Вы знаете, что "время его работы не полиномиально"?

-- Пт июл 20, 2012 14:06:13 --

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

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

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

-- Пт июл 20, 2012 14:13:25 --

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

Удивляюсь Вашему удивлению, что-то не припомню чтобы мной предлагались бы какие-либо методологии.

См.:

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

Вы написали:

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

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

Т.е. никакого содержательного обсуждения с Вашей стороны, но тогда и остальные участники свои доказательства оставят при себе (в том числе и я). А значит, все молча проявят пристальное внимание и … ничего. А к чему проявлять пристальное внимание, если я оставлю при себе исправленный алгоритм? К черновику?

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

В итоге имеем ситуацию, когда никто ничего не говорит и никого не слышит (а что слушать, если все молчат?), никто ничего не знает (кроме того, что сам придумал). А зачем тогда форум? И зачем здесь время тратить?

Т.е. предложенная Вами методология обсуждения ведет к молчанию: "никто ничего не говорит и никого не слышит (а что слушать, если все молчат?)".

[whitefox]

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

1) Но он решает те же СЛУ, значит, по Вашей логике, он эквивалентен другим моим алгоритмам и сибирским алгоритмам

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

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

2) А откуда Вы знаете, что "время его работы не полиномиально"?

А Вы умеете делать полный перебор за полиномиальное время? Ну тогда Вы решили не только проблему изоморфизма, но и проблему P vs NP.

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

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

Сделали-сделали. Я говорю Вам: Ваш алгоритм (имеется ввиду обсуждаемый из препринта) эквивалентен сибирскому, а потому не применим ко всем графам.
Вы отвечаете: Мой алгоритм (имея ввиду алгоритм с возвратом) применим ко всем графам, а потому не эквивалентен сибирскому.

И как это назвать если не подменой?

(Оффтоп)

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

Т.е. предложенная Вами методология обсуждения ведет к молчанию: "никто ничего не говорит и никого не слышит (а что слушать, если все молчат?)".

Опять Вы о какой-то методологии, якобы предложенной мной. Это что - ещё одна подмена? О каком "заговоре молчания" Вы говорите? Ведь Вы сами не отвечаете по существу предъявленных возражения.

[bin]

Отвечаю по существу: Вы написали:

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

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

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)$

В алгоритмах препринта (их 4 - по количеству версий препринтов) и в алгоритме с возвратом я оперирую теми же матрицами (в некоторых версиях, я оперировал и W-матрицами, но не буду придираться), по-Вашему $\mathrm{D_0}+(-)\mathrm{M}$ означает эквивалентность. Отсюда следует вывод, что по-Вашему, мои 4 неэквиалентных алгоритма препринта+изначальный с возвратом эквивалентны друг другу и сибирским. Из Вашего утверждения следует абсурдный вывод, и Вы сами это признаете:

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

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

При том, что не понятно о каком из 4х алгоритмов препринтов Вы говорите.

-- Пт июл 20, 2012 23:03:57 --

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

А Вы умеете делать полный перебор за полиномиальное время?

Нет, не умею, но откуда Вы знаете, что этот алгоритм делает полный перебор? Из того, что он с возвратом, не следует, что он когда-либо делает полный перебор

[bin]

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

О каком "заговоре молчания" Вы говорите?

Об этом:

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

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

[bin]

Алгоритм полностью пересмотрен, новый препринт (версия 5) можно сгрузить с http://arxiv.org/abs/1004.1808. По многочисленным просьбам сделал русский перевод, который вскоре будет доступен.

[bin]

Файл с переводом

[rtfai]

С интересом читаю дискуссию.

Зачем заливать сюда формулы?

Напишите нормальную статью и отправьте в Труды ИММ, там есть А.А. Махнев
http://www.mathnet.ru/php/person.phtml? ... sonid=8456
он занимается подобными проблемами.

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

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

http://www.mathnet.ru/php/archive.phtml ... n_lang=rus

[bin]

rtfai,

rtfai в сообщении #731949 писал(а):

С интересом читаю дискуссию.

Спасибо за интерес.

rtfai в сообщении #731949 писал(а):

Зачем заливать сюда формулы?

Спасибо за Ваш вопрос, но я его не понял Что значит "заливать формулы"?

rtfai в сообщении #731949 писал(а):

Напишите нормальную статью и отправьте в Труды ИММ, там есть А.А. Махнев

Пока что я написал препринт, т.е. черновик для обсуждения, а вот когда смогу написать "нормальную статью", то, при всем уважении к Трудам ИММ, отправлю в несколько более известный международный журнал, например, J of Graph Theory. (М.б. я пристрастен, но у меня интересная переписка с редакцией этого журнала ).

rtfai в сообщении #731949 писал(а):

там есть А.А. Махнев
http://www.mathnet.ru/php/person.phtml? ... sonid=8456 он занимается подобными проблемами.

По списку публикаций в приведенной ссылке можно видеть, что А. А. Махнев занимается более частными проблемами, нпр., "Графы, в которых окрестности вершин изоморфны графу Матье", но если его интересует общая проблема и покажется интересным мой препринт - он (как и все) может высказать свое мнение здесь, на форуме. Сможете проинформировать его и дать ссылку?

rtfai в сообщении #731949 писал(а):

http://www.mathnet.ru/php/archive.phtml ... n_lang=rus

про это уже здесь говорилось ранее. А по сути препринта у Вас есть что сказать?