Research output: Contribution to journal › Article › peer-review
О проблеме изоморфизма графов и об одном матричном алгоритме ее решения. / Погожев, С.В.; Хитров, Г.М.
In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ, No. 4, 2008, p. 80-84.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 5133409