Данная работа посвящена изучению матриц бинарных отношений, то есть квадратных (ОД)-матриц, в контексте исследования графов, бинарных отношений и теории подстановок. Такой матричный подход, основанный на использовании (ОД)-матриц, достаточно удобен и логически оправдан по следующим причинам. Во-первых, потому что существует взаимно однозначное соответствие между матрицами и графами, матрицами и бинарными отношениями, матрицами и подстановками. Во-вторых, на данный момент существует достаточно мощный математический пакет 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, были Р-подобными необходимо и достаточно, чтобы сущесгпвовала такая матргща Р, что диагональный ненулевой элементы переводился бы в аналогичный диагональный элемент и что главные миноры второго порядка матриц В и РАР' совпадали.
ЗАКЛЮЧЕНИЕ
.
Дальнейшие направления для рассмотрения и изучения, интерес к которым напрямую вытекает из полученных в данной работе результатов:
— изучение остальных классов бинарных отношених матричным методом (в работе был успешно рассмотрен класс ацикличного бинарного отношения).
— машинная реализация полученного в четвертой главе алгоритма проверки Р-подобия матриц.
— как связан вектор Фробениуса-Перрона матрицы, А с размерностью групп автоморфизмов матрицы А.
— совершенствование общего алгоритма проверки Р-подобия матриц смежностей графов.
