2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Какие существуют алгоритмы проверки изоморфности 2х графов?
Сообщение20.06.2009, 11:57 


20/12/08
8
Если память не подводит, эффективные алгоритмы существуют, помимо графов конечной степени, также и для графов, вкладываемых в поверхность с небольшим числом ручек (bounded genus graphs).

 Профиль  
                  
 
 Re: Какие существуют алгоритмы проверки изоморфности 2х графов?
Сообщение21.06.2009, 01:22 


31/01/09
96
Москва, мехмат МГУ, МИЭТ
Woland в сообщении #25704 писал(а):
Но пока читаешь текст, действительно возникает впечатление ,что речь идёт именно о n! способов переобозначить вершины. (Как правильно читать, чтоб и у Вас возникло такое впечатление,
я отвечу по личной переписке).

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

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


Если они так считают (а я этого не вижу), то они не правы. Потому что известен c 1983 года алгоритм в $2^{O(\sqrt {(n \log n)}\;)}$: The Babai-Luks-Zemlyachenko algorithm for general GI

 Профиль  
                  
 
 Re:
Сообщение30.03.2014, 09:26 


15/09/13
8
незваный гость в сообщении #10548 писал(а):
Теперь мы можем повторить подсчет дуг, но уже считая, в какой или из какого класса эквивалентности они идут. Опять-таки сигнатуры должны совпасть. А количество классов - увеличиться.


Поясните, что имеется в виду.

 Профиль  
                  
 
 Re: Какие существуют алгоритмы проверки изоморфности 2х графов?
Сообщение11.04.2014, 22:14 


25/08/05
645
Україна
Существуют чисто алгебраические методы - для labeled graph находится система полиномиальных инвариантов ( инварианты некоторой погруппы симметрической группы),которые вычисляются для каждого графа. Если все значения инвариантов свопадают то графы изоморфны. Правда явно система таких инвариантов полностью найдена лишь для графа из 5 вершин, их всего 57. Если граф простой то количество инвариантов можно значительно уменьшить,кажется до 4-5.

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

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



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

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


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

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