НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o123.pdf (1640.68Кб)

УДК 004.02 + 519.1

1 МГТУ им. Н.Э. Баумана, Москва, Россия

Объектами исследования являются неориентированные графы. Рассматривается задача установления их изоморфизма. Анализ литературы, посвященной решению этой задачи, показал, что не существует способа определения полного инварианта графа в виде уникальной структурной характеристики каждой его вершины, вычислительная сложность определения которой лучше, чем О(n⁴).
Цель работы – получение характеристики структуры графов, которая могла бы быть использована для решения задачи установления их изоморфизма за время лучше, чем О(n⁴). В качестве такой характеристики предложено использовать множество кодов корней деревьев всех кратчайших, в смысле числа ребер, цепей из каждой вершины в ос-тальные, однозначно определяющих структуру каждого дерева. Доказана теорема о возможности сведения задачи установления изоморфизма неориентированных графов к задаче определения изоморфизма их расщепления на деревья всех кратчайших, в смысле числа ребер, цепей из каждой вершины в остальные. Разработан алгоритм построения деревьев кратчайших цепей от каждой вершины графа до всех остальных и вычисления кодов их вершин. В качестве последних использованы коды Ахо, применяемые при распознавании изоморфизма деревьев. Выполнена теоретическая оценка вычислительной сложности по-лучения структурных характеристик вершин графа, которая составила О(n³).
Экспериментальные исследования проводились в виде натурного эксперимента с помощью разработанного комплекса программ генерации исходных данных – аналитиче-ского представления графа с количеством вершин равным 1200 и программы получения кодов корней деревьев. Для получения оценки «в худшем» временной сложности алго-ритма разложения графов на деревья кратчайших цепей и определения кодов их корней проведено экспериментальное исследование зависимости количества вершин дерева от плотности графа. Для худшего случая получена зависимость количества вершин дерева от числа вершин графа, аппоксимируемая квадратичной функцией, что согласуется с теоре-тическими оценками. Результаты экспериментальных исследований в целом подтвержда-ют полученные теоретические оценки.

1. Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с.
2. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 с.
3. Овчинников В.А. Вычислительная сложность алгоритмических моделей задач идентификации и покрытия схем ЭВМ // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 1992. № 2. С. 31-42.
4. Ullmann J.R. An Algorithm for Subgraph Isomorphism // Journal of the Association for Computing Machinery (JACM). 1976. Vol. 23, no. 1. P. 31-42. DOI: 10.1145/321921.321925
5. Cordella L.P., Foggia P., Sansone C., Vento M. A (sub)graph isomorphism algorithm for matching large graphs // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004. Vol. 26, no. 10. P. 1367-1372. DOI: 10.1109/TPAMI.2004.75
6. Cordella L.P., Foggia P., Sansone C., Vento M. An Improved Algorithm for Matching Large Graphs // Proc. of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, 2001. P. 149-159.
7. Dehmer M., Grabner M., Mowshowitz A., Emmert-Streib F. An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants // Advances in Computational Mathematics. 2013. Vol. 39, no. 2. P. 311-325. DOI: 10.1007/s10444-012-9281-0
8. McKay B.D., Piperno A. Practical graph isomorphism, II // Journal of Symbolic Computation. 2014. Vol. 60. P. 94-112. DOI: 10.1016/j.jsc.2013.09.003
9. Попов А.Ю. Реализация алгоритмов обхода графов в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 10. С. 453-472. DOI: 10.7463/1015.0820736
10. Luks E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time // Proc. of the 21st IEEE FOCS Symp. 1980. P. 42-49.
11. Hoffmann C.M. Group-Theoretic Algorithms and Graph Isomorphism // Lecture Notes in Computer Science. 1982. Chap. V. P. 127-138.
12. Babai L., Grigoryev D.Yu., Mount D.M. Isomorphism of graphs with bounded eigenvalue multiplicity // Proceedings of the 14^th annual ACM symposium on Theory of computing (STOC '82). 1982. P. 310-324. DOI: 10.1145/800070.802206
13. Faizullin R.T., Prolubnikov A.V. An Algorithm of the Spectral Splitting for the Double Permutation Cipher // Pattern Recognition and Image Analysis. 2002. Vol. 12, no. 4. P. 365-375. Режим доступа: http://www.omgtu.ru/general_information/faculties/radio_engineering_department/department_of_quot_integrated_protection_of_information_quot/files/theses/publications/ProlubnikovFaizullinPattern.pdf (дата обращения 01.03.2016).
14. Пролубников А.В. Прямой алгоритм проверки изоморфизма графов // Компьютерная оптика. 2007. Т. 31, № 3. С. 86-92.
15. Погребной В.К. Алгоритм решения задачи определения изоморфизма гиперграфов // Известия Томского политехнического университета. 2010. Т. 317, № 5. С. 16-21. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2010/v317/i5/03.pdf (дата обращения 01.03.2016).
16. Погребной В.К. Метод интеграции структурных различий в графовых моделях и его применение для описания структур // Известия Томского политехнического университета. 2011. Т. 318, № 5. С. 10-16. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2011/v318/i5/02.pdf (дата обращения 01.03.2016).
17. Погребной В.К. Решение задачи определения изоморфизма графов, представленных атрибутными матрицами // Известия Томского политехнического университета. 2012. Т. 321, № 5. С. 52-56. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2012/v321/i5/11.pdf (дата обращения 01.03.2016).
18. Погребной В.К., Погребной А.В. Полиномиальный алгоритм вычисления полного инварианта графа на основе интегрального описателя структуры // Известия Томского политехнического университета. 2013. Т. 323, № 5. С. 152-159. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2013/v323/i5/25.pdf (дата обращения 01.03.2016).
19. Погребной А.В. Полный инвариант графа и алгоритм его вычисления // Известия Томского политехнического университета. Информационные технологии. 2014. Т. 325, № 5. С. 110-122. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2014/v325/i5/14.pdf (дата обращения 01.03.2016).
20. Погребной В.К., Погребной А.В. Исследование полиномиальности метода вычисления интегрального описателя структуры графа // Известия Томского политехнического университета. 2013. Т. 323, № 5. С. 146-151. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2013/v323/i5/24.pdf (дата обращения 01.03.2016).
21. Babai L. Graph Isomorphism in Quasipolynomial Time //ArXiv.org: website. Режим доступа: http://arxiv.org/abs/1512.03547 (дата обращения 15.02.2016).
22. Ахо А.B., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 536 с.
23. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с.