Нормальная форма квадратных (0,1)-матриц и ее применение тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Санкт-Петороургсюш шсударетненный университет

На правах рукописи

Савицкая Диана Владимнропна

НОРМАЛЬНАЯ ФОРМА КВАДРАТНЫХ (ОД)-МАТРИЦ И ЕЕ ПРИМЕНЕНИЕ

01.01.09 - дискретная математика и математическая кибернетика

003464552

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

з 1'.;,

Санкт-Петербург - 2009

003464552

Работа выполнена на кафедре высшей математики факультета прикладной матсматики-процессов управления Санкт-Петербургского государственного университета

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Защита состоится " 2009 г. в

седании совета Д.212.232.59 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, В.О., Средний пр.. 41/43, ауд. '57/.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034. Санкт-Петербург, Университетская наб., 7/9.

кандидат физико-математических наук, доцент Хитров Геннадий Михайлович

доктор физико-математических паук, профессор Харитонов Владимир Леонидович (Санкт-Петербургский Государственный Университет)

кандидат физико-математических наук, доцент Кривцов Александр Николаевич (Санкт-Петербургское высшее военное училище радиоэлектроники (военный институт))

Петрозаводский государственный университет

мин. на за-

Автореферат разослан

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор

Ногин В.Д.

АХ-

Общая характеристика работы.

Актуальность работы вытекает из актуальности рассматриваемой в пей задачи. Задача построении нормальной (канонической, наиболее простой и т.п.) формы квадратной матрицы всегда была одной из основных и теории матриц. Вид нормальной формы зависит от типа допустимых преобразовании, которые можно совершать с матрицами. Так, например, с помощью известного преобразования подобия, т.е. перехода от матрицы А к матрице С^1 АС. любую квадратную матриц}' А c. комплексными элементами всегда можно привести к блочно диагональной форме Жордана, с диагональными блоками - «клетками Жордана». Если в качестве допустимых преобразований матрицы можно использовать только «перестановку рядов», т.е. перестановку строк и такую же перестановку столбцов, то о нормальной форме Жордана можно забыть - при перестановке рядов элементы матрицы не меняются, меняются только места в матрице. на которых располагаются элементы. Если воспользоваться понятием матрицы перестановки Р, т.е. ортогональной (ОД)-матрицы, то перестановку рядов в матрице А можно представить в виде преобразования РАРТ. где сомножитель Р отвечает за перестановку строк, а сомножитель Р1 (транспонированная матрица Р) за «такую же перестановку» столбцов. Указанное преобразование называют также преобразованием перестановочного подобия, или просто преобразованием Р-подобия. поскольку это преобразование является частным случаем преобразования подобия с матрицей С = Рт. Преобразования перестановочного подобия широко применяются в теории матриц с неотрицательными элементами. По сути, через них дается определение так называемой разложимой матрицы.

Определение 1. Квадратная матрица А порядка п > 2 называется разложимой, если существует матрица перестановки Р, что матрица РАРТ имеет блочно треугольный вид с квадратными диагональными блоками порядков больше либо равных единице:

где В и D - указанные квадратные матрицы-блоки порядков г и п — г (1 < г < л—г) соответственно, 0-нулевая матрица размерности (п — г) х г. С-матрица размерности г х (п — г). Матрица, не яиляющаяея разложимой, называется неразложимой.

(1)

Серьезные попытки построения нормальной формы разложимой неотрицательной матрицы сделаны в книге Гантмахера Ф.Р. ¡1], недостаточность этих попыток показана в работе [2]. В работе [3] отмочено, что при изучении разложимости матриц, а также свойств примитивности и импримитивности матриц, можно от исходных матриц перейти к их индикаторным матрицам, т.е. к матрицам, где все ненулевые элементы исходных матриц заменены единицами. Индикаторные матрицы являются частным случаем так называемых (0,1 )-матриц (элементами матриц могут быть только нули или единицы). Сказанное выше о неотрицательных матрицах подчеркивает важность изучения (ОД)-матриц для определения нормальной формы разложимой матрицы. Связь же (ОД)-матриц с графами (любую квадратную (0,1)-матрицу можно рассматривать как матрицу смежности некоторого графа) показывает, что при определении нормальной формы (0,1)-матрицы можно воспользоваться терминами и результатами теории графов. Примечательно, что в [3] доказательство необходимых и достаточных условий разложимости неотрицательной квадратной матрицы опирается на понятия и методы теории графов. Это также косвенно подталкивает к мысли, что давать определение нормальной формы (ОД)-матрицы, а тем более практически ее строить, нужно отталкиваясь от теории графов.

Естественно нормальную форму (0,1)-матриц связывать с задачами теории графов и использовать ее там. где пока не видно подходящего решения задачи. Такой трудной задачей является, например, задача, об изоморфизме графа некоторому подграфу другого графа, сформулированная в [4].

Отметим, что матрицы в теории графов начали использоваться значительно раньше, чем графы н теории матриц. Для этого достаточно указать на такие специальные виды матриц, как матрицы смежности и матрицы инциденций. Можно констатировать, что взаимопроникновение теории графов и теории матриц друг в друга на сегодняшний день весьма значительно (это подтверждают монографии |Г>|. |(>) и др.)

Сказанное выше в совокупности с тем, что в тематическом плане научных исследований факультета. ПМ-ПУ СПбГУ есть тема "Разработка матричного языка теории графой", делает актуальность диссертационной работы вполне очевидной.

Цель работы состояла в сборе и систематизации материала по теории неотрицательных матриц и теории графов; в переводе на

язык матриц тех свойств графа (например, связности, транзитивного замыкания и др.); которые необходимы для определения нормальной формы квадратной (ОД)-матрицы; в формулировке самого определения нормальной формы (ОД)-матрнцы; в разработке алгоритма построения нормальной формы (0,1)-матрицы.

Методы исследования - методы теории матриц и теории графов с учетом специфики объекта исследования, т.е. класса (0,1)-матриц. Так, учет специфики объекта исследования позволил при создании алгоритма построения нормальной формы (0,1 )-матрицы перейти в большинстве случаев от обычного сложения и умножения матриц к булеву сложению и булеву умножению матриц.

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

Практическая ценность работы. Материалы диссертации могут быть использованы при чтении специальных курсов для студентов математических специальностей ВУЗов. Результаты данной работы носят теоретический характер и могут служить основой для дальнейших научных исследований в теории графов, например, для следующих задач: изоморфизм графов, изоморфизм графа некоторому подграфу другого графа, исследование в общем случае графов и орграфов с п вершинами, отыскание клик графа.

Реализация и внедрение результатов работы. Результаты данной диссертации были включены в тематический план факультета прикладной математики-процессов управления Санкт-Петербургского государственного университета. На основе полученных результатов диссертации были созданы программы для пакета <^егопе» [7], направленного на работу с графами.

Апробация работы. Результаты работы докладывались и об-

суждались на конференциях: 30 Межвузовская конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2005); 37 Международная конференция студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2006); 38 Международная конференция студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2007); 39 Международная конференция студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2008); III всероссийской научной конференции «Проектирование научных и инженерных приложений в среде МАТЬАВ» (Санкт-Петербург, 2007), а так же на семинаре кафедры высшей математики факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета.

Публикации. Основные результаты диссертационной работы отражены в 6 публикациях, в том числе 1 статья опубликована в издании рекомендованном ВАК. Список работ приведен в конце автореферата |10]-|15).

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения, приложения, списка литературы из 27 наименований. Общий объем работы - 89 страниц, включая 7 рисунков, 2 таблицы и код 1 программы из 207 строк.

Основное содержание работы.

Во введении приводится краткий обзор полученных результатов и коротко излагается содержание диссертации.

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

Одними из основных понятий теории матриц с неотрицательными элементами являются понятия разложимой и неразложимой матриц, которые приводились ранее. Рассмотрим этот тип матриц подробнее.

Определение 2 |2|. Если в (1) блок С — 0, то матрицу А будем называть сильно разложимой. Если А - разложимая матрица, и не является сильно разложимой, то ее будем называть слабо разложимой.

Теорема 1. Матрица А неразложима тогда и только тогда, когда (Е+А)у(п~1'> = £/, где и - матрица из одних единиц.

В первой главе приведены определения графа на трех языках.

• Геометрическом - графом называется фигура, состоящая из точек (называемых вершинами или узлами) и отрезков, соединяющих некоторые из этих точек. Соединяющие отрезки могут быть направленными (дугами), ненаправленными (ребрами), прямолинейными или криволинейными. Отрезок, соединяющий вершину с самой собой, называется петлей.

• Теоретико-множественном - графом называется пара (V, Я), где V - некоторое конечное множество, элементы которого называются вершинами (узлами), а Я С V х V, т.е. некоторое подмножество декартова произведения множества V на себя, или бинарное отношение на V. Элементы множества Я, т.е. упорядоченные нары (и, и) € Я (где и, V € V) соответствуют дугам предыдущего определения. Обозначается граф обычно через Я).

• Матричном - графом называется множество (класс) квадратных (0,1 )-матриц, перестановочно подобных между собой.

В соответствии с тремя различными, приведенными выше, определениями графа существуют различные способы задания графа, которые также приведены в первой главе. Приводятся некоторые разновидности графов, которые по тем или иным причинам нашли наибольшие теоретические или практические приложения (полный, пустой, единичный, плоский графы). Вводятся основные понятия теории графа: достижимость; связность; путь; длина пути; простой, элементарный, тривиальный пути; расстояние; цепь; цикл; орцикр; двудольный и /с-дольпый графы; подграф и правильный подграф; полустепень захода и полустепень исхода узла; инварианты графа и изоморфизм графов, - а также их матричные определения.

Материала, приведенного в первой главе, достаточно для построения курса по (ОД)-матрицам для студентов математических

специальностей ВУЗов, также он может являться материалом и для альтернативных методов построения нормальной формы матрицы.

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

Определение 3. Будем называть граф транзитивным, если любые две его вершины, связанные путем длины 2, смежные. Другими словами, граф транзитивный, если в графе вместе с любым путем длины два идущим из ¿-ой вершину в ^'-ую имеется и дуга (г,7') (в частности г может совпадать с ]).

Определение 4. Квадратную (ОД)-матрицу А будем называть транзитивной матрицей, если Ах2 < А (все элементы булева квадрата матрицы А меньше либо равны соответствующих элементов матрицы А).

Определение 5. Назовем транзитивным замыканием квадратной (0,1)-матрицы А порядка п (ОД)-матрицу Та = А*к (равную булевой сумме булевых степеней матрицы А).

Определение 6. Граф называется несвязным, если множество его вершин можно разбить на непересекающиеся подмножества таким образом, что вершины, входящие в различные подмножества, никак между собой не связаны. На матричном языке несвязности графа соответствует сильная разложимость матрицы графа, матрица транзитивного замыкания такого графа также будет сильно разложимой.

Граф называется связным, если он не является несвязным. Матрица связного графа может быть неразложимой или слабо разложимой матрицей. Связные графы различаются между собой по типу связности.

Определение 7. Граф, называется сильно связным, если любая его вершина достижима из любой другой. Сильно связному графу соответствует неразложимая матрица, а транзитивное замыкание является полной матрицей (матрицей из единиц).

Определение 8. Граф, называется односторонне связным, если для любой пары различных вершин I и ] либо вершина ] достижима из г, либо вершина г из либо обе вершины достижимы друг из друга. При этом граф не является сильно связным. Матрица такого графа является слабо разложимой матрицей.

Предложение 1. Транзитивное замыкание матрицы односторонне связного графа содержит нули, но не содержит симметрично расположенных относительно главной диагонали нулей.

Определение 9. Граф называется слабо связным, если он связен, и существует, по крайней мере, одна такая пара различных вершин i и j, что вершина j недостижима из г и вершина i из j. Матрица такого графа является слабо разложимой матрицей.

Предложение 2. Транзитивное замыкание матрицы слабо связного графа не является сильно разложимой матрицей и содержит симметрично относительно главной диагонали расположенные нули.

Во второй главе диссертации приведены свойства определений 3 и 4, показана их эквивалентность, сформулированы и доказаны теоремы и несколько предложений относительно транзитивных матриц, которые легли в основу построения алгоритма нормальной формы (ОД)-матрицы. Приведем особо значимые из них.

Предложение 3. Если Ä = PAP1, то Тк = РТАР'.

Теорема 2. Если в транзитивном графе есть дуга из г-ой вершины в j-ую, а степень исхода j-ой вершины равна к, то степень исхода г-ой вершины > к.

Теорема 3. Если булев квадрат симметричной неразложимой матрицы А является разложимой матрицей, то матрица А - импри-митивна, в противном случае - примитивна.

После введенных необходимых понятий и приведенных доказательств нужных результатов, приводятся алгоритмы построения нормальной формы (0,1)-матрицы для частных случаев: алгоритм разложения матрицы на ее компоненты, алгоритм построения нормальной формы разложимой матрицы, алгоритм построения нормальной формы неразложимой примитивной и имиримитивной матриц. После чего строится общий алгоритм построения нормальной формы для произвольной квадратной матрицы 6", который приведем ниже.

1. На первом шаге проверяем, является ли матрица квадратной. Если да, то переходим к следующему шагу, в противном случае - ошибка и алгоритм останавливается. На следующем шаге переходим от произвольной матрицы С к {0,1)-матрице А. Далее проверяем, является ли матрица А симметричной. Если да, то переходим к проверке на разложимость матрицы А (см. п. 2), нет - к проверке на сильную разложимость несимметричной матрицы А (см. п. 5).

2. Проверка симметричной матрицы А на разложимость, для

тугого строим транзитивное замыкание матрицы А - Та (см. онр. 5), и проверяем его на разложимость по критерию описанному в теореме 1. Если Та — U. то матрица А не является разложимой, такую матрицу А будем называть одноколтонентпной матрицей. Если Та ф U, то матрица А разложимая и переходим к разложению матрицы А на ее компоненты. Для того чтобы выделить компоненты исходной матрицы, нам необходимо найти нормальную форму сильно разложимой матрицы , т.е. с помощью перестановки рядов привести ее к блочпо-диагональному виду. Для этого строим вектор Тда = sta (е - столбец из единиц), затем строим матрицу перестановок Р\ такую, что PiSTa = sra, где Sta - вектор-столбец строчных сумм, упорядоченный по убыванию элементов. При этом внутри групп с одинаковыми строчными суммами происходит упорядочивание таким образом, чтобы одинаковые строки в матрице Так = PiAP{ следовали друг за другом. Матрица Так ~~ это блочно-диагональная матрица с квадратными блоками Urlj размерности rij на главной диагонали, состоящими из одних единиц, где 2_,j=i ni = п, an- порядок квадратной матрицы А:

Так

funi

О

V о

о

ип.

о

о

UnJ

Матрицу Ак 1 = Р\АР[ будем называть первой грубой канонической формой матрицы А\

Aki =

(А\ О

о а2 \ о о

о

Квадратные блоки А^ размерности > 1 являются неразложимыми. Если матрица А задает граф С, то матрица Ак\ показывает, что граф б может быть разложен на компоненты Сь <?2, ■ •., Сь задаваемые матрицами Ач-, ■.., Лд- соответственно. При этом подграфы йз будут сильно связными подграфами при тг_,- > 1, а блоки с размерностью п^ = 1 соответствуют изолированным вершинам (с петлей или без нее).

Необходимо запомнить матрицу перестановок Р\, с помощью которой мы нашли первую грубую каноническую форму матрицы А -Ах 1 (если исходная матрица А однокомпонентная. то Р\ — Е).

Далее саму матрицу А, если она является однокомпонептпой, или каждую ее компоненту А{ (г — 1,2,...,к) проверяем на примитивность и импримитивность по теореме 3. Если матрица А или компонента Л, является примитивной матрицей, то переходим к построению нормальной формы примитивной матрицы (см. п. 3), если импримитшшой, то переходим к построению нормальной формы симметричной импримитивной матрицы (см. п. 4).

3. В построении нормальной формы примитивной симметричной матрицы будем использовать вершинную раскраску графа, поэтому следует разделить матрицу А (под матрицей А подразумеваем примитивную матрицу А или компоненту которая является примитивной) на матрицу с нулевой главной диагональю А и диагональную матрицу 01ад{А), т.е. А ~ А+Вгад(А). Поскольку раскраска выделяет наименее связные вершины, а мы стараемся сгруппировать максимально связные вершины, то применим алгоритм раскраски к дополнительному графу, соответствующему матрице А. Для этого перейдем от матрицы Л к ее дополнению. Раскрасив дополнительный граф по алгоритму А. Ю. Красновой [8], найдем некоторую матрицу перестановки Р2: которая выделяет подмножества несмежных между собой вершин. Применив данную матрицу _Р2 к исходной матрице А, получим матрицу А = Р^АР^. у которой вдоль диагонали стоят блоки из смежных вершин. Доказательство данного факта следует из утверждения [9], в котором говорится о том, что матрицы подобны тогда и только тогда, когда подобны их дополнения. Матрицу А будем называть нормальной формой щпшитиаиой матрицы.

4. А (под матрицей А подразумеваем импримитивную матрицу А или компоненту Л;, которая является импримитивной) - неразложимая симметричная импримитивная (0,1)-матрица размерности п, значит по теореме 2 А*2 — разложимая матрица. Построив матрицу Р2, которая приводит матрицу А*2 к виду (1) при С = 0, найдем канонический вид импримитивной симметричной матрицы А -А = РоАР"2.

Как и после разложения матрицы А на ее компоненты, запоминаем матрицу перестановок Р2- с помощью которой нашли нормальную форму примитивной или импримитивной однокомпонент-ной матрицы А. В случае если матрица А разложимая, то Р> =

P>i Ф Р'22 Ф • • • Ф Р'2к (блочно-диагональная матрица с квадратными блоками Р21 на главной диагонали, все остальные элементы равны нулю), где P'^i - матрица перестановок, с помощью которой нашли нормальную форму примитивной или импримитивиой г-ой компоненты матрицы A (i — 1,2,..., к).

Теперь можем построить нормальную форму исходной симмет-' ричной матрицы С с помощью матрицы перестановок Р = РгхРь т.е. С = PCP'.

5. Проверяем несимметричную матрицу А на сильную разложимость, для этого перейдем к матрице À = А+А' и проверяем ее на разложимость. Если матрица А является разложимой, значит матрица А является сильно разложимой. В этом случае ищем компоненты матрицы А, при этом запоминаем матрицу перестановок Pi, с помощью которой нашли первую грубую каноническую форму матрицы А - матрицу Ах i- Если матрица А неразложимая, то матрица А является однокомпонентной тл Р\ — Е. Далее саму матрицу Л, если она является однокомпонентной, или каждую ос компоненту Ai (г = 1,2,... ,к) исследуем на слабую разложимость или неразложимость по критерию описанному в теореме 1. Если матрица А неразложимая, то P-i = Е, если слабо разложимая, то ищем нормальную форму слабо разложимой матрицы. Для этого упорядочиваем матрицу транзитивного замыкания матрицы А по столбцу строчных сумм, получим Так блочную верхне треугольную матрицу. Матрица Так разбивается на горизонтальные и вертикальные полосы размер-

ностей п.

к

■з 0 — 1)2,..., к), "з

Далее проверяем наличие симметричных относительно главной диагонали нулей в матрице Так■ Если в матрице нет симметричных относительно главной диагонали нулей, значит, матрица А соответствует односторонне связному графу (см. предложение 1), а матрица Л/С2, имеющая одинаковую блочную структуру с матрицей Так-, будет нормальной формой разложимой матрицы, которую назовем второй грубой канонической формой матрицы А:

Ак2 =

(А\ * ... * \ О Ai ... *

\0 0 ... Аь)

Влок Адля 71 ^ > 1, стоящий на главной диагонали, является неразложимой матрицей. Запоминаем матрицу Р-/, с помощью которой мы

упорядочили транзитивную матрицу по столбцу строчных сумм.

Если же в матрице Так есть симметричные относительно главной диагонали нули, тогда матрица А соответствует слабо связному графу (см. предложение 2). Переходим к построению нормальной формы слабо связного графа, т.е. строим цикл по ? от 0 до к — 1 и рассматриваем части столбцов матрицы расположенные в вертикальных полосах с, номерами от к до к - г и выше горизонтальной полосы с номером к — I. Если все указанные части столбцов содержат нули, то г — г + 1; не содержат нулей, тогда разбиваем матрицу

на четыре блока, т.е. придаем ей вид Т_\к - ^^ , где Ти -

матрица из одних единиц, Тц и Т22 квадратные матрицы размерности к — ? — 1 и г-г1 соответственно. Далее исследуем матрицы Гц и Т'п па сильную разложимость (переходим к началу п. Г>). Запоминаем матрицу Р-2 или Р21 соответственно, с помощью которой мы нашли нормальную форму слаборазложимой матрицы А или каждой ее слабо разложимой компоненты Л,;. Если матрица А разложимая, то р2 = рл ^ р22 © ... © р2к.

Теперь на главной диагонали матрицы стоят неразложимые матрицы-блоки. Заменим эти блоки их нормальными формами. Для этого проверяем каждую матрицу А, (г = 1,2,..., к) стоящую на главной диагонали матрицы А на примитивность и импримитивность. Если матрица А, примитивна, то переходим к построению нормальной формы примитивной матрицы, используя вершинную раскраску. Если матрица Л;, импрнмптшша, то строим нормальную форму импримитивной матрицы (в диссертации приведен подробный алгоритм построения нормальной формы несимметричной импримитивной (0,1)-матрицы). При этом запоминаем матрицу перестановок /у,, с помощью которой нашли нормальную форму примитивной или импримитивной матрицы .4;, Р3 = Рл ФР32Ф.. .фРз*.

Теперь можно построить нормальную форму исходной несимметричной матрицы С - С = РСР', где Р - матрица перестановок Р = Рч X Р-2 X 1\ .

В диссертации приведен наглядный пример построения нормальной формы квадратной (0,1)-матрицы.

В третьей главе приведены примеры использования нормальной формы (ОД)-матрицы. Например, задача изоморфизма заданного графа порядка т подграфу другого графа порядка, п.. где т < п. Покачано, что в общем случае эта задача решается полным перебо-

ром. т.е. сложность задачи равна. п!. В настоящей диссертации показано, что сложность этой задачи можно свести до «■!/((" ~ "')'1"гл|), где |тд| ~ мощность группы автоморфизмов матрицы графа А порядка т. Задача поиска |гпд| значительно упрощается, если использовать нормальную форму матрицы графа А.

Помимо этого в третьей главе показано, как нормальная форма квадратной (ОД)-матрицы используется при исследованиях обыкновенных и ориентированных 5-ти вершинных графов. Таким образом, нормальную форму квадратных (0,1 )-матрпц можно использовать и для исследований обыкновенных и ориентированных графов порядка п. Также показано как нормальная форма квадратной (0,1)-матрицы может быть использована для отыскания наибольшей клики графа.

В заключении приводится перечень основных результатов диссертации, к которым относятся: матричные определения типов связности графов (опр. 6-8, предложения 1, 2), построение транзитивного замыкания с помощью булевой арифметики (опр. Г>), понятие нормальной формы квадратной (ОД)-матрицы и алгоритмы ее построения с использованием булевой арифметики, теормемы 1, 2, 3. Также в заключении приводятся некоторые нерешенные проблемы.

В приложении приведен код программы упрощенного варианта алгоритма построения нормальной формы (ОД)-матрицы, наппса-ный в среде Ма1ТаЬ, который приведен в пакете программ ЕегОпе [7].

Литература

1. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967. 576 с.

2. Хитров Г. М. Об определении разложимой матрицы и ее нормальной формы // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2006. Вып. 3. С. 85-91.

3. Хорн Р., Джонсон Ч. Матричный анализ Пер. с англ.: Под ред. X. Д. Икрамова. М.: Мир, 1989. 055 с.

4. Погожев С. В.. Хитров Г. М. Об одном алгоритме проверки перестановочного подобия (ОД )-.матрнц // Проектирование научных и инженерных приложений в среде МАТЬАВ: Труды III

Всерос. науч. конференции. СПб., 23 - 26 октября 2007 г. СПб.: Изд-во С.-Петерб. ун-та, 2007. С. 230-237.

5. Дуб М., Захс X., Цветкович Д. Спектры графов. Киев: Наукова Думка, 1984. 384 с.

6. Тараканов В. Е. Комбинаторные задачи и (ОД)-матриды М.: Наука, 1985. 192 с.

7. Пакет программ ZerOne для MATLAB - URL http://ww\v.apmath.spbu.ru/grafomaim/dowiiload.litml.

8. Краснова А. Ю. Об одном алгоритме раскрасок графа // Проектирование научных и инженерных приложений в среде MATLAB: Труды III Всерос. науч. конференции. СПб., 23 - 26 октября 2007 г. СПб.: Изд-во С.-Петерб. ун-та, 2007. С. 230-237.

9. Виташевская И.С., Олемской И.В., Хитров Г.М. О некоторых инвариантах квадратных (ОД)-матриц // Вестн. С.-Петерб. унта. Сер. 10: Прикладная математика, информатика, процессы управления. 2007. Вып. 1. С. 38-45.

Публикации автора по теме диссертации

10. Савицкая Д. В. Нормальная форма (ОД)-матрицы и алгоритмы ее построения // Вести. С.-Петерб. ун-та. Сер. 10. 2008. Вып. 4. СПб.: С.-Петерб. ун-та. С. 88-100.

И. Савицкая Д. В. Особенности характеристических многочленов матриц смежности обыкновенных 5-вершинных графов // Процессы управления и устойчивость: Труды 36-й международной научной конференции студентов и аспирантов / Под ред. A.B. Платонова, Н.В. Смирнова. - СПб.: Изд-во С.-Петерб. ун-та, 2005. С. 544-550.

12. Савицкая Д. В. Генерирование неотрицательных матриц со специальными свойствами. Кодирование и декодирование (0,1)-матрнц // Процессы управления и устойчивость: Труды 37-й международной научной конференции студентов и аспирантов / Под ред. A.B. Платонова, Н.В. Смирнова.. - СПб.: Изд-во С.-Петерб. ун-та, 2000. С. 420-42«.

13. Савицкая Д. В. Выделение полного набора подграфов заданного графа, классифицированных; по типу связности // Процессы управления и устойчивость: Труды 38-й международной научной конференции студентов п аспирантов / Под ред. A.B. Платонова, П.В. Смирнова. - СПб.: Изд-во C.-Петерб. ун-та, 2007. С. G4-C9.

14. Савицкая Д. В. Алгоритм построения нормальной формы квадратной (0,1)-матрицы // Проектирование научных и инженерных приложений в среде MATLAB: Труды III всероссийской научной конференции. Россия, СПб.. 23-26 октября 2007 г. 2007. СПб.: С.-Петерб. ун-та. С. 346-357.

15 Савицкая Д. В. Об одном алгоритме проверки планарности графа // Процессы управления и устойчивость: Труды 39-й международной научной конференции студентов и аспирантов ! Под ред. A.B. Платонова, Н.В. Смирнова. - СПб.: Изд-во С.-Петерб. ун-та. 2008. С. 77-81.

Подписано к печати 19.02.09. Формат 60 х S4 '/:<■ Б> мага офсетная Гарнитура Times. Печать цифровая. Печ л 1,(1 Тираж 100 экз. Заказ 4390.

Отпечатано в О¿деле ог,¿рутинной полиграфии химического факультета СГ15ГУ 19&504, Санкт-Петербург, Старый Петергоф. Университетски;'. i:p .."!(' Тел.: (»12) 428-404.4, 42S-69I9

Введение.

Глава 1. Вводная.

§ 1.1. Сведения из теории матриц с неотрицательными элементами.

§ 1.2. Связь между бинарными отношениями, графами и (0,1)матрицами. Переход к булевой арифметике.

§ 1.3. Сведения из теории графов.

Глава 2. Алгоритмы построения нормальной формы (0,1)-матрицы.

§ 2.1. Алгоритм разложения матрицы на ее компоненты.

§ 2.2. Алгоритм построения нормальной формы разложимой матрицы.

§ 2.3. Алгоритм построения нормальной формы неразложимой матрицы.

§ 2.3.1. Алгоритм построение нормальной формы примитивной матрицы.

§ 2.3.2. Алгоритм построение нормальной формы импримитивной матрицы.

§ 2.4. Общий алгоритм построения нормальной формы произвольной матрицы.

Тема моей диссертационной работы - «Нормальная форма квадратных (ОД)-матриц и ее применение». Вначале тема моих исследований формулировалась как «Нормальная форма квадратных неотрицательных разложимых матриц». Предполагалось, что мои исследования будут продолжением исследований, изложенных в книге Гантмахера Ф.Р. «Теория матриц» в соответствующем параграфе [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 публикаций по теме диссертации.

1. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967. 576 с.

2. Хитров Г. М. Об определении разложимой матрицы и ее нормальной формы // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2006. Вып. 3. С. 85-91.

3. Хорн Р., Джонсон Ч. Матричный анализ Пер. с англ.; Под ред. X. Д. Икрамова. М.: Мир, 1989. 655 с.

4. Никайдо X. Выпуклые структуры и математическая экономика Пер. с англ. А. В. Малишевского; Под ред. Э. М. Бравермана М.: Мир, 1972. 520 с.

5. Дуб М., Захс X., Цветкович Д. Спектры графов. Киев: Наукова Думка, 1984. 384 с.

6. Тараканов В.Е. Комбинаторные задачи и (ОД)-матрицы М.:Наука, 1985. 192 с.

7. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2001.301 с.

8. Харари Ф. Теория графов. Пер. с анг. В. П. Козырева; Под ред. Г. П. Гаврилова. Изд. 3-е, стереотипное. М.:КомКнига, 2006. 296 с.

9. Ope О. Графы и их применение. Пер. с анг. JI. И. Головиной; Под ред. И. М. Яглома. М.: Мир, 1965. 176 с.

10. Кристофидес Н. Теория графов: Алгоритмический подход Пер. с англ. Э. В. Вершкова, И. В. Коновальчева; Под ред. Г. П. Гаврилова М.: Мир, 1978. 432 с.

11. Краснова А. Ю. Об одном алгоритме раскрасок графа // Проектирование научных и инженерных приложений в среде MATLAB: Труды III Всерос. науч. конференции. СПб., 23 26 октября 2007 г. СПб.: Изд-во С.-Петерб. ун-та, 2007. С. 230-237.

12. Виташевская И.С., Олемской И.В., Хитров Г.М. О некоторых инвариантах квадратных (ОД)-матриц // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2007. Вып. 1.С. 38-45.

13. Пакет программ ZerOne для MATLAB URL \\ http://www.apmath.spbu.ru/grafomann/download.html.

14. Пакет программ Graph Interface(Grin) URL \\ http://graph-software.narod.ru/

15. Берж К. Теория графов и ее применения. Пер. с франц. А. А. Зыкова. Под ред. И. А. Вайнштейна М.: Изд-во Иностранной литературы. 1962. 320 с.18.0ре О. Теория графов. М.: Наука, 1980. 336 с.

16. Свободная энциклопедия Википедия http://ru.wikipedia.org/

17. Зыков A.A. Основы теории графов. М.: Вузовская книга, 2004. 664 с.

18. Татт У. Теория графов. М.: Мир. 1988. 424с.22.ван дер Варден Б.Л. Алгебра. М.: Наука, 1979. 624с.

19. Постников М.М. Теория Галуа. М.: ФМ, 1963. 220с.

20. Курош А.Г. Курс высшей алгебры. М.: Наука, 1971.432с.

21. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 328с.

22. Томас X. Кормен и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION ТО ALGORITHMS. — 2-е изд. — М.: «Вильяме», 2006. — С. 1296. — ISBN 0-07-013151-1

23. Diestel R. Graph Theory, Electronic Edition. — NY: Springer-Verlag, 2005. —C. 422.