ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 9, с. 1623-1629
УДК 519.634
Посвящается светлой памяти А.П. Фаворского
НЕКОТОРЫЕ АСПЕКТЫ ДИНАМИЧЕСКОЙ ТЕОРИИ ГРАФОВ1)
© 2015 г. А. А. Кочкаров*, **, Р. А. Кочкаров**, Г. Г. Малинецкий***
(* 127083 Москва, ул. 8-го Марта, 10, стр. 1, ОАО "РТИ";
** 125993 Москва, Ленинградский пр-т, 49, Финансовый ун-т при Правительстве РФ;
*** 125047Москва, Миусская пл., 4, ИПМРАН) e-mail: Akochkar@gmail.com; Rasul_kochkarov@mail.ru; Gmalin@keldysh.ru Поступила в редакцию 00.02.2015 г.
В работе введено понятие динамического графа. Рассмотрены некоторые свойства динамических графов. Представлены инженерные приложения и основные направления развития динамической теории графов. Получены условия сохранения диаметра в траектории динамического графа. Библ. 19. Фиг. 1.
Ключевые слова: динамические графы, динамические сети, сетевые системы, дискретная оптимизация.
DOI: 10.7868/S0044466915090094
1. ВВЕДЕНИЕ
В настоящее время быстро меняются методы вычислительной математики, применимые для анализа классических моделей математических моделей — уравнений в частных производных. Это диктуется необходимостью повысить точность расчетов в технологических задачах и появлением новых поколений вычислительной техники.
Однако не менее важным представляется и другой процесс — появление новых типов математических моделей и связанных с ними вычислительных проблем. Это, в свою очередь, обусловлено расширением области приложения математических методов в различных научных дисциплинах и изменением точки зрения на ранее изучавшиеся объекты.
Оба взаимосвязанных процесса наглядно показывает научное творчество крупного специалиста в области вычислительной математики и математического моделирования профессора А.П. Фаворского, памяти которого посвящена данная статья.
В центре внимания научной школы А.Н. Тихонова и А.А. Самарского, к которой он принадлежал, были динамические системы
= f1(x1, ..., xN)>
dt
(1)
dXN = fN (xi,..., Xn ), 0 < t < 0, dt
либо отображения
n+1 _ < n n ч
x1 — <§'l(x1 , ..., xN^
; (2)
n+1 _ у n n ч
xN — gN ^b..^ xN ^ n — 1 2 ...,
Работа выполнена при финансовой поддержке РФФИ (код проекта № 13-01-00617а).
1623
которые наилучшим образом приближают (аппроксимируют) уравнения гидродинамики, магнитной гидродинамики. Этими вопросами успешно и плодотворно занимался А.П. Фаворский и его ученики (см. [1]). В зависимости от постановки задачи, доступных вычислительных ресурсов, и требований к аппроксимации (понимания слов "наилучшим образом") мы получаем разные объекты вида (1) или (2) для одних и тех же уравнений в частных производных.
Однако точно такие же модели вида (1) и (2) появляются в совершенно других областях. В них изучаемому объекту соответствует граф, имеющий N вершин, состояние каждой из которых описывается некоторой динамической системой, аргументами в которой является ее собственное
состояние xp(t) (или xnp в дискретном случае) и состояние ее соседей. Вначале такие объекты, связанные с ориентированными графами, использовали в когнитивном моделировании (см. [2]). В них вершины графа соответствуют факторам, а ребра причинно-следственным связям. Такие же математические объекты возникают в потоковых моделях в биологии (см. [2]). Такие модели позволяют оценить реакцию всей системы (целого) на локальные воздействия. Подобные объекты рассматривались А.П. Фаворским и его коллегами при моделировании реакции кровеносной системы на различные лекарственные воздействия (влияние на свойство ребер соответствующего графа) (см. [1]).
Здесь возникает новый элемент — структура зависимости функций {f ■} или {g} от своих аргументов — и свои проблемы. Например, обратная задача теории нейронных сетей состоит в том, чтобы выбрать такую зависимость от аргументов (структуру связей) и такие функции {f} или {g}, чтобы заданный набор особых точек в фазовом пространстве {у¡} соответствовал аттракторам динамических систем (1), (2). Выход на один из этих аттракторов соответствует распознаванию образа у p. При этом возникают новые критерии, позволяющие отличить "хорошие" решения этой задачи от "плохих". Как правило, одним из них становится простота (алгоритмичность) построения функций {f} или {g ¡}, позволяющая автоматизировать этот процесс.
Несмотря на очень широкий класс проблем и приложений, для которых используются динамические системы вида (1) или (2), размерность фазового пространства N в них обычно предполагалась неизменной. Мы имели дело со стационарным (не зависящим от времени) графом G, определяющим функциональную зависимость в этих динамических системах. Однако в последнее время появились задачи, в которых от времени начинает зависеть сама размерность фазового пространства.
Приведем несколько примеров таких задач. При численном моделировании нестационарных течений на адаптивных сетках в лагранжевых координатах возникает необходимость время от времени исключать ячейки (исходя из того, что их объем стал в ходе расчетов слишком мал либо углы стали слишком острыми) или добавлять новые. При этом сам граф функциональной зависимости становится зависимым от времени G(t) или Gl (l = 1,2,...). При этом так же, как в случае нейронных сетей, одним из критериев, в соответствии с которым ищется решение, является простота, позволяющая автоматизировать алгоритм исключения и добавления ячеек.
Больше внимания в настоящее время уделяется динамике саморазвивающихся систем, в частности социальных сетей. Представляет большой интерес не только динамика распространения информации по сети с заданным графом G, но и само изменение этого графа. Более того, во многих случаях сам граф обладает многими замечательными свойствами (так называемые безмасштабные сети, в которых распределение вершин по числу связей имеет степенной характер). Поэтому возникает обратная задача — построение модели, которая дает такую же динамику роста G(t), как и наблюдается в сети.
Третий класс задач, связанный с многоагентными системами упоминался еще в 1950-х годах в связи с перспективами космических исследований. Это стаи или команды мобильных роботов, которые решают общую задачу, и граф связей, между которыми меняется во времени.
2. ОПРЕДЕЛЕНИЕ ДИНАМИЧЕСКОГО ГРАФА
Понятие динамических сетей (Dynamic networks) (см. [2]) широко используется при изучении сложных структурно-изменяющихся сетей различной природы и происхождения. К динамическим сетям относят и социальные сети (см. [4]), и сети связи (см. [3], [6]) и коллективного взаимодействия (см. [7]), и структуры фондовых рынков (см. [8]), и структуры взаимных обязательств межбанковской системы (см. [9]). Несмотря на накопленный эмпирический материал по изучению динамических сетей, пока нет оснований говорить об окончательно сложившейся тео-
рии динамических сетей (Dynamic network analysis) или сетевой науки (Network science). Для формирования такой отрасли прикладной науки необходима теоретическая основа. Ее ядром может стать зарождающаяся динамическая теория графов, основным объектом которой является динамический граф — модель динамической сети.
Динамический граф Г, как модель динамической сети, представляет собой последовательность "классических" графов Gt, не имеющих параллельных ребер и петель, переход между которыми описывается различными теоретико-графовыми операциями ф^) = Gl+1 (удаление/добавление ребра, см. [10], удаление/добавление вершины, см. [10], замена вершины затравкой, см. [11], приоритетное присоединение вершин и ребер, см. [12] и т.д.). Индекс l соответствует своеобразному "топологическому времени", в последующие моменты которого меняется структура графа.
Операции удаления/добавления ребра, удаления/добавления вершины будем назвать простыми или базовыми. Любую другую операцию, которую можно описать чередованием простых операций, будем называть сложной. В общем случае динамический граф представляет собой последовательность конечных невзвешенных (не всегда связных) графов — G1, G2,Gl,..., GL,..., в которой переход к последующему графу Gl+1 осуществляется применением операции ф(Э1) = Gl+1. Операция, осуществляющая переход, может быть как простой, так и сложной. Для построения траектории динамического графа могут быть использованы несколько (конечное множество) чередующихся операций Ф = {ф'}. Также в операции может быть определен механизм выбора элементов графа (ребра, вершины, подграфы), над которыми совершается заданная операция. Последовательность графов Gt = (V,Et), l = 1,2,..., L,..., составляющих динамический граф, будем называть траекторией динамического графа Г.
Следующие ниже очевидные утверждения призваны продемонстрировать применение введенных понятий.
Утверждение 1. Траектория динамического графа Г является бесконечной, если ф(V) Ф Vt, l = 1,2,..., L,....
Утверждение 2. На множестве всех полных n-вершинных простых цепей {Pn}, n > 2, существует динамический граф Г с бесконечной траекторией P2,P3,..., Pt,..., PL,..., у которого операция ф(/>) = Pl+1, l = 2,3,..., L,..., определяется как добавление одной вершины, смежной с одной из висячих вершин графа Pl .
Утверждение 3. На множестве всех полных n-вершинных простых циклов {Cn > 3, существует динамический граф Г с бесконечной траекторией C3,C4,..., Cl,..., CL,..., у которого операция ф(С) = Cl+1, l = 3,4,..., L,..., определяется как удаление одного ребра и последующим добавлением одной вершины, смежной с обеими висячими вершинами графа Pl .
Утверждение 4. На множестве всех полных n-вершинных графов {Kn} существует динамический граф Г с бесконечной траекторией K1,K2,..., Kt,..., KL,..., у которого операция ф(К1 ) = Kt+1, l = 1,2,..., L,..., определяется как добавление одной вершины и инцидентного с ней (l + 1)-горебра.
Утверждение 5. Если операции перехода ф^) = Gl+1 динамического графа не использует простую операцию добавления вершины, то динамический граф конечен.
Одним из частных случаев динамического графа является фрактальный граф (см. [11]). Определение фрактального (предфрактального) графа базируется на сложной операции, называемой заменой вершины затравкой (ЗВ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.