2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение31.03.2006, 02:23 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение31.03.2006, 08:07 


25/01/06
102
http://www.math.fau.edu/locke/IsoTest.htm

 Профиль  
                  
 
 
Сообщение31.03.2006, 21:35 
Аватара пользователя


14/05/05
224
Баку
незванный гость писал(а):
Вопрос -- как проверить изоморфность двух матриц?

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

 Профиль  
                  
 
 
Сообщение06.07.2006, 20:10 
Аватара пользователя


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

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


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

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

 Профиль  
                  
 
 
Сообщение06.07.2006, 21:43 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение07.07.2006, 09:38 
Аватара пользователя


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

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


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

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


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

 Профиль  
                  
 
 
Сообщение07.07.2006, 09:55 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
О! Большое Вам спасибо. То есть авторы тоже не приводят доказательство.

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

 Профиль  
                  
 
 
Сообщение04.10.2006, 02:34 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
maxal писал(а):

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

 Профиль  
                  
 
 
Сообщение12.10.2006, 09:09 


12/10/06
56
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

 Профиль  
                  
 
 просьба прокомментировать статью (дискретка)
Сообщение06.03.2009, 11:45 


07/01/09
17
Уважаемые коллеги,

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

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

 Профиль  
                  
 
 
Сообщение07.03.2009, 01:34 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение07.03.2009, 11:12 


07/01/09
17
maxal в сообщении #192536 писал(а):
Если все обстоит так как написано в аннотации, то результаты актуальные. Но без серьезной рецензии что-то большее сказать сложно.

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

 Профиль  
                  
 
 
Сообщение07.03.2009, 19:14 
Заблокирован
Аватара пользователя


13/01/09

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

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

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

 Профиль  
                  
 
 Re: просьба прокомментировать статью (дискретка)
Сообщение07.03.2009, 20:40 
Заслуженный участник


15/05/05
3445
USA
flamemaker писал(а):
не могли бы вы поделиться впечатлением о следующем тексте:
http://arxiv.org/PS_cache/math/pdf/0502/0502251v4.pdf
...
в Trans. Amer. Soc статья не публиковалась
Английский язык текста очень плохой. Похоже на автоматический перевод с руccкого оригинала, ссылку на который дал maxal. Такой английский текст в печать не примут независимо от содержания.

 Профиль  
                  
 
 
Сообщение09.03.2009, 14:34 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group