Тема моей диссертационной работы — «Нормальная форма квадратных (ОД)-матриц и ее применение». Вначале тема моих исследований формулировалась как «Нормальная форма квадратных неотрицательных разложимых матриц». Предполагалось, что мои исследования будут продолжением исследований, изложенных в книге Гантмахера Ф. Р. «Теория матриц» в соответствующем параграфе [1, стр. 182−184], поскольку моим научным руководителем Хитровым Г. М. в его статье [2] была показана незавершенность исследований темы Гантмахером. Научный руководитель обратил мое внимание на определение квадратной разложимой матрицы, как на особый вид матрицы, получающийся при перестановке строк и такой же перестановке столбцов. Он так же обратил мое внимание еще на несколько моментов. Во-первых, на критерий неразложимости матрицы, который требовал, чтобы сумма единичной и искомой квадратной матрицы в степени на единицу меньшую, чем размерность искомой матрицы, была строго положительной матрицей, а также на вытекающий отсюда критерий разложимости матрицы. Во-вторых, на замечание в книге [3], что при исследовании на разложимость, а также при исследовании на примитивность и импримитивность квадратной неотрицательной матрицы, можно вместо исходной неотрицательной матрицы использовать ее индикаторную матрицу, т. е. матрицу, полученную из неотрицательной матрицы заменой ненулевых элементов единицами, таким образом, мы приходим к (ОД)-матрицам. В-третьих, что любую квадратную (0,1)-матрицу можно интерпретировать как матрицу смежности графа. Третье замечание показывало, что задачу разложимости матрицы можно свести к задаче теории графов. Перечисленные замечания научного руководителя и были отправными точками моего исследования, которое, в конце концов, трансформировалось в тему, взятую в качестве названия диссертации.
Вернемся вновь к определению разложимой матрицы и сделаем несколько простых выводов из этого определения.
Определение 0.0.1 ГЗ, стр. 4311. Матрица А&Мп называется разложимой, если либо a) п=1 и А=0, либо b) п> 2 и существует матрица перестановки Р е Мп и некоторое число г, 1 < г <п-, такие что.
В С^.
Р' АР v0 Dj А. (0.0.1).
Здесь Мп — множество квадратных матриц размерности п, а матрица.
А разбита на блоки вертикальными и горизонтальными полосами одинаковой размерности г и п-г соответственно. Если ввести в рассмотрение вектор-столбец е размерности п, определяемый как е = (1, 1, ., 1/, то произведение матрицы, А на этот столбец даст столбец строчных сумм матрицы А, т. е. столбец, элементами которого являются суммы элементов соответствующих строк матрицы А. С помощью вектора е легко определяется матрица перестановки Р е Мп, как (ОД)-матрица, для которой Ре~е и е' Р = е'. Другими словами, матрица перестановки — это такая квадратная матрица, у которой в каждой строке и каждом столбце один элемент равен единице, а остальные элементы равны нулю. Отсюда следует, что все строки и столбцы матрицы Р ортогональны и нормированы, т. е. Рт =Р~1. Теперь видно, что (0.0.1) является частным случаем подобия матриц, А и, А. Этот случай подобия в работах научного руководителя называется перестановочным подобием или-подобием. Он характеризуется тем, что при данном преобразовании элементы матрицы не изменяются, они могут менять разве лишь свое положение в матрице. Поскольку вид матрицы (0.0.1) показывает важность расположения нулей в матрице, то появляется возможность разделить элементы матрицы на нули и не нули. То есть это позволяет вместо исходной матрицы рассматривать ее индикаторную матрицу. С другой стороны критерий неразложимости матрицы требует вычисления суммы степеней матрицы и проверки полученной матрицы на положительность. Поскольку сумма неотрицательных (положительных) чисел, равно как и произведение неотрицательных (положительных) чисел, есть число неотрицательное (положительное), то это позволяет после перехода от матриц к их индикаторным матрицам при действиях с ними перейти от обычной арифметики к булевой арифметике, где один плюс один равно единице. Переход от обычной арифметики к булевой арифметике сулил большие вычислительные возможности — можно работать с матрицами больших размерностей и не бояться «переполнения», а также не беспокоиться о точности вычислений при возведении их в степень.
Связь (ОД)-матриц, каковыми являются индикаторные матрицы, с графами, давала надежду выявить аналогичную связь между действиями с матрицами и действиями с графами. Действительно, булева сумма булевых степеней (ОД)-матриц позволяет вычислять транзитивное замыкание графа. Понятие транзитивного замыкания графа в свою очередь позволило сформулировать понятие транзитивного замыкания матрицы, матрицы расстояний графа и т. д. Специфика преобразования перестановочного подобия и связь (ОД)-матриц с графами позволила отойти от методов линейной алгебры при решении вопроса о нормальной форме разложимой матрицы и положить в основу решения вопроса матричный аналог типов связности графа.
В отличие от обычного преобразования подобия при перестановочном преобразовании подобия нет однозначности нормальной формы. Вероятно, в будущем эту форму придется связывать с решаемыми задачами. Естественно нормальную форму (ОД)-матриц связывать с задачами теории графов и использовать ее там, где пока не видно подходящего решения задачи. Такой трудной задачей является, например, задача, сформулированная в статье Погожева C.B. и Хитрова Г. М. [4], об изоморфизме графа некоторому подграфу другого графа.
Изложение полученных результатов автора ведется в обратном порядке — от последней сформулированной задачи к методам ее решения, т. е. к нормальной форме матрицы смежности графа.
Перечень публикаций автора связан скорее с трудностями становления, но также отражает и основные результаты диссертации.
Структура диссертационной работы:
В первой главе вводятся основные понятия и доказываются теоретические результаты, которые понадобятся в дальнейшем для того, чтобы дать определение нормальной формы квадратной (ОД)-матрицы и построить алгоритмы ее нахождения.
В первом параграфе приведены основные определения, леммы и теоремы теории матриц с неотрицательными элементами.
Во втором параграфе рассматриваются бинарные отношения, их связь с графами и (ОД)-матрицами, так же отмечено, что в данной работе можно перейти от привычной к булевой арифметике.
В параграфе третьем главы первой даны определения графа на трех языках: геометрическом, теоретико-множественном и матричном. Приводятся некоторые разновидности графов, которые по тем или иным причинам нашли наибольшие теоретические или практические приложениявводятся основные понятия теории графа: достижимость, связность, путь, цепь, подграф, инвариант, изоморфизм графов.
Во второй главе доказываются теоремы и положения, на основе которых в дальнейшем строятся алгоритмы построения нормальной формы квадратной (ОД)-матрицы. Сначала приводятся алгоритмы для частных случаев: алгоритм разложения матрицы на ее компоненты (§ 2.1), алгоритм построения нормальной формы разложимой матрицы (§ 2.2), алгоритм построения нормальных форм неразложимых примитивной (§ 2.3.1) и импримитивной (§ 2.3.2) матриц. В последнем параграфе второй главы приводится общий алгоритм построения нормальной формы для произвольной квадратной матрицы.
В третьей главе приведены примеры использования нормальной формы (ОД)-матрицы. Для поиска мощности группы автоморфизмов, и как следствие, в задаче изоморфизма заданного графа подграфу другого графа (§ 3.1), для исследований обыкновенных (§ 3.2) и ориентированных (§ 3.3) 5-ти вершинных графов, для отыскания наибольшей клики графа (§ 3.4).
Заключение
.
В данной работе, которая начиналась, как продолжение исследований, изложенных в книге Ф. Р. Гантмахера «Теория матриц» в соответствующем параграфе [1, стр. 182−184], обсуждались уже имеющиеся предпосылки для введения понятия нормальной формы квадратной (ОД)-матрицы, специфика самой (ОД)-матрицы и ее связь с теорией графов. Было показано, что нормальную форму произвольной матрицы можно строить, используя ее индикаторную матрицу ((0,1)-матрицу), исходя из этого при изучении структуры матрицы можно перейти от обычной арифметики к булевой. Доказываются новые теоретические результаты, которые легли в основу введения нормальной формы.
Для разных классов матриц и различных видов преобразований давно существуют понятия канонической формы матрицы. Наиболее известными являются канонический вид разложимой и импримитивной матриц, которые, по сути, даются через определение преобразования перестановочного подобия (Р-подобия, т. е. преобразования связанного с перестановкой строк и такой же перестановкой столбцов в квадратных матрицах).
Поскольку Р-подобие есть частный случай подобия, то нормальную форму разложимой матрицы ранее пытались строить, базируясь на понятиях линейной алгебры. Однако, учитывая специфику (ОД)-матриц и их связь с теорией графов оказалось удобнее строить нормальную форму квадратной (ОД)-матрицы отталкиваясь от понятий теории графов. Перенесли на квадратные (ОД)-матрицы понятия транзитивного замыкания, несвязности, слабой связности, односторонней связности и сильной связности из теории графов.
По аналогии с транзитивным замыканием в теории графов ввели понятие транзитивного замыкания матрицы, т. е. матрицы, которая сопоставляется исходной (ОД)-матрице и является транзитивной. В работе введено понятие нормальной формы транзитивной (ОД)-матрицы и с ее помощью давалось понятие нормальной формы квадратной (ОД)-матрицы.
Учитывая взаимнооднозначное соответствие между (ОД)-матрицами и графами, все полученные результаты относительно нормальной формы квадратных (ОД)-матриц могут быть отнесены к нормальным формам графа.
Приведены алгоритмы построения нормальной формы (ОД)-матрицы как для частных, так и для общего случаев. При построении нормальной формы матрицы графа попутно решается классическая задача теории графов — выделение компонент связности графа.
Приведены примеры использования нормальной формы (0,1)-матрицы. Как видно, исследования орграфов пятого порядка и проблема изоморфизма графов не завершены, что планируется сделать в дальнейшем. В продолжение работы планируется найти и другие задачи в теории матриц и теории графов, решение которых удастся упростить с помощью использования нормальной формы (ОД)-матрицы.
У автора имеется 6 публикаций по теме диссертации.
