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

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

Содержание
Введение

Глава 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. Общий алгоритм построения нормальной формы
произвольной матрицы
Глава 3. Приложения (использование нормальной формы)
§ 3.1. Применение нормальной формы матрицы графа в задаче
изоморфизма заданного графа к подграфу другого графа
§ 3.2. Полное исследование обыкновенных графов пятого порядка
§ 3.3. Исследование орграфов пятого порядка
§ 3.4. Поиск максимальной клики
Заключение
Приложение (коды программ)
Литература
Введение
Тема моей диссертационной работы - «Нормальная форма квадратных (ОД)-матриц и ее применение». Вначале тема моих исследований формулировалась как «Нормальная форма квадратных неотрицательных разложимых матриц». Предполагалось, что мои исследования будут продолжением исследований, изложенных в книге Гантмахера Ф.Р. «Теория матриц» в соответствующем параграфе [1, стр. 182-184], поскольку моим научным руководителем Хитровым Г.М. в его статье [2] была показана незавершенность исследований темы Гантмахером. Научный руководитель обратил мое внимание на определение квадратной разложимой матрицы, как на особый вид матрицы, получающийся при перестановке строк и такой же перестановке столбцов. Он так же обратил мое внимание еще на несколько моментов. Во-первых, на критерий неразложимости матрицы, который требовал, чтобы сумма единичной и искомой квадратной матрицы в степени на единицу меньшую, чем размерность искомой матрицы, была строго положительной матрицей, а также на вытекающий отсюда критерий разложимости матрицы. Во-вторых, на замечание в книге [3], что при исследовании на разложимость, а также при исследовании на примитивность и импримитивность квадратной неотрицательной матрицы, можно вместо исходной неотрицательной матрицы использовать ее индикаторную матрицу, т.е. матрицу, полученную из неотрицательной матрицы заменой ненулевых элементов единицами, таким образом, мы приходим к (ОД)-матрицам. В-третьих, что любую квадратную (ОД)-матрицу можно интерпретировать как матрицу смежности графа. Третье замечание показывало, что задачу разложимости матрицы можно свести к задаче теории графов. Перечисленные замечания научного руководителя и были отправными точками моего исследования, которое, в конце концов, трансформировалось в тему, взятую в качестве названия диссертации.
Вернемся вновь к определению разложимой матрицы и сделаем несколько простых выводов из этого определения.
Определение 0.0.1 ГЗ, стр.4311. Матрица А е Мп называется разложимой, если либо
(a) п=1 иА=0, либо
(b) п> 2 и существует матрица перестановки Р е Мп и некоторое число г, 1 < г < п -1, такие что
РТАР

= А. (0.0.1)
ч0 Оу
Здесь Мп - множество квадратных матриц размерности п, а матрица А разбита на блоки вертикальными и горизонтальными полосами одинаковой размерности г и п-г соответственно. Если ввести в рассмотрение вектор-столбец е размерности п, определяемый как е = (1, 1,
V; орграфом называется граф СҐУ.Я) с произвольным бинарным отношением К на V. Матричные определения: обыкновенным графом называется класс квадратных симметричных с нулевой диагональю матриц, перестановочно подобных между собой; орграфом называется множество (класс) квадратных (0,1 )-матриц, перестановочно подобных между собой. Последнее определение орграфа совпадает с данным выше матричным определением графа, поэтому в данной работе под словом граф, будем понимать то, что выше мы определили как орграф, а то, что в большинстве учебников называется словом граф, будем называть обыкновенным графом.
Далее в данной работе употребляется также понятие обыкновенного орграфа, т.е. графа, соединение двух точек которого возможно только одной дугой и петель нет.
В соответствии с тремя различными, приведенными выше, определениями графа существуют различные способы задания графа.
Определимся вначале, что значит «задать» граф? Поскольку во все три определения графа входит понятие множества, то договоримся, что задать множество - это значит каким-то образом различить его элементы. Проще всего - перенумеровать элементы множества.
Понятно, что в указанном случае мы будем задавать не сам граф, а конкретное его представление. Это представление не единственное, поскольку зависит от нумерации элементов множества.
Первое и на наш взгляд самое простое задание графа - это представление его с помощью картинки (диаграммы) в соответствии с геометрическим определением графа. При этом, в соответствии с договоренностью выше, вершинам конкретного представления графа будут приписаны номера.
Так на рисунке 1.3.1 даны два представления одного и того же графа.