TY - JOUR

T1 - О проблеме изоморфизма графов и об одном матричном алгоритме ее решения

AU - Погожев, С.В.

AU - Хитров, Г.М.

PY - 2008

Y1 - 2008

N2 - В статье решается задача об изоморфизме двух графов, заданных своими матрицами смежности А и В. Исходная задача сведена к задаче о перестановочном подобии двух квадратных (0,1)-матриц одинаковой размерности, т. е. к задаче отыскания такой матрицы перестановки Р, при которой В = РАР'. Очевидное решение последней задачи сводится к полному перебору матриц перестановок, которое для размеров исходных матриц в пределах 25 пока не может быть реализовано. Сокращение полного перебора, равно как и отсечение большинства случаев неподобных матриц, основывается на понятии матричных инвариантов. Если построенные одинаковым образом матричные инварианты исходных матриц различны по составу, то исходные матрицы не подобны перестановочно. Если же матричные инварианты совпадают по составу, то рассматривается так называемое разнообразие этого инварианта. Использование разнообразия инварианта позволяет перебирать не всю группу матриц перестановок заданной размерности, а лишь подгруппу матриц перестановок, имеющих блочно-диагональн

AB - В статье решается задача об изоморфизме двух графов, заданных своими матрицами смежности А и В. Исходная задача сведена к задаче о перестановочном подобии двух квадратных (0,1)-матриц одинаковой размерности, т. е. к задаче отыскания такой матрицы перестановки Р, при которой В = РАР'. Очевидное решение последней задачи сводится к полному перебору матриц перестановок, которое для размеров исходных матриц в пределах 25 пока не может быть реализовано. Сокращение полного перебора, равно как и отсечение большинства случаев неподобных матриц, основывается на понятии матричных инвариантов. Если построенные одинаковым образом матричные инварианты исходных матриц различны по составу, то исходные матрицы не подобны перестановочно. Если же матричные инварианты совпадают по составу, то рассматривается так называемое разнообразие этого инварианта. Использование разнообразия инварианта позволяет перебирать не всю группу матриц перестановок заданной размерности, а лишь подгруппу матриц перестановок, имеющих блочно-диагональн

M3 - статья

SP - 80

EP - 84

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1811-9905

IS - 4

ER -