К вопросу распознавания изоморфизма двудольных графов

Abstract

Работа посвящена новым инвариантам простых изоморфных графов. Приводится инвариант графа, основанный на преобразовании его матрицы смежности к «блочно-нулевому» виду. Предложен метод распознавания и установления изоморфизма двудольных графов. Данный метод включает в себя нахождение неплотности двудольных графов с помощью булевых функций методом Магу, преобразование матриц смежности графов к «блочно-нулевому» виду с учетом неплотности и выделенных долей графа, применение «оптимальной сортировки» ненулевых блоков матриц. Такая процедура позволяет установить взаимно однозначное соответствие между множествами вершин изоморфных двудольных графов, сохраняющее соответствующую смежность. Демонстрируется работа алгоритма на примере. The paper is devoted to new invariants of simple isomorphic graphs. An invariant of the graph is given, based on the transformation of its adjacency matrix to a «block-null» form. The method of recognition and establishment of isomorphism of bipartite graphs is proposed. This method involves finding openings in bipartite graphs via Boolean functions by the Мaghоut method, the transformation matrices adjacency graph to «block-null» form taking into account the density and allocated graph parts, applying the «optimal» sorting the nonzero blocks of the matrices. This procedure allows us to establish a one-to-one correspondence between sets of vertices of isomorphic bipartite graphs preserving the corresponding adjacency. The work of the algorithm is demonstrated by an example.