Самарин А.И., Терентьева Ю.Ю. 

О применении некоторых инвариантов графов в задачах исследования сетей связи

Резюме: Задача проверки возможного изоморфизма графов имеет широкое практическое применение и является важной проблемой для теоретической информатики вообще и теории алгоритмов в частности. Из многочисленных областей применения алгоритмов решения проблемы определения изоморфности графов отметим задачу синтаксического и структурного распознавания образов, некоторые проблемы математической химии и хемоинформатики (исследование молекулярных структур химических соединений), задачи, связанные с исследованием социальных сетей (например, связывание нескольких аккаунтов одного пользователя в Facebook). Неизвестно, имеется ли она для этой задачи полиномиальный алгоритм — в предположении P≠NP. Известно, например, что NP-полной является связанная задача поиска изоморфного подграфа в заданном графе. Таким образом, актуальными являются проводимые в настоящее время исследования, которые направлены на решение задачи проверки изоморфности как для произвольных графов, так и для графов специального вида (на практике для подобных исследований могут применяться как точные, так и эвристические алгоритмы). В различных алгоритмах работы с графами одним из распространённых инвариантов является вектор степеней. Однако использование только этого инварианта для построения большинства практических алгоритмов на графах, по-видимому, не является достаточным; его возможным обобщением является рассматриваемый авторами более сложный инвариант – вектор степеней второго порядка. При этом рассматриваемые в работе графы с генерируемым вектором степеней второго порядка можно считать моделями для многих реальных сложных задач. Ранее были опубликованы работы, в которых анализировались порядки применения инвариантов, вычисляемых за полиномиальное время, причём такие варианты алгоритмов, для которых нужны малые степени применяемого полинома. При анализе подобных алгоритмов возникают задачи сравнения рассматриваемых инвариантов — сравнения по какой-либо специальным образом подобранной метрике, отражающей «качество» инварианта на рассматриваемом подмножестве множества всех графов. В статье показано, что при применении любой естественной метрики вектор степеней второго порядка лучше широко применяемого индекса Рандича.

Ключевые слова: теория графов, изоморфизм графов

A.I. Samarin, Yu.Yu. Terentyeva

On the application of some graph invariants in communication network research tasks

Summary: The problem of checking the possible isomorphism of graphs has a wide practical application and is an important problem for theoretical computer science in general and the theory of algorithms in particular. Among the numerous areas of application of algorithms for solving the problem of determining graph isomorphism, we note the problem of syntactic and structural pattern recognition, some problems of mathematical chemistry and chemoinformatics (study of molecular structures of chemical compounds), problems related to the study of social networks (for example, linking several accounts of one user on Facebook). It is not known whether it belongs to a polynomial algorithm for this problem — assuming P≠NP. It is known, for example, that NP-complete is the related problem of finding an isomorphic subgraph in a given graph. Thus, the current research is relevant, which is aimed at solving the problem of checking isomorphism for both arbitrary graphs and graphs of a special type (in practice, both exact and heuristic algorithms can be used for such studies). In various algorithms for working with graphs, one of the most common invariants is the vector of degrees. However, the use of this invariant alone for constructing most practical algorithms on graphs is apparently not sufficient; its possible generalization is the more complex invariant considered by the authors — the vector of second–order degrees. At the same time, the graphs considered in this paper with the generated vector of second-order degrees can be considered models for many real complex problems. Previously, works were published in which the orders of application of invariants calculated in polynomial time were analyzed, and such variants of algorithms for which small degrees of the applied polynomial are needed. When analyzing such algorithms, there are problems of comparing the invariants under consideration — comparing by some specially selected metric that reflects the «quality» of the invariant on the subset of the set of all graphs under consideration. The article shows that when using any natural metric, the vector of second-order degrees is better than the widely used Randich index.

Keywords: graph theory, graph isomorphism

DOI: 10.34219/2078-8320-2023-14-4-37-41