Научный журнал
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ.
СЕВЕРО-КАВКАЗСКИЙ РЕГИОН.

ТЕХНИЧЕСКИЕ НАУКИ

Главная » Архив » 2020 » Выпуск 2, июнь 2020 » КРИТЕРИЙ ИЗОМОРФИЗМА ГРАФОВ НА ОСНОВЕ РЕЗИСТИВНОГО РАССТОЯНИЯ

ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2020; 2: 13-18

 

http://dx.doi.org/10.17213/1560-3644-2020-2-13-18

 

КРИТЕРИЙ ИЗОМОРФИЗМА ГРАФОВ НА ОСНОВЕ РЕЗИСТИВНОГО РАССТОЯНИЯ

А.Н. Иванченко, К.Н. Иванченко

Иванченко Александр Николаевич – канд. техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники», Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова, г. Новочеркасск, Россия. Е-mail: ian2008.52@mail.ru

Иванченко Кирилл Николаевич – магистрант, кафедра «Программное обеспечение вычислительной техники», Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова, г. Новочеркасск, Россия. Е-mail: kni2012.15@gmail.com

 

 

Аннотация

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

 

Ключевые слова: проблема изоморфизма графов; инварианты графа; спектр графа; эквивалентные преобразования резистивных электрических цепей; резистивное расстояние; матрица Лапласа-Кирхгофа.

 

Полный текст: [in elibrary.ru]

 

Ссылки на литературу

  1. What are the applications of the isomorphic graphs? URL: <https://math.stackexchange.com/questions/120408/what-are-the-applications-of-the-isomorphic-graphs/120482# 120482> (дата обращения 25.02.2020).
  2. Graph_property. URL: <https://en.wikipedia.org/wiki/Graph _property> (дата обращения 25.02.2020).
  3. Ландо С.К. Графы и топология. URL: <https://electives. hse.ru/data/ 2018/04/19/1150479911/GraphTopology18.pdf> (дата обращения 25.02.2020).
  4. Cvetković D.M., Doob M., Sachs H. Spectra of Graphs. 3rd revised and enlarged edition. Heidelberg/Leipzig, Johann Ambrosius Barth Verlag, 1995. 447 p.
  5. Cvetković D. Applications of graph spectra: an introduction to the literature // Zbornik Radova. Matematički institut SANU, Beograd, 2011. Issue: 14(22), P. 9-34. URL: <http://elib.mi.sanu.ac.rs/files/journals/ zr/22/zbr14009.pdf> (дата обращения 25.02.2020).
  6. Resistance Distance. URL: <https://mathworld.wolfram.com/ ResistanceDistance.html> (дата обращения 25.02.2020).
  7. Klein D.J., Randić M. Resistance distance // Journal of Mathematical Chemistry, 12(1993) P. 81-95. URL: <https://www.researchgate.net/ publication/226420782_ Resistance_Distance> (дата обращения 25.02.2020).
  8. Ravindra B. Bapat, Ivan Gutman, Wenjun Xiao A. Simple Method for Computing Resistance Distance. URL: <http://yaroslavvb.com/papers/bapat-simple.pdf> (дата обращения 25.02.2020).
  9. Laplacian Matrix. URL: <https://mathworld.wolfram.com/ LaplacianMatrix.html> (дата обращения 25.02.2020).
  10. Rosen A. A new network theorem // Journal of the Institution of Electrical Engineers. 1924. Vol. 62, Iss. 335, Р. 916 –918. DOI: 10.1049/jiee-1.1924.0120
  11. McKay B.D., Piperno A. Nauty and Traces. Software distribution web page. URL: <http://users.cecs.anu.edu.au /~bdm/nauty/> (дата обращения 25.02.2020).
  12. McKay B.D. Practical Graph Isomorphism // Congressus Numerantium, 30 (1981). Р. 45-87. URL: <http://users.cecs.anu. edu.au/~bdm/nauty/pgi.pdf> (дата обращения 25.02.2020).
  13. McKay B. D., Piperno A. Practical Graph Isomorphism, II // J. Symbolic Computation (2013) Vol. 60, p. 94-112. URL: <https://arxiv.org/pdf/1301.1493.pdf> (дата обращения: 25.02.2020).
Яндекс.Метрика

© НовоЦНИТ ЮРГПУ(НПИ), 2024