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

федеральное государственное бюджетное учреждение науки

ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ им. В.А. Трапезникова Российское"

005011308

Агаев Рафиг Паша оглы

МЕТОДЫ ЛАПЛАСОВСКОЙ ТЕОРИИ ОРГРАФОВ В УПРАВЛЕНИИ МНОГОАГЕНТНЫМИ СИСТЕМАМИ

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

1 МАР Ш

АВТОРЕФЕРАТ

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

Москва 2012

005011308

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

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

Чеботарев Павел Юрьевич Официальные оппоненты:

доктор физико-математических наук, профессор Назин Александр Викторович

доктор технических наук,

профессор Фрадков Александр Львович

доктор физико-математических наук Буякас Виктор Игнатьевич

Ведущая организация — Московский государственный университет им. М.В. Ломоносова.

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

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

Автореферат разослан "_"_2012 г.

Ученый секретарь Диссертационного Совета кандидат технических наук

В.Н. Лебедев

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

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

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

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

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

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

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

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

Следует заметить, что целый ряд кажущихся на первый взгляд никак не связанными задач о поведении динамических систем и управлении ими имеет тесную связь с проблемой консенсуса для многоагентных систем. Например, решения задач синхронизации связанных осцилляторов, перемещения мобильных агентов в группе (flocking theory), быстрого согласования в "малом мире" (fast consensus in small world networks), "рандеву" в пространстве и т.д. также связаны со спектром лапласовских матриц и другими функциями от лапласовских матриц сети коммуникаций.

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

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

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

• исследование собственного проектора квадратной (в частности, лапла-

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

• исследование матриц исходящих лесов орграфов с помощью лапласов-ских матриц и их применение в децентрализованном управлении;

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

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

• решение задачи действительности спектра лапласовских матриц орграфов кольцевой структуры, моделирующих распространенный тип коммуникационных сетей;

• синтез процедур согласования мнений в многоагентиых системах при несвязном орграфе коммуникаций.

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

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

К основным новым результатам диссертации относятся следующие:

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

• исследованы свойства максимальных исходящих лесов орграфа, с помощью которых описана и интерпретирована процедура ортогональ-

иой проекции при произвольной правильной матрице влияний в дискретной модели многоагентной системы управления;

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, в Институте вычислительной математики РАН (2004 г.), на кафедре алгебры механико-математического факультета МГУ им. М.В. Ломоносова (2011 г.), в Вычислительном центре им. A.A. Дородницына РАН (2011 г.), на общемосковском семинаре "Математические методы в экспертных оценках и анализ данных", на 34-й Международной конференции "Моделирование и имитация систем", MOSIS-2000 (Остра-ва, 2000 г.), XIV Международном симпозиуме "Управление большими системами", CONTROL-2000 (Тбилиси, 2000 г.), Международной конференции по анализу порядковых и символьных данных (Брюссель, 2000 г.), 7-й Конференции Международной федерации обществ классификации (На-мюр, 2000 г.), Международной конференции по линейной алгебре (Хайфа, 2001 г.), Международной конференции по матричному анализу и его применениям (Форт Лодердейл, 2003 г.), Международной конференции обществ GAMM и SIAM по прикладной линейной алгебре (Дюссельдорф, 2006 г.), 3-й Международной конференции по проблемам управления (Москва, 2006 г.), 2-й Международной конференции по матричным методам и операторным уравнениям (Москва, 2007 г.), 16-й Международной конференции "Проблемы управления безопасностью сложных систем" (Москва, 2008 г.), Международной научной конференции "Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей" (Минск, 2009 г.), 4-й Международной конференции но проблемам

управления (Москва, 2009 г.), Международной конференции "Управление в технических системах" (С.Петербург, 2010 г.), Международных научных конференциях "Проблемы регионального и муниципального управления" (Москва, 2008, 2010,2011 гг.), 16-й Конференции Международного общества по линейной алгебре (Пиза, 2010 г.), 17-й Конференции Международного общества по линейной алгебре (Брауншвейг, 2011 г.), 54-й Научной конференции МФТИ "Проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе" (Москва-Долгопрудный, 2011 г.).

Публикации. Материал диссертации опубликован в 38 работах, среди которых 15 статей в ведущих рецензируемых журналах и одна монография.

Объем и структура работы. Диссертация состоит из введения, семи глав, заключения и списка литературы, число наименований в котором — 239. Содержание работы изложено на 256 страницах. В текст включено 17 рисунков.

Содержание диссертации

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

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

В терминологии следуем в основном классическому учебнику Ф. Ха-рари и монографии Ф.Р. Гантмахера.

Пусть Г — взвешенный орграф без петель с множеством вершин V(r) = {l,...,n} (n > 1) и множеством дуг -Е(Г). Веса всех дуг будем

предполагать положительными. Остовный подграф орграфа Г — это подграф с множеством вершин ^(Г).

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

Обозначим через .Е(Г) = (е^) матрицу весов дуг (г, .7). Ее элемент е^ равен нулю тогда и только тогда, когда из вершины г пет дуги в вершину у. Если Г' — подграф орграфа Г, то его весом е(Г') называют произведение весов всех его дуг; если в Г' есть вершины, по нет дуг, то е(Г') = 1. Вес непустого множества орграфов @ определяется так:

£(е) = $>(Я),

Яее

а вес пустого множества полагают равным 0.

Исходящее дерево — это орграф, не имеющий полуконтуров, с одной отмеченной вершиной (корнем), из которой достижимы все вершины. В исходящем дереве для всех некорневых вершин ги ¡с1(«;)=1; если ш — корень, то 1с1(ш)=0.

Исходящий лес — это орграф, в котором нет контуров и для всех вершин ги ¡с1(ш) < 1.

Лапласовская матрица — это квадратная матрица с неположительными элементами вне главной диагонали и нулевыми строчными суммами.

Матрица Кирхгофа взвешенного орграфа Г — это (п х п)-матрица Ь = £(Г) = с элементами = —] ф г, и 1ц = — ^ г = 1,..., п.

Заметим, что матрица Кирхгофа принадлежит классу лапласовских матриц. Поэтому в работе вместо выражения "матрица Кирхгофа орграфа" используется "лапласовская матрица орграфа".

Лапласовский спектр орграфа вр(1/) — это спектр (совокупность собственных значений с учетом кратностей) его лапласовской матрицы.

Класс лапласовских матриц является подмножеством М-матриц.

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

вектора Фидлера.

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

Одна из первых моделей достижения консенсуса в многоагентных системах была предложена и изучена М. Де Гроотом. В основе согласования мнений лежат итерации, последовательно сближающие мнения агентов. Если s(0) = (sq, ... ,So)T ~ вектор начальных мнений членов группы, a s( 1) = (sj,..., sf )т — вектор мнений па следующем шаге, то s(l) = Ps(0), где Р — стохастическая матрица, элемент которой щ задает степень влияния мнения j-ro агента на мнение г-го. Тем самым на к-м шаге

s{k) = Pks{ 0), к =1,2,....

Согласие достижимо, если при некотором s е IR для всех г имеет место lim^oo s'k = s.

Вероятностный вектор тт называют стационарным для стохастической матрицы Р, если имеет место 7гтР = 7гт.

В многоагентной системе согласие достигается тогда и только тогда, когда существует вектор 7г = {-к\,..., 7гп)т такой, что для всех г, j имеет место lim^oo = "j - Общее мнение в этом случае определяется формулой

E"=i

Если согласие достижимо при любых начальных мнениях, и согласованное мнение равно 7rTs(0) = ^¡Li^So' т0 вектор п — единственный

стационарный вектор для Р.

Кроме дискретной модели изучается более общая модель согласования характеристик движения, где предполагается, что каждый агент характеризуется 2d параметрами в cí-мерном пространстве: координатами и проекциями скорости. Устойчивость движения исследуется с использованием терминов, характеризующих связность орграфов коммуникаций.

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

Вторая глава посвящена собственным проекторам — главным идемпотентам квадратных (в частности, лапласовских) матриц, играющим важную роль при решении задач согласования характеристик в управлении многоагептными системами. Получены явные формулы для вычисления собственного проектора квадратной матрицы А. Доказано, что собственный проектор может быть вычислен с помощью любого аннулирующего многочлена для Аи, где и ^ ind А Пользуясь этим, можно найти компоненты и минимальный многочлен матрицы А, а также псевдообратную по Дразину ÁP. Полученные результаты используются в методе проекции для решения задачи о консенсусе, разработанном в седьмой главе.

Пусть А € Спхп - квадратная матрица. Через 7Z(A) и J\Í(A) обозначим образ и ядро А, соответственно, а через г — суммарную кратность ненулевых собственных значений A, v = тг — г — кратность 0 как собственного значения A, v = ind Л — индекс матрицы А, т.е. наименьшее к 6 {0,1,..., п — 1}, при котором гапк(ЛА;+1) = гапк(ЛА).

Собственным проектором1 матрицы А, соответствующиль собственному значению 0, называют такой проектор (т.е. идемпотентную матрицу) Z, что 7Z(Z) = M{AV) и j\f(Z) = TZ(AV). Иными словами, Z есть проектор на J\f(Av) вдоль TZ(AV).

Пусть, и > v и ip(X) = AÉ(A9 + PiA9-1 + ... + ря) — произвольный ненулевой многочлен, аннулирующий для Аи: <р(Аи) = 0.

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

Положим

2 = НА"). (2.1)

Теорема 2.1. Пусть и ^ v. Тогда для любого ненулевого многочлена Л), аннулирующего для матрицы А", матрица определяемая формулой (2.1), является собственным проектором А.

Пусть Ах,..., А4 € С — различные собственные значения А. Через 1Ук будем обозначать индекс собственного значения Хк (к = 1,...,в), т.е. размер наибольшей жордановой клетки, соответствующей А^, равный, как известно, степени множителя (А — А^) в минимальном многочлене А. Собственным проектором А, соответствующим А^, называют собственный проектор матрицы А — А¡¡I-

Отыскав Лх,..., Л5, можно использовать теорему 2.1 для нахождения соответствующих им собственных проекторов. Известно, что для любой функции / : С —> С, имеющей конечные производные /^'(Ак) в точках Аь..., А5 порядка ] — 0,..., щ соответственно, /(/1) естественно определяется следующим образом:

к=1

где под производной порядка 0 понимается значение функции.

Матрицы Z^:j называют компонентами А. При этом компонента есть собственный проектор А, соответствующий А^ (к = 1,..., в), а остальные получаются последовательным умножением Zkя па А — Хк I и на числовые коэффициенты:

г^ = (^г1(А-хк1угк о.

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

(A — Afc/)"', Uk ? ind(j4 — \kl), к = 1,... ,s, можно далее найти собственные проекторы, соответствующие всем собственным значениям, компоненты А, индексы собственных значений и минимальный многочлен для А.

Предложение 2.1. Пусть А € С"*", Z — собственный проектор матрицы A, Ai,... ,AS — ее различные собственные значения, v\,...,va — их индексы. Пусть щ,... ,и3 — целые числа такие, что щ > щ (г = 1,..., s); и > ind А. Тогда

2= П (j-m)")"'

2i?e Zkj — компонента A порядка j, соответствующая Afc, Jfc = j = 0,... ,i/fc — 1.

При j = 0 формула (2.2) дает выражения для собственных проекторов Л, соответствующих ее собственным значениям.

Результаты этой главы могут быть использованы при вычислении собственного проектора и обобщенно обратных матриц, которые играют важную роль при решении задач консенсуса в многоагентных системах. В монографии Blanchard Р., Krüger T., Volchenkov D., "Random Graphs and Random Walks. An Introduction to the Stochastic Analysis of Complex Networks and Databases" (2010) полученные здесь выражения собственного проектора использованы для нахождения групповых обратных матриц.

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

Число деревьев в максимальном лесе назовем лесной размерностью орграфа и обозначим через v. Это число равно числу базовых бикомпонент орграфа.

Пусть К = и Ki, где ..., К,, — все базовые бикомпоненты оргра-i=i

фа Г, а К^ — множество всех вершин, достижимых из Ki и недостижимых из других базовых бикомпонент. Если к 6 К, то через К (к) будем обозначать базовую бикомпоненту, содержащую к. Для любой базовой бикомпоненты К орграфа Г обозначим через сужение Г на К и через - подграф с множеством вершин У(Г) и множеством дуг Зафиксировав К, через 7" будем обозначать множество всех остовных исходящих деревьев для Гд-, а через — множество всех максимальных исходящих лесов для Через J~k (к е К) обозначим подмножество 7", состоящее из деревьев, исходящих из к, и через (г £ V(r)) — множество всех максимальных исходящих лесов орграфа в которых г достижима из некоторой вершины, принадлежащей К.

Через J-(r) = JF и Л(Г) = Tk обозначим множества всех остовных исходящих лесов орграфа Г и множество всех остовных исходящих лесов Г с к дугами, а через J^3 — множество всех остовных исходящих лесов с к дугами, где j принадлежит дереву, исходящему из г.

Предложение 3.1. iTtjcmb К — произвольная базовая бикомпонента орграфа Г и множества Т, V> Т3 и (j е К, i е V(r)) построены

по К. Тогда

1- Fn-v = TQV и = 4ТМР);

2. для любых j £ К ui £ У(Г)

= И е{тС1) = е(ТЛ)е(ГКЛ

Определим матрицу максимальных исходящих лесов Q„~v = {qffv) орграфа Г: ^ = е(^).

Теорема 3.1. Пусть Г — произвольный орграф, К — базовая бикомпонента в Г. Тогда выполняются следующие утверждения:

1. Для любого i е У(Г) £ q"~v = e(Fn-v)\

1

2- 4ifv Ф 0 {j & К иг достижима из j в Г);

3. Пусть j Е К. Для любого i £ ^(Г) имеет место q'¿j " = £{Tj)e{VK^). При этом если i <Е К+, то q%~v = = e(q-j)£(v)-

4. £ g!?"" = В частности, если j - недоминируемая зек JJ

вершина, то =

5. Если л,72 6 А", я» «Х" = (£(Th)/£(Th))qn~V, т.е. h-й и j2-U столбцы матрицы Q„-v пропорциональны.

Определение 3.1. Нормированной матрицей максимальных исходящих лесов орграфа назовем матрицу J = (Jij) = a~lQn-v, где а = £(Тп-у)-

Теорема 3.2. Для любого орграфа Г и для всех i,j 6 {1,...,п} имеет место:

1- Jii ^ Jji}

2. Если Ju > Jji, то i 6 К и j ф K+(i), где К(г) — базовая биком-понента, включающая i, и, значит, Г не содержит путей из j в ц

3. Если Ja > Jji > 0, то j ф. К, и, значит, j не является корнем ни в одном максимальном исходящем лесе Г;

4. Если Jij > 0, то Ja = J^.

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

Имеет место определенная дополнительность матриц L и J. Предложение 3.2. rank L = п — и; rank J = v.

Определение 3.2. Будем говорить, что стационарная цепь Маркова с множеством состояний {!,...,п} и матрицей переходных вероятностей Р связана с взвешенным орграфом Г, если существует а Ф 0 такое, что

Р=1-аЬ{Г).

Определение 3.3. Предельная матрица средних вероятностей цепи Маркова — это матрица

1 fc-1 B= lim r Vp1

k->00 fc ' t=0

(если предел существует). Рассмотрим матрицу

1 т-1

mU

где т — период цепи, Во,..., ßm_i — предельные матрицы для сходящихся подпоследовательностей последовательности {Р*}:

Bj = lim j = 0,..., m - 1.

¿->00

Случай m = 1 соответствует сходящейся последовательности {Р'}.

Следующая теорема, впервые полученная А.Д. Вентцелем и М.И. Фрсйдлиным и позже неоднократно персоткрывавшаяся, легко выводится из результатов дайной главы.

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

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

Результаты этой главы (предложение 3.2, теорема 3.1, 3.2, 3.4) лежат в основе метода проекции, предложенного в главе 7, для согласования характеристик в многоагентпых системах.

В четвертой главе изучены остовные исходящие леса орграфа и

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

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

Главный результат главы 4 — выражение матриц С}к = (<?§), в виде многочленов от матрицы Ь (теорема 4.2). Он позволяет получить новые доказательства для матричной теоремы о лесах, полученной П. Чеботаревым и Е. Шамис, теорем 3.3 и 3.4, а также выразить матрицу С,)(т) = (I + тЬ)~1 как многочлен от Ь.

Определим матрицы исходящих лесов = (д^) орграфа Г с А" дугами: ^ =

Обозначим через <гк вес множества всех остовных исходящих лссов в Г с к дугами: ак = е(Тк) > к = 0,..., п — V.

Теорема 4.1. Для любого взвешенного орграфа

Як+1 = <7к+11 - ЬС^к, Ок+1 = ^ , к = 0,..., п - V.

Итерации, приведенные в теореме 4.1, аналогичны алгоритму Леве-рье-Фаддеева для вычисления характеристического многочлена матрицы. Из теоремы 4.1 выводятся следующие результаты.

Следствие из теоремы 4.1. Итеративно вычисленные матрицы лесов (^к являются коэффициентами присоединенной матрицы для Ь.

Теорема 4.2. Для любого взвешенного орграфа и любого к = 0,..., п — V имеет место

к ¿=0

Предложение 4.1. Все матрицы АО/- являются лапласовскими матрицами некоторых орграфов.

Следствие 1 из теоремы 4.2. Для любого Г имеем =(¿п^Ь=0.

В силу определения 3.1 данное следствие эквивалентно теореме 3.4. Тем самым получено новое доказательство этой теоремы. Рассмотрим теперь матрицы

Имеем Зо = /, ./„_„ = 3.

В силу предложения 4.1 и следствия 1 из теоремы 4.2 матрицы <4 связаны соотношением

Л+1 = I - ЛЬ, А; = 0,... ,п — г> — 1,

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

Предложение 4.2. Для любого взвешенного орграфа Г матрицы 3^ (к = 0,... ,п — г;) являются стохастическими.

Следствие из теоремы 4.1. Для любого взвешенного орграфа

П-У

к=О

71—V

где в = е(Я = £ сгк.

¡с=О

Данное следствие совпадает с матричной теоремой о лесах для орграфов. Том самым получено новое доказательство этой теоремы.

Теорема 4.3. Для любого взвешенного орграфа Г

(J+LгWl|>™(-ь)^

¿=о

к

где, вк = ~ вес множества исходящих лесов в Г с числом дуг, не

¿=0

превосходящим к (к = 0,...,п — и).

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

Теорема 4.4. Для любого Г матрица L + J невырождена. Предложение 4.3. Для матриц L и J имеет место:

1. ДО) = ВД и ДО) = ВД;

2. ВДптг(</) = {0};

3. indL = 1;

4. матрица J является проектором для L.

Из предложений 4.3 и 3.2 следует, что число нулевых собственных значений лапласовской матрицы равно лесной размерности соответствующего орграфа. Ряд американских специалистов но управлению группами движущихся объектов (см.: Veerman J.J.P., Lafferriere G., Caughman J.S., Williams A., Flocks and Formations (2005); Caughman J.S., Veerman J.J.P., Kernels of directed graph Laplacians (2006); работы группы В. Репа) пользовались этими результатами в своих разработках. В книге иод редакцией Дж. Шаммы (Shamma J.S., Cooperative Control of Distributed Multi-agent Systems, 2007) отмечено, что полученные нами результаты позволяют охарактеризовать структурные свойства орграфов по их спектру. В монографиях Wu C.W., Synchronization in Complex Networks of Nonlinear Dynamical Systems (2007) и Mesbahi M., Egerstedt M., Graph Theoretic Methods in Multiagent Networks (2010) результаты, связывающие кратность нулевого собственного значения с лесной размерностью, используются при формулировании необходимых и достаточных условий сходимости процедур управления многоагентными системами.

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

Предложение 4.4. L* = <7n~v~1 ( Jn_„_1 — J) .

Пусть Z = L + J . Доказано, что эта матрица невырождена. Теорема 4.7. L+ = LT(ZZT)-1 = LT(f J+LLT)-1.

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

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

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

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

Основные результаты этой главы используется в методе проекции, предложенном в главе 7.

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

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

Для удобства сравнения выражений, полученных для разных п, рассматриваем стандартизованные (нормированные) лапласовские матрицы L = (tij) с элементами

— <4/^0, 3 фг, г = 1,... ,п. п

Для таких матриц

О < £ц < 1--, г = 1,... ,7г.

п

Если рассматривается класс Оь взвешенных орграфов с весами дуг, не превосходящими Ь > О, и £(Г) — лапласовская матрица взвешенного орграфа Г на п вершинах, то стандартизованная лапласовская матрица, связанная с Г в классе бь, определяется как Х(Г) =

Пусть J € Нпхп — матрица с элементами 1 /п. Рассмотрим матрицу К = I -

Определим матрицы

Р = Ь + (5.1)

ЬС = К~Ь. (5.2)

Тогда Р — стохастическая матрица. Ьс есть стандартизованная лапласовская матрица дополнительного взвешенного орграфа Гс, в котором (6 — г^-) — вес дуги (г,.?), j ф г, где е^ — вес той же дуги в Г. Если е^ — Ь, то в Гс нет дуги (г,]) и наоборот: если в Г нет дуги (г,то вес дуги (г, в Гс равен 6. Из (5.1) и (5.2) следует

Р = 1-Ьс.

Теорема 5.1. Пусть Ь — стандартизованная лапласовская матрица, Р — стохастическая матрица, определяемая формулой (5.1), Ьс определяется (5.2). Тогда для А ^ {0,1} следующие утверждения эквивалентны:

(а) А е вр(£), (Ь) А 6 зр(Р), (с) (1 - А) е вр(1£), причем эти собственные значения имеют одну и ту же геометрическую кратность. Кроме того, V — собственный вектор Ь, соответствующий А $ {0,1}, тогда и только тогда, когда вектор2

2Иногда вместо ~А используется обозначение где А — матрица, а ф 0 — комплексное число.

является собственным вектором Р, соответствующим а также собственным вектором матрицы Lc, соответствующим (1 — А).

Теорема 5.2. Пусть /¿(Л), /р(А) и fiJX) — характеристические многочлены L, Р и Lc соответственно. Тогда для всех А ^ {0,1}

}р{ А) = ^/¿(А),

/£с(А) = (-1Г114д/1(1-Л).

Теорема 5.3. Для каждой стандартизованной лапласовской матрицы L и соответствующей стохастической матрицы Р, определяемой (5.1), L и Р — сходящиеся.

Пусть тл{А) — алгебраическая кратность собственного значения А матрицы A, V¿(А) — множество собственных векторов А, соответствующих А. Собственное значение называют полупростым, если его алгебраическая и геометрическая кратности совпадают.

Теорема 5.4. Пусть v и vc — лесные размерности орграфа, соответствующего L, и дополнительного орграфа соответственно. Тогда:

1. mL{0) = V, m¿( 1) = vc - 1;

2. тр(0) = v - 1, тР( 1) = vc\ 3- m¿c(!) = v - 1, ш£с(0) = vc,

и эти собственные значения — полупростые, 4. ы <= V¿(0) и ÄU ф 0, то Ки е Vp(0) = V¿c(l); если а; € Vp(l) = VLc{0) иКхф 0, то Кх е V¿(1).

Пункт 1) теоремы 5.4 часто применяется при решении задач управления многоагсптпыми системами. Так, в работах Рена, Као (W. Ren, Y. Cao), Эгерстедта (М. Egerstedt), Менга (Z. Meng), опубликованных в Intern. J. Control, IEEE Trans. Systems, Man, and Cybernetics, IEEE Trans. Automatic

Control, Systems and Control Lett., трудах IEEE Conference on Decision and Control, показано, что необходимым и достаточным условием сходимости ряда алгоритмов управления группами мобильных автономных агентов с фиксированной и меняющейся топологией сети является единственность нулевого собственного значения лапласовской матрицы. Согласно теореме 5.4 нуль — простое собственное значение тогда и только тогда, когда орграф коммуникаций содержит дерево. В указанных публикациях при изучении дискретных и непрерывных моделей без лидера, с одним и несколькими лидерами, а также моделей с запаздыванием используются результаты па-стоящего исследования.

Позже частный случай пункта 1) теоремы 5.4, в котором v = 1, был получен также в работах Джадбабаи и др. (Jadbabaie A., Lin J., Morse А., IEEE Trans. Automatic Control, 2003); Лаффери и др. (Lafferriere G., Williams A., Caughman J.S., Veerman J.J.P., Systems and Control Letters, 2005); Лина и др. (Lin Z., Francis В., Maggiore M., IEEE Trans. Automatic Control, 2005); Моро (Moreau L., IEEE Trans. Automatic Control, 2005); Олфати-Сабера и Мюррея (Olfati-Saber R., Murray R.M., IEEE Trans. Automatic Control, 2004); Репа и др. (Ren W., Beard R.W., McLain T.W., Lecture Notes in Control and Information Sciences, 2005).

В монографии Рена и Као (Ren W., Cao Y. Distributed Coordination of Multi-agent Networks, 2011) нункт 1) теоремы 5.4 играет ключевую роль и цитируется во всех разделах. Эта теорема также использовалась в работах Масуды и др. для ранжирования узлов ориентированных сетей (Masuda N., Kawamura Y., Kori H., New Journal of Physics, 2009).

Разработчики сетевой теории децентрализованного управления Факс, Мюррей и Олфати-Сабер в своих работах, начиная с 2002 г., использовали результаты, приведенные в предложениях 3.2 и 4.3, опубликованные нами в Automation and Remote Control (2000, 2001) и присланные им по их просьбе. Тем не менее, они предпочитали приводить эти результаты как полученные заново, не ссылаясь на источники. Это обстоятельство было отражено в дискуссии, опубликованной в Proceedings of IEEE, 2010.

Теорема 5.5. 1) Все собственные значения стандартизованных лапла-

совских матриц порядка п принадлежат пересечению двух кругов с центрами в точках 1/п и 1 — 1/п и радиусом 1 — 1 /п. Кроме того, эта область входит в пересечение двух углов: меньшего угла, образованного лучами, исходящими из точки 1 и проходящими через точки е~2т!п и е2т!п, и л1енъшего угла, образованного лучами, исходящими из точки 0 и проходящими через точки и

2) Для мнимых частей Q(A) собственных значений А стандартизованных лапласовских матриц имеет место |ö(A)| < j^ctg^-

Пусть

г(п) = sup{|ö(A)| : А— с. з. стандартизованной лапласовской матрицыпхп}. Следствие 5.1. lim z(n) = 1 /7г.

п-юо

Замечание 5.1. Используя теоремы Дмитриева и Дынкина (1946) о локализации собственных значений стохастических матриц, можно показать, что sp(L) содержит собственное значение, имеющее аргумент | — тогда н только тогда, когда орграф является гамильтоновым циклом на п вершинах. При этом в силу той же теоремы собственное значение А с указанным аргументом единственно, и |А| < f sin^ ^(А) < ^sin Компоненты соответствующего собственного вектора являются вершинами правильного многоугольника. Аналогично sp(L) содержит собственное значение, принадлежащее отрезку [1,е^], тогда и только тогда, когда дополнительный орграф Гс является гамильтоновым циклом на п вершинах. В этом случае такое собственное значение А' также единственно и Э(А') < ^sin^.

Рассмотрим п — 1 матриц

Lk = -(kI-Q-Q2-...-Qk), k = 1,..., п - 1. п '

Спектр Lk содержит

\к = I (к - e~2wi,n-----е-2*"*7") , fc = 1,.. •, п - 1 (5.3)

и комплексно сопряженное число Л^.

Последнее выражение приводится к виду

A* = rr4 1 cos----tSm

ктт

ктт п

п nsm

к sin^ ^(к+1)тг 1)тг

ir гпа

п

Tl

П

)■

(5.4)

Теперь обозначим через 5 выпуклый многоугольник с 2(п — 1) вершинами Л0 = О, Ль • •., Л„_2, А„_! = 1, Лп-2,..., Ль

Теорема 5.6. Каждая точка многоугольника Б является собственным значением некоторой стандартизованной лапласовской матрицы порядка п.

llm(A)

-1/7Г

1_ Ro(A)

Рис. 5.1.

Согласно теореме 5.5 для всех п = 2,3,... z(n) ^ ^ ctg

Предложение 5.1. Если п нечетно, то

кроме того, z(n) = Q(A(n-i)/2), где \п-\)/2 определено (5.3). Предложение 5.2. Если п > 2 четно, то

max Qf(Äfc) = ö(An/2) = - ctg - < ctg 0«fc«2n-l ' п п 2п 2п

Локализация спектра лапласовской матрицы играет важную роль для оценки показателя стабилизации в децентрализованном управлении многоагентными системами (см., например, Lafferriere, G., Williams А., Caughman J., Veerman J.J.P., Decentralized control of vehicle formations, Systems and Control Letters, 2005). Этот показатель определяется дробью а(^ч-а2) ' а + ^ — собственное значение лапласовской матрицы. Чем меньше значение дроби, тем быстрее происходит стабилизация.

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

Предположение 5.1. Множество всех собственных значений стандартизованных лапласовских матриц порядка п совпадает с многоугольником S.

Теорема 5.7. Кривая (см. рис. 5.1), к которой сходится граница многоугольника S при п —»• оо образуется участками двух циклоид с параметрическими уравнениями z(t) = х(т) + гу(т) и г(т) = х{т) — гу(т), где re [ОМ,

х{т) = (27г)-1(т — sin г), у(т) = (27г)_1(1 — cost).

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

Одним из ключевых результатов является теорема, в которой доказано, что если Г„ — орграф на п > 3 вершинах, состоящий из двух противонаправленных гамильтоновых циклов, в одном из которых отсутствуют произвольные г (2 < i < п) дуг, то Г„ является существенно циклическим; указан характеристический многочлен лапласовской матрицы любого такого орграфа.

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

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

Исследование базируется па использовании многочленов Чебьшева второго рода п-й степени Р„{х), масштабированных на ]—2,2[. Эти многочлены имеют рекуррентное представление

Рп(х) = xPn-i(x) - Рп-2{х)

с начальными условиями Ро(х) s 1 и Р\{х) = х.

Рассмотрим трехдиагональную матрицу Мп = (т^) £ R."xn, которая определена следующим образом: тпц = 2 для всех г = 1 ,...,п; rriij = —1, если |i - j\ -= 1 и rriij = 0, в противном случае.

В частности, М\ = (l). Пусть Zn(x) — характеристический многочлен матрицы Мп: Zn(x) = det(xi — Мп). Заметим, что

Zn(x) = {х~ 2)Zn-l{x) - Zn_2(x),

с начальными условиями Zo(x) = 1 и Z\(х) = х — 1. Многочлен Zn(х) играет важную роль при изучении существенной цикличности орграфов с кольцевой структурой.

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

Лемма 6.1. Zn(х2) = Pin{x), для всех п = 0,1,2,...

Пусть Г* = (V„,E^) и Г^ = (Vn, El) — орграфы с множествами вершин и дуг Vn = {1,... ,n}, Е\ = {(1,п), (п,п - 1),..., (2,1)} и Е2п =

E\ U {(1,2), (2,3),..., (n - 1, n), (n, 1)}. Будем говорить, что Гп = {Vn, Е)

является орграфом кольцевой структуры, если он изоморфен некоторому Гп = (К, Е) с множеством дуг С Е С Е\.

Теорема 6.1.

1. Г' — существенно цикличен;

■^2+ | к = 1,... ,п| — его лапласовекий спектр.

2. Г2 не является существенно циклическим; его лапласовекий спектр:

Рассмотрим орграф, отличающийся от Г2 одной дугой. Пусть Г^ =

Теорема 6.2. Пусть Ь'п — лапласовская матрица орграфа Г|г, у которого множество дуг состоит из дуг гамильтонова цикла (1,тг), (тг,п — 1),..., (2,1) и дуг пути (1,2), (2,3),..., (п — 1,тг). Тогда:

1. Характеристическим многочленом для Ь'п является Д^А) =

2. rj, не является существенно циклическим, и его лапласовекий спектр есть {4 cos2 , k — 1,..., п}.

Теперь рассмотрим орграфы кольцевой структуры, состоящие из двух гамильтоновых циклов, в одном из которых удалены две произвольных дуги. Орграф Г" этого вида получается из Г', удалением некоторой дуги (г,г + 1) (1 < г < тг). Поэтому матрица L" для Г" получается из L'n заменой двух элементов в г-ой строке.

Теорема 6.3. Пуст L"n — лапласовская матрица орграфа Г", множество дуг которого состоит из дуг гамильтонова цикла (1, тг), (тг, тг—1),..., (2,1) и дуг направленных путей (1,2), (2,3),..., (г — 1,г) и (г + 1,г + 2),..., (п — 1, п), где 1 $ г < п. Тогда:

1. Ах»(А) = Zi(X)Zn-i(X) — (—1)" является характеристическим многочленом матрицы L"n\

(КХ), где = ЯЫМ)}-

Zn(А) - (—1)";

2. Если п четно, то Г" является существенно циклическим для всех г £ {1,...,п — 1} кроме г = е последнем случае собственными значениями Ь"п являют,ся 4соэ2 ^ и 4 соя2 к = 1,...,

3. Если п нечетно, то Г" является существенно циклическим для всех г £ {1,... ,п — 1} кроме г = ^^ и г = е последнем случае собственными значениями Ь"г являются 4соз2^-, к = 1,... , п.

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

Теорема 6.4. Пусть Г„ — орграф на п > 3 вершинах, состоящий из двух противонаправленных гамильтоновых циклов, в одном из которых отсутствуют произвольные г (2 < г < п) дуг. Тогда:

1. Характеристический многочлен лапласовской матрицы Ьп орграфа Г„ имеет вид

к=1

где ¿1,. ■. ,гк ~ длины путей в разложении цикла {(1,п), (п,п— 1),..., (2,1)} на пути, связывающие последовательные вершины с полустепенью

захода 1;

2. Г — существенно циклический орграф.

Если задача о действительности лапласовского спектра орграфа Г^ связана с исследованием произведения ZiZj, то решение аналогичной задачи для матрицы смежности А[[ орграфа Г" связано с анализом произведения РгР3. В силу соотношения Р2п(х) = 2п(х2) при решении задачи для лапласовского спектра рассматриваются произведения Р^Р; при четных к и I, а при доказательстве аналогичного утверждения для матрицы смежности нужно рассматривать произведения для всевозможных к и I. Решение этой задачи связано с действительностью корней уравнения р — 1 = 0

при фиксированном п, а именно, ищется значение г, при котором уравнение PiP„~i — 1=0 имеет только действительные корни.

Теорема 6.5. Спектр матрицы смежности А"п для орграфа Г" действителен тогда и только тогда, когда п четно ui —

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

Сети кольцевой структуры часто рассматриваются в качестве "сетей малого мира" (Olfati-Saber R., Ultrafast consensus in small-world networks, American Control Conference, 2005), где характеристическая длина сети исследуется с помощью лапласовского спектра орграфа. Для таких задач действительность спектра существенна, т.к. значение характеристической длины тесно связно с алгебраической связностью орграфа коммуникаций.

Сети кольцевой структуры широко используются также в моделях информационного управления в социальных сетях. В монографии Губанова Д.А., Новикова Д.А. и Чхартишвили А.Г., "Социальные сети: модели информационного влияния, управление и противоборства" такая топология используется при изучении формирования и динамики мнений агентов.

В седьмой главе изучается проблема дискретного согласования характеристик в многоагентной системе в случае, когда орграф коммуникаций не содержит остовного исходящего дерева. Дана характеризация подпространства Тр начальных мнений (где Р — матрица влияний), обеспечивающих сходимость процедуры согласования в модели Де Гроота. Предлагается метод согласования, сводящийся к 1) преобразованию вектора начальных мнений в вектор, принадлежащий области сходимости Тр, с помощью ортогональной проекции и 2) дальнейшей коррекции мнений посредством умножения матрицы влияний Р на вектор мнений. Исследованы свойства метода ортогональной проекции и показано, что любая сходящаяся процедура согласования может быть приближена процедурой Де Гроота, орграф коммуникаций который является гамильтоновым циклом. Установлено, что итоговая матрица процедуры ортогональной проекции может рассматриваться как регуляризованный предел степеней стохастической мат-

рицы.

Вершины, принадлежащие базовым бикомпонеитам, назовем базовыми, не принадлежащие — небазовыми; соответственно базовыми и небазовыми будем называть и агентов, представленных этими вершинами; число базовых вершин обозначим Ь, через и будем обозначать число базовых би-компонент.

Занумеруем сначала базовые вершины по компонентам, а затем небазовые вершины по компонентам. Матрица влияний Р и матрица Ь = I — Р приобретают нижний блочно-треугольный вид, в котором левому верхнему блоку размера 6x6 соответствуют базовые вершины орграфа коммуникаций (эти блоки обозначим Рц и Ьц):

Пусть Р — нерегулярная стохастическая матрица влияний агентов, последовательность степеней которой имеет предел. Этот предел обозначим Р°°. В пространстве векторов ¿-(О) начальных мнений найдем подпространство Тр, каждый вектор которого матрицей Р°° преобразуется в вектор с одинаковыми компонентами. В модели Де Гроота согласие достигается тогда и только тогда, когда 5'(0) € Тр, поэтому Тр будем называть областью сходимости процедуры согласования. Идея метода согласования, который представлен в настоящей главе, состоит в том, чтобы до начала итераций заданный вектор начальных мнений а(0), не принадлежащий Тр, преобразовать в максимально близкий к нему вектор из Тр.

Следующая теорема характеризует область Тр.

Теорема 7.1. Если последовательность степеней стохастической матрицы Р сходятся к Р°°, то Тр = Ц{Ь)®Т\, где ТР — подпространство начальных мнений з(0), для которых достигается согласие в модели Де Гроота, Ь = I — Р, Т\ — линейная оболочка вектора 1 = (1,..., 1)т.

Если матрица Р нерегулярна, то Тр ф И", т. е. существуют векторы начальных мнений, не приводимые данной процедурой Де Гроота к консенсусу. Рассмотрим случай, когда достичь консенсуса все же необходимо. Как

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

Преобразование, отображающее произвольный вектор в(0) в ближайший к нему по евклидовой метрике вектор из Тр, осуществляется оператором ортогонального проектирования И" на Тр (вдоль ортогонального подпространства Тр). Известно, что этот проектор задается симметричной идемпотентной матрицей; обозначим ее 5.

Таким образом, предельный вектор мнений з(оо) с учетом коррекции начальных условий выражается произведением Рос5а(0):

з(оо) = Р°°5й( 0).

Эту процедуру назовем процедурой ортогональной проекции в задаче о консенсусе. Матрицу будем называть итоговой матрицей просо

цедуры ортогональной проекции и обозначать через Р:

Р=

По построению процедура ортогональной проекции приводит к консенсусу при любом векторе начальных мнений я(0). Следовательно все стро-

оо

ки матрицы Р одинаковы, т. е. существует вектор а = (сц,..., ап) :

со _

Р= 1а . (7.2)

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

в(оо) = Р°°5«(0) =Р з(0) = 1атв(0) = 1в, (7.3)

где 5 = атв(0) — консенсус.

Матрица 5 имеет единичные строчные суммы. С учетом того, что

оо

роо _ СТОхастическая, получаем, что Р= Р°°3 также имеет единичные

строчные суммы, т. е. оц = 1. При этом 5 может иметь отрицательные элементы, и вопрос о неотрицательности элементов а нетривиален. Ответ

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

Для прямоугольной матрицы А матрица АА+, где А+ — псевдообратная к Л по Муру-Пенроузу, является ортогональным проектором с образом Ц(А). Пусть U — матрица, полученная из матрицы L отбрасыванием по одному столбцу, соответствующему какой-либо вершине каждой базовой бикомпонеиты, с последующим добавлением столбца из единиц 1 в качестве первого. Тогда rank U = n — + 1, т. е. U — матрица полного столбцового ранга и в силу теоремы 7.1 1Z(U) = Тр. Ортогональный проектор S с образом Тр можно определить выражением S = UU+. Для определения U+ воспользуемся формулой U+ = (UTU)+UT, которая для матрицы полного столбцового ранга U приобретает вид U+ = (U1:UyAUT. Тогда

где 5в — ортогональный проектор на область сходимости Трв процедуры с матрицей Рц.

2. Область сходимости процедуры Де Гроота есть Тр=Трвх Ип~\

Предложение 7.1. Если матрица Р — правильная, то итоговый вектор мнений й(оо) метода ортогональной проекции не зависит от исходных мнений небазовых агентов.

Отметим, что согласно (7.3) .ч(оо) = Рхя'(0), где в'(0) = 5б'(0). При этом в силу п. 1 теоремы 7.2 компоненты в'(0), отвечающие небазовым вершинам, равны соответствующим компонентам й(0). Тем самым, предкоррек-ция, осуществляемая матрицей 5, не меняет мнений небазовых агентов. И это естественно: изменение компонент, которые никак не повлияют на итог,

5 = UU+ = U(UTUylUT.

(7.4)

Теорема 7.2. 1. Ортогональный проектор S на Тр имеет вид

(7.5)

вошло бы в противоречие с минимизацией ||з'(0) — б'(0)[[, обеспечиваемой ортотональным проектированием.

Предложение 7.2. Для любой правильной матрицы Р вектор а, определяющий итоговую матрицу Р= 1аТ метода ортогональной проекции, имеет вид

а = («!,..., а6,0,...,0)т, где («1,..., щ) — любая строка матрицы (Рв^Зв (см. (7.1), (7.5)).

Ответ на более общий вопрос: "Влияет ли на результат согласования мнений присутствие небазовых агентов?" — также отрицательный.

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

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

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

Пусть, как и ранее, число базовых бикомпонент равно гл Поскольку между ними нет связей, процедура Де Гроота, использующая матрицу Р, распадается на и автономных процессов. Пусть ггц — число вершин в г-ой бикомпоненте. Ее матрицу Кирхгофа обозначим через Ь{ = (£'т). В рассматриваемом случае матрица Ь и соответствующая предельная матрица

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

Pi = I~Li, г = 1,...,п. Поскольку матрица Р — I — L — блочио-диагональная, Ff° = lim Pf, г = 1,... ,п.

г к->ос 1

Матрицы Р-° соответствуют сильно связным орграфам, поэтому все строки каждой из них одинаковы, и эти матрицы представляются в виде

РГ = 1(<)т, i = \,...,v,

где (7г')т — любая строка Р2°°.

Поставим следующую задачу: выяснить, как вектор а, входящий в представление (7.2) метода ортогональной проекции, связан с векторами 7г\ Пусть ql = л-*-1 — 7гг, г = 2,..., р, где ттг Е lRn есть вектор пг, дополненный нулевыми элементами в позициях, отвечающих всем бикомпонентам, кроме г-ой. Определим матрицу X следующим образом: X получается из L заменой первого столбца столбцом 1 из п единиц и заменой первого столбца каждого из блоков, соответствующих остальным базовым бикомпонентам, столбцом из нулей. Таким образом, матрица X содержит v — 1 столбцов из нулей, а все остальные столбцы линейно независимы, и rankX — п — I/ + 1.

Теперь построим матрицу Z, заменив в X нулевые столбцы в блоках с номерами i = 2,..., v векторами q'.

Лемма 7.1. Матрица Z — невырожденная.

Ортогональный проектор S с образом Тр определим выражением

S = XZ-\ (7.6)

Теорема 7.3. 1. Вектор-строка ат совпадает с первой строкой

2. Все компоненты вектора а положительны, и = 1- Сумма элементов любой строки Z~~x, кроме первой, равна нулю.

3. Пусть д есть к-я вершина г-ой бикомпоненты Г, /г есть г-я вершина ¿-ой бикомпоненты. Тогда

где Д = (¿')2/ХХ='1№)2> ? и Ц — суммарный вес всех остовных исходящих деревьев в г-ой бикомпоненте Г и суммарный вес тех из них, которые имеют корень I.

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

Проектор Б может быть представлен в виде (7.6) и в общем случае, т. е. при наличии нсбазовых агентов. Для этого достаточно применить определения матриц X я Z к произвольной матрице Ь.

Матрицу X, определенную выше для множества базовых вершин (обозначим ее Х&), дополним нулевым блоком справа, блоком отвечающим в Ь небазовым вершинам, и произвольно заполненным блоком3 С. Матрица Z — аналогичное расширение Zв'■

Предложение 7.4. 1. Ортогональный проектор на область сходимости процедуры Де Гроота имеет представление £> = XZ~1, где X и Z определены (7.7).

гр оо _

2. Вектор-строка сс такая, что Р= 1 а , есть первая строка Z~1.

Важно отметить, что смысл п. 2 теоремы 7.3 выходит за рамки задачи о консенсусе. А именно, с учетом определения ортогонального проектора

3В частности, блок в, может быть взят из матрицы Ь.

ад _ Д 4

(7.7)

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

оо

рица Р= Р°°Б 1) стохастическая, 2) имеет ранг 1, значит, все ее строки

оо

одинаковы, и 3) в случае, когда Р регулярна, Р~ Р00.

Кроме того, п. 3 теоремы 7.3 устанавливает, что элементы вектора а, определяющего матрицу Р, связаны естественными соотношениями. А именно, в рамках одной (г-й) базовой бикомпоненты их отношение равно отношению соответствующих элементов вектора тгг — стационарного вектора бикомпоненты; если же они принадлежат разным бикомпонентам, то дополнительный множитель равен отношению "весов" бикомпонент, определяемых их внутренней однородностью по весам деревьев, входящих в их вершины.

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

Эти свойства позволяют назвать матрицу Р, сопоставленную нерегулярной стохастической матрице Р, регуляризованным пределом степеней Р1, Р2,... матрицы Р.

Предложение 7.5. Для любой правильной матрицы Р

СО

1) вектор а такой, что Р= 1а , есть стационарный вектор матрицы Р:атР = ат;

оо оо оо оо оо

2) РР = РР=Р30Р = РР00 = Р.

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

Лемма 7.2. Для любого положительного вектора д = (дъ • • •, дп)Т существует единственный взвешенный гамильтонов цикл вида п —> (п — 1) —> • • • —» 2 —> 1 —> п, вектор (¿1,..., £П)Т суммарных весов исходящих деревьев которого совпадает с 5. Вес дуги, входящей в вершину к в этом цикле, равен " у ПГ=1 к = 1,..., п.

Рассмотрим орграф коммуникаций Г(У,Е), состоящий только из не связанных сильных бикомпонеит. В каждой к-й бикомпоненте зафиксируем произвольную вершину Ук,к = \,... Эти вершины соединим циклом /г = (в1,... ,е„), где е^ = (^,«¡+1), г = 1,...,1> и ^¡,+1 = г?ь к соединяет бикомпоненты в одну. Полученный орграф обозначим через Г''(К, Ей). В силу связности Г''(1/, Еь) последовательность степеней его матрицы влияний имеет предел — матрицу с одинаковыми строками. Эту регулярную положительную матрицу обозначим через

Предложение 7.6. 1. Для некоторого цикла К = (в!,..., е„), соединяющего все базовые бикомпоненты, при определенных весах дуг ..., ■ш(е„), предел последовательности степеней матрицы влияний связанной с орграфом ГЬ(У, Ей), совпадает с итоговой матрицей процедуры ортогональной проекции при орграфе коммуникаций Г(У,Е). 2. Каждый блок матрицы 3^ пропорционален соответствующему блоку матрицы Р°°.

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

п

= г = 1,...,п. (7.8)

3=1

В матричной форме (7.8) можно представить как х(Ь) = —Ьх(р), где

Ь = (£ц) с элементами = —а^, при j и £ц = — £ £ц, г = 1,..., п.

Зфг

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

Предложение 7.7. Еслих(Ь) — решение уравнения £(£)= — , удо-

влетворяющее начальному условию х(0) = хо, то

Ит а;^) = 3Хо, ¿->00

где J — собственный проектор лапласовской матрицы Ь.

Основные результаты диссертационной работы

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

В ходе решения поставленных задач получены следующие основные научные результаты:

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

• предложен метод вычисления собственного проектора — главного идемпотента произвольной матрицы. Установлено, что главный идем-потент лапласовской матрицы совпадает с предельной матрицей влияний модели Де Гроота и играет важную роль в управлении многоагентными системами;

• исследованы нормированные матрицы максимальных исходящих лесов

орграфа коммуникаций, являющиеся предельными матрицами влияний для дискретных моделей согласования мнений в многоагентных системах;

• доказано, что условие достижения согласия в децентрализованном управлении многоагентной системой выполняется тогда и только тогда, когда максимальный исходящий лес является деревом;

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

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

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

• установлено, что в случае правильной матрицы влияний многоагентной системы область сходимости модели Де Гроота равна прямой сумме образа соответствующей лапласовской матрицы и линейной оболочки вектора из единиц;

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

посредством заданной матрицы влияний;

• установлено, что итоговая матрица ортогональной проекции дискретной модели согласования мнений совпадает с нормированной матрицей максимальных исходящих деревьев специального орграфа коммуникаций, в котором все агенты соединены гамильтоновым циклом;

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

Основные публикации по теме работы

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

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

3. Агаев Р. П., Чеботарев П. Ю. О нахождении собственного проектора и компонент матрицы // Автоматика и Телемеханика. — 2002. — № 10. — С. 3-12.

4. Chebotarev Р., Agaev R. Forest matrices around the Laplacian matrix // Linear Algebra and its Applications. - 2002. - Vol. 356. - Pp. 253-274.

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

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

7. Агаев P. П., Никифоров С. В., Андрюшина Н. А. О спектре матрицы смежности орграфа кольцевой структуры и его применении // Проблемы управления. — 2008. — №4.-С. 11-15.

8. Агаев Р. П. Об исследовании и применении лапласовских спектров орграфов кольцевой структуры // Автоматика и телемеханика. — 2008. — № 2. — С. 3-16.

9. Чеботарев П. Ю., Агаев Р. П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов // Автоматика и телемеханика.— 2009. — № 3. — С. 136-151.

10. Agaev R., Chebotarev P. Which digraphs with ring structure are essentially cyclic? // Advances in Applied Mathematics. — 2010. —Vol. 45, no. 2,— Pp. 232-251.

11. Агаев Р. П., Чеботарев П. Ю. Сходимость и устойчивость в задачах согласования характеристик (обзор базовых результатов) // Управление большими системами. —

2010. - Т. 30, № 1. - С. 470-505.

12. Агаев Р. П. Дискретная процедура согласования характеристик с помощью минимального цикла, объединяющего базовые бикомпоненты // Управление большими системами. — 2011. — Т. 34. — С. 46-61.

13. Агаев Р. П., Чеботарев П. Ю. Метод проекции в задаче о консенсусе и регуляризо-ванный предел степеней стохастической матрицы //Автоматика и Телемеханика. —

2011. — № 12.-С. 38-59.

14. Чеботарев П. Ю., Агаев Р. П. Уточнение к статье "О нахождении собственного проектора и компонент матрицы" // Автоматика и Телемеханика. — 2011. — № 3. — С. 173.

15. Агаев Р. П. Об области сходимости дифференциальной модели достижения консенсуса // Управление большими системами. — 2012. — Т. 36.

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

2012. - № 1. - С. 178-183.

17. Чеботарев П. К)., Агаев Р. П. Матричная теорема о лесах и лапласовские матрицы орграфов. — 2011. — Саарбрюккене, Lambert, 2011.

18. Чеботарев П. 10., Агаев Р. П. Псевдообратная матрица для матрицы Кирхгофа ориентированного графа / Труды 14 Международного Симпозиума "Управление большими системами", CONTROL'2000. - Тбилиси: 2000. - С. 23-25.

19. Chebotarev P., Agaev R., Shamis Е. The out forests of a (di)graph and the investigation of its structure / International Conference on Ordinal and Symbolic Data Analysis. — Bruxelles: Universite Libre de Bruxelles, 2000. — P. 8.

20. Chebotarev P., Shamis E., Agaev R. A new metric for graph vertices and its properties / Abstracts of the 7th Conference of the International Federation of Classification Societies. — Namur: University of Namur, 2000. — P. 46.

21. 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.

22. Agaev R. P. On the generalized inverses of the Kirchoff matrix / International Linear Algebra Conference. — Haifa: Institute of Advanced Studies in Mathematics, Technion, 2001. - P. 13.

23. Agaev R., Chebotarev P. On the Faddeev matrix and the generalized inverses /International Conference on Matrix Analysis and Applications. — Fort Lauderdale: Nova Southeastern University, 2003. — P. 1.

24. Chebotarev P., Agaev R. On of the spectrum of the digraph Laplacian / International Conference on Matrix Analysis and Applications. — Fort Lauderdale: Nova Southeastern University, 2003. - Pp. 4-5.

25. Агаев P. П. О матричных коэффициентах присоединенных матриц / Третья межд. конф. по проблемам управления. Тезисы докладов.- Т.1.— Москва: 2006.— С. 70.

26. Chebotarev P., Agaev R. When is the Laplacian spectrum of a weighted digraph real? / International GAMM-SIAM Conference on Applied Linear Algebra. — Düsseldorf: University of Düsseldorf, 2006. — P. 29.

27. Agaev R. On the spectra of the Laplacian matrices of a certain class / 2 International conference on matrix methods and operator equations. — Moscow: Institute of Numerical Mathematics RAS, 2007. - P. 1.

28. Агаев P. П., Никифоров С. В. О свойствах сетей с разреженными топологиями /Проблемы управления безопасностью сложных систем. Труды XVI международной конференции. — Москва: Издательский центр РГГУ 2008. — С. 39-42.

29. Агаев Р. П., Никифоров С. В. Об оценке отказоустойчивости сетей с кольцевой структурой / Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. — Москва: Издательский центр РГГУ 2008. - С. 182-186.

30. Агаев Р. П. О числе входящих деревьев орграфов кольцевой структуры /Труды четвертой международной конференции по проблемам управления. — Москва: 2009. — С. 1639-1641.

31. Чеботарев П. Ю., Агаев Р. П. Управление многоагентными системами и спектры лапласовских матриц орграфов / Труды четвертой международной конференции по проблемам управления, — Москва: 2009.— С. 1571-1584.

32. Agaev R. The problem of the reality of the Laplacian spectrum of digraphs / Массовое обслуживание: потоки, системы, сети. Международная научная конференция "Современные математические методы анализа и оптимизации информациоино-телекоммуникационных сетей". — Минск: 2009. — С. 268-273.

33. Агаев Р. П. Об одной методе согласования характеристик в многоагеитных системах при орграфе коммуникаций, не имеющем остовного дерева / Материалы конференции "Управление в технических системах" (УТС-2010). — Санкт-Петербург: 2010. — С. 99-102.

34. Агаев Р. П., Никифоров С. В. Об одном методе согласования мнений в многоагентной системе / Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции.— Москва: Издательский центр РГГУ 2010.- С. 47-50.

35. Агаев Р. П., Никифоров С. В. Объединение базовых бикомпонент гамильтоновым циклом минимальной длины для задач консенсуса в многоагентных системах /Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. — Москва: Издательский центр РГГУ 2010. — С. 208212.

36. Agaev R. P., Chebotarev P. Which digraphs with ring structure are essentially cyclic? / 16th Conference of the International Linear Algebra Society. — Pisa, Italy: University of Pisa, 2010. - P. 29.

37. Agaev R. P., Chebotarev P. A regularized limit of a decomposable stochastic matrix / 17th ILAS Conference. Pure and Applied Linear Algebra: The new Generation.— Braunschweig, Germany: Technische Universität Braunschweig, 2011. — P. 170.

38. Агаев Р. П. Процедуры согласования характеристик в управлении многоагентными системами /Труды 54-й научной конференции МФТИ. "Проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе".— Москва-Долгопрудный-Жуковский 2011,— С. 96.

Вклад автора в работы, опубликованные в соавторстве. В работах [16,18-21,24,26] автором написаны разделы, относящиеся к теории графов, связи между лесной размерностью и кратностью нулевого собственного значения, исследованию структур орграфов, свойствам нормированных матриц исходящих деревьев, итеративному методу вычисления исходящих деревьев, явным выражениям для вычисления проекторов матриц, области локализации спектров лапласовских матриц. В [22,23] автору принадлежат постановки задач. В [7] автору принадлежит постановка задачи, доказательства теорем. В [9,10] автору принадлежат постановки задач и результаты, относящиеся к спектру лапласовских матриц орграфов четного порядка, существенной цикличности орграфов кольцевой структуры, в которых удалены больше двух дуг. В [13,16] автору принадлежат постановки задач и доказательства теорем, связанных с областью сходимости, выражениями для проекторов, регуляризованной стохастической матрицей, гамильтоновым циклом. В [28-31,34-37] автору принадлежат постановки задач, доказательства теорем.

Зак. IB. Тир. 100. ИПУ РАН.

Введение

Глава 1. Основные определения и базовые результаты

1.1. Общие понятия теории графов.

1.2. О лапласовском спектре орграфа.

1.3. Некоторые результаты исследования лапласовского спектра неориентированного графа

1.4. Модели достижения консенсуса.

1.4.1. Дискретные модели достижения консенсуса.

Модель Де Гроота.

Обобщения модели Де Гроота.

Дискретная модель согласованного движения по плоскости

1.4.2. Непрерывные модели согласования характеристик

Модель с коррекцией скоростей.

Задача устойчивости

1.5. О модели движения стаи

Выводы к главе

Глава 2. О нахождении собственного проектора и компонент матриц

3.2. Основные понятия.62

3.3. Свойства остовных исходящих лесов.63

3.4. Максимальные исходящие леса, базы и базовые бикомпоненты 66

3.5. Конструктивное описание максимальных исходящих лесов . . 70

3.6. Матричные теоремы о лесах в параметрической форме . 72

3.7. Матрица максимальных исходящих лесов.73

3.8. Цепи Маркова, связанные с взвешенным орграфом .83

3.9. Вес максимальных исходящих лесов как показатель достижимости вершин орграфа.91

3.10. Матрица предельных достижимостей и задача о лидере . 94

3.11. Матрицы лесов и задача структурирования орграфа.97

Выводы к главе 3 .102

Глава 4. Остовные леса орграфа и их применения 104

4.1. Введение.104

4.2. Предварительные результаты.105

4.3. Матрицы исходящих лесов и переходные вероятности цепей Маркова.107

4.4. Выражение матриц лесов через лапласовскую матрицу и его следствия.110

4.5. О некоторых линейных операторах, связанных с орграфом . . 118

4.6. Псевдообратная и групповая обратная матрицы для лапласовской матрицы.125

4.7. Об области Гершгорина и аннулирующем многочлене лапла-совской матрицы.130

4.8. Достижимость по лесам и по "густым" лесам в орграфе . 131

4.8.1. Достижимость по лесам .131

4.8.2. Достижимость по "густым" лесам.134

Выводы к главе 4 .137

Глава 5. Лапласовские спектры орграфов 139

5.1. Лапласовские и стохастические матрицы .140

5.2. Связь спектров лапласовских и стохастических матриц . 142

5.3. Область, содержащая лапласовские спектры.147

5.4. Многоугольник лапласовских собственных значений.149

5.5. Об асимптотических свойствах лапласовских спектров . 152 Выводы к главе 5 .153

Глава 6. Спектры лапласовских матриц орграфов кольцевой структуры 154

6.1. Введение и основные понятия.154

6.2. Вспомогательные леммы.157

6.3. Существенно циклические орграфы кольцевой структуры . . . 159

6.3.1. Орграфы Г* с п дугами и Г^ с 2п дугами .160

6.3.2. Орграфы Г^ с 2п — 1 дугами.161

6.3.3. Орграфы Г" с 2п — 2 дугами.162

6.3.4. Орграфы Гп с т (п < т < 2п — 2) дугами.170

6.4. Существенная цикличность взвешенных орграфов.175

6.5. О спектре матрицы смежности орграфа с кольцевой структурой 182

6.6. Другие применения многочленов Чебышева второго рода в задачах исследования лапласовских матриц.183

6.7. Об оценке мнимых частей собственных значений лапласовской матрицы циркулянтного орграфа четного порядка.185

6.7.1. Оценка Пика. 185

6.7.2. Оценка 1ш|(Л)| для матрицы четного порядка. 186

Выводы к главе 6 . 191

Глава 7. Метод проекции в задаче о консенсусе и регуляризованный предел степеней стохастической матрицы 192

7.1. Введение. 192

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

7.3. Условия, гарантирующие достижение согласия в модели

Де Гроота. 195

7.4. Характеризация области сходимости процедуры Де Гроота . . 197

7.5. Метод ортогональной проекции. 198

7.6. Компонентная структура ортогонального проектора и области сходимости . 200

7.7. Небазовые агенты в методе проекции . 202

7.8. Неортогональное проектирование на область сходимости . . . 204

7.9. Метод ортогональной проекции в случае, когда все агенты -базовые . 206

7.10. Об интерпретации метода ортогональной проекции. 212

7.11. Метод ортогональной проекции при произвольной правильной матрице влияний. 213

7.12. Регуляризованный предел стохастической матрицы. 214

7.13. Представление итоговой процедуры согласования взвешенным гамильтоновым циклом. 215

7.14. Дискретная процедура согласования характеристик с помощью минимального цикла, объединяющего базовые бикомпо-ненты . 219

7.15. Метод ортогональной проекции как частный случай процедуры минимального объединяющего цикла . 221

7.16. О свойствах трансформирующей матрицы для Ь.226

7.17. Согласование характеристик в дифференциальной модели с начальным вектором состояний.228

Выводы к главе 7 .231

Заключение 233

Список литературы.236 г

Введение

Актуальность темы. Решение многих задач управления многоагент-ными системами сводится к анализу лапласовской матрицы ориентированного графа комммуникаций агентов и матриц, связанных с ней. Как для дискретных [159,199-201,206-209], так и для непрерывных моделей согласования мнений и управления группой движущихся объектов [109,135-138,166,167, 199-201,203,205,208,209,213,224,230] знание спектра, собственных проекторов, миноров и других функций лапласовской матрицы орграфа коммуникаций позволяет ответить на все основные вопросы о поведении моделируемой системы.

В начале 2000-х годов проблема децентрализованного управления группой движущихся объектов со структурой информационных связей, задаваемой графом, изучалась в [135,138]. В этих работах структурные свойства и собственные значения-лапласовских матриц орграфа коммуникаций впервые используются для анализа сходимости и устойчивости группы движущихся объектов.

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

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

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

В [205] предложен вычислительный алгоритм для согласования траекторий при ограничениях, наложенных на управление. Этот алгоритм обеспечивает согласование траекторий в случае, когда лидеры группы и структура связей меняются. Алгоритм был применен для согласования траекторий движения роботов.

В более общих моделях совместного движения предполагается, что каждый агент характеризуется 2d параметрами (координаты и проекции скорости) в (i-мерном пространстве. Задача состоит в построении траекторий, согласованных с заданным курсом и поддерживающих предписанную конфигурацию группы объектов. Для исследования устойчивости таких систем необходимо нахождение спектра лапласовской матрицы графа коммуникаций [230]. Достаточное условие устойчивости формулируется в терминах действительной части ненулевого собственного значения лапласовской матрицы [224]. Необходимое и достаточное условие устойчивости задается системой неравенств, зависящей от элементов матрицы управления и ненулевого собственного значения лапласовской матрицы [167].

Следует заметить, что целый ряд кажущихся на первый взгляд никак не связанными задач о поведении динамических систем и управлении ими имеет тесную связь с проблемой консенсуса для многоагентных систем. Например, решения задач синхронизации связанных осцилляторов, перемещения мобильных агентов в группе (flocking theory), быстрого согласования в "малом мире" (fast consensus in small world networks), "рандеву" в пространстве и т.д. также связаны со спектром лапласовских матриц и другими функциями от лапласовских матриц сети коммуникаций.

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

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

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

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

• исследование матриц исходящих лесов орграфов с помощью лапласовских матриц и их применение в децентрализованном управлении;

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

• решение задачи действительности спектра лапласовских матриц орграфов кольцевой структуры, моделирующих распространенный тип коммуникационных сетей;

• синтез процедур согласования мнений в многоагентных системах при несвязном орграфе коммуникаций.

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

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

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

• исследованы свойства максимальных исходящих лесов орграфа, с помощью которых описана и интерпретирована процедура ортогональной проекции при произвольной правильной матрице влияний в дискретной модели многоагентной системы управления;

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

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

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

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, в Институте вычислительной математики РАН (2004 г.), на кафедре алгебры механико-математического факультета МГУ им. М.В. Ломоносова (2011 г.), в Вычислительном центре им. A.A. Дородницына РАН (2011 г.), на общемосковском семинаре "Математические методы в экспертных оценках и анализ данных", на 34-й Международной конференции "Моделирование и имитация систем", MOSIS-2000 (Острава, 2000 г.), XIV Международном симпозиуме "Управление большими системами", CONTROL-2000 (Тбилиси, 2000 г.), Международной конференции по анализу порядковых и символьных данных (Брюссель, 2000 г.), 7-й Конференции Международной федерации обществ классификации (Намюр, 2000 г.), Международной конференции по линейной алгебре (Хайфа, 2001 г.), Международной конференции по матричному анализу и его применениям (Форт Лодердейл, 2003 г.), Международной конференции обществ GAMM и SIAM по прикладной линейной алгебре (Дюссельдорф, 2006 г.), 3-й Международной конференции по проблемам управления (Москва, 2006 г.), 2-й Международной конференции по матричным методам и операторным уравнениям (Москва, 2007 г.), 16-й Международной конференции "Проблемы управления безопасностью сложных систем" (Москва, 2008 г.), Международной научной конференции "Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей" (Минск, 2009 г.), 4-й Международной конференции по проблемам управления (Москва, 2009 г.), Международной конференции "Управление в технических системах" (С.Петербург, 2010 г.), Международных научных конференциях "Проблемы регионального и муниципального управления" (Москва, 2008, 2010, 2011 гг.), 16-й Конференции Международного общества по линейной алгебре (Пиза, 2010 г.), 17-й Конференции Международного общества по линейной алгебре (Брауншвейг, 2011г.), 54-й Научной конференции МФТИ "Проблемы фундаментальных и прикладных, естественных и технических наук в современном информационном обществе" (Москва-Долгопрудный, 2011г.).

Публикации. Материал диссертации опубликован в 38 работах, среди которых 15 статей в ведущих рецензируемых журналах и одна монография.

Объем и структура работы. Диссертация состоит из введения, семи глав, заключения и списка литературы, число наименований в котором — 239. Содержание работы изложено на 256 страницах. В текст включено 17 рисунков.

Выводы к главе 7

В главе 7 рассмотрена задача согласования мнений агентов в случае, когда их матрица влияний, входящая в модель Де Гроота, правильна, но не регулярна. Для решения этой задачи предложен метод проекции, на первом этапе отображающий пространство всевозможных начальных мнений на специальное подпространство Тр, каждый вектор которого дальнейшей итеративной коррекцией приводится к консенсусу. Область Тр есть прямая сумма 71{Ь), где Ь = I — Р, и линейной оболочки вектора из единиц. Исследованы свойства метода ортогональной проекции и показано, что любая сходящаяся процедура согласования может быть приближена процедурой Де Гроота, орграф влияний который является гамильтоновым циклом. Установлено, что оо итоговая матрица Р = Р°°3 метода ортогональной проекции, где 5 - ортогональный проектор на Тр, = Ит^оо Рк, может рассматриваться как регуляризованный предел степеней стохастической матрицы Р. При применении предложенного метода на первом этапе изменению подвергаются мнения только тех агентов, которые соответствуют базовым вершинам. А мнения других агентов не меняются. Но с другой стороны, эти же мнения не влияют на конечный результат согласования мнений.

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

Заключение

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

В ходе решения поставленных задач получены следующие основные научные результаты:

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

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

1. Агаев Р. П. О матричных коэффициентах присоединенных матриц // Третья межд. конф. по проблемам управления. Тезисы докладов.-Т.1.- Москва: 2006,- С. 70.

2. А гаев Р. П. Об исследовании и применении лапласовских спектров орграфов кольцевой структуры //Автоматика и телемеханика. — 2008. — № 2. С. 3-16.

3. Агаев Р. П. О числе входящих деревьев орграфов кольцевой структуры // Труды четвертой межд. конф. по проблемам управления. — Москва: 2009.- С. 1639-1641.

4. Агаев Р. П. Об одном методе согласования характеристик в многоагент-ных системах при орграфе коммуникаций, не имеющем остовного дерева //Материалы конференции "Управление в технических системах" (УТС-2010). Санкт-Петербург: 2010. - С. 99-102.

5. Агаев Р. П. Дискретная процедура согласования характеристик с помощью минимального цикла, объединяющего базовые бикомпоненты // Управление большими системами. — 2011. — Т. 34. — С. 46-61.

6. Агаев Р. П. Об области сходимости дифференциальной модели достижения консенсуса // Управление большими системами. — 2011. — Т. 35.

7. Агаев Р. П., Никифоров С. В. О свойствах сетей с разреженными топологиями // Проблемы управления безопасностью сложных систем. Труды XVI международной конференции. — Москва: Издательский центр РГ-ГУ 2008. С. 39-42.

8. Агаев Р. П., Никифоров С. В. Об оценке отказоустойчивости сетей с кольцевой структурой // Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции. — Москва: Издательский центр РГГУ 2008. С. 182-186.

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

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

11. Агаев Р. П., Чеботарев П. Ю. О нахождении собственного проектора и компонент матрицы // Автоматика и Телемеханика. — 2002. — № 10. — С. 3-12.

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

13. Агаев Р. П., Чеботарев П. Ю. Сходимость и устойчивость в задачах согласования характеристик (обзор базовых результатов) // Управление большими системами. — 2010. — Т. 30, № 1. — С. 470-505.

14. Агаев Р. П., Чеботарев П. Ю. Метод проекции в задаче о консенсусе и регуляризованный предел степеней стохастической матрицы // Автоматика и Телемеханика. — 2011. — № 12.— С. 38-59.

15. Агаев Р. П., Чеботарев П. Ю. Представление дискретной процедуры согласования характеристик с помощью циклического орграфа // Автоматика и Телемеханика. — 2012. — № 1. — С. 178-183.

16. Барабанов И. Н., Коргин Н. А., Новиков Д. А., Чхартишвили А. Г. Динамические модели информационного управления в социальных сетях // Автоматика и телемеханика. — 2010. — № 11. — С. 172-182.

17. Белкин А. Р., Левин М. Ш. Принятие решений: комбинаторные модели аппроксимации информации. — Москва: Наука, 1990.

18. Блюмин С. Л. Мультиагентные системы: проблемы и протоколы согласия, псевдообращение лапласианов графов // Системы управления и информационные технологии. — 2007. — № 2(28). — С. 4-9.

19. Буякас В. И. Задача управления коллективным движением // Автоматика и телемеханика. — 1974. — № 2. — С. 63-77.

20. Буякас В. И. Математическая модель взаимодействия хищника и стаи // Доклады Академии Наук СССР. 1981. - Т. 261, № 1. - С. 252-256.

21. Буякас В. И., Дарков А. А., Радаков Д. В., Чекулаев Ю. В. Математическая модель движения стаи рыб // Вопросы ихтиологии. — 1978. — Т. 18, № 5. — С. 924-934.

22. Вентцель А. Д., Фрейдлин М. И. О малых случайных возмущениях динамических систем // Успехи математических наук. — 1970. — Т. 25. — С. 3-55.

23. Габасов Р., Дмитрук Н. М., Кириллова Ф. М. Оптимальное децентрализованное управление группой динамических объектов // Журнал вычислительной математики и математической физики. — 2008. — Т. 48, № 4. С. 593-609.

24. Гантмахер Ф. Р. Теория матриц. — 3 изд. — Москва: Наука, 1988.

25. Гельфанд И. М. Лекции по линейной алгебре. — М.: Наука, 1971.

26. Губанов Д.А., Новиков Д. А., Чхартишвили А.Г. Социальные сети: модели информационного влияния, управления и противоборства. — Москва: Физматлит, 2010.

27. Джунусов И. А., Фрадков А. Л. Синхронизация в сетях линейных агентов с обратными связями //Автоматика и телемеханика. — 2011. — в печати.

28. Дмитриев Н. А., Дынкин Е. Б. О характеристических числах стохастической матрицы //Доклады Академии Наук СССР.— 1945.— Т. 49.— С. 159-162.

29. Дмитриев Н. А., Дынкин Е. Б. Характеристические корни стохастических матриц // Известия Академии наук СССР. — 1946.— Т. 10.— С. 167-184.

30. Золотухин Ю. П., Котов К. Ю., Нестеров А. А. Децентрализованное управление подвижными объектами в составе маневрирующей группы II Автометрия. 2007. - Т. 43, № 3. - С. 31-39.

31. Зыков А. А. Теория конечных графов, — Новосибирск: Наука, 1969.

32. Икрамов X. Д. Несимметричная проблема собственных значений. Численные методы. — Москва: Физматлит, 1991.

33. Икрамов X. ДНазари А. М. Об одном замечательном следствии формулы Малышева II Доклады РАН. 2002. - Т. 385, № 5. - С. 599-600.

34. Икрамов X. Д., Назари А. М. О спектральном расстоянии от нормальной матрицы до множества матриц с кратным собственным значением нуль // Записки научных семинаров ПОМИ. — 2005. — Т. 323. — С. 50-56.

35. Келъманс А. К. О числе деревьев графа. I II Автоматика и Телемеханика. 1965. - Т. 26, № 12. - С. 2194-2204.

36. Келъманс А. К. О числе деревьев графа. II // Автоматика и Телемеханика. 1966. - Т. 27, № 2. - С. 56-65.

37. Келъманс А. К. О свойствах характеристического многочлена графа //^Кибернетику — на службу коммунизму / Под ред. акад. А. И. Берга. М.-Л.: Энергия, 1967. - С. 27-41.

38. Ким Д. П. Теория автоматического управления. Многомерные, нелинейные, оптимальные и адаптивные системы. — Москва: Физматлит. 2004.

39. Колмогоров А. Н. Об аналитических методах в теории вероятностей // Успехи математических наук. — 1938. — № 5. — С. 5-41.

40. Колотилина Л. Ю. Неравенства для крайних собственных значений блочных эрмитовых матриц с приложениями к спектральной теории графов // Записки научных семинаров ПОМИ. — 2010. — Т. 382. — С. 82103.

41. Колотилина Л. Ю. Оценки для крайних собственных значений лапласиана и положительного лапласиана графа // Записки научных семинаров ПОМИ. 2010. - Т. 395. - С. 104-123.

42. Куржанский А. Б. Задача управления групповым движением. Общие соотношения // Доклады РАН. 2009. - Т. 426, № 1. - С. 20-25.

43. Ланкастер П. Теория матриц. — Москва: Наука, 1978.

44. Мак-Миллан В. Д. Динамика твердого тела. — Москва: ИЛ, 1951.

45. Маркус М., Минк X. Обзор по теории матриц и матричных неравенств. — Москва: Наука, 1972.

46. Парлетт Б. Симметричная проблема собственных значений. Численные методы. — Москва: Мир, 1983.

47. Пароди М. Локализация характеристических чисел матриц и ее применения. — Москва: Иносранная литература, 1960.

48. Пашковский С. Вычислительные применения многочленов и рядов Че-бышева. — Москва: Наука, 1983.

49. Поляк Б. Т., Щербаков П. С. Робастная устойчивость и управление. — Москва: Наука, 2002.

50. Романовский В. И. Дискретные цепи Маркова. — Москва: Гостехиздат, 1949.

51. Сарымсаков Т. А. Об эргодическом принципе для неоднородных цепей Маркова-//-Доклады Академии-наук СС-СР. — 1953. — № 1. — С. 25-28.

52. Станкевич М. П., Станкевич, И. В., Зефиров П. С. Топологические индексы в органической химии // Успехи химии. — 1988.— Т. 57, № 3.— С. 337-366.

53. Tamm У. Теория графов, М.: Мир, 1988.

54. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. — Москва: Наука, 1970.

55. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. — 2 изд. — Москва-Ленинград: Физматгиз, 1963.

56. Фрадков А. Л. Адаптивное управление в сложных системах. Беспоисковые методы. — Москва: Наука, 1990.

57. Фунаси Р., Аракова М., Тсуда Ю., Кавагучи Д. Децентрализованное управление группой спутников с учетом информационного обмена // Труды МАИ (электронный журнал). ~ 2009. — № 9.

58. Харари Ф. Теория графов. — М.: Мир, 1973.

59. Хорн Р., Джонсон Ч. Матричный анализ. — Москва: Мир, 1989.

60. Цветкович Д. Дуб М., Захс X. Спектры графов: теория и применение. — Киев: Наукова думка, 1984.

61. Чеботарев П. Ю., Агаев Р. П. Псевдообратная матрица для матрицы Кирхгофа ориентированного графа // Труды 14 Международного Симпозиума "Управление большими системами", CONTROL'2000. — Тбилиси: 2000. С. 23-25.

62. Чеботарев П. Ю., Агаев Р. П. Согласование характеристик в много-агентных системах и спектры лапласовских матриц орграфов // Автоматика и телемехатька. — 2009. — № 3. — С. 136-151.

63. Чеботарев П. Ю., Агаев Р. П. Управление многоагентными системами и спектры лапласовских матриц орграфов // Труды четвертой межд. конф. по проблемам управления. — Москва: 2009. — С. 1571-1584.

64. Чеботарев П. Ю., Агаев Р. П. Уточнение к статье "О нахождении собственного проектора и компонент матрицы" // Автоматика и Телемеханика. 2011. -т 3. - С. 173.

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

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

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

68. Abdesselam A. Grassmann-Berezin calculus and theorems of the matrix-tree type // Advances in Applied Mathematics. — 2004. — Vol. 33. — Pp. 51-70.

69. Agaev R. On the spectra of the Laplacian matrices of a certain class //2 International conference on matrix methods and operator equations. — Moscow: Institute of Numerical Mathematics RAS, 2007. — P. 1.

70. Agaev R., Chebotarev P. On the Faddeev matrix and the generalized inverses // International Conference on Matrix Analysis and Applications. — Fort Lauderdale: Nova Southeastern University, 2003.— P. 1.

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

72. Agaev R., Chebotarev P. Which digraphs with ring structure are essentially cyclic? // Advances in Applied Mathematics. — 2010. — Vol. 45, no. 2. — Pp. 232-251.

73. Agaev R. P. On the generalized inverses of the Kirchoff matrix // International Linear Algebra Conference. — Haifa: Institute of Advanced Studies in Mathematics, Technion, 2001.- P. 13.

74. Agaev R. P., Chebotarev P. Which digraphs with ring structure are essentially - cyclic?- -// l-6th- Conference of -the- International Li-near Algebra Society. —

75. Pisa, Italy: University of Pisa, 2010. P. 29.

76. Agaev R. P., Chebotarev P. Y. The matrix of maximum out forests of a digraph and its applications // Automation and Remote Control. — 2000. — Vol. 61, no. 9.- Pp. 1424-1450.

77. Agaev R. P., Chebotarev P. Y. Spanning forests of a digraph and their applications // Automation and Remote Control.— 2001.— Vol. 62, no. 3.— Pp. 443-466.

78. Anderson Jr. W. N., Morley T. D. Eigenvalues of the Laplacian of a graph // Linear and Multilinear Algebra. — 1985. — Vol. 18. — Pp. 141-145.

79. Bapat R. В., Constantine G. An enumerating function for spanning forests with color restrictions // Linear Algebra and its Applications. — 1992. — Vol. 173.- Pp. 231-237.

80. Bapat R. В., Pati S. Algebraic connectivity and the characteristic set of a graph // Linear and Multilinear Algebra. — 1998. — Vol. 45. — Pp. 247-273.

81. Ben-Israel A., Charnes A. Contributions to the theory of generalized inverses // Journal of the Society for Industrial and Applied Mathematics. — 1963. — Vol. 11, no. 3.- Pp. 667-699.

82. Ben-Israel A., Greville T. N. E. Generalized Inverses: Theory and Applications. New York: Wiley, 1974.

83. Berman A., Plemmons R. Nonnegative Matrices in the Mathematical Sciences. — New York: Academic Press, 1979.

84. Berman A., Shaked-Monderer N. Non-negative matrices and digraphs //Encyclopedia of Complexity and Systems Science. — New York: Springer,2009. Pp. 6239-6252.

85. Berman K. A. A graph theoretical approach to handicap ranking of tournaments and paired comparisons // SIAM Journal on Algebraic and Discrete Methods. 1980. - Vol. 1. - Pp. 359-361.

86. Bertsekas D., Tsitsiklis J. Parallel and distributed computation: numerical methods. Prentice hall Englewood Cliffs, NJ, 1989. - Vol. 23.

87. Bertsekas D., Tsitsiklis J. Comments on "coordination of groups of mobile autonomous agents using nearest neighbor rules" // IEEE Transactions Automatic Colitrol. -"2007."- Vol."52, no:"5. Pp. 968^969. "

88. Blanchard P., Dawin J., Volchenkov D. Markov chains or the game of structure and chance, from complex networks, to language evolution, to musical compositions // The European Physical Journal — Special Topics. — June2010. Vol. 184, no. 1. - Pp. 1-82.

89. Blanchard P., Kriiger T., Volchenkov D. Random Graphs and Random Walks. — Berlin, Heidelberg: Springer, 2010.

90. Boesch F. T., Prodinger H. Spanning tree formulas and Chebyshev polynomials // Graphs and Combinatorics. — 1986. — Vol. 2, no. 1. — Pp. 191-200.

91. Bollobas B. Modern Graph Theory. — New York: Springer, 1998.

92. Borrelli F., Keviczky T. Distributed LQR design for identical dynamically decoupled systems // IEEE Transactions on Automatic Control. — 2008. — Vol. 53, no. 8. Pp. 1901-1912.

93. Browne E. Limits to the characteristic roots of a matrix // The American Mathematical Monthly. 1939. - Vol. 46, no. 5. - Pp. 252-265.

94. Brualdi R. A. Spectra of digraphs // Linear Algebra and its Applications. — 2010. Vol. 432. - Pp. 2181-2213.

95. Campbell S. L., Meyer, Jr. C. D. Generalized Inverses of Linear Transformations. — London: Pitman, 1979.

96. Campbell S. L., Meyer, Jr. C. D. Rose N. J. Applications of the Drazin inverse to linear systems of differential equations with singular constant coefficients // SIAM Journal on Applied Mathematics. — 1976.— Vol. 31.— Pp. 411-425.

97. Cao Y., Li Y., Ren W., Chen Y. Distributed coordination of networked fractional-order systems // IEEE Transactions On Systems, Man, And Cybernetics-Part B: Cybernetics. 2010. - Vol. 40, no. 2. - Pp. 362-370.

98. Cao Y., Ren W. LQR-based optimal linear consensus algorithms // 2009 American Control Conference. — Hyatt Regency Riverfront, St. Louis, MO, USA: 2009. Pp. 5204-5209.

99. Cao Y., Ren W. Multi-vehicle coordination for double-integrator dynamics under fixed undirected/directed interaction in a sampled-data setting // International Journal of Robust and Nonlinear Control. — 2009. — Published Online: 13 Aug 2009.

100. Cao Y., Ren W. Containment control with multiple stationary or dynamic leaders under a directed interaction graph // Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference. — Shanghai, P.R. China: 2010. Pp. 3014-3019.

101. Cao Y., Ren W. Optimal linear-consensus algorithms: An LQR perspective J/ IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. 2010. - Vol. 40, no. 3. - Pp. 819-830.

102. Cao Y., Ren W. Sampled-data discrete-time coordination algorithms for double-integrator dynamics under dynamic directed interaction // International Journal of Control. 2010.- Vol. 83, no. 3,- Pp. 506-515,- First Published on 04 November 2009.

103. Cao Y., Stuart D., Ren W. Co-ordinated collective motion patterns in a discrete-time setting with experiments // IET Control Theory and Applications. 2010. - Vol. 4, no. 11. - Pp. 2579-2591.

104. Caughman J., Veerman J. Kernels of directed graph Laplacians // The Electronic Journal of Combinatorics. — 2006. — Vol. 13, no. 1. — P. R39.

105. Chaiken S. A combinatorial proof of the all minors matrix tree theorem // SIAM Journal on Algebraic and Discrete Methods. — 1982,— Vol. 3, no. 3. Pp. 319-329.

106. Chatterjee S., Seneta E. Towards consensus: Some convergence theorems on repeated averaging // Journal of Applied Probability. — 1977. — Vol. 14. — Pp. 89-97.

107. Chebotarev P. Comments on "Consensus and cooperation in networked multiagent systems" // Proceedings of the IEEE. — 2010. Vol. 98, no. 7. -Pp. 1353-1354;

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

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

110. Chebotarev P., Agaev R. On of the spectrum of the digraph Laplacian //International Conference on Matrix Analysis and Applications. — Fort Lauderdale: Nova Southeastern University, 2003. — Pp. 4-5.

111. Chebotarev P., Agaev R. When is the Laplacian spectrum of a weighted digraph real? // International GAMM-SIAM Conference on Applied Linear Algebra. — Düsseldorf: University of Düsseldorf, 2006. — P. 29.

112. Chebotarev P., Agaev R., Shamis E. The out forests of a (di)graph and the investigation of its structure // International Conference on Ordinal and Symbolic Data Analysis. — Bruxelles: Universite Libre de Bruxelles, 2000. — P. 8.

113. Chebotarev P., Shamis E., Agaev R. A new metric for graph vertices and its properties // Abstracts of the 7th Conference of the International Federation of Classification Societies. — Namur: University of Namur, 2000. — P. 46.

114. 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.

115. Chung F. Laplacians and the Cheeger inequality for directed graphs // Annals of Combinatorics. 2005. - Vol. 9. - Pp. 1-19.

116. Chung F. R. K. Spectral Graph Theory. — Providence, RI: American Mathematical Society, 1994. — Vol. 17 of Colloquium Publications.

117. Coates C. Flow-graph solutions of linear algebraic equations // IRE Transactions on Circuit Theory. 1959. - Vol. 6. - Pp. 170-187.

118. Cook W. D., Kress M. Ordinal Information and Preference Structures: Decision Models and Applications. — Englewood Cliffs, NJ: Prentice-Hall, 1992.

119. Cucker F. Smale S. On the mathematics of emergence // Japanese Journal of Mathematics. 2007. - Vol. 2, no. 1. - Pp. 197-227.

120. David H. A. The Method of Paired Comparisons. — Second edition. — London: Griffin, 1988.

121. David H. A., Andrews D. M. Nonparametric methods of ranking from paired comparisons // Probability Models and Statistical Analyses for Ranking Data /Ed. by M. A. Fligner, J. S. Verducci. New York: Springer, 1993. - Pp. 2036.

122. DeGroot M. H. Reaching a consensus // Journal of American Statistical Association. 1974. - Vol. 69, no. 345. - Pp. 118-121.

123. Doyle P. G., Snell J. L. Random Walks and Electric Networks. — Washington D. C.: Mathematical Association of America, 1984. —

124. Available at URL http://arxiv.org/abs/math/0001057 (version 2000).

125. Eckart C., Young G. The approximation of one matrix by another of lower rank // Psychometrika. — 1936. — Vol. 1, no. 3. — Pp. 211-218.

126. Erdds P. L. A new bijection on rooted forests // Discrete Mathematics. — 1993. Vol. 111. - Pp. 179-188.

127. Fax J.; Murray R. Information flow and cooperative control of vehicle formations // IEEE Transactions Automatic Control — 2003. — Vol. 49, no. 9. — Pp. 1465-1476.

128. Fax I. A, Optimal and cooperative control of vehicle formations: Ph.D. thesis / California Institute of Technology. — 2002.

129. Fax J. A., Murray R. M. Graph Lapla.cians and stabilization of vehicle formations: CDS Technical Report 01-007. — Pasadena: California Inst, of Technology, July 2001.

130. Fax J. A., Murray R. M. Graph Laplacians and stabilization of vehicle formations //Proceedings of the 15th IFAC Congress. — Barcelona, Spain: July 2002.

131. Fiedler M. Bounds for eigenvalues of doubly stochastic matrices // Linear Algebra and its Applications. — 1972. — Vol. 5. — Pp. 299-310.

132. Fiedler M. Algebraic connectivity of graphs // Czechoslovak Mathematical Journal. 1973. - Vol. 23, no. 98. - Pp. 298-305.

133. Fiedler M. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory // Czechoslovak Mathematical Journal. — 1975.- Vol. 25, no. 100.- Pp. 619-633.

134. Fiedler M., Sedlácek J. O VK-basích orientovanych grafü // Casopis Pest. Mat. 1958. - Vol. 83. - Pp. 214-225.

135. Fouss F., Pirotte A., Renders J., Saerens M. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation // IEEE Transactions on Knowledge and Data Engineering. — 2007. Pp. 355-369.

136. Golub G., Hoffman A., Stewart G. A generalization of the eckart-young-mirsky matrix approximation theorem I I Linear Algebra and Its Applications. 1987. - Vol. 88. - Pp. 317-327.

137. Grone R. Merris R. The Laplacian spectrum of a graph II // SIAM Journal on Discrete Mathematics. 1994. - Vol. 7, no. 2. - Pp. 221-229.

138. Grone R., Merris R., Sunder V. S. The Laplacian spectrum of a graph // SIAM Journal on Matrix Analysis and Applications. — 1990. — Vol. 11, no. 2. Pp. 218-238.

139. Hajnal J. The ergodic properties of non-homogeneous finite Markov chains // Proceedings of the Cambridge Philosophical Society. — 1956. — Vol. 52. — Pp. 67-77.

140. Hajnal J. Weak ergodicity in non-homogeneous Markov chains //Proceedings of the Cambridge Philosophical Society. — 1958. — Vol. 54. — Pp. 233-246.

141. Hall K. M. An r-dimensional quadratic placement algorithm // Management Science. 1970. - Vol. 17, no. 3. - Pp. 219-229.

142. Harary F., Norman R. Z., Cartwright D. Structural Models: An Introduction to the Theory of Directed Graphs. — New York: Wiley, 1965.

143. Harte R. E. Spectral projections // Irish Mathematical Society Newsletter. — 1984,-Vol. 11.- Pp. 10-15.

144. Hartwig R. E. More on the Souriau-Frame algorithm and the Drazin inverse // SI AM Journal on Applied Mathematics. 1976. - Vol. 31. - Pp. 42-46.

145. Hartwig R. E., Levine J. Applications of the Drazin inverse to the Hill cryptographic system, Part III // Cryptologia. — 1981. — Vol. 5. — Pp. 67-77.

146. Householder A. S. The Theory of Matrices in Numerical Analysis. — New York: Blaisdell, 1964.

147. Jadbabaie A. Lin J. Morse A. S. Coordination of groups of mobile autonomous agents using nearest neighbor rules // IEEE Trans. Automatic Control. 2003. - Vol. 48, no. 6. - Pp. 988-1001.

148. Johns J.; Mahadevan S. Constructing basis functions from directed graphs for value function approximation '/'/' Procee'dirigs of the 24th InternationalConference on Machine Learning (ICML). 2007. - Pp. 385-392.

149. Kelmans A. K., Chelnokov V. M. A certain polynomial of a graph and graphs with an extremal number of trees // Journal of Combinatorial Theory, Series B. 1974. - Vol. 16. - Pp. 197-214.

150. Keviczky T., Borrelli F. Balas G. J. Distributed predictive control: Synthesis, stability and feasibility // Cooperative Control of Distributed MultiAgent Systems / Ed. by J. S. Shamma. — John Wiley & Sons, Ltd., 2007. — Pp. 79-108.

151. Klein D. J. Centrality measure in graphs //Journal of Mathematical Chemistry. 2010. - Vol. 47, no. 4. - Pp. 1209-1223.164:. Koliha J. J. Block diagonalization // Mathematica Bohemica.— 2001.— Vol. 126. Pp. 237-246.

152. Koliha J. J., Straskraba I. Power bounded and exponentially bounded matrices //Applications of Mathematics. — 1999. — Vol. 44, no. 4. — Pp. 289-308.

153. Lafferriere G., Caughman J., Williams A. Graph theoretic methods in the stability of vehicle formations // Proceedings of the 2004 American Control Conference. Vol. 4. - 2004. - Pp. 3729- 3734.

154. Lafferriere G., Williams A. Caughman J. S., Veerman J. J. P. Decentralized control of vehicle formations // Systems and Control Letters. — 2005. — Vol. 54, no. 9. Pp. 899-910.

155. Laslier J. F. Tournament Solutions and Majority Voting. — Berlin: Springer, 1997.

156. Lin Z., Francis B., Maggiore M. Necessary and sufficient graphical conditions for formation control of unicycles // IEEE Trans. Automatic Control. — 2005. Vol. 50, no. 1. - Pp. 121-127.

157. Liu C. J., Chow Y. Enumeration of forests in a graph // Proceeding of the American Mathematical Society. — 1981. — Vol. 83, no. 3. — Pp. 659-663.

158. Luna B., Ugalde E. Dominant vertices in regulatory networks dynamics // Physica D: Nonlinear Phenomena. 2008. - Vol. 237. - Pp. 2685-2695.

159. Mahadevan S. Learning representation and control in Markov decision processes: New frontiers // Foundations and Trends in Machine Learning. — 2008. Vol. 1~ no. 4. - Pp. 403-565.

160. Malyshev A. N. A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues // Numerische Mathematik. — 1999. — Vol. 83, no. 3,- Pp. 443-454.

161. Markovski J. Real and Stochastic Time in Process Algebras for Performance Evaluation: Ph.D. thesis / Eindhoven University of Technology. — 2008.

162. Markovski J., Trcka N. Lumping Markov chains with silent steps // Third International Conference on the Quantitative Evaluation of Systems — (QEST'06). Riverside, CA, USA: IEEE Computer Society, 2006. - Pp. 221232.

163. Markovski J., Trcka N. Aggregation methods for Markov reward chains with fast and silent transitions // 14th GI/ITG Conference Measurement, Modelling and Evalutation of Computer and Communication Systems. — Dortmund: 2008.- Pp. 1-15.

164. Marsaglia G., Styan G. P. H. Equalities and inequalities for ranks of matrices // Linear and Multilinear Algebra. 1974. - Vol. 2. - Pp. 269-292.

165. Masuda N., Kawamura Y., Kori H. Impact of hierarchical modular structure on ranking of individual nodes in directed networks // New Journal of Physics. 2009. - Vol. 11. - P. 113002 (21 pp.).

166. Masuda N., Kawamura Y., Kori H. Collective fluctuations in networks of noisy components // New Journal of Physics. — 2010. — Vol. 12. — Pp. 115.

167. Maxwell J. C. Electricity and Magnetism. — 3 edition. — London/New York: Oxford Univ. Press, 1892.- vol. 1, part. II, p. 409.

168. Meng Z., Cao Y., Ren W. Stability and convergence analysis of multi-agent consensus with information reuse // International Journal of Control. — 2010. Vol. 83, no. 5. - Pp. 1081-1092.

169. Meng Z., Ren W., Cao Y., You Z. Leaderless and leader-following consensus with communication and input delays under a directed network topology // IEEE Transactions on Systems, Man, and Cybernetics, Part, B: Cybernetics. 2010. - no. 99. - Pp. 1-14.

170. Merris R. Laplacian matrices of graphs: A survey // Linear Algebra and its Applications. 1994. - Vol. 197-198. - Pp. 143-176.

171. Merris R. A survey of graph Laplacians // Linear and Multilinear Algebra. — 1995.-Vol. 39.- Pp. 19-31.

172. Merris R. Doubly stochastic graph matrices // Publikacije Elektrotehnickog Fakulteta Univerzitet. U Beogradu, Serija: Matematika. — 1997. — Vol. 8. — Pp. 64-71.

173. Merris R. Doubly stochastic graph matrices II // Linear and Multilinear-Algebra. 1998. - Vol. 45. - Pp. 275-285.

174. Mesbahi M., Egerstedt M. Graph Theoretic Methods in Multiagent Networks. — Princeton, NJ: Princeton University Press, 2010. — 413 pp.

175. Meyer, Jr. C. D. Limits and the index of a square matrix // SIAM Journal on Applied Mathematics. 1974. - Vol. 26. - Pp. 469-478.

176. Meyer, Jr. C. D. The role of the group generalized inverse in the theory of finite Markov chains // SIAM Review. 1975. - Vol. 17, no. 3. - Pp. 443464.

177. Meyer, Jr. C. D., Stadelmaier M. W. Singular M-matrices and inverse posi-tivity // Linear Algebra and its Applications. — 1978. — Vol. 22. — Pp. 139156.

178. Mohar B. The Laplacian spectrum of graphs // Graph Theory, Combinatorics and Applications / Ed. by Y. Alavi, G. Chartrand, O. Oellermann, A. Schwenk. New York: Wiley, 1991. - Pp. 871-898.

179. Mohar B. Laplace eigenvalues of graphs — a survey // Discrete Mathematics. 1992. - Vol. 109. - Pp. 171-183.

180. Moon J. W., Ptdlman N. J. On generalized tournament matrices // SIAM Review. 1970. - Vol. 12. - Pp. 384-399.

181. Moreau L. Stability of multiagent systems with time-dependent communication links if IEEE Trans. Automatic Control — 2005.— Vol. 50, no. 2,— Pp. 169-182.

182. Myrvold W. Counting /c-component forests of a graph // Networks. — 1992. — Vol. 22. Pp. 647-652.

183. Novikov D. A. Models of strategic behavior // Automation and Remote Control. 2012. - Vol. 73, no. 1. - Pp. 1-19.

184. Olfati-Saber R. Ultrafast consensus in small-world networks // Proc. American Control Conference.- 2005.- Pp. 2371-2378.

185. Olfati-Saber R., Fax J. A., Murray R. M. Consensus and cooperation in networked multi-agent systems // Proceedings of the IEEE. — 2007.— Vol. 95, no. 1. Pp. 215-233.

186. Olfati-Saber R., Murray R. M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Transactions on Automatic Control. 2004. - Vol. 49, no. 9. - Pp. 1520-1533.

187. Pick G. Uber die Wurzeln der charakteristischen Gleichungen von Schwingungsproblemen //Zeitschrift fur angewandte Mathematik und Mechanik. — 1922. — Vol. 2. Pp. 353-357.

188. Ren W. Consensus based formation control strategies for multi-vehicle systems //2006 American Control Conference. 2006. - Pp. 4237-4242.

189. Ren W. Collective motion from consensus with Cartesian coordinate coupling // IEEE Transactions on Automatic Control. — 2009. — Vol. 54, no. 6. — Pp. 1330-1335.

190. Ren W. Consensus tracking under directed interaction topologies: Algorithms and experiments // IEEE Transactions on Control Systems Technology. — 2010. Vol. 18, no. 1. - Pp. 230-237.

191. Ren W., Beard R., Atkins E. A survey of consensus problems in multi-agent coordination // 2005 American Control Conference.— 2005.— Pp. 18591864.

192. Ren W., Beard R. W. Consensus seeking in multi-agent systems under dynamically changing interaction topologies // IEEE Transactions on Automatic Control. 2005. - Vol. 50, no. 5. - Pp. 655-661.

193. Ren W., Beard R. W. Distributed Consensus in Multi-vehicle Cooperative Control: Theory and Applications. — London: Springer, 2008.

194. Ren W., Beard R. W., Atkins E. M. Information consensus in multivehicle cooperative control // IEEE Control Systems Magazine. — 2007. — Vol. 27, no. 2. Pp. 71-82.

195. Ren W., Cao Y. Convergence of sampled-data consensus algorithms for double-integrator dynamics // Proceedings of the 47th IEEE Conference on

196. Decision and Control Cancun, Mexico, Dec. 9-11, 2008.- No. ThTA06.4.-2008. Pp. 3965-3970.

197. Ren W., Cao Y. Distributed Coordination of Multi-agent Networks: Emergent Problems, Models, and Issues. — Springer, 2011.

198. Ren W., Chao H., Bourgeons W., Sorensen N. Chen Y. Experimental validation of consensus algorithms for multivehicle cooperative control I I IEEE Transactions On Control Systems Technology. — 2008. — Vol. 16, no. 4. — Pp. 745-752.

199. Riethmùller C. A Maintenance Model for Systems with Phase-type Distributed Times to Failure: Ph.D. thesis / Fakultàt fur Mathematik der Otto-von-Guericke-Universitàt Magdeburg. — 2010. — Pp. 1-112.

200. Rothblum U. G. Computation of the eigenprojection of a nonnegative matrix at its spectral radius I I Mathematical Programming Study. — 1976. — Vol. 6.- Pp. 188-201.

201. Rothblum U. G. A representation of the Drazin inverse and characterizations of the index // SIAM Journal on Applied Mathematics. — 1976.— Vol. 31, no. 4. Pp. 646-648.

202. Schwartz T. The Logic of Collective Choice. — New York: Columbia Univ. Press, 1986.

203. Shamma J. Cooperative control of distributed multi-agent systems. — Wiley Online Library, 2007.

204. Simeon B., Fiihrer C., Rentrop P. The Drazin inverse in multibody system dynamics I I Numerische MathemMik. — 1993. — Vol. 64, no. 4. — Pp. 521539.

205. Takacs L. Enumeration of rooted trees and forests // Mathematical Scientist. 1993. - Vol. 18. - Pp. 1-10.

206. Tizghadam A., Leon-Garcia A. On random walks in direction-aware network problems // ACM SIGMETRICS Performance Evaluation Review.— September 2010. Vol. 38, no. 2. - Pp. 9-11.

207. Tsitsiklis J., Bertsekas D., Athans M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms // IEEE Transactions Automatic Control. 1986. - Vol. 9. - Pp. 803-812.

208. Udrea G. Catalan's identity and Chebyshev polynomials of the second kind I I Portugaliae Mathematics 1995. - Vol. 52. - Pp. 391-397.

209. Veerman J. J. P., Lafferriere G., Caughman J., Williams A. Flocks and formations I I Journal of Statistical Physics. — 2005.— Vol. 121, no. 5-6.— Pp. 901-936.

210. Veerman J. J. P., Stosic B. D., Tangerman F. M. Automated traffic and the finite size resonance // Journal of Statistical Physics. — 2009. — Vol. 137, no. 1.- Pp. 189-203.

211. Vicsek T., Czirok A., Jacob E. B. Cohen I., Schochet O. Novel type of phase transitions in a system of self-driven particles // Physics Review Letters. — 1995. Vol. 75. - Pp. 1226-1229.

212. Volchenkov D. Random walks and flights over connected graphs and complex networks (review) // Communications in Nonlinear Science and Numerical Simulation. 2011. - Vol. 16, no. 1. - Pp. 21-55.

213. Wei Y. A characterization and representation of the Drazin inverse // SI AM Journal on Matrix Analysis and Applications. — 1996. — Vol. 17, no. 4. — Pp. 744-747.

214. Wilkinson J. H- Note en-the practical-significance of the-Drazin inverse //Recent Applications of Generalized Inverses / Ed. by S. Campbell. — London: Pitman, 1982. Pp. 82-99.

215. Williams A., Lafferriere G., Veerman J. J. P. Stable motions of vehicle formations //44th IEEE Conference on Decision and Control, and the European Control Conference. — Seville, Spain: December 2005. — Pp. 72-77.

216. Wolfowitz J. Products of indecomposable, aperiodic, stochastic matrices // Proceedings of the American Mathematical Society. — 1963. — Vol. 15. — Pp. 733-736.

217. Wu C. W. Algebraic connectivity of directed graphs // Linear and Multilinear Algebra. 2005. - Vol. 53, no. 3. - Pp. 203-223.

218. Wu C. W. Synchronization in Complex Networks of Nonlinear Dynamical Systems. World Scientific, 2007.

219. Wu C. W. Evolution and dynamics of complex networks of coupled systems // Circuits and Systems Magazine, IEEE. — 2010. — Vol. 10, no. 3. — Pp. 5563.

220. Young G. F., Scardovi L., Leonard N. E. Robustness of noisy consensus dynamics with directed communication //Proceedings of the American Control Conference. — Baltimore, MD: 2010.

221. Zarei M., Samani K. A., Omidi G. R. Complex eigenvectors of network matrices give better insight into the community structure // Journal of Statistical Mechanics: Theory and Experiment (An IOP and SISSA journal). — 2009.- Pp. 1-20.- P10018.

222. Zhang L. A characterization of the Drazin inverse // Linear Algebra and its Applications. 2001. - Vol. 335. - Pp. 183-188.

223. Zhang Y., Yong X., Golin M. J. Chebyshev polynomials and spanning tree formulas for circulant and related graphs // Discrete Mathematics. — 2005. — Vol. 298. Pp. 334-364.