Автоматика и телемеханика, № 8, 2015
Системный анализ и исследование
операций
© 2015 г. Л.Ю. ЖИЛЯКОВА, д-р физ.-мат. наук (zhilyakova.ludmila@gmail.com) (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
ГРАФОВЫЕ ДИНАМИЧЕСКИЕ МОДЕЛИ И ИХ СВОЙСТВА1
Дан обзор ряда неклассических потоковых моделей и пороговых моделей распространения активности в сетях. Приведено описание потоковых моделей с нестандартной достижимостью. Описаны целочисленные пороговые модели, к которым относится «игра выстреливания фишек» (chip-firing game) и «вероятностный абак»; описана модель самоорганизованной критичности и ее графовая интерпретация. Приведены основные свойства вещественнозначной пороговой модели «ресурсная сеть». Сделан сравнительный анализ этих видов моделей.
1. Введение
Большое количество задач из разных предметных областей решается с помощью алгоритмической теории графов. Классические сетевые задачи - это задачи распределения дорожного трафика, управления транспортными потоками, потоками данных, задачи распределения нагрузки в компьютерных сетях и ряд других, в которых сетевая модель имеет в качестве прообраза реальную сеть. Сходные инструменты применяются при решении задач, связанных с информационными сетями: с появлением сетей мобильных операторов, социальных сетей и блогов в Интернет выделился класс задач, связанных с моделированием распространения мнений в социальных сетях, установлением взаимных влияний абонентов сетей телефонных операторов, управлением связностью ad hoc сетей (ad hoc сети - децентрализованные беспроводные сети, не имеющие постоянной структуры, где узлы соединяются «на лету») и др. Модели достижения консенсуса в многоагентных системах также основываются на графах коммуникаций, характеризующих степень влияния агентов друг на друга при формировании мнений.
В задачах, моделирующих материальные или информационные потоки, ребра графа соответствуют дорогам или иным физическим каналам связи и основное внимание уделяется нахождению способов наилучшей передачи потока по этим каналам. В других задачах внимание концентрируется на состояниях, соответствующих вершинам графа, а ребра лишь задают переходы между ними (возможно, с некоторой вероятностью). Так, в вероятностных
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 14-01-00422а).
задачах вершинам графа соответствует множество состояний, а ребрам - допустимые переходы между ними. Часть таких задач адекватно описывается статическими моделями, однако в большинстве случаев строятся динамические модели.
Отметим, что в настоящей работе под «динамикой» понимается изменение состояний (потоков, ресурсов и др.) при постоянной топологии. За рамками обзора остаются все модели, в которых топология графа изменяется. К ним относятся модели роста (см., например, [1]), в которых в граф добавляются новые вершины; модели «случайной эволюции» [2], в которых при постоянном количестве вершин происходит «перемонтаж» ребер, за счет чего изменяются топологические характеристики графа; модели структурного разрушения, в которых при определенных условиях происходит удаление узлов вместе с их инцидентными ребрами [3, 4].
Исходя из применяемых методов, графовые динамические модели с постоянной топологией можно разбить на три класса:
1) классические потоковые модели и их модификации;
2) случайные блуждания и рассеяние на графах;
3) целочисленные пороговые модели.
Настоящий обзор посвящен отдельным, в основном малоизвестным моделям из этих классов, каждая из которых, на взгляд автора, представляет большой интерес. Из первого класса будут рассмотрены задача поиска сбалансированного потока в сети и потоковые модели на графах с нестандартной достижимостью. Для второго класса, которому посвящено большое количество литературы (см., например, [5] и библиографический список к ней), будут лишь перечислены некоторые задачи, моделируемые случайными блужданиями. Из моделей третьего класса будут описаны «игра выстреливания фишек» и некоторые ее приложения. Кроме этого, будут приведены основные результаты, полученные для графовой динамической пороговой модели «ресурсная сеть», предложенной О.П. Кузнецовым [6, 7] и исследованной автором в [8-14]. Эта модель не сводится ни к одному из перечисленных выше классов и обладает рядом новых свойств.
Структура статьи соответствует приведенной классификации. Второй раздел посвящен потоковым моделям, третий - случайным блужданиям, четвертый - целочисленным пороговым моделям, в пятом приводятся основные определения и свойства ресурсной сети. Ресурсная сеть сравнивается со всеми описанными классами моделей.
Отметим, что графовая терминология в статье соответствует терминологии оригинальных работ. Термины «дуги» и «ребра» используются в основном в одном и том же смысле, за исключением тех фрагментов, где это оговаривается отдельно.
2. Потоковые модели
2.1. Классические потоковые модели и их динамические модификации
К этому классу относятся различные варианты потоковых моделей, от статических задач о нахождении оптимального потока до многополюсных
и многопродуктовых динамических асинхронных моделей [16-19]. Основные направления развития этого класса задач в большой степени обусловлены их приложениями в городском планировании, транспорте, энергетике, коммуникациях и других областях, в которых важны выборы маршрутов, оптимальных по тому или иному критерию или некоторой их совокупности. Задачи комбинаторной оптимизации, решаемые с помощью динамических графовых моделей, - это задачи о составлении расписаний, о максимальных паросоче-таниях (например, трудоустройстве), о паросочетаниях с минимальным расстоянием и др. [18-21].
Алгоритмы, используемые для решения таких задач, хорошо изучены и описаны. К ним относятся поиск максимального потока (алгоритм Форда-Фалкерсона [17] и его модификации [22]), поиск допустимых и максимальных потоков с минимальной стоимостью, составление динамических потоков, удовлетворяющих тем или иным временным ограничениям и ряд других.
2.2. Поиск сбалансированного потока
Задача поиска сбалансированного потока рассматривается в [23]. Потоковая модель задана ориентированным графом G = (V, E), |V| = п. Пропускные способности дуг в модели не ограничены.
Каждой вершине i поставлено в соответствии два множества: Ii и O i. I -множество «входящих соседей» вершины i: Ii = {k : (k,i) € E}; Oi - множество «исходящих соседей» вершины i: Oi = {k : (i,k) € E}, i € V.
В графе имеется множество стоковых вершин T - это вершины без исходящих дуг: T = {i € V: Oi = 0}.
Нестоковым вершинам приписаны некоторые неотрицательные константы qi, называемые потенциалами. Вершины с qi > 0 являются источниками сети.
Потоком в такой сети называются действительные числа Xij, заданные на множестве (i,j) € E. Каждая вершина в дискретном времени распределяет пришедший и порожденный (при qi > 0) поток во все исходящие дуги в заданной пропорции.
Начальный поток задается потенциалами вершин-источников. Поток, пришедший в стоки, вычитается из суммарного потока. В каждой нестоковой вершине на каждом такте происходит перераспределение входящего в нее потока и ее потенциала в исходящие дуги: заданы доли потока, направляемого в каждую из исходящих дуг.
Поток называется сбалансированным, если для каждой вершины выполняется закон сохранения - сумма входящего в нее потока и собственного потенциала вершины равна величине исходящего потока:
qi + Xpi =^2 Xij, i € v \ т.
p&Ii j&Oi
Процесс изменения потока не всегда приходит к сбалансированному (равновесному) состоянию. Исследуются условия стабилизации потока, скорость сходимости процесса, ищется вектор сбалансированного потока.
Равновесное распределение ресурсов. Те же авторы в [24] описывают другую сетевую модель, функционирующую в дискретном времени, названную «системой». Модель задана взвешенным графом О = (V, Е), IV| = п. Вершинам графа приписаны неотрицательные величины названные ресурсами. На каждом такте ресурс вершины распределяется между инцидентными ребрами. Каждое ребро представлено парой дуг, ресурсы в дугах на каждом такте времени называются их весами. Веса дуг (г,]) и (], г) могут быть различны.
Величины ресурсов в вершинах постоянны. Состояние сети - это распределение ресурсов по дугам. Состояния меняются с течением времени. Вес дуги (г,]) на шаге к обозначается через ж-. Считается, что начальные веса ж0, известны и для них выполняется:
= дг, г € V, ] € V = {I € V:(г,1) € Е}.
,еУ;
Для каждой пары смежных вершин г,] задана функция с,(ж,, ж,). Вершина г на каждом следующем шаге выбирает новые веса ж^1 так, чтобы минимизировать максимальное значение функции с,, ] € V;.
То есть решается задача оптимизации
тах а, О^1,, ^ иа+п ;
Е
З&Уг
— 0_г;
ж*;1 = 0, (г,]) /Е.
При этом веса считаются известными.
,;
Для такой модели найдены достаточные условия существования предельных и равновесных состояний; для некоторых частных случаев (функций с;, специального вида) приведены формулы их вычисления.
2.3. Потоки на графах с нестандартной достижимостью
Понятие графа с нестандартной достижимостью было введено Я.М. Ерусалимским и Е.О. Басанговой в [25, 26].
В графах с нестандартной достижимостью вводятся те или иные ограничения на некоторое подмножество дуг, вследствие чего не все пути в графе становятся допустимыми или появляются пути, придающие потоку некоторые дополнительные характеристики. Вид ограничений определяет тип достижимости в графе. При такой постановке классические графы можно рассматривать как частный (тривиальный) случай графов с нестандартной достижимостью. Для большинства видов достижимости задача нахождения максимального потока оказывается КР-трудной [27].
Потоки в сетях с различными видами нестандартных достижимостей были исследованы в [27-38].
Ориентированный граф в этих работах задается тройкой С^, и, /), где X = 0 - множество вершин, и - множество дуг; функция /: и ^ X х X -отображение, называемое отображением инцидентности.
2.3.1. Смешанная достижимость на орграфах. Ориентированные графы со смешанной достижимостью и
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.