Исследование изоморфизма графов с помощью жордановых форм матриц смежности | Прикладная дискретная математика. 2018. № 40. DOI: 10.17223/20710410/40/7

Для установления отсутствия изоморфизма между орграфами предлагается использовать жорданову форму матриц смежности графов. Задача приведения матрицы к жордановой форме имеет полиномиальную временную сложность, верхняя оценка необходимого числа операций для n-вершинного графа составляет О (та4). Показано, что жорданова форма матриц смежности орграфов содержит больше информации о структуре графа, чем его спектр, определяемый собственными значениями матрицы смежности и их кратностью. В результате исследования жор-дановых форм матриц смежности орграфов на отдельных примерах установлено, что изоспектральные матрицы, имеющие одинаковый набор собственных значений, могут приводиться к различным жордановым формам. Это означает, что матрицы смежности не являются подобными, т. е. не являются и перестановочно подобными, что свидетельствует об отсутствии изоморфизма между графами.
  • Title Исследование изоморфизма графов с помощью жордановых форм матриц смежности
  • Headline Исследование изоморфизма графов с помощью жордановых форм матриц смежности
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 40
  • Date:
  • DOI 10.17223/20710410/40/7
Ключевые слова
Jordan form of matrix, similarity matrices, adjacency matrix, graph isomorphism, directed graph, graph, жорданова форма, подобие матриц, матрица смежности, изоморфизм графов, орграф, граф
Авторы
Ссылки
Deri J. A. and Mourn J. M. F. Spectral projector-based graph Fourier transforms // IEEE J. Selected Topics in Signal Processing. 2017. V. 11. No. 6. P. 785-795.
Пролубников А. В. Прямой алгоритм проверки изоморфизма графов // Компьютерная оптика. 2007. Т. 31. №3. С. 86-92.
Deri J. A. and Mourn J. M. F. Graph Equivalence Classes for Spectral Projector-Based Graph Fourier "Transforms. arXiv: 1701.02864 vl [cs.SI] 11 Jan 2017.
Беклемишев Д. В. Дополнительные главы линейной алгебры. М.: Наука, 1983. 336 с.
Володичева М. П., Григорьев-Голубев В. В., Jleopa С. Н. Собственные векторы, жордановы формы, функции матриц. MatLab, Mathematica, Maple. СПб.: Изд. центр СПбГМТУ, 2009. 175 с.
Nina H., Soto R.L., and Cardoso D. M. The Jordan canonical form for a class of weighted directed graphs // Linear Algebra and its Appl. 2013. V.438. No. 1. P. 261-268.
Уилкинсон Дэю. Ч. Алгебраическая проблема собственных значений. М.: Наука, 1970. 564 с.
Cardon D. A. and Tuckfield В. The Jordan canonical form for a class of zero-one matrices // Linear Algebra and its Appl. 2011. V.435. No. 11. P. 2942-2954.
Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. СПб.: Лань, 2009. 736 с.
Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. 655с.
Lopez-Presa J. L. and Fernandez A. A. Fast algorithm for graph isomorphism testing // Proc. 8th Intern. Symp. Experimental Algorithms. 2009. P. 221-232.
Darga P. Т., Sakallah K. A., and Markov I. L. Faster symmetry discovery using sparsity of symmetries // Proc. 45th Design Automation Conf. 2004. P. 149-154.
Junttila T. and Kaski P. Engineering an efficient canonical labeling tool for large and sparse graphs // Proc. 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics. SIAM, 2007. P. 135-149.
McKay B. D. and Piperno A. Practical graph isomorphism, II // J. Symbolic Computation. 2014. V.60. P. 94-112.
McKay В. D. Practical graph isomorphism // Congressus Numerantium. 1981. V. 30. P. 45-87.
Погребной В. К., Погребной А. В. Полиномиальный алгоритм вычисления полного инварианта графа на основе интегрального описателя структуры // Известия Томского политехнического университета. 2013. Т. 323. №5. С. 152-159.
Погребной А. В. Метод определения сходства структур графов на основе выделения частичного изоморфизма в задачах геоинформатики // Известия Томского политехнического университета. 2015. Т. 326. №11. С. 56-66.
Погребной А. В. Полный инвариант графа и алгоритм его вычисления // Известия Томского политехнического университета. 2014. Т. 325. №5. С. 110-122.
Погожее С. В., Хитрое Г. М. О проблеме изоморфизма графов и об одном матричном алгоритме ее решения // Вестн. С.-Петерб. ун-та. 2008. Сер. 10. № 1. С. 1-5.
Хитрое Г. М. О разнообразии графа и применении этого понятия к проблеме изоморфизма графов // Вестн. С.-Петерб. ун-та. 2006. Сер. 10. №2. С. 91-100.
Babai L. Graph isomorphism in quasipolynomial time. arXiv:1512.03547 (vl:ll Dec 2015, v2:19 January 2016). http: //people. cs.uchicago. edu/~laci/update.html
Зыков А. А. Основы теории графов. M.: Вузовская книга, 2004. 664 с.
Teke O. and Vaidyanathan P. P. Uncertainty principles and sparse eigenvectors of graphs // IEEE Trans. Signal Process. 2017. V.65. No. 20. P. 5406-5420.
Sandryhaila A. and Mourn J. M. F. Discrete signal processing on graphs: frequency analysis // IEEE Trans. Signal Process. 2014. V.62. No. 12. P. 3042-3054.
Newman М. Е. J. Networks: an Introduction. Oxford: Oxford University Press, 2010. 784 p.
Sandryhaila A. and Mourn J. M. F. Discrete signal processing on graphs // IEEE Trans. Signal Process. 2013. V.61. No. 7. P. 1644-1656.
Марлей В. Е., Плотников С. П. Алгоритм распознавания изоморфного вложения алгоритмических сетей // Вестник ВГУ ИТ. 2014. №3. С. 72-75.
Ильяшенко М. Б., Голдобин А. А. Решение задачи поиска изоморфизма графов для проектирования специализированных вычислителей // Радиоэлектроника, информатика, управление. 2012. №1. С. 31-36.
Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. 1104 с.
Цветкович Д., Дуб М., Захс X. Спектры графов. Теория и применение. Киев: Наукова думка, 1984. 378 с.
 Исследование изоморфизма графов с помощью жордановых форм матриц смежности | Прикладная дискретная математика. 2018. № 40. DOI: 10.17223/20710410/40/7
Исследование изоморфизма графов с помощью жордановых форм матриц смежности | Прикладная дискретная математика. 2018. № 40. DOI: 10.17223/20710410/40/7