Какие существуют алгоритмы проверки изоморфности 2х графов?

[незваный гость]

Amigo писал(а):

Полностью согласен с MrD , что для положительного ответа во всех случаях, необходимо перебрать N! способов обозначить вершины. (частные эвристики способны во многтх ситуациях облегчить ответ, однако не способны его полностью исчерпать)

А почему? Ну хоть намек на идею доказательства этого факта?

[Igor Borovikov]

http://www.math.fau.edu/locke/IsoTest.htm

[Ринат]

незванный гость писал(а):

Вопрос -- как проверить изоморфность двух матриц?

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

[Woland]

незваный гость писал(а):

Amigo писал(а):
Полностью согласен с MrD , что для положительного ответа во всех случаях, необходимо перебрать N! способов обозначить вершины. (частные эвристики способны во многтх ситуациях облегчить ответ, однако не способны его полностью исчерпать)

А почему? Ну хоть намек на идею доказательства этого факта

Намёк находится здесь:
А.И Белоусов , С.Б. Ткачёв Дискретная математика.
Издательство МГТУ имени Н.Э. Баумана, подписанно в печать
09.09.2002. страница 366 строка 7(снизу).

Там же находится эта проклятая теорема о лексикографической сортировке.

[незваный гость]

Не откажите в любезности процитировать (а может, найдете возможным одну-две страницы отсканировать и положить, например, на imageshack.net). До книжки добраться трудновато...

[Woland]

Незванный гость писал(а):

Не откажите в любезности процитировать (а может, найдете возможным одну-две страницы отсканировать и положить, например, на imageshack.net). До книжки добраться трудновато...

Уважаемый Незванный гость!
Подумав над Вашей просьбой(и перечетав ещё раз текст) , я прокрутил в своей голове, счётное количество различных, сюжетных линий. И обнаружил удивительную вещь,- среди них тех, которые бы могли с успехом развиваться для меня, в случае публикации данных страниц - Нет. Но а на нет и суда нет. Однако, напомню, речь идёт всего лишь о намёке. А намёк вешь весьма не благодарная. Кто его знает, что автор имеет ввиду. Но пока читаешь текст, действительно возникает впечатление ,что речь идёт именно о n! способов переобозначить вершины. (Как правильно читать, чтоб и у Вас возникло такое впечатление,
я отвечу по личной переписке).

Вот указанные мною строки:
.....
Однако для доказательства изоморфизма графов необходимо явно
указать биекцию множества вершин одного графа на множество
вершин второго, при которой сохраняется отношение смежности.
Поиск такой биекции весьма трудоёмок, так как может потребовать
ПОЛНОГО ПЕРЕБОРА ВСЕХ ВОЗМОЖНЫХ ВАРИАНТОВ.
Для доказательства неизоморфности достаточно показать принципиальную
невозможность установления требуемой биекции. (далее рассказывается о "тонких структурах циклов") .


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

[незваный гость]

О! Большое Вам спасибо. То есть авторы тоже не приводят доказательство.

Ссылка, которую дал Igor Borovikov, более конструктивна в том смысле, что приводит более конкретные известные факты. В частности, известно, что построение некоторых инвариантов графа есть NP полная проблема. Так что изоморфизм скорее всего не проще (но гарантии нет). С другой стороны, NP-полнота не означает сложность $n!$ -- достаточно ведь и экспоненты, не правда ли.

[незваный гость]

maxal писал(а):

Читайте Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография.

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

[esperanto]

Determining if two graphs are isomorphic is thought to be neither an NP-complete problem nor a P-problem, although this has not been proved (Skiena 1990, p. 181). In fact, there is a famous complexity class called graph isomorphism complete which is thought to be entirely disjoint from both NP-complete and from P.

However, a polynomial time algorithm is known when the maximum vertex degree is bounded by a constant (Luks 1980; Skiena 1990, p. 181).

Добавлено спустя 1 минуту 34 секунды:

http://portal.acm.org/citation.cfm?id=1 ... EN=6184618

[flamemaker]

Уважаемые коллеги,

не могли бы вы поделиться впечатлением о следующем тексте:
http://arxiv.org/PS_cache/math/pdf/0502/0502251v4.pdf
(несмотря на надпись на первой странице, в Trans. Amer. Soc статья не публиковалась)
Хотелось бы понять степень новизны актуальности и строгости полученных результатов.

Заранее спасибо.

[maxal]

вот эта же статья по-русски, кстати:
http://www.psy.omsu.omskreg.ru/session/ ... sm_rus.pdf

Если все обстоит так как написано в аннотации, то результаты актуальные. Но без серьезной рецензии что-то большее сказать сложно.

[flamemaker]

maxal в сообщении #192536 писал(а):

Если все обстоит так как написано в аннотации, то результаты актуальные. Но без серьезной рецензии что-то большее сказать сложно.

спасибо, конечно, но у нас имеются сомнения именно в том, что "все обстоит так как написано в аннотации", поэтому вопрос и выложен на обсуждение

[Nik_Svan]

maxal писал(а):

вот эта же статья по-русски, кстати:
http://www.psy.omsu.omskreg.ru/session/ ... sm_rus.pdf

Если все обстоит так как написано в аннотации, то результаты актуальные. Но без серьезной рецензии что-то большее сказать сложно.

Я занимался проверкой изоморфности 2-х графов на примере сравнения оптически активных изомеров. Интересно проверить предлагаемый алгоритм для этой задачи.

[Yuri Gendelman]

flamemaker писал(а):

не могли бы вы поделиться впечатлением о следующем тексте:
http://arxiv.org/PS_cache/math/pdf/0502/0502251v4.pdf
...
в Trans. Amer. Soc статья не публиковалась

Английский язык текста очень плохой. Похоже на автоматический перевод с руccкого оригинала, ссылку на который дал maxal. Такой английский текст в печать не примут независимо от содержания.

[rtfai]

А зачем именно по английски?

http://www.ipsi.smr.ru/research/publica ... 313216.pdf