Архив публикаций

Тезисы

XXI-ая конференция

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

Круглый А.Л.

Научно-исследовательский институт системных исследований РАН, Россия, 117218, Москва, Нахимовский пр-т, 36, к. 1

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

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

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

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

Литература

1. Krugly, A. L., A sequential growth dynamics for a directed acyclic dyadic graph, arXiv: 1112.1064 [gr-qc].

• открыть в PDF формате (на русском языке) (PDF)