Матрицы бинарных отношений и их применение в теории графов

• Автор: Беспалов, Александр Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Санкт-Петербург
• Количество страниц: 67 с.

Глава 1. Матрицы бинарных отношений
1.1. Понятие бинарного отношения. Матрица бинарного отношения
1.2. Множество квадратных матриц из нулей и единиц
1.3. Операции над отношениями, основные определения
1.4. Определение цепи, пути. Ацикличное бинарное отношение и его свойства
1.5. Построение матрицы ацикличного отношения
Глава 2. Разложимые и неразложимые матрицы
2.1. Используемые определения
2.2. Теорема о разложимости и неразложимости в терминах матриц бинарных отношений
• 2.3. Алгоритм, позволяющий исследовать матрицы на разложимость
и приводящий разложимую матрицу к каноническому виду
2.4. Алгоритм исследования неразложимой матрицы и приведения
имирнмитивной матрицы к канонической форме
Глава 3. Перестановочное подобие матриц
3.1. Р-подобие матриц
3.2. Необходимое условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц
3.3. Автоморфизмы матриц перестановок

Глава 4. Матричный метод проверки изоморфизма графов
4.1. Изоморфизм графов, матричная интерпретация
4.2. Матричные инварианты преобразования Р-подобия
4.3. Общий алгоритм решения задачи Р-подобия
4.4. Матрицы смежностей обыкновенных графов
4.4.1. Алгоритм проверки Р-подобия матриц
4.4.2. Необходимые и достаточные условия Р-подобия
* Заключение
Литература

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

изоморфизма графов сводится к проблеме Р-иодобин соответствующих им матриц смежности А и В.
Пример 4.1..1 Рассмотрим два графа (7 = {Х,В) и Н = (У, <2 1), X = {1,7,3} и У = {а, Ь, с}. Пусть И = {(1,2), (9, 3), (3,8)} и <21 = {(а, с), (с, Ь), (Ь, а)}. Тогда биекция <р : X —* У, задаваемая перечислением р : 1 —> а, 2 —> с, 0 —» Ь, будет являться изоморфизмом.
В матричной интерпретации графам С = (Х,Я) и Н = (У,<20 У
- упорядоченное мноэ/ссство У, У

Vе
( 0 1 еЛ ( 0 0 А
А и В такие, что А = 0 0 1 и В — 1 0
Iі 0 1° 1
) соответствуют матрицы
Биекцию р
^10 0^
установит операция P-подобия с матрицей перестановок Р
0 0 1 0 1
и будет выполнено соотношение РАР' = В
Пример 4.1..2 Теперь расаиотрим два графа G = (X, R) (гіз предыдущего примера) и Но — (У, Q2), Q2 = {(а, 6), (с, а), (Ь, а)}. Очевидно, что графу Но будет взаимно однозначно соответствовать следующая матрица:

0 1 о
1 о о
О О
Нетрудно видеть, что матрица Во может быть получена хю матрицы В (см. предыдугций пример) перестановкой двух последних столбцов.