Данная работа посвящена изучению матриц бинарных отношений, то есть квадратных (ОД)-матриц, в контексте исследования графов, бинарных отношений и теории подстановок. Такой матричный подход, основанный на использовании (0,1)-матриц, достаточно удобен и логически оправдан по следующим причинам. Во-первых, потому что существует взаимно однозначное соответствие между матрицами и графами, матрицами и бинарными отношениями, матрицами и подстановками. Во-вторых, на данный момент существует достаточно мощный математический пакет Mat-lab, основным элементом данных которого является массив, что позволяет решать задачи, в которых используются матрицы и вектора, в несколько раз быстрее, чем при использовании скалярных языков программирования (СИ, Фортран). В-третьих, обычно выше перечисленные объекты (графы, бинарные отношения, подстановки) изучают как изолированные области, матрицы же позволяют рассматривать их как совокупность взаимно связанных объектов.
В работе нас будут интересовать в первую очередь квадратные (0,1)-матрицы, так как именно использование оных при изучении графов дает больше полезной информации, нежели при рассмотрении прямоугольных матриц. Использование, матриц смежностей позволяет привлекать к изучению матриц графов свойства характеристических многочленов этих матриц и их спектров. Также плюсом является то, что квадратные матрицы с отличным от нуля определителем образуют группу относительно операции умножения. В этой группе матрицы, у которых det = 1 или det — —1, образуют подгруппу, включающую в себя группу ортогональных матриц.
В этой подгруппе матрицы перестановок будут также образовывать свою подгруппу. Таким образом, можно изучать группу (ОД)-матриц используя ранее наработанный обширный научный материал по каждой из перечисленных выше групп.
В главе 1 рассматриваются основные понятия теории бинарных отношений в терминах квадратных (ОД)-матриц. Показана эффективность матричного подхода на примере изучения отдельных классов бинарных отношений, например ациклического бинарного отношения (см. теоремы (1.5.1), (1.5.2)). Вторая глава посвящена применению квадратных (0,1) — матриц в изучении таких матричных свойств как разложимость (неразложимость), примитивность (импримитивность). Изложение доказательства теоремы о необходимых и достаточных условиях разложимости матрицы в терминах матриц бинарных отношений (см. [15, с. 432, теорема 6.2.23]) позволило извлечь из него конструктивный алгоритм приведения разложимой матрицы к специальному виду, через который, собственно, и дается определение разложимой матрицы. То есть разложимую матрицу, А можно представить в следующем виде:
А = РАР' = В С Л о V.
D] где В{ - квадратные неразложимые блоки, D — либо неразложимый блок, либо верхне треугольная матрица с нулевой диагональю. Данный канонический вид уточняет канонический вид предложенный в книге [5, с.373].
На основе полученных результатов был дополнительно разработан и алгоритм исследования неразложимых матриц и приведения импримитивной матрицы к следующей канонической форме:
Аг = РАР' =.
О 0. а21 о.: Лю о о.
Aim О О о.
На диагонали стоят квадратные нулевые матрицы.
Необходимо заметить, что достоинство предложенных алгоритмов заключается не только в получении указанных канонических видов, но в нахождении матриц перестановок Р, осуществляющих переход от исходных матриц к их каноническим формам.
К тому же предложенные алгоритмы были упешно реализованы в качестве самостоятельной программы исследования выше указанных матричных свойств.
В третьей главе рассматривается понятие перестановочного подобия матриц'. То есть преобразования при котором переход от первой матрицы ко второй совершается с помощью умножения первой матрицы слева на некоторую матрицу перестановки Р ([15, с. 39, с. 430]), а справа на матрицу Р' - транспонированную к Р (см. опр. (3.1.2)). Матрицу Р так же называют и матрицей подстановки ([13, с. 19]). Такое преобразование называется перестановкой рядов ([5, с. 352], то есть перестановка строк и точно такая же перестановка столбцов. Очевидно, что Р' = Р" 1, а значит ([5, с. 80, опр. 10]) вышеуказанный переход является преобразованием подобия с матрицей перестановки. Такое преобразование называется преобразованием Р-подобия (перестановочного подобия, см. [15, с. 183]).
Вводятся необходимые условие Р-подобия матриц и достаточное условие Р-подобия для отдельного вида матриц.
Далее рассматривается автоморфизмы матриц бинарных отношений, то есть класс матриц Ga — {Р '¦ PAP' = А}} Р — матрица перестановки, Аматрица бинарных отношений.
В четвертой главе рассматривается матричная интерпретация изоморфизма графов, устанавливается взаимноодонозначное соответствие между изоморфизмом графов и перестановочным подобием соответствующим графам матриц смежностей.
В рассматриваемых нами терминах графы будут изоморфными, если их матрицы смежностей Р-подобны. Другими словами, чтобы установить, изоморфны два графа или нет, необходимо установить, можно ли с помощью преобразования Р-подобия от матрицы первого графа перейти к матрице второго графа. Если такой переход возможен, то мы не только устанавливаем изоморфизм графов, но и указываем соответствующую нумерацию вершин первого графа, то есть переход, задаваемый матрицей, от первоначальной нумерации к искомой нумерации, в которой обе матрицы графов будут одинаковыми.
Понятно, что поиск необходимой матрицы Р равносилен перебору (число матриц перестановок n-ого порядка равно п!). Однако мы резко сократим число подлежащих испытанию матриц Р, если будем рассматривать матричные инварианты преобразования Р-подобия. Несовпадение инвариантов ведет к отрицательному ответу на вопрос об изоморфизме рассматриваемых графов.
Помимо рассмотрения набора матричных инвариантов вводится и следующее определение:
Определение. Назовем разнообразием матрицы, А число всех различных строк в матрице А. Строки называются различными, если они отличаются друг от друга хотя бы одним элементом, располоэ/сенным на одинаковых местах в строке.
На основе введенного опрделения составляется общий алгоритм проверки Р-подобия матриц.
Далее рассматривается класс матриц смежностей обыкновенных графов, алгоритм проверки Р-подобия таких матриц и построения матриц перехода Р, а так же формулируются следующие две теоремы о необходимых и достаточных условиях Р-подобия:
Теорема. Для того, чтобы две симметричные матрицы, А и В размерности [п, п], SpA = SpB — 0, были Р-подобными необходимо и достаточно, чтобы существовала такая матрица Р, что главные миноры второго порядка матриц В и РАР' совпадали.
Теорема. Для того, чтобы две симметричные матрицы, А и В размерности [п, п], SpA = SpB 1, были Р-подобными необходимо и достаточно, чтобы существовала такая матрица Р, что диагональный ненулевой элементы переводился бы в аналогичный диагональный элемент и что главные миноры второго порядка матриц В и РАР' совпадали.
ЗАКЛЮЧЕНИЕ
Дальнейшие направления для рассмотрения и изучения, интерес к которым напрямую вытекает из полученных в данной работе результатов:
• изучение остальных классов бинарных отношений матричным методом (в работе был успешно рассмотрен класс ацикличного бинарного отношения).
• машинная реализация полученного в четвертой главе алгоритма проверки Р-подобия матриц.
• как связан вектор Фробениуса-Перрона матрицы, А с размерностью групп автоморфизмов матрицы А.
• совершенствование общего алгоритма проверки Р-подобия матриц смежностей графов.
