WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. ТРАПЕЗНИКОВА РАН

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

УДК 519.177:519.173:519.816 Чеботарев

Павел Юрьевич МЕТОДЫ ЛАПЛАСОВСКОЙ ТЕОРИИ ОРГРАФОВ В СТРУКТУРНОМ АНАЛИЗЕ СИСТЕМ

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Москва - 2008

Работа выполнена в Учреждении Российской академии наук Институте проблем управления им. В.А. Трапезникова РАН

Официальные оппоненты:

доктор физико-математических наук профессор В.В. Дикусар доктор физико-математических наук Г.А. Кошевой доктор технических наук профессор В.В. Подиновский Ведущая организация - Московский государственный университет им. М.В. Ломоносова

Защита состоится 2008 г. в ч. на заседании диссертационного совета Д 002.226.02 при Институте проблем управления им. В.А. Трапезникова РАН по адресу: 117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В.А. Трапезникова РАН.

Автореферат разослан 2008 г.

Ученый секретарь диссертационного совета кандидат технических наук В.Н. Лебедев

Общая характеристика работы

Актуальность темы. В ряде задач управления, системного анализа и информатики (управление многоагентными системами, декомпозиция больших систем, кластеризация, агрегирование экспертных предпочтений, анализ сетей различной природы, теория баз данных, теория параллельных вычислений, химическая информатика, наукометрия и др.) графы, моделирующие соответствующие структуры, исследуют посредством анализа матриц, сопоставленных этим графам. Характеристики таких матриц - их ранги, спектры, собственные подпространства, собственные проекторы, миноры, коэффициенты характеристических многочленов, обратные и обобщенно-обратные матрицы и др. - доставляют важную информацию не только о соответствующих графах и сетях, но и о характере функционирования моделируемых систем. Посредством матричных вычислений информация такого рода может быть получена без использования трудоемких переборных алгоритмов. Анализом взаимосвязи свойств графов и соответствующих им матриц занимается алгебраическая теория графов, которая берет свое начало со знаменитой матричной теоремы о деревьях, полученной в середине XIX века в разных вариантах Кирхгофом, Сильвестром и Борхардтом.

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

уже в 60-70-е гг. существенные продвижения в ней были получены работавшим тогда в Институте проблем управления А.К. Кельмансом.

К настоящему времени лапласовская теория неориентированных графов довольно хорошо разработана. Еще в 90-е годы вышли обзоры Своим названием она обязана процессу дискретизации оператора Лапласа, приводящему к матрицам такого рода.

P. Мерриса с соавторами и Б. Мохара, а также монография Ф.Р.К. Чанг, в которых были систематизированы более ранние результаты и представлены оригинальные результаты авторов этих работ.

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

1. Децентрализованное управление многоагентными системами.

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

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

3. Кластер-анализ. Один из подходов к кластеризации на графах связан с нахождением спектров и собственных подпространств их лапласовских матриц.

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

В задачах анализа социальных сетей элементу сети ставят в соответствие значения центральности/периферийности, совокупной силы связи с другими элементами, баланса входящих и исходящих связей и др.; пару элементов характеризуют показателями силы, длины, направления связей между ними, индексами сходства их профилей связности и “ролей” в сети; дуги и Этот оператор часто называют оператором достижения консенсуса.

пути характеризуют пропускной способностью по отношению к информации и управляющим воздействиям, критичностью разрыва по отношению к связности сети; сеть в целом оценивают степью связности, сплоченности, однородности, взаимности связей и т. д. Потребность в “оцифровке” возникает и при анализе/синтезе транспортных, компьютерных, организационных, семантических и других сетей, а также баз данных. Другой класс задач, требующий специальной оцифровки вершин графов, - агрегирование экспертных оценок, оценка силы участников турнира, если турнир некруговой или данные неполные, или план парных сравнений не сбалансирован. Далее, следует упомянуть популярную в последнее время задачу ранжирования интернет-страниц, найденных поисковой машиной по пользовательскому запросу (PageRank problem): ранжирование производится с использованием орграфа ссылок страниц друг на друга. Наконец, задачи такого типа нужно решать при разработке алгоритмов работы распределенных компьютерных рекомендательных систем, где каждый пользователь, указав свои музыкальные, литературные, кинематографические и т. п.

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

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

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

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

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

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

• Исследование лапласовских спектров орграфов;

• Разработка методов классификации остовных3 лесов (ор)графов;

• Разработка методов анализа (ор)графов с помощью классификации остовных лесов и с использованием матриц лесов;

• Установление соотношений между матрицами лесов с одной стороны и лапласовской матрицей, ее собственным проектором, матрицами, обобщенно обратными к ней, и другими матрицами орграфа - с другой;

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

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

Научная новизна. В работе разработаны основы лапласовской теории ориентированных графов и ее применений, в том числе:

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

структурных индексов графов. Введен класс лесных метрик графа и изучены его свойства; установлены связи между лесными метриками и резисторной метрикой графа.

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

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

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

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

6. Разработан нормативный подход к анализу мер близости вершин графов и орграфов. Введено понятие функций -близости и установлена их двойственность метрикам.

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, ЦЭМИ РАН, Институте вычислительной математики РАН, ИСЭП РАН, в университетах Барселоны, Кана, Ванкувера, Тампере, на общемосковском семинаре “Математические методы в экспертных оценках и анализ данных”, на 6 Всесоюзной школе-семинаре по непараметрическим и робастным методам статистики в кибернетике и информатике (Томск, 1987 г.), 3 Всесоюзной школе-семинаре “Программноалгоритмическое обеспечение прикладного многомерного статистического анализа” (Цахкадзор, 1987 г.), Всесоюзной научно-практической школесеминаре “Программное обеспечение ЭВМ: индустриальная технология, интеллектуализация разработки и применения” (Ростов-на-Дону, 1988 г.), 3 Всесоюзной конференции “Методы социологических исследований” (Звенигород, 1989 г.), 7 Всесоюзной школе-семинаре по непараметрическим и робастным методам статистики в кибернетике и информатике (Иркутск, 1990 г.), Всесоюзном совещании “Пути повышения качества прогнозов” (Ленинград, 1990 г.), 3 Всесоюзной школе-семинаре “Комбинаторностатистические методы анализа и обработки информации, экспертное оценивание” (Одесса, 1990 г.), Всесоюзном научно-практическом семинаре “Интеллектуальное программное обеспечение ЭВМ” (Терскол, 1990 г.), 4 Всесоюзной школе-семинаре “Статистический и дискретный анализ данных и экспертное оценивание” (Одесса, 1991 г.), 5 Международной конференции “Статистический и дискретный анализ данных и экспертные оценки” (Одесса, 1995 г.), Международной конференции по анализу порядковых и символьных данных (Париж, 1995 г.), 5 Конференции Международного общества по линейной алгебре (Атланта, 1995 г.), 9 Европейском симпозиуме психометрического общества (Лейден, 1995 г.), 3 Международной конференции “Эконометрические модели принятия решений: конструирование целевых функций” (Хаген, 1995 г.), Российско-испанском семинаре по групповому выбору (Барселона, 1995 г.), Международном семинаре по агрегированию информации и решений (Вашингтон, 1996 г.), 3 Международном симпозиуме Общества социального выбора и благосостояния (Маастрихт, 1996 г.), Международной научно-практической конференции “Управление большими системами” (Москва, 1997 г.), 7 Конференции Международного общества по линейной алгебре (Мэдисон, 1998 г.), 1 Международной конференции по проблемам управления (Москва, 1999 г.), 20 Международной конференции по социальным сетям (Ванкувер, 2000 г.), 5 Международном симпозиуме Общества социального выбора и благосостояния (Аликанте, 2000 г.), Международной конференции по анализу порядковых и символьных данных (Брюссель, 2000 г.), 7 Конференции Международной федерации обществ классификации (Намюр, 2000 г.), 4 Международной конференции “Эконометрические модели принятия решений: конструирование и применение целевых функций” (Хаген, 2000 г.), 2 Международной конференции “Логика, теория игр и социальный выбор” (Санкт-Петербург, 2001 г.), Международной конференции по линейной алгебре (Хайфа, 2001 г.), 2 Европейском семинаре по алгебраической теории графов (Эдинбург, 2001 г.), Международной конференции “Теория полезности и ее применения” (Триест, 2002 г.), Международной конференции по матричному анализу и его применениям (Форт Лодердейл, 2003 г.), 13 Конференции Международного общества по линейной алгебре (Амстердам, 2006 г.), Международной конференции обществ GAMM и SIAM по прикладной линейной алгебре (Дюссельдорф, 2006 г.).

Публикации. Материал диссертации опубликован в 77 работах, среди которых 22 - статьи в ведущих рецензируемых журналах (список ВАК России) [1-4,17,18,22,28-33,37,43,44,46,47,50,52,57,59], 21 - статьи в других изданиях [5-10,12,14-16,20,34,38,41,45,51,53-56,58] и 34 - тезисы докладов (объемом не более 3 страниц), в том числе [11,13,19,21,2327,35,36,39,40,42,48,49]. 18 работ опубликовано по смежной теме - кооперативному принятию решений, из них 4 - в журналах из списка ВАК РФ.

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

изложено на 279 страницах.

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

В первой главе дан обзор направления в алгебраической теории графов, развившегося из матричной теоремы о деревьях (Г. Кирхгофа и Дж. Сильвестра), сформулирована матричная теорема о лесах и приведены два ее доказательства. Данная теорема была получена при поиске теоретико-графовой интерпретации оценок обобщенного метода суммы очков - разработанного автором метода агрегирования неполных предпочтений (ему посвящена глава 7 диссертации).

В терминологии теории графов мы следуем в основном Ф. Харари.

Пусть G - взвешенный мультиграф с множеством вершин V (G) = {1,...,n} и мультимножеством4 ребер E(G); - взвешенный мультиорграф5 с множеством вершин V () = {1,..., n} и мультимножеством дуг E(); n > 1.

Ребро - неупорядоченная пара вершин; дуга - упорядоченная пара вершин.

Через p > 0 обозначим вес p-го ребра (дуги) из i в j. = (ij) E ij матрица суммарных весов ребер (дуг) для пар вершин:

nij ij = p, i, j = 1,..., n, ij p=где nij - число ребер (дуг), соединяющих i с j. ij = 0 тогда и только тогда, когда из i нет ребер (дуг) в j. Произведение весов всех ребер (дуг) подграфа H мультиграфа G (мультиорграфа ) называем весом H и обозначаем (H). Вес подграфа, не имеющего ребер (дуг), принимается равным 1. Для непустого множества подграфов его вес есть G В мультимножестве допускается кратное вхождение элементов.

В работе всюду рассматриваются взвешенные мультиграфы и мультиорграфы; прилагательное “взвешенный” и префикс мульти- будем иногда опускать.

( ) = (H).

G H G Вес пустого множества равен нулю.

Определение. Лапласовская матрица взвешенного мультиорграфа это (n n)-матрица L = L() = (ij) с элементами ij = -ij, j = i, ii = - ij, i = 1,..., n.

j=i Матрица Кирхгофа взвешенного мультиорграфа - это (n n)-матрица L = L() = (ij) с элементами ij = -ji, j = i, ii = - ij, i = 1,..., n.

j=i Отличие определений лапласовской матрицы и матрицы Кирхгофа - порядок индексов в выражениях недиагональных элементов. Лапласовской матрицей представляется линейный оператор согласования характеристик (оператор достижения консенсуса), входящий в большинство дифференциальных и дискретных моделей децентрализованного управления многоагентными системами. Это приложение лапласовской теории орграфов рассмотрено в главе 5 диссертации.

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

• • Через () = и () = обозначаем множество всех F• F• Fk Fk остовных исходящих лесов мультиорграфа и множество всех остовных i•j исходящих лесов с k дугами. и - множество всех остовных Fi•j Fk исходящих лесов, где j принадлежит дереву, исходящему из i, и множество таких же остовных исходящих лесов с k дугами. Соответствующие обознаi•j • чения для входящих лесов:, и. Аналогичные F•, Fk Fi•j Fk ij обозначения для неориентированных графов:,, и.

F F Fij Fk k Рассмотрим матрицы W = W (G) = I + L(G), W = W () = I + L(), W = W () = I + L(), -1 - где I - единичная матрица. Пусть Q = (qij) = W, Q = (qij) = W (если эти матрицы существуют).

Теорема 1.4 (матричная теорема о лесах)6.

1. Для любого взвешенного мультиграфа существует матрица Q, и qij = ( ) ( ) = ( ) ( ), i, j = 1,..., n.

Fji F Fij F 2. Для любого взвешенного мультиорграфа существуют матрицы Q, Q, и qij = ( ) ( Fi•j F•), qij = ( ) ( ), i, j = 1,..., n.

Fj•i F• В главе 1 приведены два доказательства этой теоремы и указаны ее взаимосвязи с другими результатами алгебраической теории графов. Существенная часть результатов диссертации связана с этой теоремой.

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

гочлена и псевдообратной по Дразину AD через любой ненулевой аннулирующий многочлен для Au, где u ind A.

Пусть A Cnn - квадратная матрица. Через (A) и (A) обоR N значаем образ и ядро A соответственно. Индексом A, ind A, называют наименьшее k II N{0}, при котором rank(Ak+1) = rank(Ak). Пусть ind A = .

Собственным проектором (главным идемпотентом) матрицы A, соответствующим собственному значению 0, или, для краткости, собственным проектором A называют такой проектор (т. е. идемпотентную матрицу) Z, что (Z) = (A) и (Z) = (A). Собственный проектор единствен, R N N R т. к. проектор определяется своим образом и ядром.

Теорема 2.1. Пусть ind A = ; u II {0}, u . Тогда для любого N многочлена () = t(q + p1q-1 +... + pq) (pq = 0), аннулирующего для Au, матрица Z = h(Au), где h() = p-1(q + p1q-1 +... + pq), - собственный проектор для A.

q Пусть 1,..., s - различные собственные значения A. Через k обозначим индекс собственного значения k (k = 1,..., s), т. е. размер наибольшей жордановой клетки A, соответствующей k, равный степени множителя ( - k) в минимальном многочлене A. Собственным проектором A, соответствующим k, называют собственный проектор матрицы A - kI.

Найдя 1,..., s, можно использовать теорему 2.1 для нахождения соответствующих им собственных проекторов, что, в свою очередь, позволяет строить функции от матрицы. Для любой функции f : C C, имеющей в точках k (k = 1,..., s) конечные производные f(j)(k) порядков j = 0,..., k, по определению, s k- def f(A) = f(j)(k) Zkj, k=1 j=где f(0)(k) = f(k), а матрицы Zkj - так называемые компоненты A. Компонента Zk0 есть собственный проектор A, соответствующий k, а остальные компоненты находятся последовательным домножением Zk0 на A-kI и числовые коэффициенты:

Zkj = (j!)-1(A - k I)j Zk0. (2.16) Все компоненты линейно независимы, поэтому среди них нет нулеk вых. При этом для всех k = 1,..., s (A - kI) Zk0 = 0. Таким образом, после нахождения компоненты Zk0 с помощью теоремы 2.1 остальные компоненты Zkj вычисляются по формуле (2.16); процедура заканчивается, когда получен 0. Найденное число компонент равно k.

Теперь знание k и k позволяет построить минимальный многочлен s k для A: () = ( - k). Итак, начав с нахождения собственных k=значений A и аннулирующих многочленов для (A - kI)u, u ind(A kI), k = 1,..., s, далее находим собственные проекторы, соответствующие всем собственным значениям, а также компоненты A, индексы собственных значений и минимальный многочлен для A.

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

Теорема 2.2. Пусть A Cnn имеет индекс и собственный проектор Z; пусть 1,..., s - все ее различные собственные значения, 1,..., s - их индексы, а целые числа u, u1,..., us таковы, что u и ui i (i = 1,..., s). Тогда i (Au - uI)u i i: i= u Z =, (2.17) i (-u ) i i: i= u i k k (A - kI)u - (i - k)u I i =k Zkj = (j!)-1(A - k I)j, (2.18) uk i -(i - k)u i =k где k = 1,..., s, j = 0,..., k - 1.

Теорема 2.2 обобщает известную формулу, верную для недефектных матриц. Результаты главы 2 применяются в главе 3, где, в частности, изучаются собственные проекторы матриц Кирхгофа и Лапласа.

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

Обсуждается применение матриц максимальных лесов в задаче выявления структуры орграфа. Другие их применения - в задачах агрегирования предпочтений и измерения близости вершин взвешенного орграфа - изложены в главах 6 и 9. Ниже приводятся основные результаты главы 3 и необходимые определения.

Остовный исходящий лес F мультиорграфа максимален, если в нет остовных исходящих лесов с числом дуг, б ольшим, чем в F. Каждый максимальный исходящий лес содержит минимально возможное число исходящих деревьев; это число назовем размерностью мультиорграфа по исходящим лесам и обозначим v. Число дуг в любом таком лесе равно n - v. Число входящих деревьев в любом максимальном входящем лесе - размерность мультиорграфа по входящим лесам, обозначаемая v. Для мультиорграфа на n вершинах v, v {1,..., n}.

j Рассмотрим матрицы Qk = (qij) с элементами qij = ( ), k = k k Fk•i 0,..., n - v. В частности, элемент qij матрицы Qn-v есть вес множества n-v всех максимальных исходящих лесов , в которых вершина i принадлежит дереву, исходящему из j. Матрицу Qn-v назовем матрицей максимальных исходящих лесов . Нормированной матрицей максимальных исходящих • лесов назовем матрицу J = (Jij) = Qn-v/n-v, где n-v = ( ).

Fn-v Непустое подмножество вершин K V () мультиорграфа - недоминируемый узел7 в , если все вершины, принадлежащие K, взаимно Недоминируемые узлы называют также базовыми бикомпонентами (бикомпонента - компонента сильной, т. е. двусторонней связности).

u достижимы и недостижимы из других вершин . Пусть K = Ki, где i=K1,..., Ku - все недоминируемые узлы , а Ki+ - множество всех вершин, достижимых из Ki и недостижимых из других недоминируемых узлов. Через K обозначим сужение на K и через -K - подграф с множеством вершин V () и множеством дуг E()\E(K). Зафиксировав K, через T обозначим множество всех остовных исходящих деревьев мультиорграфа K, а через - множество всех максимальных исходящих лесов мультиP k орграфа -K. Через (k K) обозначим подмножество, состоящее из T T деревьев, исходящих из k, а через (i V ()) - множество всех макPK•i симальных исходящих лесов в -K, где i достижима из некоторой вершины, принадлежащей K. Через J обозначаем j-й столбец J.

.j Теорема 3.2. Пусть K - недоминируемый узел мультиорграфа . Выполняются следующие утверждения.

n 1. J - строчно-стохастическая: Jij 0, Jik = 1, i, j = 1,..., n.

k= 2. Jij = 0 (j K и i достижима из j в ).

j 3. Пусть j K. Для любого i V () Jij = ( ) ( )/n-v.

T PK•i j Если при этом i K+, то Jij = Jjj = ( )/( ).

T T 4. Jjj = 1.

jK j2 j 5. Если j1, j2 K, то J = (( )/( )) J.

T T.j2.jТеорема 3.3. Для любого мультиорграфа и всех i, j {1,..., n} имеет место следующее.

1. Jii Jji.

+ 2. Если Jii > Jji, то i K и j Kk, где Kk i, и, следовательно, / не содержит путей из j в i.

3. Если Jii > Jji > 0, то j K, и значит, j не является корнем ни / в одном максимальном исходящем лесе .

4. Если Jij > 0, то Jii = Jji.

Теорема 3.4. Матрица J идемпотентна: J2 = J.

Теорема 3.5. L J = JL = 0.

Теорема 3.6. J = lim(I + L)-1.

Теорема 3.7. Для любого мультиорграфа 1. Матрица8 L + J невырождена;

2. rank L = n - v; rank J = v;

3. N (L) = R(J) и R(L) = N (J);

4. R(L) R(J) = {0};

5. ind L = 1;

6. J - собственный проектор матрицы L.

Определение 3.2. Будем говорить, что стационарная цепь Маркова с множеством состояний {1,..., n} и переходной матрицей P связана с ор графом , если существует = 0, такое что P = I - L().

Определение 3.3. Предельная матрица средних вероятностей цепи Маркова с переходной матрицей P - это матрицаk- t P = lim P. (3.12) k k t=Из п. 6 теоремы 3.7 выводится следующая теорема, впервые полученная А. Вентцелем и М. Фрейдлиным и позже неоднократно переоткрывавшаяся.

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

Матрицей достижимостей орграфа называют матрицу (rij), каждый элемент rij которой равен 1, если содержит путь из i в j, и 0 в противном случае.

Использование матриц лесов для выявления структуры орграфа основано на использовании теорем 3.2 и 3.3 и следующего предложения.

8 Через J обозначена матрица, эрмитово сопряженная (в данном случае - транспо нированная) к J.

k Данный предел, в отличие от limk P, всегда существует.

Предложение 3.16. Матрица достижимостей орграфа может быть T получена из матрицы Q (), где Q() = (I + L)-1, при любом > заменой всех ее ненулевых элементов на 1. Поскольку результат не зависит от весов дуг, все они могут быть выбраны равными 1.

Отметим, что нахождение матрицы J позволяет сразу определить недоминируемые узлы мультиорграфа и вершины, достижимые из каждо го узла, что важно для приложений. Методы вычисления J приведены в главах 2, 3 и 4 диссертации.

В четвертой главе изучается множество всех остовных исходящих лесов орграфа и связанные с ним матрицы. Показано, что нормированная матрица исходящих лесов орграфа Q() = (I + L)-1 является матрицей переходных вероятностей в геометрической модели наблюдения за цепью Маркова. Получены выражения псевдообратной матрицы L+ и групповой # обратной матрицы L для матрицы Кирхгофа L через матрицу максимальных исходящих лесов орграфа. Матрицы исходящих лесов с заданным числом дуг и нормированные матрицы исходящих лесов представлены многочленами от матрицы Кирхгофа; с помощью этого представления дано новое доказательство матричной теоремы о лесах и некоторых других результатов алгебраической теории орграфов. Для матрицы Кирхгофа указан аннулирующий многочлен, степень которого определяется размерностью орграфа по исходящим лесам. Области приложения этих результатов: управление многоагентными системами, агрегирование предпочтений, анализ структуры графов и сетей и построение их алгебраических индексов.

Пусть цепь Маркова связана с орграфом в смысле определения 3.1, и - параметр связи. Рассмотрим следующую модель, приводящую к геометрическому распределению моментов наблюдения.

Геометрическая модель выбора момента наблюдения. Проводятся испытания Бернулли с вероятностью успеха q (0 < q < 1) в моменты времени t = 0, 1, 2,... Момент первого успеха становится моментом наблюдения.

Рассмотрим переходы цепи Маркова за случайное число шагов: от начального состояния, в котором цепь находится в момент t = 0, к состоянию в момент наблюдения, подчиняющийся геометрической модели с пара метром q. Пусть P (, q) = pij(, q) - матрица безусловных вероятностей переходов данной цепи за указанное число шагов.

Теорема 4.1. Для любых взвешенного орграфа, параметра > 0 и связанной с орграфом цепи Маркова имеет место Q() = P (, q), где q = (/ + 1)-1.

Существенным результатом главы 4 является рекуррентная проце дура вычисления матриц исходящих лесов Q1,..., Qn-v, где Qk = (qij), k j • qij = ( ), i, j = 1,..., n, а также весов k = ( ) множеств лесов.

k Fk•i Fk Начав с матрицы Q0 = I, остальные матрицы Qk, включая Qn-v = n-v J, можно последовательно найти с помощью следующей теоремы.

Теорема 4.2. Для любого взвешенного орграфа tr(LQk) Qk+1 = k+1I - LQk, k+1 =, k = 0,..., n - v.

k + Эта теорема позволяет также проинтерпретировать матрицы, вычисляемые при получении характеристического многочлена матрицы Кирхгофа с помощью алгоритма Леверье-Фаддеева.

Далее, установлено, что матрицы Qk исходящих лесов с k дугами выражаются очень простыми многочленами от матрицы Кирхгофа:

Теорема 4.3. Для любого взвешенного орграфа и любого k = 0,..., n - v k i Qk = k-i (-L).

i=С помощью теоремы 4.3 нормированная матрица исходящих лесов - Q = (I + L) также представляется в виде многочлена от L.

Теорема 4.4. Для любого взвешенного орграфа n-v - Q = (I + L) = -1 sn-v-i(-L)i, i= k где sk = j - вес множества исходящих лесов в с числом дуг, не j= n-v превосходящим k, = ( ) = k.

F• k=- Изучены свойства нормированных матриц Jk = k Qk исходящих лесов с k дугами (k = 0,..., n - v); J = Jn-v. В частности, Предложение 4.5. Матрицы Jk - строчно-стохастические.

# Получены выражения групповой обратной L и обобщенно обратной по Муру-Пенроузу L+ для матрицы Кирхгофа.

Теорема 4.7. При любом = # L = (L + J)-1 - -1 J, # # причем L L = LL = I - J.

# Предложение 4.6. L = lim Q() - J.

n-v-1 # Предложение 4.7. L = Jn-v-1 - J.

n-v Пусть Z = L + J. Доказано, что эта матрица невырождена.

Теорема 4.8. L+ = L(ZZ)-1 = L(JJ +LL)-1.

Как установлено в главе 2, для нахождения собственного проектора вырожденной матрицы A, ее компонент, функций от нее, псевдообратных и др. полезно знать аннулирующий многочлен для Au при u ind A. Со гласно теореме 3.7 ind L = 1. По теореме Кэли-Гамильтона аннулирующим является характеристический многочлен. Следующее предложение указывает аннулирующий многочлен более низкой степени.

n-v Предложение 4.9. Многочлен p() = n-v-i (-)i является анi= нулирующим для L.

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

Зная свойства матриц Кирхгофа, легко установить свойства лапласовских матриц. Для этого достаточно обратить все дуги орграфа (с сохранением их весов). Тогда лапласовская матрица исходного орграфа равна матрице Кирхгофа получившегося; исходящие леса получившегося орграфа однозначно и с сохранением весов соответствуют входящим лесам исходного. Таким образом, “графовые” свойства лапласовской матрицы получаются из свойств матрицы Кирхгофа заменой исходящих лесов на входящие и инверсией индексов - точно так, как в матричной теореме о лесах (теорема 1.4). В следующих главах чаще встречаются лапласовские матрицы, т. к. в формулировках их свойств порядок индексов оказывается более естественным.

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

Установлено, что кратность собственного значения 0 матрицы равна размерности по входящим лесам соответствующего орграфа, а кратность собственного значения 1 на единицу меньше размерности по входящим лесам дополнительного орграфа. Доказано, что спектры матриц принадлежат пересечению двух кругов с центрами в точках 1/n и 1 - 1/n и радиусом 1 - 1/n. Кроме того, область, их содержащая, входит в пересечение двух определенных в данной главе угловых областей с вершинами 0 и 1 и поло1 сы |Im(z)| ctg (в пределе - полоса |Im(z)| < ). Построен много2n 2n угольник, все точки которого являются собственными значениями нормированных лапласовских матриц порядка n и сформулирована гипотеза, что этот многоугольник совпадает с областью собственных значений указанных матриц. Эти результаты необходимы для анализа моделей управления многоагентными системами и уже нашли применение в этой области.

Действительную квадратную матрицу порядка n называем нормированной (стандартизованной) лапласовской матрицей, если (1) ее строчные суммы равны 0; (2) ее недиагональные элементы неположительны и не превосходят 1/n по модулю. Использование такой нормировки облегчает сравнение результатов, касающихся локализации спектров лапласовских матриц, при разных n. Нормированные лапласовские матрицы обозначаем .

Если рассматривается класс Gb взвешенных орграфов с весами дуг, не превосходящими b > 0, и L() - лапласовская матрица взвешенного орграфа на n вершинах, то нормированная лапласовская матрица, связанная с , определяется в классе Gb как () = (nb)-1L().

Пусть J IRnn - матрица10 со всеми элементами 1/n; K = I J. K IRnn - нормированная лапласовская матрица полного орграфа с весами всех дуг b в классе орграфов Gb. Определим матрицы P = + J, (5.9) c = K - . (5.10) Тогда P - стохастическая матрица; c - нормированная лапласовская матрица дополнительного взвешенного орграфа c, в котором (b - ij) - вес дуги (i, j), j = i, где ij - вес той же дуги в . Если ij = b, то в c нет дуги (i, j) и наоборот: если в нет дуги (i, j), то вес дуги (i, j) в c равен b. В силу (5.9), (5.10) и определения K P = I - c. (5.11) Следующие результаты касаются соотношения спектров , P и c.

Теорема 5.3. Пусть - нормированная лапласовская матрица, P и c определяются (5.9) и (5.10). Тогда для {0, 1} следующие утверждения эквивалентны11:

(а) sp , (б) sp P, (в) 1 - sp c, причем эти собственные значения имеют одну и ту же геометрическую кратность. Кроме того, v - собственный вектор , соответствующий собственному значению {0, 1}, тогда и только тогда, когда вектор J x = I - v (5.12) 1 - - собственный вектор P, соответствующий , а также собственный вектор c, соответствующий 1 - .

Не путать с матрицей J, изучавшейся в главе 3.

sp A - спектр матрицы A.

1 A Вместо A иногда пишем, где A - матрица, = 0 - комплексное число.

Теорема 5.4. Пусть f(), fP () и f () - характеристические мноc гочлены , P и c соответственно. Тогда для всех {0, 1} - fP () = f(), (5.14) f () = (-1)n-1 f(1 - ). (5.15) c 1 - Теорема 5.5. Для любой нормированной лапласовской матрицы и матрицы P, определяемой (5.9), и P - полусходящиеся.

Теорема 5.6. Пусть d и dc - размерности по входящим лесам орграфа, соответствующего , и дополнительного орграфа. Тогда1) m(0) = d, m(1) = dc - 1, 2) mP (0) = d - 1, mP (1) = dc, 3) m (1) = d - 1, m (0) = dc, c c и эти собственные значения - полупростые14;

4) Если15 v V(0) и Kv = 0, то Kv VP (0) = V (1);

c если x VP (1) = V (0) и Kx = 0, то Kx V(1).

c Теорема 5.7. 1. Все собственные значения нормированных лапласовских матриц порядка n принадлежат:

• пересечению двух замкнутых кругов с центрами в точках 1/n и 1 1/n и радиусом 1 - 1/n;

• меньшей замкнутой угловой области, ограниченной лучами, исходящими из точки 1 и проходящими через точки e-2i/n и e2i/n;

• меньшей замкнутой угловой области, ограниченной лучами, исходя 2 n 2 n щими из точки 0 и проходящими через точки e-( - )i и e( - )i.

2. Для мнимых частей () собственных значений нормированных 1 лапласовских матриц имеет место |()| ctg.

2n 2n mA() - алгебраическая кратность sp A.

Т. е. с совпадающими алгебраической и геометрической кратностями.

VA() - собственное подпространство A, соответствующее .

Замечание 5.2. Используя теорему Дмитриева и Дынкина (1946) о спектрах стохастических матриц, можно показать, что sp содержит собствен ное значение с аргументом - тогда и только тогда, когда - гамиль2 n тонов цикл на n вершинах. При этом собственное значение с таким ар2 1 2 гументом единственно и || sin, () sin. Данному собственn n n n ному значению соответствует собственный вектор, компоненты которого вершины правильного n-угольника на комплексной плоскости. Аналогично 2i n sp содержит собственное значение, принадлежащее отрезку [1, e ], тогда и только тогда, когда c - гамильтонов циклом на n вершинах. Такое 1 2 собственное значение также единственно и () sin.

n n () n 1 ctg 2n 2n 1 2 sin () n n 1 0,5 n-0 n n Рис. 5.2. Область, согласно теореме 5.7 содержащая спектр нормированной лапласовской матрицы порядка n (заштрихована); здесь n = 7.

Теорема 5.7 и замечание 5.2 иллюстрируются рисунком 5.2.

Пусть n - класс нормированных лапласовских матриц порядка n.

Изучим вопрос о локализации спектров матриц n. Положим k(n) = k - e-2i/n - · · · - e-2ki/n, k = 1,..., n - 1. (5.22) n Это выражение приводится к виду k sin n k(n) = n-1 k - e-(k+1)i/n, k = 1,..., n - 1. (5.23) sin n Обозначим через S(n) выпуклый многоугольник с вершинами 0(n) = 0, 1(n),..., n-2(n), n-1(n) = 1, n-2(n),..., 1(n). (5.24) Теорема 5.8. Каждая точка многоугольника S(n) - собственное значение некоторой матрицы n.

Пусть h(n) = sup{(): - собственное значение n}.

1 В силу теоремы 5.7 для всех n = 2, 3,... h(n) ctg.

2n 2n Теорема 5.9. Если n нечетно, то 1 h(n) = ctg, (5.26) 2n 2n кроме того, h(n) = ((n-1)/2(n)), где (n-1)/2(n) определено (5.22).

Следствие 5.2 из теоремы 5.7. lim h(n) = 1/.

n Следующее предположение пока не доказано.

Предположение 5.1. Вне многоугольника S(n), вершины которого задаются формулой (5.24), не существует собственных значений нормированных лапласовских матриц порядка n.

Теорема 5.10. Граница многоугольника S(n) с вершинами (5.24) при n сходится к овалу, образуемому участками двух циклоид с параметрическими уравнениями z() = x() + i y() и z() = x() - i y(), где [0, 2], x() = (2)-1( - sin ), (5.27) y() = (2)-1(1 - cos ). (5.28) () 1/ n = () 0,n = Рис. 5.3. Многоугольник лапласовских собственных значений при n = 4 и n = 5 и предельная кривая, задаваемая теоремой 5.10.

На рис. 5.3 показаны многоугольники S(n) при n = 4 и n = 5, а также предельная кривая, уравнение которой определяется теоремой 5.10.

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

Базовая дифференциальная модель распределенного согласования характеристик агентов имеет вид:

n i(t) = - aij(t) (xi(t) - xj(t)), i = 1,..., n, (5.29) j=где n - число агентов, xi(t) - характеристика i-го агента в момент t, aij(t) 0 - вес, с которым i-й агент учитывает расхождение в значении характеристики с j-ым агентом. В качестве характеристик могут рассматриваться положение в пространстве (если агентам необходимо сблизиться), скорость (если они участвуют в совместном движении), моменты ожидаемого прибытия в пункты назначения (если эти моменты необходимо синхронизировать) и т. д. Данную модель называют также моделью достижения консенсуса.

Обычно при децентрализованном управлении необходимо решать более сложные задачи, чем простое согласование характеристик. Так, если рассматривается управление комплексом движущихся объектов, то типичная задача - движение по заданной траектории с сохранением геометрической формы комплекса объектов и стабильной ориентации по отношению к курсу движения. Если необходимо произвести резкий маневр, то при маневре геометрическая форма может быть изменена, но после его окончания она должна быть восстановлена. Изменение и последующее восстановление формы характерны также для ситуаций, когда комплекс движущихся объектов сталкивается с опасностью или встречает препятствие. Во всех этих случаях согласование характеристик агентов - далеко не единственный, но обязательно присутствующий элемент стратегии управления. Этот элемент - ключевой в том смысле, что именно от него обычно зависят показатели устойчивости системы, ее управляемости и т.д. Поэтому анализ моделей согласования, таких, как модель (5.29), в том или ином виде производится и при исследовании более сложных процессов управления. Именно моделям согласования в главе 5 уделяется наибольшее внимание.

Модели (5.29) ставят в соответствие взвешенный ориентированный граф коммуникаций агентов (t), и в матричной форме она приобретает вид (t) = -L(t) x(t), (5.30) T где x(t) = (x1(t),..., xn(t)), L(t) - матрица Кирхгофа орграфа коммуникаций (t). Тем самым, свойства траекторий модели (5.29) определяются спектральными свойствами лапласовских матриц / матриц Кирхгофа, изученными в данной главе и главе 3. Поэтому некоторые из этих свойств, впервые опубликованные нами в 2000 г., позже неоднократно переоткрывались в работах по децентрализованному управлению.

Дискретизацией модели (5.29) получают итерационную модель распределенного согласования характеристик:

n xi(k + 1) = xi(k) - aij(k) (xi(k) - xj(k)), i = 1,..., n, (5.31) j=где k - дискретное время, > 0 - шаг разностной схемы. В матричной форме модель (5.31) имеет вид x(k + 1) = P x(k), (5.32) где P = I -L - строчно-стохастическая (при достаточно малом ) матрица, изучавшаяся в главах 3-5 диссертации. Свойства модели (5.32) определяются спектральными свойствами матрицы P. Они могут быть исследованы с помощью собственного проектора матрицы I - P, совпадающего с собственным проектором L и с нормированной матрицей остовных ис ходящих лесов J орграфа коммуникаций (t), изученной в диссертации.

Модели (5.29), (5.31) являются базовыми; при анализе более сложных моделей децентрализованного управления, предполагающем исследование сходимости, устойчивости, управляемости, скорости сходимости и т. д., также применимы (и уже применялись) результаты по локализации спектров лапласовских матриц, полученные в главах 3-5.

В шестой главе подход, связанный с построением структурных индексов графов, используется для анализа, в духе теории группового выбора, “чувствительных” алгебраических методов агрегирования предпочтений. Введена аксиома, “самосогласованной монотонности” (ССМ) и установлено, что ряд известных алгебраических методов оценивания относится к классу процедур, комбинирующих победы и поражения и, согласно доказанной в главе 6 теореме, нарушают ССМ. Получено достаточное условие самосогласованной монотонности и указаны процедуры, ему удовлетворяющие.

Рассматриваются данные о предпочтениях в форме массива = A (A(1),..., A(m)) парных сравнений объектов, где A(p) = (ap )nn. Элемент ap ik ik есть результат сравнения объектов i и j, произведенного p-ым индивидуумом. ap = 1 интерпретируется как чистый выигрыш, ap = 0 - как чистый ik ik проигрыш, и допускаются промежуточные градации, например, ap = 0,ik (ничья, равноценность). Такой массив, вообще говоря, неполный (не все ap ik определены) называем профилем индивидуальных предпочтений. Оценивающая процедура - функция из множества рассматриваемых профилей в S T s IRn, где значение = (s1,..., sn) функции есть вектор-столбец оценок S объектов. Оценивающие процедуры, рассматриваемые в главе 6, нейтральны (любая переиндексация объектов сохраняет их оценки) и анонимны (любая переиндексация участников сохраняет оценки объектов). Под агрегированием предпочтений понимаем сопоставление объектам оценок s1,..., sn:

чем больше оценка, тем интенсивнее коллективное предпочтение.

Самосогласованная монотонность (ССМ). Процедура оценивания S самосогласованно монотонна, если для любого множества объектов J, любого профиля и любых объектов i, j J она удовлетворяет следующему A условию.

Пусть Ui = ap | k, p и Uj = aq | l, q - мультимножества реik jl зультатов сравнений объектов i и j соответственно. Предположим, что Ui I II может быть разбито на UiI и UiII, а Uj может быть разбито на Uj и Uj таким образом, что I (A) Если ap UiI, то ap = 1; если aq Uj, то aq = 0;

ik ik jl jl II (B) существует взаимно-однозначное соответствие из UiII на Uj, такое что (ap ) = aq влечет ap aq и sk sl.

ik jl ik jl Тогда si sj.

I Кроме того, если UiI непусто, или Uj непусто, или хотя бы одно неравенство в (B) хотя бы в одном случае - строгое, то si > sj.

Рисунок 6.2 иллюстрирует соотношение объектов i и j, удовлетворяющих посылке самосогласованной монотонности.

a b i c d j e f Рис. 6.2. Фрагмент массива предпочтений, включающий результаты i и j.

Будем говорить, что процедура оценивания основана на индивидуS альных оценках, если существуют функции f и , такие что для всех проs филей = (A(1),..., A(m)) соответствующие им векторы оценок предстаA s s(1) s(m) s(p) вимы в виде = (,..., ), где - вектор оценок, зависящий лишь s(p) от матрицы сравнений участника p: = f(A(p)), p = 1,..., m.

Предложение 6.1. Существуют оценивающие процедуры, основанные на индивидуальных оценках, которые удовлетворяют ССМ на полных предпочтениях, но никакая процедура этого типа не удовлетворяет ССМ на неполных предпочтениях.

Далее рассматриваются процедуры, в которых итоговая оценка, вообще говоря, не может быть построена по совокупности оценок, определяемых предпочтениями отдельно взятых участников. Такие процедуры называем совокупными. Многие известные процедуры этого типа сводятся к манипуляциям с матрицей A = (aij) суммарных результатов сравнений на парах объектов:

0, если ap не определено ни при одном p {1,..., m}, ij aij = ap в противном случае.

ij p Далее в главе 6 изучается ряд таких процедур, в частности, - процедуры Уэя-Кендалла, Хассе, Рамануяхариулу, Каца-Томпсона-Тейлора, Дэниэлса-Ушакова-Годдарда-Левченкова. Попутно рассматриваются алгебраические индексы графов, связанные с этими процедурами.

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

Очки этой процедуры удовлетворяют системе уравнений n wi = aijwj, i = 1,..., n, (6.19) ci j= n где ci = aji, i = 1,..., n.

j=В наших обозначениях эта процедура сводится к нахождению неотрицательных и не полностью нулевых решений системы уравнений T w L = 0, (6.21) где L - матрица Кирхгофа (определение см. на с. 11) мультиорграфа результатов парных сравнений, или, эквивалентно, ii wi = (-ji) wj, i = 1,..., n. (6.22) j=i Очки wi имеют интересные и разнообразные интерпретации.

Интерпретации очков в процедуре направленных деревьев.

(1) Очки wi пропорциональны суммарным весам деревьев, исходящих из соответствующих вершин в (Берман, 1980);

(2) Очки wi пропорциональны стационарным вероятностям “выигрывающей марковской цепи” (Ушаков, 1971 и др.);

w (3) есть вектор “честных ставок” в модели Муна и Палмена (1970).

Далее в главе 6 рекурсивно вводится понятие индекса побед-пражеT T w ний - пары векторов (, ) = ((w1,..., wn), (l1,..., ln) ), в которой перl вый вектор в определенном смысле агрегирует “победы” объектов в сравнениях, а второй - “поражения”. Из-за ограниченности объема реферата соответствующую серию определений опускаем. Затем вводится определение 6.4, устанавливается, что рассмотренные выше процедуры ему соответствуют и доказывается основной результат (теорема 6.1).

Определение 6.4. Оценивающая процедура есть процедура, комбиниS рующая победы и поражения, если для любого профиля существует инA w декс побед-поражений (, ) и функция h, такие что l si = h(wi, li), i = 1,..., n.

Теорема 6.1. Любая оценивающая процедура, комбинирующая победы и поражения и имеющая область определения, включающую все неразложимые профили предпочтений, нарушает условие ССМ.

Далее рассмотрена процедура наименьших квадратов, также нарушающая ССМ, и получено достаточное условия выполнения ССМ.

Теорема 6.2. Пусть для процедуры оценивания существует функция S f(s, V ), где s IR, V - конечное мультимножество пар действительных чисел, со следующими свойствами.

(A) Для любого профиля пусть Vi = (ap, sj) | j, p, i = 1,..., n. Тогда A ij f(si, Vi) = 0, i = 1,..., n.

(B) Функция f(s, V ) строго возрастает по каждому элементу каждой пары из V и строго убывает по s.

(C) Для каждого профиля и любых i, k J, A если (1, sk) Vi, то f(si, Vi (1, sk)) < f(si, Vi);

если (0, sk) Vi, то f(si, Vi (0, sk)) > f(si, Vi).

Тогда удовлетворяет самосогласованной монотонности.

S В Таблице 6.1 указаны четыре известные процедуры, удовлетворяющие достаточному условию теоремы 6.2, а значит, и ССМ.

Процедура Обл. опред. f(·) в теореме 6. Цермело (1928), si ID ap ij si + sj Брэдли и Терри (1952) j, p n sj si Дэниэлс (1969), Гиновкер (1981) ID aij si - aji sj j=n aijsj j=Коуден (1975) ID - si n (aijsj + aji(1 - sj)) j= p Обобщ. процедура суммы очков [18,47] U (rij - (si - sj)) - si j, p ID означает неразложимые профили предпочтений, U - все профили.

Таблица 6.1. Некоторые процедуры, удовлетворяющие ССМ.

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

В седьмой главе аксиоматически построен и изучен метод агрегирования неполных предпочтений, названный обобщенным методом суммы очков. Он связан с использованием матрицы остовных корневых лесов графа сравнений. В случае линейных и слабых порядков “на входе” он совпадает с методами Борда и Коупленда соответственно, а в случае турниров - с методом суммы очков. При несбалансированных данных он сводится к решению системы линейных уравнений. Установлено, что оценки метода совпадают с гребневыми оценками параметров модели парных сравнений Шеффе.

Рассмотрим множество объектов = {X1,..., Xn} и массив R = X (R(1), R(2),..., R(m)), представляющий результаты парных сравнений элементов по предпочтению, где R(p) (p = 1,..., m) - матрица парных X p p сравнений порядка n, в которой rij и rji при i = j выражают результат p сравнения объектов Xi и Xj в p-й серии экспериментов. Элементы rii не соответствуют сравнениям, и их значения определяются некоторым техническим соглашением. Матрицы R(p), вообще говоря, заполнены частично:

p p если Xi и Xj не сравнивались в p-ой серии экспериментов, то rij и rji не определены. Если матрица полностью определена, называем ее полной. Массив R полон, если полны все матрицы R(1), R(2),..., R(m). Числа n и m параметры R.

Каждому объекту Xi сопоставляется “сумма очков” в R:

p si = rij, i = 1,..., n, (7.1) (j, p)|i p где обозначает суммирование по тем j и p, для которых rij опреде(j, p)|i p лено в R; если все rij не определены, то si не определено. Метод суммы очков упорядочивает объекты по убыванию величин si. В случае неколичественных парных сравнений элементы R(p) могут быть определены так:

p p rij = 1, если в p-ой серии экспериментов Xi превосходит Xj, rij = -1, если p Xj превосходит Xi и rij = 0, если Xi и Xj равноценны или i = j.

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

p p p неполных матриц, таких что (a) если rij определено, то rji = -rij и p (b) rii = 0, i, j = 1,..., n, p = 1,..., m.

Рассмотрим следующее обобщение сумм очков (7.1):

p xi = fij, i = 1,..., n, (7.4) (j, p)|i где p p fij = f(xi, xj, rij) (7.5) - “вклад” в оценку xi объекта Xi от сравнения его с Xj в p-ой серии экспериментов. Функцию f : IR3 IR называем функцией платежа. Для конкретной функции f соотношения (7.4) при условии (7.5) образуют систему n уравнений с n неизвестными x1,..., xn:

p xi = f(xi, xj, rij), i = 1,..., n. (7.6) (j, p)|i Наложим на функцию платежа два ограничения.

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

p p p Условие ставки. Если rij определено, то fij = -fji.

Используя кососимметричность, запишем условие ставки в виде (x, y, r) IR3 f(x, y, r) = -f(y, x, -r). (7.9) Характеризация всех функций, удовлетворяющих условиям согласованности и ставки, дана в [47]. Однако “почти все” эти функции всюду разрывны. Добавим следующее естественное требование к функции платежа.

Условие непрерывности в одной точке. Функция f непрерывна хотя бы в одной точке (x, y, r) IR3.

Главный результат главы 7 - следующая теорема.

Теорема 7.1. Функция f(x, y, r) при данных n > 3 и m II удовлетвоN ряет условиям ставки, согласованности и непрерывности в одной точке тогда и только тогда, когда при некотором IR (x, y, r) IR3 f(x, y, r) = r + ·(y - x + mnr). (7.10) Слабое условие неубывания. При некоторых x, y1, y2 > y1 и r имеет место f(x, y2, r) f(x, y1, r).

Это естественное условие, добавление которого влечет 0. Теперь функции (7.10) можно подставить в систему уравнений (7.6):

p p xi = rij + ·(xj - xi + mnrij), i = 1,..., n. (7.12) (j, p)|i При любом выбранном 0 оценки x1,..., xn, удовлетворяющие (7.12), будем называть обобщенными суммами очков.

Предложение 7.1. Система уравнений (7.12) эквивалентна системе xi = si + · (xi - xj), i = 1,..., n, (7.13) (j, p)|i p где сумма с “” берется по таким j и p, что rij не определено в R и = /(1 + mn). (7.14) Из (7.14) и неотрицательности следует 0 < 1/(mn).

В матричной форме вектор решений (7.12) представ в виде им x = (I + L)-1(1 + mn)s, где L - лапласовская матрица неориентированного графа количеств сравнений. Поэтому (I + L)-1 = Q() - матрица взвешенных остовных корневых лесов данного графа, и каждая обобщенная сумма очков есть линейная комбинация сумм очков с коэффициентами, равными суммарным весам лесов, “соединяющих” соответствующие пары вершин.

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

Рассмотрены также вероятностные модели парных сравнений, для которых обобщенные суммы очков являются оптимальными (в определенном смысле) оценками параметров. Речь идет о гребневых оценках для моp дели Шеффе E(rij) = i -j, где i - неизвестный параметр, характеризующий i-ый объект, и о наилучших линейных предикторах для байесовского варианта модели Шеффе.

Для случая парных сравнений с ограниченным результатом введены понятия корректности выбора параметров и . Установлено, что эти понятия корректности эквивалентны и равносильны выполнению неравенств 0 (m(n - 2))-1 и 0 (2m(n - 1))-1.

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

В заключение главы 7 предложены методы выбора параметра модели и рассмотрены примеры.

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

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

Подробнее остановимся на результатах о функциях сигма-близости.

Определение 8.2. Пусть A - непустое конечное множество, - действительное число. Функцию : A2 IR назовем -близостью на A, если для любых x, y, z A выполняются 1) условие нормировки: (x, t) = ;

tA 2) неравенство треугольника для близостей: (x, y) + (x, z) - (y, z) (x, x), причем если z = y и x = y, то неравенство строгое.

Предложение 8.1. Пусть есть -близость на A. Тогда x, y A (x, y) = (y, x) (симметричность);

если x = y, то (x, x) > (x, y) (“эгоцентризм”).

Исследуем соотношение между -близостями и метриками. Пусть d - метрика на A и |A| = n. Введем обозначения:

d(x, ·) = d(x, t), (8.12) n t A d(·, ·) = d(s, t). (8.13) ns, t A Предложение 8.2. Для любой метрики d на A функция (x, y) = d(x, ·) + d(y, ·) - d(x, y) - d(·, ·) + (8.14) n является -близостью на A.

Предложение 8.3. Для любой -близости на A функция d(x, y) = 0,5((x, x) + (y, y)) - (x, y) (8.16) является метрикой на A.

Отображения, задаваемые (8.14) и (8.16) обозначим (d) и ().

Теорема 8.6. и задают взаимно-однозначные соответствия множеств метрик на A и -близостей на A; = -1.

Обобщим эти результаты на случай бесконечных множеств. Пусть A - непустое множество, A1 и A2 - множества всех функций A IR и A2 IR соответственно.

Определение 8.3. Вещественный функционал µ, заданный на множестве B1 A1, назовем линейным усредняющим функционалом, если µ и B1 обладают следующими свойствами:

1) B1 - линейное пространство над IR, содержащее все константы;

2) µ - линейный функционал, константам сопоставляющий их значения;

3) если f, g B1 и x A f(x) g(x), то µ(f) µ(g) (монотонность).

Пусть µ - линейный усредняющий функционал на B1. Пусть f A2, и при любом x0 A f(x0, y) принадлежит B1 как функция y. Через f(x, ·) = µy(f(x, y)) обозначим функцию от x, каждому x ставящую в соответствие результат применения µ к f(x, y) как к функции y.

Определение 8.4. B2 A2 назовем семейством двухместных усредняемых функций, если B2 - линейное пространство над IR, содержащее все константы и все элементы B1 как функции каждого из аргументов, постоянные по второму аргументу, и для любой функции f B1) x A gx(y) B1, где gx(y) = f(x, y);

2) f(x, ·) B1 и g(x) B1, где g(x) = f(x, x).

Пусть для A заданы B1, µ и B2, определенные выше; m IR.

Определение 8.5. Функцию B2 назовем m-близостью на A, если для любых x, y, z A выполняются 1) условие нормировки: (x, ·) = m;

2) неравенство треугольника для близостей: (x, y) + (x, z) - (y, z) (x, x), причем если z = y и x = y, то неравенство строгое.

Тогда, как показано в диссертации, выполняются прямые аналоги предложений 8.1–8.3 и теоремы 8.6. Пример использования этих результатов - следствие 8.1.

Следствие 8.1. Для любых множества A, метрики d B2 и x A d(x, ·) d(·, ·)/2.

Пример -близости - относительная достижимость по лесам.

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

Относительная достижимость по лесам - это мера близости вершин графа, задаваемая матрицей Q = (I + L)-1, где L - лапласовская матрица графа. В случае орграфов рассматриваются две меры близости, задаваемые матрицами Q = (I + L)-1 (достижимость по входящим лесам) и Q = (I +L)-1 (достижимость по исходящим лесам), где L - лапласовская матрица, L - матрица Кирхгофа. В главе 9 рассматриваются свойства и применения этих показателей и связанных с ним структурных индексов.

При этом используются те же характеристические условия, что и в главе 8, и ряд специфических условий (в частности, стохастичность и независимость от макровершины). Доказана Теорема 9.2 (об одношаговом изменении относительной достижимости по лесам). Пусть в мультиграфе G вес некоторого ребра p увеличился на kt kt > 0 или к G добавлено новое ребро между k и t с весом kt > 0.

Пусть G - полученный мультиграф и W = W (G), Q = Q(G). Тогда 1) Q = hR, где Q = Q - Q, h = (dkt +1/kt)-1, dkt = qkk +qtt -2qkt, R = (rij)nn - матрица с элементами rij = (qik -qit)(qjt -qjk);

2) все строки и все столбцы матрицы Q пропорциональны;

3) если qik > qit, то qij > 0 тогда и только тогда, когда qjt > qjk, и qij < 0 тогда и только тогда, когда qjk > qjt;

4) знаки всех приращений qij не зависят от модуля kt > 0, а модули ненулевых qij строго возрастают по kt;

5) i, j V (G) dij = -1(dik -dit +djt -djk)2(dkt +1/kt)-1 и d dij.

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

В силу матричной теоремы о лесах матрица относительной достижимости по лесам представима в виде Q = -1(Q0 + Q1 +... + Qn-v), где Qk - матрица лесов с k ребрами (дугами), v - размерность графа по лесам.

Наряду с матрицей Q в главе 9 изучены меры близости, определяемые матрицами Qn-v-1 и Qn-v - для графов и орграфов. Рассмотрены также параметрические меры близости, определяемые матрицами Q() = (I + L)-( - параметр).

Для неориентированных графов псевдообратная (по Муру–Пенро+ + узу) матрица L = (ij) проинтерпретирована в графовых терминах.

Теорема 9.7 (графовая интерпретация матрицы, псевдообратной к L).

ij ( ) - · ( ) Fn-v-1 |Vi| F n-v-при j Vi, + ij = (9.18) ( ) F n-v 0 иначе, где Vi - множество вершин компоненты графа G, содержащей i.

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

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

Рассмотрим следующий однопараметрический класс показателей взвешенной достижимости по лесам: при выбранном > 0 матрица Q() = (qij) сравнительной близости вершин задается формулой Q() = (I + L)-1. (10.1) Матрицы Q() - дважды стохастические и симметричные. Параметр определяет пропорцию учета длинных и коротких связей вершин. Нами введены следующие метрики.

Определение 10.1. При выбранном параметре > 0 величину 1 d = (qii + qjj - qij - qji), i, j = 1,..., n (10.4) ij назовем лесным расстоянием между вершинами i и j, а величину = (qii + qjj - qij - qji) = 2 d, i, j = 1,..., n (10.5) ij ij назовем приведенным лесным расстоянием между вершинами i и j.

Зафиксировав , будем использовать обозначения dij и ij. В силу предложения 8.3 dij и ij, действительно, являются расстояниями. Из двойной стохастичности Q() следует dij 1, ij 2 (i, j = 1,..., n), причем равенство достигается только когда i и j - две изолированные вершины.

Р. Меррис (1997) дал иную оценку для dij: dij (1 + a(G))-1, где a(G) - введенная М. Фидлером алгебраическая связность графа - второе минимальное собственное значение L. Заметим, что (1 + a(G))-1 - второе максимальное собственное значение Q().

В силу теоремы 9.2, если суммарный вес ребер G с концами k и t получил приращение kt > 0, то при отсутствии других изменений в G (ik -it +jt -jk)i, j V (G) ij = -. (10.6) 4(kt +1/kt) Для мультиграфа G, отличающегося лишь ребром от G, через kt = обозначаем приращение веса ребра (k, t), переводящее G в G;

все обозначения со штрихами относятся к G, без штрихов - к G.

Лемма 10.1. Пусть взвешенный мультиграф G отличается от G лишь ребром (k, t). Тогда ( )-1 - (kt)-1 = kt.

kt Так, при добавлении ребра (k, t) к невзвешенному графу 1/ =1/kt + 1.

kt Определение 10.3. Пусть i, j V (G) и i = j. Совокупным весом связей между i и j в G назовем величину ij = (ij)-1 - (2)-1.

В силу леммы 10.1 kt = kt + при добавлении дуги (k, t) с весом .

Следующее утверждение проясняет смысл совокупного веса связей.

Теорема 10.1. Пусть i = j, ij - суммарный вес ребер (i, j) в G.

0 1) ij = ij + ij, где ij - совокупный вес связей между i и j в графе, получающемся из G удалением всех ребер (i, j);

2) ij ij ;

3) ij = ij тогда и только тогда, когда i и j не связаны ребрами ни с какими другими вершинами - лишь, возможно, друг с другом.

Отсюда dij (1 + 2 ij)-1, (10.14) ij ((2)-1 + ij)-1, i, j = 1,..., n. (10.15) Условия равенства здесь те же, что теореме 10.1. В диссертации получены соотношения, связывающие лесные расстояния для пары графов, отличающихся одним ребром.

Фрагментацией графа, отделяющей j от i называем остовный корневой лес, в котором i - корень дерева, и j не принадлежит этому дереву.

Рассмотрена модель случайного выбора леса в графе и доказана Теорема 10.2. Лесное расстояние dij равно вероятности выбора фрагментации, разделяющей i и j, в модели случайного выбора леса.

Изучены асимптотические свойства лесной метрики графа, а именно, найдены пределы d = lim d и = lim . Кроме того, полуij ij ij ij чены соотношения между лесной метрикой и резисторной метрикой графа:

введено понятие -расширения графа и показано, что, с одной стороны, ij(G ) = 2d (G), где ij - резисторная метрика, G - -расширение G, а ij с другой стороны = ij.

ij В заключении диссертации подведены итоги проведенных исследований и кратко изложены основные выводы.

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

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

Основные научные результаты, полученные в диссертационной работе, состоят в следующем:

1. Получена матричная теорема о лесах.

2. Разработан подход к нахождению собственного проектора и компонент квадратной матрицы A с помощью произвольного ненулевого аннулирующего многочлена для Au, где u ind A.

3. Изучены структура и свойства множеств остовных корневых лесов графов и орграфов и связанных с ними матриц. Установлено, что матрица максимальных входящих лесов орграфа является собственным проектором лапласовской матрицы. Из последнего факта выведена матричная теорема о деревьях для цепей Маркова. Эти результаты составляют основу анализа моделей распределенного согласования характеристик в многоагентных системах.

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

5. Введена аксиома самосогласованной монотонности для процедур агрегирования предпочтений. Ряд известных алгебраических методов агрегирования предпочтений и их классов протестирован на выполнение этой аксиомы. Классы методов при этом определялись в терминах свойств индуцируемых ими алгебраических индексов на орграфах предпочтений.

6. Аксиоматически построен и исследован новый метод агрегирования неполных предпочтений - обобщенный метод суммы очков, обобщающий процедуры Борда, Коупленда и турнирную процедуру агрегирования. Показано, что метод эквивалентен нахождению гребневых оценок параметров статистической модели парных сравнений Шеффе и что назначаемые методом итоговые баллы можно трактовать как прогнозные значения сумм очков после пополнения массива предпочтений.

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

8. Аксиоматически введен класс функций -близости. Доказана теорема о двойственности понятий -близость и расстояние. Область приложения этих результатов - анализ данных.

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

10. Введен класс лесных метрик графов. Исследованы свойства этих метрик, дана вероятностная интерпретация лесного расстояния, установлены соотношения между лесными метриками и резисторной метрикой графа. Области применения - анализ сетей, химическая информатика.

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

Публикации по теме работы 1. Агаев Р. П., Чеботарев П. Ю. Матрица максимальных исходящих лесов орграфа и ее применения //Автоматика и Телемеханика. 2000. № 9. С. 15–43.

2. Агаев Р. П., Чеботарев П. Ю. Остовные леса орграфа и их применение //Автоматика и Телемеханика. 2001. № 3. С. 108–133.

3. Агаев Р. П., Чеботарев П. Ю. О нахождении собственного проектора и компонент матрицы с помощью аннулирующего многочлена //Автоматика и Телемеханика.

2002. № 10. С. 3–12.

4. Агаев Р. П., Чеботарев П. Ю. Лапласовские спектры орграфов и их приложения //Автоматика и Телемеханика. 2005. № 5. С. 47–62.

5. Пригарина Т. А., Чеботарев П. Ю. Методы экспертных оценок на примере определения предпочтительности объектов: Препринт. Москва: ЦЭМИ АН СССР, 1989.

6. Пригарина Т. А., Чеботарев П. Ю. Методы экспертных оценок и определение предпочтительности объектов // Экспертные оценки в социологических исследованиях.

Гл. VIII /Под ред. В. И. Паниотто. Киев: Наукова думка, 1990. С. 190–225.

7. Пригарина Т. А., Чеботарев П. Ю., Шмерлинг Д. С. Анализ нечисловой информации //Математические методы в социально-экономических исследованиях /Под ред. С. М. Ермакова, В. Б. Меласа. СПб: Петрополис, 1996. С. 123–138.

8. Пригарина Т. А., Чеботарев П. Ю., Шмерлинг Д. С. Парные сравнения объектов (аналитический обзор) // Научно-техническая информация. Серия 2. Информационные процессы и системы. 1996. № 2. С. 20–25, 32.

9. Чеботарев П. Ю. Аксиоматическое задание одного метода оценивания объектов по результатам экспертного опроса //Труды науч.- техн. конф. молодых ученых и спец.

Моск. ин-та нефти и газа. 1987. С. 27–32. Деп. в ВИНИТИ 24.07.87, № 5369B87.

10. Чеботарев П. Ю. Байесовское оценивание качества объектов по результатам парных сравнений //Материалы X конф. Молодых ученых Ун-та дружбы народов.– Ч. 2.

1987. С. 35–38. Деп. в ВИНИТИ 29.12.87, № 9152-B87.

11. Чеботарев П. Ю. Обобщение метода строчных сумм для неполных парных сравнений //III Всес. школа-семинар “Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа”. Тезисы докладов.– Ч. 2. М.: ЦЭМИ, 1987. С. 249–250.

12. Чеботарев П. Ю. Два метода упорядочения объектов по произвольному множеству парных сравнений. 1988. Деп. в ВИНИТИ 22.07.88, № 5879-B88.

13. Чеботарев П. Ю. Использование метода обобщенных строчных сумм для обработки числовых экспертных оценок с пропусками //Научно-практическая школа-семинар “Программное обеспечение ЭВМ: индустриальная технология, интеллектуализация разработки и применения”. Тезисы докладов. Т. 2. Ростов-на-Дону: ВНИИПС, 1988. С. 153–155.

14. Чеботарев П. Ю. Неполные парные сравнения и метод строчных сумм. 1988.

Деп. в ВИНИТИ 26.02.88., № 1576-B88.

15. Чеботарев П. Ю. Агрегирование неполных предпочтений // III Всесоюзная конференция “Методы социологических исследований”. Т. 5. Москва: ИС АН СССР, 1989. С. 59–62.

16. Чеботарев П. Ю. Метод оценивания объектов по неполному набору парных сравнений // Комплексный подход к анализу данных в социологии. Москва: ИС АН СССР, 1989. С. 79–93.

17. Чеботарев П. Ю. Метод строчных сумм и приводящие к нему модели // Сб. тр.

ВНИИ системных исследований. 1989. № 3. С. 94–110.

18. Чеботарев П. Ю. Обобщение метода строчных сумм для неполных парных сравнений //Автоматика и телемеханика. 1989. № 8. С. 125–137.

19. Чеботарев П. Ю. Ранжирование объектов в аддитивной модели парных сравнений со случайными факторами // IV Всес. конф. “Применение многомерного стат. анализа в экономике и оценке качества продукции”. Тезисы докладов.– Ч. 1. Тарту:

Тартуский университет, 1989. С. 33–34.

20. Чеботарев П. Ю. Агрегирование предпочтений: регрессионная модель // Методы математической статистики в кибернетике и информатике. Томск: ТГУ, 1990.

Т. 2. С. 541–550.

21. Чеботарев П. Ю. Алгоритмы выбора параметра в методе обобщенных строчных сумм // III Всесоюзная школа-семинар “Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание”. Тезисы докладов. Одесса:

1990. С. 104.

22. Чеботарев П. Ю. О некоторых оптимизационных методах агрегирования предпочтений //Сб. тр. ВНИИ системных исследований. 1990. № 8. С. 67–72.

23. Чеботарев П. Ю. О некоторых оптимизационных методах агрегирования предпочтений //Всес. научно-практический семинар “Интеллектуальное программное обеспечение ЭВМ”. Тезисы докладов.– Ч. 1. Ростов-на-Дону–Терскол: 1990. С. 95–97.

24. Чеботарев П. Ю. Об одном прогнозном подходе к агрегированию экспертных оценок //Всесоюзное совещание “Пути повышения качества прогнозов”. Тезисы докладов.

Москва–Ленинград: Союз научных и инженерных обществ СССР, 1990. С. 60–62.

25. Чеботарев П. Ю. Уточненный пример обобщенной немонотонности метода КемениСлейтера //IV Всес. школа-семинар “Статистический и дискретный анализ данных и экспертное оценивание”. Тезисы докладов. Одесса: 1991. С. 136–138.

26. Чеботарев П. Ю. Новые меры связности графов и их применение в анализе социального поведения // Информационный бюллетень РФФИ. 1996. Т. 4, № 1.

С. 430.

27. Чеботарев П. Ю. Анализ социальных сетей: основные подходы //Тезисы докладов I Всероссийского Социологического Конгресса “Общество и социология: новые реалии и новые идеи” /Под ред. Ю. В. Асочакова, И. Д. Демидовой. Санкт-Петербург:

СПбГУ, 2000. С. 510–511.

28. Чеботарев П. Ю., Митькин А. Н., Шмерлинг Д. С. Об оценивании вклада ведомственных целевых программ в достижение целей правительства //Проблемы управления. 2007. № 4. С. 43–50.

29. Чеботарев П. Ю., Шамис Е. В. Матричная теорема о лесах и измерение связей в малых социальных группах // Автоматика и Телемеханика. 1997. № 9.

С. 124–136.

30. Чеботарев П. Ю., Шамис Е. В. О двойственности метрик и -близостей // Автоматика и Телемеханика. 1998. № 4. С. 204–209.

31. Чеботарев П. Ю., Шамис Е. В. О мерах близости вершин графов // Автоматика и Телемеханика. 1998. № 10. С. 113–133.

32. Чеботарев П. Ю., Шамис Е. В. Некоторые свойства лесной метрики графа // Автоматика и Телемеханика. 2000. № 8. С. 137–146.

33. Agaev R., Chebotarev P. On the spectra of nonsymmetric Laplacian matrices // Linear Algebra and its Applications. 2005. Vol. 399. Pp. 157–168.

34. Chebotarev P. Constructing extensions of utility functions // International Conference “Logic, Game Theory and Social Choice”. Saint-Petersburg: Saint-Petersburg State University, 2001. Pp. 49–55.

35. Chebotarev P. Outforests of a digraph, the Kirchhoff matrix, and Markov chain probabilities // Second Euroworkshop on Algebraic Graph Theory. Edinburgh: University of Edinburgh, 2001. P. 5.

36. Chebotarev P. Extending utility representations of partial orders without continuity requirements // Abstracts of the Int. conference “Utility Theory and Applications”.

Trieste: University of Trieste, Faculty of Economics, 2002. Pp. 12–13.

37. Chebotarev P. On the extension of utility functions // Constructing and Applying Objective Functions /Ed. by A. S. Tangian, J. Gruber. Berlin: Springer-Verlag, 2002.

Vol. 510 of Lecture Notes in Economics and Mathematical System. Pp. 63–74.

38. Chebotarev P. Spanning forests of digraphs and limiting probabilities of Markov chains //Electronic Notes in Discrete Mathematics. 2002. Vol. 11. Pp. 108–116.

39. Chebotarev P. On of the spectrum of the digraph Laplacian // International Conference on Matrix Analysis and Applications. Fort Lauderdale: Nova Southeastern University, 2003. Pp. 4–5. http://www.resnet.wm.edu/cklixx/novabs.pdf.

40. Chebotarev P. Laplacian matrices and essentially cyclic weighted digraphs // Abstracts of the 13th Conference of the International Linear Algebra Society. Amsterdam: Free University of Amsterdam, 2006. Pp. 60–61.

41. Chebotarev P. A graph theoretic interpretation of the mean first passage times: arXiv paper math.PR/0701359: arXiv, 2007. http://arxiv.org/abs/math/0701359.

42. Chebotarev P. The Laplacian matrix, spanning forests, and the golden ratio //Abstracts of the 14th Conference of the International Linear Algebra Society. Shanghai: Shanghai University, 2007. P. 12.

43. Chebotarev P. Spanning forests and the golden ratio //Discrete Applied Mathematics.

2008. Vol. 156, no. 5. Pp. 813–821.

44. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix //Linear Algebra and its Applications. 2002. Vol. 356. Pp. 253–274.

45. Chebotarev P., Agaev R. Matrices of forests and the analysis of digraphs: arXiv paper math.co/0508171: arXiv, August 2005. http://arxiv.org/abs/math/0508171.

46. Chebotarev P., Shamis E. The forest metrics for graph vertices // Electronic Notes in Discrete Mathematics. 2002. Vol. 11. Pp. 98–107.

47. Chebotarev P. Y. Aggregation of preferences by the generalized row sum method //Mathematical Social Sciences. 1994. Vol. 27. Pp. 293–320.

48. Chebotarev P. Y. On ridge regression techniques as applied to the Scheffe-Noether paired comparison model //9 European Meeting of the Psychometric Society. Leiden: Leiden University, 1995. P. 20.

49. Chebotarev P. Y. Out forests of a digraph and Markov chain probabilities //International Linear Algebra Conference. Haifa: Institute of Advanced Studies in Mathematics, Technion, 2001. Pp. 20–21.

50. Chebotarev P. Y., Agaev R. P. The matrix of maximum out forests and structural properties of systems modeled by digraphs // Modelling and Simulation of Systems, MOSIS-2000, 34th Spring Int. Conf. Vol. 1. Ostrava: Univ. of Ostrava, 2000.

Pp. 101–106.

51. Chebotarev P. Y., Shamis E. Incomplete preferences and indirect scores: Working Paper 365.97. Barcelona: Universitat Autonoma de Barcelona and Institut d’Analisi Economica, CSIC, 1997.

52. Chebotarev P. Y., Shamis E. Characterizations of scoring methods for preference aggregation //Annals of Operations Research. 1998. Vol. 80. Pp. 299–332.

53. Chebotarev P. Y., Shamis E. V. Matrix-forest theorems: arXiv paper math.co/0602575:

arXiv, 1995. http://arxiv.org/abs/math.co/0602575.

54. Chebotarev P. Y., Shamis E. V. On optimization models for aggregating incomplete preferences //International Conference on Ordinal and Symbolic Data Analysis. Paris:

INRIA Rocquencourt, 1995. Pp. 148–151.

55. Chebotarev P. Y., Shamis E. V. On optimization models for aggregating incomplete preferences // Ordinal and Symbolic Data Analysis / Ed. by E. Diday, Y. Lechevallier, O. Opitz. Berlin: Springer-Verlag, 1996. Studies in Classification, Data Analysis and Knowledge Organization. Pp. 328–338.

56. Chebotarev P. Y., Shamis E. V. Preference fusion when the number of alternatives exceeds two: Indirect scoring procedures // Proceedings of Workshop on Information / Decision Fusion /Ed. by N. S. V. Rao, V. Protopopescu, J. Bernen, G. Seetharaman. Lafayette, LA: Acadiana, 1996. Pp. 20–32.

57. Chebotarev P. Y., Shamis E. V. Constructing an objective function for aggregating incomplete preferences //Econometric Decision Models, Lecture Notes in Economics and Mathematical Systems, Vol. 453 / Ed. by A. Tangian, J. Gruber. Berlin: Springer, 1997. Pp. 100–124.

58. Chebotarev P. Y., Shamis E. V. Graph proximity functions and linear aggregation of incomplete preferences // Труды международной конференции по проблемам управления. Т. 2. Москва: Синтег, 1999. С. 271–278.

59. Chebotarev P. Y., Shamis E. V. Preference fusion when the number of alternatives exceeds two: Indirect scoring procedures // Journal of the Franklin Institute. 1999.

Vol. 336. Pp. 205–226. Erratum, J. Franklin Inst., 1999, vol. 336, pp. 747–748.

Вклад автора в работы, опубликованные в соавторстве. В работах [5,6,7,8] автором получены результаты и написаны разделы, относящиеся к агрегированию предпочтений. В [29,31,32,46] автору принадлежат постановки задач, формулировки и доказательства свойств мер достижимости вершин графов, свойств лесных метрик графов, выражений и графовых интерпретаций обобщенно обратных матриц, в [51,56,59] - аксиома самосогласованной монотонности и теоремы о необходимых и достаточных условиях ее выполнения, в [54,55,57] - систематизация оптимизационных процедур агрегирования предпочтений и доказательство их свойств, в [58] - аксиоматизация линейных процедур агрегирования, в [52] - систематизация позиционных методов агрегирования предпочтений и доказательство теоремы об эквивалентности условия самосогласованности и существования монотонной неявной формы процедуры агрегирования, в [30] - определение мер сигма-близости, формулировка и доказательство результатов о соответствии метрик и функций сигма-близости для произвольных множеств, в [53] - доказательство матричной теоремы о лесах. В [1,2,3,4,33,44,45,50] автору принадлежат постановки задач, а также результаты, относящиеся к теории графов, теории цепей Маркова, мерам близости вершин графов, матричной теореме о лесах, характеристическим многочленам нормированных лапласовских матриц, асимптотическим свойствам их спектров и агрегированию предпочтений. В [28] автором разработана методика оценивания целевых программ.




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.