Почему проблема изоморфизма графов считается не решенной?

[sqribner48]

Естественный вопрос: Почему в настоящее время проблема изоморфизма графов считается до конца нерешенной?
Ведь еще Зыков А.А. в своей книге: Теория конечных графов. Издательство «Наука» • Сибирское отделение, Новосибирск . 1969 на стр. 35
написал:

Цитата:

В свете исследований С. В. Яблонского (1959) и Ю. И. Журавлева (1/1964, 2/1965) по теории конечных алгорифмов, для класса всех графов и для целого ряда его наиболее интересных подклассов не может существовать такого алгорифма решения проблем изоморфизма и изоморфного вхождения, который был бы существенно проще полного перебора всех мыслимых случаев (например, перебора всех матриц, сильно подобных данной квадратной матрице);

Литература:

1. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных
схем. Сб. «Проблемы кибернетики», 2, М., Физматгиз, 1959, 75—121. РЖМат, 1961, 5А209.
2. Журавлев Ю. И. Оценка сложности локальных алгоритмов для
некоторых экстремальных задач на конечных множествах.
Докл. АН СССР, 158 (1964), № 5, 1018—1021. РЖМат, 1965, 2А123.
2. Журавлев Ю. И. Локальные алгоритмы решения дискретных экстремальных задач. Автореф. докт. дисс. Новосибирск, 1965, 14 стр.

В литературе и в интернете я не нашел никакой реакции на высказывание Зыкова А.А. и на статьи Журавлева Ю.И. и Яблонского С.В.
В связи с этим всплывают дополнительные вопросы:
1. Может быть эти статьи Журавлева Ю.И. и Яблонского С.В. "за рубежом" никто не читал?
2. Может уважаемый Зыков А.А. немного ошибся в своем вышеуказанном выводе?
Или...
Хочется узнать мнение профессионалов-математиков нашего форума по этому вопросу.

[Xaositect]

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

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

[sqribner48]

Xaositect.
Спасибо. То есть Вы хотите сказать, что Зыков А.А. мог ошибаться?

[sqribner48]

... вот сейчас нашел одну ссылку на мнение Зыкова А.А.
В статье Погожев С.В., Хитров Г. М. О проблеме изоморфизма графов и об одном матричном алгоритме ее решения. Вестник СПбГТУ, Сер. 10, 2008,вып. 4, стр. 83-89. Авторы пишут:

Цитата:

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

Видно, что авторы прямо скопировали текст из книги Зыкова А.А., даже не указав ссылку на эту книгу.
P.S. К сожалению, номер 62 в списке литературы к статье отсутствует, поэтому невозможно узнать, какую статью С.В. Яблонского имели в виду авторы.

[bin]

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

... вот сейчас нашел одну ссылку на мнение Зыкова А.А.
В статье Погожев С.В., Хитров Г. М. О проблеме изоморфизма графов и об одном матричном алгоритме ее решения. Вестник СПбГТУ, Сер. 10, 2008,вып. 4, стр. 83-89. Авторы пишут:

Цитата:

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

Видно, что авторы прямо скопировали текст из книги Зыкова А.А., даже не указав ссылку на эту книгу.
P.S. К сожалению, номер 62 в списке литературы к статье отсутствует, поэтому невозможно узнать, какую статью С.В. Яблонского имели в виду авторы.

Нет, это пишут не авторы (Погожев и Хитров), а Горьковой В. Ф., большая цитата из книги которого и приведена в упомянутой статье. Более того, в первых строках Погожев и Хитров отмечают:

Цитата:

Данная статья является дальнейшим развитием работы [1]. [...]
1. Хитров Г. М. О разнообразии графа и применении этого понятия к проблеме изоморфизма графов // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2006. Вып. 2. С. 91_100.

Если посмотреть [1], то эта статья оканчивается недвусмысленным выводом:

Цитата:

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

Далее, возвращаясь к началу:

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

Ведь еще Зыков А.А. в своей книге: Теория конечных графов. Издательство «Наука» • Сибирское отделение, Новосибирск . 1969 на стр. 35
написал:

Цитата:

В свете исследований С. В. Яблонского (1959) и Ю. И. Журавлева (1/1964, 2/1965) по теории конечных алгорифмов, для класса всех графов и для целого ряда его наиболее интересных подклассов не может существовать такого алгорифма решения проблем изоморфизма и изоморфного вхождения, который был бы существенно проще полного перебора всех мыслимых случаев (например, перебора всех матриц, сильно подобных данной квадратной матрице);

В последующих книгах Зыкова, Основы теории графов, M, 2004 г. и 1987 г. я этой цитаты найти не смог (искать не просто, т.к. общего списка литературы там нет). М.б., автор поменял мнение, а может и в 1969 его не разделял. Нужно смотреть контекст. На с.58 (2004 г.) Зыков отмечает, что хотя конструкция Визинга сама по себе не решает проблему изоморфизма, однако

Цитата:

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

Эти слова Зыкова перекликаются с лекциями И.Н. Пономаренко по проблеме изоморфизма графов, где на с.18 читаем:

Цитата:

Теорема 2.2 Для почти всех графов с $n$ вершинами проблема изоморфизма разрешима за время $O(n^2)$.

Возвращаясь к Зыкову, стоит обратить внимание и на его замечание (с.9, 2004) о

Цитата:

модной сейчас теории полиномиальной разрешимости и сводимости переборных задач

Можно вспомнить, что по проблеме $P=NP$ даже голосования проводились. Однако высказанные мнения не являются доказательством

[sqribner48]

bin. Спасибо.
А нет ли у Вас файла (или бесплатной ссылки) со статьей:
"Хитров Г. М. О разнообразии графа и применении этого понятия к проблеме изоморфизма графов // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2006. Вып. 2. С. 91-100".

Эта статья меня заинтересовала, а на сайте журнала этой статьи нет, есть только содержание. Буду очень благодарен Вам или любому кто поможет.

Мне кажется что, эта статья - попытка открыть новое направление в решении проблемы изоморфизма графов.

[bin]

sqribner48
Да, это интересная статья. Мне ее прислал автор, в варианте, который может незначительно отличаться от публикации, и мне было бы неэтично распространять ее. Но Вы можете набрать в гугле Хитров Г. М. - первой же будет ссылка на его страницу Хитров Геннадий Михайлович, а там email , телефон, адрес. Напишите или позвоните ему, уверен, что он поможет.

[sqribner48]

bin
Спасибо. Попробую связаться с ним. Вообще, в последнее время появляется много статей, в которых делается попытка решения проблемы изоморфизма с "нетрадиционной стороны" (см., например, работы В.К. Погребного и М.Н. Назарова):
1. В.К. Погребной. Метод интеграции структурных различий в графовых моделях и его применение для описания структур. // Известия Томского политехнического университета. 2011. Т. 318. № 5, с. 10-16.
2. В.К. Погребной, Ан.В. Погребной. Исследование полиномиальности метода вычисления интегрального описателя структуры графа. // Известия Томского политехнического университета. 2013. Т. 323. № 5, с. 46-151.
3. В.К. Погребной, Ан.В. Погребной. Полиномиальный алгоритм вычисления полного инварианта графа на основе интегрального описателя структуры .// Известия Томского политехнического университета. 2013. Т. 323. № 5,
с. 52-158.
4. М. Н. Назаров. Альтернативные подходы к описанию классов изоморфных графов, Прикладная дискретная математика, 2014, № 3, с. 86–97.

Сюда же можно отнести более раннюю работу Джона Тевета Тагора (с его семиотическим подходом).
К сожалению, все эти работы довольно сложны и просто так их очень трудно проверить. Особенно сложна работа Погребного и Д.Т. Тевета(из-за отсутствия доступных русскоязычных источников).