Введение к работе
Актуальность работы вытекает из актуальности рассматриваемой в ней задачи. Задача построения нормальной (канонической, наиболее простой и т.п.) формы квадратной матрицы всегда была одной из основных в теории матриц. Вид нормальной формы зависит от типа допустимых преобразований, которые можно совершать с матрицами. Так, например, с помощью известного преобразования подобия, т.е. перехода от матрицы А к матрице С-1 АС, любую квадратную матрицу А с комплексными элементами всегда можно привести к блочно диагональной форме Жордана, с диагональными блоками - «клетками Жордана». Если в качестве допустимых преобразований матрицы можно использовать только «перестановку рядов», т.е. перестановку строк и такую же перестановку столбцов, то о нормальной форме Жордана можно забыть - при перестановке рядов элементы матрицы не меняются, меняются только места в матрице, на которых располагаются элементы. Если воспользоваться понятием матрицы перестановки Р, т.е. ортогональной (ОД)-матрицы, то перестановку рядов в матрице А можно представить в виде преобразования PAP , где сомножитель Р отвечает за перестановку строк, а сомножитель Рт (транспонированная матрица Р) за «такую же перестановку» столбцов. Указанное преобразование называют также преобразованием перестановочного подобия, или просто преобразованием Р-подобия, поскольку это преобразование является частным случаем преобразования подобия с матрицей С = Рт. Преобразования перестановочного подобия широко применяются в теории матриц с неотрицательными элементами. По сути, через них дается определение так называемой разложимой матрицы.
Определение 1. Квадратная матрица А порядка п > 2 называется разложимой, если существует матрица перестановки Р, что матрица РАРТ имеет блочно треугольный вид с квадратными диагональными блоками порядков больше либо равных единице:
PApT=(f> ). о
где В и D - указанные квадратные матрицы-блоки порядков г и п — г (1 < г < п — г) соответственно, 0 - нулевая матрица размерности (п — г) х г, С - матрица размерности г х (п — г). Матрица, не являющаяся разложимой, называется неразложимой.
Серьезные попытки построения нормальной формы разложимой неотрицательной матрицы сделаны в книге Гантмахера Ф.Р. [1], недостаточность этих попыток показана в работе [2]. В работе [3] отмечено, что при изучении разложимости матриц, а также свойств примитивности и импримитивности матриц, можно от исходных матриц перейти к их индикаторным матрицам, т.е. к матрицам, где все ненулевые элементы исходных матриц заменены единицами. Индикаторные матрицы являются частным случаем так называемых (ОД)-матриц (элементами матриц могут быть только нули или единицы) . Сказанное выше о неотрицательных матрицах подчеркивает важность изучения (ОД)-матриц для определения нормальной формы разложимой матрицы. Связь же (ОД)-матриц с графами (любую квадратную (ОД)-матрицу можно рассматривать как матрицу смежности некоторого графа) показывает, что при определении нормальной формы (ОД)-матрицы можно воспользоваться терминами и результатами теории графов. Примечательно, что в [3] доказательство необходимых и достаточных условий разложимости неотрицательной квадратной матрицы опирается на понятия и методы теории графов. Это также косвенно подталкивает к мысли, что давать определение нормальной формы (ОД)-матрицы, а тем более практически ее строить, нужно отталкиваясь от теории графов.
Естественно нормальную форму (ОД)-матриц связывать с задачами теории графов и использовать ее там, где пока не видно подходящего решения задачи. Такой трудной задачей является, например, задача, об изоморфизме графа некоторому подграфу другого графа, сформулированная в [4].
Отметим, что матрицы в теории графов начали использоваться значительно раньше, чем графы в теории матриц. Для этого достаточно указать на такие специальные виды матриц, как матрицы смежности и матрицы инциденций. Можно констатировать, что взаимопроникновение теории графов и теории матриц друг в друга на сегодняшний день весьма значительно (это подтверждают монографии [5], [6] и др.)
Сказанное выше в совокупности с тем, что в тематическом плане научных исследований факультета ПМ-ПУ СПбГУ есть тема " Разработка матричного языка теории графов", делает актуальность диссертационной работы вполне очевидной.
Цель работы состояла в сборе и систематизации материала по теории неотрицательных матриц и теории графов; в переводе на
язык матриц тех свойств графа (например, связности, транзитивного замыкания и др.), которые необходимы для определения нормальной формы квадратной (ОД)-матрицы; в формулировке самого определения нормальной формы (ОД)-матрицы; в разработке алгоритма построения нормальной формы (ОД)-матрицы.
Методы исследования - методы теории матриц и теории графов с учетом специфики объекта исследования, т.е. класса (0,1)-матриц. Так, учет специфики объекта исследования позволил при создании алгоритма построения нормальной формы (ОД)-матрицы перейти в большинстве случаев от обычного сложения и умножения матриц к булеву сложению и булеву умножению матриц.
Научная новизна. Основным результатом диссертации является введение нового понятия нормальной формы квадратной (0,1)-матрицы. По ходу исследований было введено понятие транзитивной матрицы, даны матричные определения типов связности графов, сформулированы и доказаны теоремы, утверждения и предложения, использованные при создании алгоритмов построения нормальной формы для частных случаев квадратной (ОД)-матрицы (разложение матрицы на ее компоненты; нормальная форма разложимой, неразложимой примитивной и неразложимой импримитивнои матриц), а также для произвольной квадратной матрицы. Отметим, что взаимнооднозначное соответствие (ОД)-матриц и графов позволяет все полученные результаты относительно нормальной формы квадратной (ОД)-матрицы отнести к нормальным формам графа.
Практическая ценность работы. Материалы диссертации могут быть использованы при чтении специальных курсов для студентов математических специальностей ВУЗов. Результаты данной работы носят теоретический характер и могут служить основой для дальнейших научных исследований в теории графов, например, для следующих задач: изоморфизм графов, изоморфизм графа некоторому подграфу другого графа, исследование в общем случае графов и орграфов с п вершинами, отыскание клик графа.
Реализация и внедрение результатов работы. Результаты данной диссертации были включены в тематический план факультета прикладной математики-процессов управления Санкт-Петербургского государственного университета. На основе полученных результатов диссертации были созданы программы для пакета «Zerone» [7], направленного на работу с графами.
Апробация работы. Результаты работы докладывались и об-
суждались на конференциях: 36 Межвузовская конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2005); 37 Международная конференция студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2006); 38 Международная конференция студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2007); 39 Международная конференция студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2008); III всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB» (Санкт-Петербург, 2007), а так же на семинаре кафедры высшей математики факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.
Публикации. Основные результаты диссертационной работы отражены в 6 публикациях, в том числе 1 статья опубликована в издании рекомендованном ВАК. Список работ приведен в конце автореферата [10]-[15].
Структура и объем диссертации. Работа состоит из введения, трех глав, заключения, приложения, списка литературы из 27 наименований. Общий объем работы - 89 страниц, включая 7 рисунков, 2 таблицы и код 1 программы из 207 строк.
