Название: К вопросу распознавания изоморфизма двудольных графов
Авторы: Марченко, Л.Н.
Подгорная, В.В.
Ключевые слова: двудольный граф
изоморфизм графов
булевы методы в теории графов
bipartite graph
graph isomorphism
adjacency matrix
Boolean methods in graph theory
Дата публикации: 2019
Издательство: Гомельский государственный университет имени Ф.Скорины
Библиографическое описание: Марченко, Л.Н. К вопросу распознавания изоморфизма двудольных графов / Л.Н. Марченко, В.В. Подгорная // Известия Гомельского государственного университета имени Ф. Скорины. Сер.: Естественные науки. - 2019. - № 3 (114). - С. 163-169.
Краткий осмотр (реферат): Работа посвящена новым инвариантам простых изоморфных графов. Приводится инвариант графа, основанный на преобразовании его матрицы смежности к «блочно-нулевому» виду. Предложен метод распознавания и установления изоморфизма двудольных графов. Данный метод включает в себя нахождение неплотности двудольных графов с помощью булевых функций методом Магу, преобразование матриц смежности графов к «блочно-нулевому» виду с учетом неплотности и выделенных долей графа, применение «оптимальной сортировки» ненулевых блоков матриц. Такая процедура позволяет установить взаимно однозначное соответствие между множествами вершин изоморфных двудольных графов, сохраняющее соответствующую смежность. Демонстрируется работа алгоритма на примере. 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.
URI (Унифицированный идентификатор ресурса): http://elib.gsu.by/handle/123456789/7299
ISSN: 1609-9672
Располагается в коллекциях:Известия ГГУ им. Франциска Скорины. Естественные науки

Файлы этого ресурса:
Файл Описание РазмерФормат 
30 Марченко,Подгорная (163-169).pdf360.04 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.