Матрицы бинарных отношений и их применение в теории графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Беспалов, Александр Александрович

• Беспалов, Александр Александрович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Беспалов, Александр Александрович

Введение

Глава 1. Матрицы бинарных отношений

1.1. Понятие бинарного отношения. Матрица бинарного отношения

1.2. Множеетво квадратных матриц из нулей и единиц.

1.3. Операции над отношениями, основные определения.

1.4. Определение цепи, пути. Ацикличное бинарное отношение и его свойства.

1.5. Построение матрицы ацикличного отношения.

Глава 2. Разложимые и неразложимые матрицы

2.1. Используемые определения.

2.2. Теорема о разложимости и неразложимости в терминах матриц бинарных отношений

• 2.3. Алгоритм, позволяющий исследовать матрицы на разложимость и приводящий разложимую матрицу к каноническому виду . 34 2.4. Алгоритм исследования неразложимой матрицы и приведения импримитивной матрицы к канонической форме.

Глава 3. Перестановочное подобие матриц

3.1. Р-подобие матриц.

3.2. Необходимое условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц.

3.3. Автоморфизмы матриц перестановок.4G

Глава 4. Матричный метод проверки изоморфизма графов

4.1. Изоморфизм графов, матричная интерпретация.

4.2. Матричные инварианты преобразования Р-подобия.

4.3. Общий алгоритм решения задачи Р-подобия.

4.4. Матрицы смежностей обыкновенных графов.

4.4.1. Алгоритм проверки Р-нодобия матриц.

4.4.2. Необходимые и достаточные условия Р-подобия.G

Введение диссертации (часть автореферата) на тему «Матрицы бинарных отношений и их применение в теории графов»

Данная работа посвящена изучению матриц бинарных отношений, то есть квадратных (ОД)-матриц, в контексте исследования графов, бинарных отношений и теории подстановок. Такой матричный подход, основанный на использовании (ОД)-матриц, достаточно удобен и логически оправдан по следующим причинам. Во-первых, потому что существует взаимно однозначное соответствие между матрицами и графами, матрицами и бинарными отношениями, матрицами и подстановками. Во-вторых, на данный момент существует достаточно мощный математический пакет Mat-lab, основным элементом данных которого является массив, что позволяет решать задачи, в которых используются матрицы и вектора, в несколько раз быстрее, чем при использовании скалярных языков программирования (СИ, Фортран). В-третьих, обычно выше перечисленные объекты (графы, бинарные отношения, подстановки) изучают как изолированные области, матрицы же позволяют рассматривать их как совокупность взаимно связанных объектов.

В работе нас будут интересовать в первую очередь квадратные (0,1)-матрицы, так как именно использование оных при изучении графов дает больше полезной информации, нежели при рассмотрении прямоугольных матриц. Использование матриц смежпостей позволяет привлекать к изучению матриц графов свойства характеристических многочленов этих матриц и их спектров. Также плюсом является то, что квадратные матрицы с отличным от нуля определителем образуют группу относительно операции умножения. В этой группе матрицы, у которых det = 1 или det = —1, образуют подгруппу, включающую в себя группу ортогональных матриц.

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

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

Вторая глава посвящена применению квадратных (0,1)- матриц в изучении таких матричных свойств как разложимость (неразложимость), примитивность (импримитивность). Изложение доказательства теоремы о необходимых и достаточных условиях разложимости матрицы в терминах матриц бинарных отношений (см. [15, с. 432, теорема 6.2.23]) позволило извлечь из него конструктивный алгоритм приведения разложимой матрицы к специальному виду, через который, собственно, и дается определение разложимой матрицы. То есть разложимую матрицу А можно представить в следующем виде:

Л = РАР' = В С

В\

Сх

В2 02 с2

D] где Bi - квадратные неразложимые блоки, D - либо неразложимый блок, либо верхне треугольная матрица с нулевой диагональю. Данный канонический вид уточняет канонический вид предложенный в книге [5, с.373].

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

Ас = РАР' =

О 0 .

А21 О ^32 О О т О о о

О АЯ(Яe(e-i) О

На диагонали стоят квадратные нулевые матрицы.

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

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

В третьей главе рассматривается понятие перестановочного подобия матриц. То есть преобразования при котором переход от первой матрицы ко второй совершается с помощью умножения первой матрицы слева на некоторую матрицу перестановки Р ([15, с. 39, с. 430]), а справа на матрицу

Р' - транспонированную к Р (см. опр. (3.1.2)). Матрицу Р так же называют и матрицей подстановки ([13, с. 19]). Такое преобразование называется перестановкой рядов ([5, с. 352], то есть перестановка строк и точно такая же перестановка столбцов. Очевидно, что Р' = Р-1, а значит ([5, с. 80, опр. 10]) вышеуказанный переход является преобразованием подобия с матрицей перестановки. Такое преобразование называется преобразованием Р-подобия (перестановочного подобия, см. [15, с.183]).

Вводятся необходимые условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц.

Далее рассматривается автоморфизмы матриц бинарных отношений, то есть класс матриц G,i = {Р : PAP' = А}, Р - матрица перестановки, А -матрица бинарных отношений.

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

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

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

Помимо рассмотрения набора матричных инвариантов вводится и следующее определение:

Определение. Назовем разнообразием матрицы А число всех различных строк в матрице А. Строки называются различными, если они отличаются друг от друга хотя бы одним элементом, располоо/сениым на одинаковых местах в строке.

На основе введенного опрделения составляется общий алгоритм проверки Р-иодобия матриц.

Далее рассматривается класс матриц смежностей обыкновенных графов, алгоритм проверки Р-подобия таких матриц и построения матриц перехода Р, а так же формулируются следующие две теоремы о необходимых и достаточных условиях Р-подобия:

Теорема. Для того, чтобы две симметричные матрицы А и В размерности [72,72], SpA = SpB = 0, были Р-подобными необходимо и достаточно, чтобы существовала такая матрица Р, что главные миноры второго порядка матриц В и РАР' совпадали.

Теорема. Для того, чтобы две симметричные матрицы А и В размерности [п,п], SpA = SpB = 1, были Р-подобными необходимо и достаточно, чтобы сущесгпвовала такая матргща Р, что диагональный ненулевой элементы переводился бы в аналогичный диагональный элемент и что главные миноры второго порядка матриц В и РАР' совпадали.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Беспалов, Александр Александрович

ЗАКЛЮЧЕНИЕ

Дальнейшие направления для рассмотрения и изучения, интерес к которым напрямую вытекает из полученных в данной работе результатов:

- изучение остальных классов бинарных отношених матричным методом (в работе был успешно рассмотрен класс ацикличного бинарного отношения)

- машинная реализация полученного в четвертой главе алгоритма проверки Р-подобия матриц

- как связан вектор Фробениуса-Перрона матрицы А с размерностью групп автоморфизмов матрицы А

- совершенствование общего алгоритма проверки Р-подобия матриц смежностей графов

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1998.

2. Басакер Р., Саати Т. Конечные графы и сети. М., 1997.

3. Беспалов А.А. Р-подобие матриц. // Устойчивость и процессы управления Т.2 Секции 6-8 : Труды между народи ой конференции. 2005. С. 731-740.

4. Беспалов А.А., Хитров Г.М. Один алгоритм исследования матриц на разлоэюимость и примитивность. // Процессы управления и устойчивость: Труды XXXIV конференции аспирантов и студентов. 2003. С. 321-328.

5. Гантмахер Ф.Р. Теория матриц. М., 19G7.

6. G. Горьковой В.Ф. Лекции по математическим основам информационно-логических систем. СПб., 2003, 174 с.

7. Зыков А.А. Основы теории графов. М., 1987.

8. Кристофпдес Н. Теория графов. Алгоритмический подход. М., 1997.

9. Макаров И.М., Виноградская Т.М., Рубчинский А.А., Соколов В.Б. Теория выбора и принятия решений. М., 1982.

10. Математическая 'лщиклопедая. Том 1. М., 1977.

11. Никайдо X. Выпуклые структуры и математическая экономика. М., 1972.

12. Оре О. Теория графов. М., 2003.

13. Тараканов В.Е. Комбинаторные задачи и (0,1)-матрицы. М., 1985.

14. Харари Ф. Теория графов. М., 2003.

15. Хорн Р., Джонсон Ч. Матричный анализ. М., 1989.