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

• Савицкая, Диана Владимировна
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Савицкая, Диана Владимировна

Введение.

Глава 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. Общий алгоритм построения нормальной формы произвольной матрицы.

Введение диссертации (часть автореферата) на тему «Нормальная форма квадратных (0,1)-матриц и ее применение»

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

Список литературы диссертационного исследования кандидат физико-математических наук Савицкая, Диана Владимировна, 2009 год

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.