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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

БЕСПАЛОВ Александр Александрович

МАТРИЦЫ БИНАРНЫХ ОТНОШЕНИЙ И ИХ ПРИМЕНЕНИЕ В ТЕОРИИ ГРАФОВ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2005 г.

Работа выполнена па факультете Прикладной математики - процессов управления Санкт-Петербургского государственного университета.

Научный руководитель: кандидат физико-математических наук,

доцент Хитров Геннадий Михайлович

Официальные оппоненты: доктор физико-математических наук,

профессор Жабко Алексей Петрович

кандидат технических наук, старший научный сотрудник Кочергин Сергей Васильевич

Ведущая организация: Петрозаводский государствешгый

университет

Защита состоится 2005 г. в Ж час. на

заседании диссертационного совета К-212.232.07 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском государственном университете по адресу: 190004, Санкт-Петербург, 10-я линия В.О., д. 33, ауд. .

С диссертацией можно познакомиться в научной библиотеке им. А. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан " 17 " огШ^/иЭ 2005 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Г

В.Ф. Горьковой

¿M69JW

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Матрицы бинарных отношений, то есть квадратные (0,1)-матрицы, успешно применяются в теории бинарных отношений, в теории графов, в теории выбора и принятия решений, математической экономике, но как вспомогательный аппарат. Данная работа посвящена выделению класса матриц бинарных отношений как отдельного объекта.

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

К классу матриц бинарных отношений можно также отнести и класс так называемых индикаторных матриц, то есть матриц, полученных из произвольной матрицы заменой ненулевых элементов единицами. Поскольку относительно свойств разложимости, примитивности и импримитивности исходные квадратные неотрицательные матрицы и их индикаторные матрицы эквивалентны, то увеличивается актуальность и важность задач и изучения матриц бинарных отношений. Применение индикаторных матриц (или что тоже матриц бинарных отношений) упрощает изучение свойств разложимости, примитивности и импримитивности произвольных матриц, что важно в вычислительной математике и математической экономике. Готовых алгоритмов исследования выше указанных классов матриц в таких математических пакетах как Matlab, Maple не было обнаружено, то есть построенная полученным данным самостоятельная программа является уникальной и значительно упрощает математические и практические исследования упомянутых матриц.

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

рос. НАЦиенлльнля

библиотека

3

вэ"яи^З^Х^

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

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

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

- исследованию разложимости и импримитивности матриц: изучению канонического вида, построению и реализации алгоритмов приведения исходных матриц к соответсвуюшему каноническому виду при одновременном получении матриц перехода к каноническому виду

- изучению перестановочного подобия матриц

матричному методу исследования изоморфизма графов, построению алгоритмов проверки изоморфизма графов

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

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

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

Основные положения, выносимые на защиту:

1. Предложенный матричный подход к изучению теории бинарных отношений и графов.

2. Теорема о каноническом виде ацикличного бинарного отношения.

3. Алгоритмы (и соответствующий материал, предшествующий построению алгоритмов) исследования разложимых и неразложимых матриц.

4. Результаты исследования перестановочного подобия матриц, связь с изоморфизмом графов. Определение разнообразия матриц.

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

6. Теоремы о необходимых и достаточных условиях Р-подобия матриц смежностей обыкновенных графов.

7. Алгоритм проверки Р-подобия матриц смежностей обыкновенных графов (и соответствующий материал предшествующий построению алгоритмов).

Апробация работы. Основные положения диссертации и полученные результаты докладывались на научных конференциях "Процессы управления и устойчивость" факультета Прикладной математики и процессов управления (г. Санкт-Петербург, 2002-2003 гг.), а так же на конференции 8СР'2005 (г. Санкт-Петербург, 2005 г.).

Публикации. Все результаты выполнешгых исследований

опубликованы в количестве четырех работ. (Две в трудах научных конференция "Процессы управления и устойчивость", одна в "Вестнике СПбГУ" и одна в трудах международной конференции "Устойчивость и процессы управления" (8СР'2005).

Структура и объем работы. Диссертациошюя работа состоит из введения, четырех глав, заключения и списка литературы, включающего 15 наименований. Общий объем диссертации 67 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приведен ряд определений базовых понятий, знание которых необходимо для понимания хода рассуждений в работе. Расписывается сам ход проводимых исследований (по главам), причины использования и достоинства рассматриваемого в работе матричного метода.

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

Теорема. Пусть матрица А(11) 6 Мп соответствует ацикличному отношению Я (далее такую матрицу будем для простоты называть ацикличной), тогда

1. матрица А(В.) имеет нулевые столбцы.

2. матрица А(Н) может быть приведена к виду

(0 А ,2 * * \

0 0 л23 *

0 0

0 0 • • • ^8,8 + 1

V о 0 0 0 0/

где наддиагональные блоки fie имеют нулевых столбцов.

3. длина наддиагонали s совпадает с длиной у максимальных путей в соответствующем графе.

Замечание. Второе утверждение теоремы является необходимым и достаточным условием ацикличности бинарного отношения В, соответствующего матрице А{В).

Замечание- Третье утверждение теоремы уточняет соответствующую теорему 2 из книги Макарова И.М. и др. "Теория выбора и принятия решений" на с. 31, сформулированную в терминах цепи, в которой, по сути, утверждается, что я > (¡.

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

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

Вторая глава посвящена применению квадратных (0,1)-матриц в изучении таких матритшых свойств как разложимость (неразложимость), примитивность (импримитивность). Изложение доказательства теоремы о необходимых и достаточных условиях разложимости матрицы в терминах матриц бинарных отношений (см. Хорн Р., Джонсон Ч. "Матричный анализ", теорема 6.2.23, с. 432) позволило извлечь из пего конструктивный алгоритм приведения разложимой матрицы к специальному виду, через который, собственно, и дается определение разложимой матрицы. Глава 2 как раз и иллюстрирует построение данного алгоритма. На основе полученных результатов был дополнительно разработан и алгоритм исследования неразложимых матриц и приведения импримитивной матрицы к канонической форме. Таким образом, построены и реализованы в качестве самостоятельной программы алгоритмы исследования выше указанных матричных свойств, приводящие в случаях разложимости и импримитивности к следующим каноническим видам:

Для разложимой матрицы матрицы А:

А = PAP' =

( В

\

С

Di

Oi

Сг

В2 02

С2

Р]

/

где Вг - неразложимые квадратные блоки, И - либо верхне треугольная матрица с нулевой диагональю, либо неразложимая. Для импримитивной матрицы А:

Аг = PAP' =

( О

A2i

V О

о о

¿32

О

О А,

(5-1)

Alm \ О

О /

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

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

В третьей главе ведется речь о перестановочном подобии матриц.

Определение. Матрицы А и В будем называть Р-подобными, если выполняется соотношение PAP' — В, причем Р - матрица перестановок.

Определение. Две матрицы А и В, связанные отношением В = Т~гАТ, где Т - некоторая неособенная матрица, называются подобными.

Замечание. Сравнивая определения выше предложенные определения, видим, что Р -подобие является частным случаем подобия матриц.

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

Утверждение. Чтобы матрицы Л и В были Р-подобными, необходимо одновременное выполнение следующих равенств

PsA — Sß и PqA = Чв, (!)

где sa, sb - вектора строчных сумм, а цл-. qn - вектора столбцовых сумм матриц А и В соответственно, Р - матрица перестановок из . соотношения PAP1 = В.

Утверждение. Если же в векторе аЛ все элементы различны, t то вышеуказанное утверждение будет и достаточным условием Р-

к подобия матриц А и В.

Пример. Рассмотрим случай показывающий недостаточность условия (1). Пусть Т и F- перестановочные матрицы одинаково размерности такие, что их характеристические многочлены различны. Очевидно, что st — sf = qr = qf = e и sf — Pst и qp = Pq-r для любой пересташвочной матрицы Р, то есть условие (1) выполнено. Но матрицы Т и F не могут быть перестановочно подобными, так как их характеристические многочлены не совпадают.

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

Определение. Под автоморфизмом будем понимать отображение матрицы самой на себя посредством преобразования Р-подобия.

Очевидно, что класс Ga будет образовывать группу, которую t в дальнейшем будем называть группой автоморфизмов. Не трудно

видеть, что G/i представляет собой класс матриц, перестановочных с А.

. Утверждение. Класс матриц Ga отличен от тривиальной

подгруппы, совпадающей с единичной матрицей Е, тогда и только тогда, когда Р-подобие матриц А и В {А ^ В) не единственно, то есть существуют матрицы Р\ и Р2 такие, что Р\ ф Pi и Р\АР[ — В и Р2АР\ = В.

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

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

Определение. Конечным графом G = (X, R) называется пара (X, R), где X - конечное множество вершин, a R - бинарное отношение на X.

Из данного определения следует, что как только вершины графа G ~ (X, R) перенумерованы, так бинарному отношению R однозначно сопоставляется матрица А, которую в дальнейшем будем называть матрицей графа. Все сказанное выше относительно матриц бинарных отношений, очевидно, переносится на матрицы графа. Иногда введенную выше матрицу бинарных отношений (следовательно, и матрицу графа) называют матрицей смежностей или матрицей смежности.

Определение. Два графа G — (X. R) и II = (Y, Q) называются изоморфными, если существует биекция <р : X —>> Y, такая, что для всех х, у е X uz,teY, для которых <р(х) = z, ip(y) = t, из того, что xRy в G следует, что zQt в И.

Это определение можно переписать в следующем виде:

Определение. Два графа G = (X, R) и Н = (Y, Q) называются изоморфными, если существует нумерация элементов множеств X

, Х2 Хп } и Y = {уЛ, у2,..., Уп), определяющая функцию ip(xt) = yt такую, что (x,,xj) £ R тогда и только тогда, когда, (уг, у}) € Q.

Выше указанное определение эквивалентно следующим определениям:

Определение. Два графа G = (X. R) и II = (Y, Q) будем пазъьвать изоморфными, если существует такая нумерация элементов множеств X и Y, при которой им будет соответствовать одна и та же матрица смежности.

Определение. Два графа G — (X, R) и Н = (Y, Q) будем называть изоморфтлми, если их матрицы смежности Р-подобны между собой.

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

смежности А и В. Другими словами, проблема сводится к отысканию такой матрицы Р, что PAP' — В, Если такая матрица существует, то графы G и Н изоморфны, если не существует, то графы не изоморфны.

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

Пусть при произвольной нумерации графу G соответствует матрица А, графу Я в его собственной нумерагщи - матрица В, таким образом проблема изоморфизма графов сводится к проблеме Р-подобия соответствующих им матриц смежности Ли В.

Далее рассматриваются матричные инварианты преобразования Р-подобия.

Вводятся обозначения: <sA — Ае, qA = А'е. Нетрудно видеть, что s д

- вектор строчных сумм, а qA - вектор столбцовых сумм матрицы А, е

- единичный вектор е — (1,1,..., 1)'.

Утверждение. Матрица А из нулей и единиц будет являться матрицей перестановки тогда и только тогда, когда яА — qA = с.

Рассмотрим две Р-подобные матрицы А и В (В = PAP'). Из В = PAP' следует, что sB = Ве = (РАР')е = РАе = Р.чА. Аналогично получаем, что гщ = PqA- Далее В2 = (РАР')(РАР') = PAP'PAP' = РА2Р'. Отсюда следует, что = PsA2, qB2 = PqA2 и вообще sBk = PsAk, qBk = PqAi- для степени k. Последнее означает, что состав строчных и столбцовых сумм степеней матрицы является инвариантом преобразования Р-подобия (элементы столбцов разве лишь переставляются).

К рассмотрению степеней матриц приводит и следующее наблюдение. Р-подобие матриц есть частный случай подобия. Из подобия следует равенство характеристических многочленов подобных матриц, откуда вытекает, что коэффициенты характеристического многочлена — инварианты преобразования Р-подобия. Коэффициенты многочлена, в соответствии с формулами Виета с точностью до знака, являются основными симметрическими многочленами от корней многочлена. Они однозначно выражаются через степенные суммы корней многочлена с помощью формул Ньютона. Степенные суммы корней для характеристического многочлена матрицы есть не что иное,

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

Обозначим через В,\ диагональную матрицу, полученную из матрицы А, то есть

Da =

(ац 0 ... О Ö22

V о 0 ...

О \

О

О /

Введем в рассмотрение вектор йл — (ац-а'22, ..., апп)'. Для рассматриваемых выше Р-подобных матриц Ац В Ив = РОдР' и йв = Р(1а, и вообще ИВк = РОАкР' и йвк = РИдк.

Сказанное выше относительно инвариантов вЛк и длк имеет место и относительно инвариантов ЛАк, к = 1,2,....

Пусть Р-подобные матрицы Ли В неразложимые и пусть

В = PAP', ВХв = ХвХв, АХа = ЛАХа, (2)

где Ал, Лв - числа Фробениуса-Перрона, ХА > 0 и Хв > 0 - вектора Фробениуса-Перрона матриц Au В, Будем полагать, что

е'Хл = е'Хв = 1. (3)

Из подобия матриц А и В следует равенство корней характеристических многочленов, в частности следует равенство Ал = Ад. Из свойств неразложимых неотрицательных матриц следует единственность векторов Xл и Хв, удовлетворяющих соотношению

(3).

Возьмем соотношения (2) и рассмотрим цепочку следствий вытекающую из них:

АХа = ХАХЛ =>• РЛХА = ХЛРХА => РЛР'РХа = \АРХА В(РХА) = Ла(РХа) => В(РХа) = \в(РХА) = РХА.

Таким образом мы показали, что при преобразовании Р-подобия состав вектора ХА не меняется. Может меняться лишь только порядок элементов вектора ХА,

Введены еще два определения, характеризующих неотрицательные матрицы.

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

Если обозначим через ра разнообразие матршщ А, то очевидно, что Ра < щ где п - число строк матрицы. Разнообразие вектора - частный случай разнообразия матрицы.

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

Очевидно, что матрицы А и В могут быть подозрительными на Р-подобие тогда и только тогда, когда Ад равно Лв и матршщ Ил — (вл, Ял ■ Л л, Ха), Рв = (^в,Чв-дв,Хв) имеют одинаковый состав. Последние столбцы в матрицах ЯА и До, то есть ХА и Хц, это положительные нормированные (сумма координат равна единице) собственные вектора матриц Л и В, отвечающие собственным числам Ад и Лв соответственно. В этом случае, если рА = рцл = Ряв — п, то матрица Р (если преобразование Р-подобия существует) будет определяться единственным образом.

Если же рял = рн„ = к < п, то тогда число возможных матриц перестановок, используемых для проверки Р-подобия матриц А и В, будет равно га^пг! • • • п*!, что будет меньше п\ {п] (7 = -размерность групп одинаковых строк, а к - число групп одинаковых строк).

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

Обозначим через I квадратную матрицу из одних единиц, через К = I - Е - матрицу из единиц с нулевой диагональю (Е - единичная матрица), через А - матрицу смежности графа, через А матрицу А — I - Л, через А матрицу А = К - А (здесь А - матрица смежности обыкновенного графа). Тогда имеют место две следующие теоремы:

Теорема. Матрицы смежности А\ и Ао ~Р-подобны тогда и только тогда, когда V-подобны матрицы А\ и

Теорема. Матрицы смежностей обыкновенных графов А\ и А2 Т*-подобны тогда и только тогда, когда I*-подобны матрицы А^ и Л2.

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

Пусть у нас выполнены все необходимые условия Р-подобия для матриц смежностей А ж В размерности [п, п] обыкновенных графов.

1. Рассматриваем матрицу Л. Если количество нулей у этой матрицы меньше, чем (п — 1)п/2, то строим дополнительную матрицу А такую, что

/01 ... 1 \ 10 ... 1

А + А = К =

: ... 1 VI 1 ... 0 у

(4)

Тогда К = РКР' = Р(А+А)Р' = PAP' + PAP' = В+В, то есть задачу проверки Р-подобия матриц А и В мы можем заменить эквивалентной задачей проверки Р-подобия матриц Л и В на основании выше введенной теоремы.

2. Теперь начинаем работать с матрицами Л и В. У матрицы А число нулей больше, чем п(п — 1)/2. Если эта матрица разложима, то приводим ее к каноническому виду (метод описай во второй главе). И рассматриваем далее диагональные и надциагональные неразложимые блоки. Но так как наши матрицы симметритшые, то при применении алгоритма разбиения на неразложимые блоки, она становится в конетшом итоге квазидиагональной. Параллельно

проводим аналогичные действия и с матрицей В. Если надо, то для каждой неразложимой матрицы из диагональных блоков опять строим дополнительную, приводящую ее к виду (4), до тех пор пока не получим неразложимую матрицу с числом нулей большим, чем п(п — 1)/2.

Таким образом, в конечном счете данный алгоритм сводится к проверке Р-подобия двух неразложимых матриц с числом нулей большим, чем п(п - 1)/2.

3. Проверка Р-подобия для неразложимых матриц с числом нулей большим, чем п(п — 1)/2.

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

Далее строим вектор строчных сумм и ставим пашу единицу в блок с наименьшим числом различных элементов, то есть на диагональ, так чтобы она сказалась при учете строчных сумм указанного блока. Во второй матрице тоже ставим единицу на аналогичное место. И начинаем возводить матрицы в степень. Если же в процессе возведения в степень мы получаем различные составы у создаваемых матриц В'л и Я1В, для некоторого I, то ставим единицу у второй исходной матрицы на второе соответствующее место место в рассматриваем подозрительном на подобие блоке и начинаем заново возводить в степень.

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

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

3.3. Если же вне зависимости от расстановки единицы в

подозрительном блоке второй матрицы у нас Р-подобие не осуществляется, то значит исходные матрицы не Р-подобны.

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

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

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

В заключении описаны дальнейшие направления для исследования, вытекающие из результатов диссертациошюй работы.

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ

РАБОТЫ:

1. Беспалов A.A. О матрицах бинарных отношений // Процессы управления и устойчисвость: Труды ХХХШ научной конференции студентов и аспирантов. 2002. С. 456-460.

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

3. Беспалов A.A. Матричный метод проверки изоморфизма графов. // Вестник Санкт-Петербургского университета. Сер. 10. 2004. Вып. 3. С. 3-12.

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

Подписано в печать ¡и .09.2005. Формат бумаги 60x84 1/16 Бумага офсетная Печать ризографическаная Усл. печ л. 1,0.

Тираж 100 экз. Заказ 3657. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ. 198504, Санкт-Петербург, Старый Петергоф, Универсшетский пр 26

/

I

j

4

I

I (

!

0

1

i

h

ч

! I

Р165 2 7

РНБ Русский фонд

2006-4 12407

Введение

Глава 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, были Р-подобными необходимо и достаточно, чтобы сущесгпвовала такая матргща Р, что диагональный ненулевой элементы переводился бы в аналогичный диагональный элемент и что главные миноры второго порядка матриц В и РАР' совпадали.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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.