Нормальная форма (0,1)-матрицы и алгоритмы ее построения
В статье обсуждаются уже имеющиеся предпосылки для введения понятия нормальной формы квадратной (0,1)-матрицы, специфика самой (0,1)-матрицы и ее связь с теорией графов; доказываются новые теоретические результаты, которые легли в основу введения нормальной формы. Для разных классов матриц и различных видов преобразований давно существуют понятия канонической формы матрицы. Наиболее известными являются канонический вид разложимой и импримитивной матриц, которые, по сути, даются через определение преобразования перестановочного подобия (Р-подобия, т. е. преобразования, связанного с перестановкой строк и такой же перестановкой столбцов в квадратных матрицах). Поскольку Р-подобие есть частный случай подобия, то нормальную форму разложимой матрицы ранее пытались строить, базируясь на понятиях линейной алгебры. Однако, учитывая специфику (0,1)-матриц и их связь с теорией графов, оказалось удобнее строить нормальную форму квадратной (0,1)-матрицы, отталкиваясь от понятий теории графов. На квадратные (0,1)-матрицы переносятся понятия транзитивного замыкания, несвязности, слабой связности, односторонней связности и сильной связности из теории графов. По аналогии с транзитивным замыканием в теории графов вводится понятие транзитивного замыкания матрицы, т. е. матрицы, которая сопоставляется исходной (0,1)-матрице и является транзитивной. В статье вводится понятие нормальной формы транзитивной (0,1)-матрицы и с ее помощью вводится нормальная форма квадратной (0,1)-матрицы. Отмечено, что все полученные результаты относительно нормальной формы квадратных (0,1)-матриц могут быть отнесены к нормальным формам графа. Приведен алгоритм построения нормальной формы (0,1)-матрицы. При построении нормальной формы матрицы графа попутно решается классическая задача теории графов - выделение компонент связности графа. Библиогр. 8 назв.