It is proposed to use a Jordan form of adjacency matrices to establish the absence of isomorphism between direct graphs. The problem of reduction of a matrix to a Jordan form has polynomial time complexity. The upper estimate of the required number of operations for n-vertex graph is 0(n4). It is shown that the Jordan form of the adjacency matrix contains more information about the structure of the graph than its spectrum determinated by the eigenvalues of the adjacency matrix and their multiplicity. As a result of research on specific examples it was found that the isospec-tral matrices of the same set of eigenvalues may have different Jordan forms. This means that the adjacency matrices are not similar and therefore are not permutation similar, indicating a lack of isomorphism between direct graphs.
Download file
Counter downloads: 307
- Title Study of graph isomorphism using Jordan forms of adjacency matrices
- Headline Study of graph isomorphism using Jordan forms of adjacency matrices
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 40
- Date:
- DOI 10.17223/20710410/40/7
Keywords
Jordan form of matrix, similarity matrices, adjacency matrix, graph isomorphism, directed graph, graph, жорданова форма, подобие матриц, матрица смежности, изоморфизм графов, орграф, графAuthors
References
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 с.
Study of graph isomorphism using Jordan forms of adjacency matrices | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 40. DOI: 10.17223/20710410/40/7
Download full-text version
Counter downloads: 793