ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2021; 4: 17-23
http://dx.doi.org/10.17213/1560-3644-2021-4-17-23
АНАЛИЗ ИНВАРИАНТОВ, ИСПОЛЬЗУЕМЫХ ДЛЯ ТЕСТИРОВАНИЯ ИЗОМОРФИЗМА ГРАФОВ И ПРИНЦИПЫ ИХ СИСТЕМАТИЗАЦИИ
Иванченко Александр Николаевич – канд. техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники», Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова, г. Новочеркасск, Россия. ian2008.52@mail.ru
Иванченко Кирилл Николаевич – аспирант, Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова, г. Новочеркасск, Россия. kni2012.15@gmail.com
Аннотация
Изложены принципы классификации инвариантов графа и построена система их классификации, допускающая расширение и пополнение как новыми инвариантами, так и новыми классификационными группами. Детально рассмотрены 29 инвариантов, большинство из которых являются оригинальными. Использование рёберных графов автоматически расширило число анализируемых инвариантов графов в два раза. Применение формализма мультимножеств для векторных инвариантов позволило в унифицированной и легко алгоритмизируемой форме представить «громоздкие» инварианты и выполнять с ними различные операции (сравнение, сортировка и пр.), а использование мультимножеств, элементами которых являются мультимножества, позволило компактно представить сложные «матричные» инварианты, характеризующие расстояние между парами вершин графа. В качестве такого расстояния предложено использовать как общепринятую геодезическую метрику (расстояние выражается количеством рёбер), так и предложенную ранее авторами резистивную метрику (расстоянием считается эквивалентное сопротивление электрической цепи, представленной графом). Приведённые в статье числовые примеры демонстрируют способности инвариантов различать неизоморфные графы.
Ключевые слова: проблема изоморфизма графов, инварианты графа, резистивное расстояние, мультимножество, способность инвариантов различать неизоморфные графы
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Зыков А.А. Основы теории графов. М.: Наука, 1986. 384 с.
- Graph_property. Available at: <https://en.wikipedia.org/wiki/ Graph_property> (accessed 15.10.2021).
- Мельников Б.Ф., Сайфуллина Е.Ф. Генерация графов с заданным вектором степеней второго порядка и задача проверки изоморфизма // Стохастическая оптимизация в информатике. 2014. Т. 10, № 2. С. 24 – 36.
- Мельникова Е.А., Сайфуллина Е.Ф. Подход к проверке изоморфизма графов с помощью построения инвариантов // Вектор науки Тольяттинского государственного университета. 2013. № 1 (23). С. 113 – 120. URL:<https: //www.elibrary.ru/item.asp?id=20394979> (дата обращения 15.10.2021).
- Максимов А.Г., Завалишин А.Д., Абрамов М.В., Тулупьев А.Л. Хемоинформатика: приложения информатики в анализе химических структур (на примере сульфида кадмия) // Компьютерные инструменты в образовании. 2019. № 4. С. 44 – 54.
- Добрынин А.А., Мельников Л.С. Индекс Винера для графов и их реберных графов // Дискретный анализ и исследование операций. 2004. Серия 2. Т. 11, вып. 2. С. 25–44.
- Петровский А.Б. Пространства множеств и мультимножеств. М.: Едиториал УРСС, 2003. 248 с.
- Resistance Distance. Available at: <https://mathworld. wolfram.com/ ResistanceDistance.html> (accessed 15.10.2021).
- Klein D.J., Randić M. Resistance distance // Journal of Mathematical Chemistry, 12(1993) P. 81 – 95. Available at: <https://www.researchgate.net/publication/226420782_Resistance_Distance> (accessed 15.10.2021).
- Иванченко А.Н, Иванченко К.Н. Критерий изоморфизма графов на основе резистивного расстояния // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2020. № 2. С. 13 –18. doi: 10.17213/1560-3644-2020-2-13-18
- Watts D., Strogatz S. Collective dynamics of ‘small world’ networks. Nature. 1998. Vol. 393. P. 440 – 442.
- McKay B.D., Piperno A. Nauty and Traces. Software dis-tribution web page. Available at: <http://users.cecs. anu.edu.au/~bdm/nauty/> (accessed 15.10.2021).
- McKay B.D. Practical Graph Isomorphism // Congressus Numerantium, 30 (1981). Р. 45 – 87. Available at: <http:// users.cecs.anu.edu.au/~bdm/nauty/pgi.pdf> (accessed 15.10.2021).
- McKay B. D., Piperno A. Practical Graph Isomorphism, II // J. Symbolic Computation (2013) Vol. 60, p. 94 – 112. Available at: <https://arxiv.org/pdf/1301.1493.pdf> (accessed 15.10.2021).