Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

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

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

Доказывается возможность эффективной реализации предложенных алгоритмических схем при работе с машинными числами с ограниченной мантиссой. Приводятся результаты вычислительного эксперимента, включая орбиты всех сильно-регулярных графов из библиотеки по адресу http://www.maths.gla.ac.uk/~es, что характеризует вычислительную эффективность предложенного подхода.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:52:52)