Software & Systems

Новый алгоритм порождения графа, описанный в данной работе, по многим своим свойствам может рассматриваться как модель дискретного физического пространства-времени и процессов на этом пространстве. Попытки моделирования пространства-времени в микромире различными дискретными структурами многократно предпринимались в двадцатом веке с целью распространения квантовых свойств на пространство и/или время, так как в квантовой механике и квантовой теории поле пространство-время остается классическим. Подробный обзор работ до шестидесятых годов прошлого века содержится в монографии Вяльцева [1]. Использовались и различные модели графов, например, в моделях спиновых сетей (spin net) или спиновой пены (spin foam). Модель локально конечного частично упорядоченного множества предложена в работах [2, 3]. Эта модель может быть представлена ориентированным ациклическим графом. Ацикличность графа является моделью принципа причинности и необратимости времени в физическом пространстве-времени.

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

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

Рассмотрим ориентированный ациклический бинарный граф. Ориентированный граф – это граф, все ребра которого имеют ориентацию. На рисунках такие ребра изображаются стрелками. Бинарный граф – это граф, каждая вершина которого инцидентна двум входящим и двум выходящим ребрам. На рисунке 1 изображена одна вершина с инцидентными ей ребрами. Ациклический граф – это граф, не содержащий ориентированные циклы. Далее рассматриваются только такие графы, поэтому для краткости будет использоваться термин «граф» или «Х-граф». Минимальный Х-граф изображен на рисунке 1, он называется Х-элементом. Предполагается, что вершины и ребра не имеют внутренних свойств и все свойства модели определяются только топологией графа.

Рассматриваются только конечные графы. В теории графов ребро – это бинарное отношение вершин. Очевидно, что в силу ацикличности некоторые вершины конечного графа будут иметь меньше четырех инцидентных ребер. Свободные валентности – это места для ребер, к которым в процессе роста графа присоединяются новые вершины. Формально валентность можно рассмотреть как ребро, у которого одна вершина актуально существует, а другая потенциально возможна, но не включена в состав вершин графа. Далее для удобства свободные валентности будут называться также внешними ребрами. На рисунках они изображаются как ребра или стрелки, инцидентные только одной вершине. Очевидно, что внешние ребра могут быть входящими или выходящими. Если вершину на рисунке 1 рассматривать как граф, то все изображенные ребра являются внешними (четыре свободные валентности – две входящие и две выходящие). В работе [7] показано, что число входящих внешних ребер для любого рассматриваемого графа равно числу выходящих внешних ребер. Это число будем называть шириной графа.

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

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

Последовательный рост

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

Первый вид продолжения графа заключается в добавлении новой вершины к двум выходящим внешним ребрам (рис. 2a). Граф G изображен прямоугольником. Фактически он может иметь произвольную структуру. Внешние ребра, участвующие в элементарном продолжении, выделены. При этом продолжении число n внешних ребер не меняется.

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

Имеются еще два элементарных продолжения, симметричных рассмотренным. Третий вид продолжения заключается в добавлении новой вершины к двум входящим внешним ребрам (рис. 2c). При этом число n внешних ребер не меняется.

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

Можно доказать, что любой конечный связный Х-граф может быть построен в результате ко- нечной последовательности элементарных продолжений этих четырех видов [7]. Таким образом, рассмотренные элементарные продолжения составляют полный набор операций, для которого должны быть сформулированы законы динамики в форме алгоритма порождения графа. Термин «динамика» далее используется только в этом смысле.

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

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

Амплитуда связи

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

Рассмотрим ориентированный маршрут в графе (рис. 3). Он начинается в некоторой вершине с номером a и заканчивается некоторым выходящим внешним ребром с номером i. Здесь и далее вершины будут обозначаться буквами греческого алфавита, а внешние ребра – латинского. При этом номера вершин принимают значения от 1 до N, где N – число вершин в графе, а номера как входящих, так и выходящих внешних ребер принимают значения от 1 до n, где n – ширина графа (число входящих или выходящих внешних ребер, то есть число внешних ребер одного направления).

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

Введем амплитуду a(f)ia связи вершины номер a и внешнего выходящего ребра номер i. По определению она равна сумме вероятностей всех ориентированных маршрутов из вершины номер a во внешнее выходящее ребро номер i:

,                                    (1)

где индекс m нумерует ориентированные маршруты из вершины номер a во внешнее ребро номер i; M=Mf(a, i) – число этих ориентированных маршрутов; k(m) – число вершин в маршруте номер m, включая вершину номер a. Эта амплитуда является неотрицательным числом, не превышающим единицу. Она имеет ясный смысл. Связь тем сильнее, чем больше ориентированных маршрутов и чем короче эти маршруты.

Аналогично введем амплитуду a(p)ia связи вершины номер a и внешнего входящего ребра номер i. По определению, для M=Mp(a, i)

.                                     (2)

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

Алгоритм вычисления вероятностей

Рассмотрим алгоритм вычисления вероятностей элементарных продолжений, основанный на амплитудах. Он состоит из трех шагов. Далее термин «нечто выбирается с указанными вероятностями» означает, что выбор осуществляется вероятностно независимо в совокупности от всех введенных и реализованных ранее случайных величин.

На первом шаге выбирается элементарное продолжение по ориентации ребер (в будущее) или против ориентации (в прошлое). Предполагается симметрия направления процесса. Поэтому определим этот выбор как равновероятный с вероятностями, равными 1/2, независимо от топологии графа.

На втором шаге равновероятно выбирается вершина «лидер». Обозначим ее номер через a. Этот выбор осуществляется с вероятностями, равными 1/N, где N – число вершин графа.

На третьем шаге выбираются два внешних ребра, к которым присоединяется новая вершина. Если на первом шаге выбрано продолжение по ориентации ребер, то это выходящие внешние ребра. Иначе – это входящие внешние ребра. По определению, выбор внешнего выходящего ребра номер i делается с вероятностью a(f)ia, а выбор внешнего входящего ребра номер i – с вероятностью a(p)ia.

Для вероятности p(f)ij добавления новой вершины к внешним выходящим ребрам с номерами i и j получаем следующее выражение:

.                                (3)

Отметим, что при перестановке номеров ребер i и j получится то же элементарное продолжение. Таким образом, при неравных номерах i и j итоговая вероятность элементарного продолжения первого вида равна удвоенному выражению (3), так как величина p(f)ij симметрична относительно перестановки индексов.

Аналогично для вероятности p(f)ij добавления новой вершины к внешним входящим ребрам с номерами i и j получаем следующее выражение:

.                                (4)

Если номера i и j совпадают, то, по определению, это вероятность добавления вершины к одному внешнему ребру, то есть это элементарное продолжение второго или четвертого видов (для внешних выходящих или входящих ребер соответственно). В данном случае удвоение величин p(f)ii и p(p)ij не происходит.

Вероятности элементарных продолжений нормированы на 1. Сумма по i амплитуд a(f)ia равна 1, так как обязательно выбирается какой-то ориентированный маршрут. Суммируя (3) или (4) по i и j, под знаком суммы получаем 1. Сумма N единиц равна N. Сумма по всем внешним выходящим или входящим ребрам равна 1/2. Итого сумма вероятностей всех путей равна 1.

Рассмотрим смысл этого определения. При добавлении новой вершины к выходящим внешним ребрам с номерами i и j образуются новые неориентированные циклы. Рассмотрим циклы специального вида, состоящие из двух ориентированных маршрутов (рис. 4). Назовем такие циклы петлями. Припишем каждой петле вес, равный произведению вероятностей составляющих ее ориентированных маршрутов до присоединения новой вершины. Тогда сумма петель, образованных новой вершиной, присоединенной к выходящим внешним ребрам с номерами i и j, и начинающихся в вершине номер a, равна a(f)iaa(f)aj. Сумма всех петель, образованных добавлением новой вершины, получается суммированием по a. В итоге получаем определение (3). Как уже отмечалось, при неравных номерах i и j петли учитываются дважды.

Уравнения (3) и (4) можно записать в матричной форме. Рассмотрим следующие матрицы. Квадратная симметричная матрица pf вероятностей по ориентации (в будущее) размера n. (Далее все матрицы будут обозначаться латинскими буквами c жирным шрифтом.) Ее элементами являются величины p(f)ij, где i и j – номера внешних выходящих ребер. Квадратная симметричная матрица pp вероятностей против ориентации (в прошлое) размера n. Ее элементами являются величины p(p)ij, где i и j – номера внешних входящих ребер. Прямоугольная матрица af амплитуд по ориентации (в будущее) размера (n, N). Ее элементами являются амплитуды a(f)ia, где номер строки i – номер внешнего выходящего ребра, а номер столбца a – номер вершины. Прямоугольная матрица ap амплитуд против ориентации (в прошлое) размера (n, N). Ее элементами являются амплитуды a(p)ia, где номер строки i – это номер внешнего входящего ребра, а номер столбца a – номер вершины. Уравнения (3) и (4), соответственно, для внешних выходящих и входящих ребер в матричной форме имеют вид

,                                                      (5)

.                                                       (6)

Отметим, что в каждой матрице вероятностей сумма всех элементов равна 1/2, что соответствует нормировке. В матрицах амплитуд сумма элементов каждого столбца равна 1, а сумма всех элементов равна N.

Алгоритм вычисления матриц амплитуд

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

Граф, состоящий из одной вершины, имеет ширину 2 (рис. 1). Обозначим его G1,2. Для его матриц амплитуд af(G1,2) и ap(G1,2) имеем

.                             (7)

Рассмотрим граф GN,n ширины n, состоящий из N вершин. Пусть для него известны матрицы af(GN,n) и ap(GN,n). Рассчитаем новые матрицы амплитуд при каждом из четырех видов элементарных продолжений.

Рассмотрим элементарное продолжение первого вида (рис. 2а). При добавлении вершины к двум выходящим внешним ребрам с номерами i и j ширина графа не меняется. Два выходящих внешних ребра становятся внутренними ребрами, и возникают два новых выходящих внешних ребра. Присвоим новым выходящим внешним ребрам те же номера i и j. Поскольку ребра эквивалентны, не имеет значения, какой номер какому из новых выходящих внешних ребер присвоен. При этом каждая строка с номерами i и j новой матрицы af(GN+1,n) равна среднему арифметическому строк с номерами i и j исходной матрицы af(GN,n). Для элементов этих двух строк имеем

                     (8)

где индексы i и j фиксированы, а индекс a принимает значения от 1 до N. Кроме того, к af(GN,n) добавляется новый столбец с номером N+1. Соответствующая ему новая вершина связана только с новыми внешними выходящими ребрами с номерами i и j, при этом с каждым только одним ориентированным маршрутом, состоящим из одной вершины (это сама новая вершина). Следовательно, все элементы нового столбца равны нулю, кроме элементов с номерами i и j, которые равны 1/2. Получаем

,     (9)

                                           (10)

где индекс s принимает все значения от 1 до n, кроме i и j.

Все элементы матрицы ap(GN,n) не меняются, так как не меняются внешние входящие ребра. Но к ap(GN,n) добавляется столбец номер N+1. Обозначим через b и g номера вершин, которым в графе GN,n инцидентны внешние выходящие ребра с номерами i и j. Тогда новый столбец равен среднему арифметическому столбцов с номерами b и g. Получаем

                     (11)

где индекс s принимает значения от 1 до n.

Рассмотрим элементарное продолжение второго вида (рис. 2b). При добавлении вершины к одному выходящему внешнему ребру с номером i ширина графа увеличивается на 1. Одно выходящее внешнее ребро становится внутренним ребром, и возникают два новых выходящих внешних ребра и одно новое входящее внешнее ребро. Присвоим одному новому выходящему внешнему ребру номер i. Не имеет значения, какому из новых выходящих внешних ребер присвоен номер, так как эти ребра эквивалентны. Оставшемуся выходящему внешнему ребру присвоим номер n+1. Входящему внешнему ребру также присвоим номер n+1. При этом все элементы строки с номером i новой матрицы af(GN+1,n+1) равны элементам этой строки матрицы af(GN,n), деленным на 2, и им равны элементы строки с номером n+1:

             (12)

где индекс i фиксирован, а индекс a принимает значения от 1 до N. Кроме того, к af(GN,n) добавляется новый столбец номер N+1. В столбце с номером N+1 элементы с номерами (i, N+1) и (n+1, N+1) равны 1/2, а остальные элементы этого столбца равны нулю. Имеем

                            (13)

                                        (14)

где индекс i фиксирован, а индекс s принимает значения от 1 до i–1 и от i+1 до n.

Все элементы матрицы ap(GN,n) не меняются, так как не меняются внешние входящие ребра. Но к ap(GN,n) добавляются строка номер n+1 и столбец номер N+1. Обозначим через b номер вершины, которой в графе GN,n инцидентно внешнее выходящее ребро номер i. Все элементы нового столбца номер N+1 от строки номер 1 до строки номер n равны элементам столбца с номером b, деленным на 2. Получаем

,                  (15)

где индекс s принимает значения от 1 до n. Все элементы новой строки номер n+1 равны нулю, кроме элемента номер N+1, который равен 1/2:

,                                         (16)

,                                   (17)

где индекс γ принимает значения от 1 до N.

Элементарные продолжения третьего и четвертого видов полностью симметричны рассмотренным. Для элементарного продолжения (с точностью до перестановки индексов (f) и (p)) третьего вида (рис. 2с) справедливы формулы (8)–(11), четвертого вида (рис. 2d) – формулы (12)–(17).

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

Свойства алгоритма роста графа

Из рассмотренного выше алгоритма построения матриц амплитуд следует, что элемент матрицы амплитуд не может превышать 1/2.

Теорема 1. Максимально возможная вероятность элементарного продолжения первого и третьего видов равна 1/4. Максимально возможная вероятность элементарного продолжения второго и четвертого видов равна 1/8.

Доказательство. Элемент матрицы вероятностей равен произведению двух строк матрицы амплитуд. Элемент матрицы амплитуд не больше 1/2, а число элементов в строке равно N. Итого сумма элементов строки матрицы амплитуд не больше N/2. При перемножении двух строк каждый элемент умножается не более чем на максимальный элемент 1/2. Итого элемент матрицы вероятностей, равный произведению двух строк матрицы амплитуд, не превышает N/4. Вероятности элементарных продолжений первого и третьего видов равны сумме двух элементов матрицы вероятностей, умноженных на 1/(2N). Таким образом, они не превышают 1/4. Вероятности элементарных продолжений второго и четвертого видов равны элементу матрицы вероятностей, умноженному на 1/(2N). Таким образом, они не превышают 1/8. Теорема доказана.

Простейшим примером элементарных продолжений с максимальными значениями вероятностей является рост графа, состоящего из одной вершины (рис. 1). Имеются одно элементарное продолжение первого вида и одно третьего вида с вероятностью 1/4. Оба эти продолжения заключаются в образовании особой петли – двойного ребра (рис. 5).

Имеются по два элементарных продолжения второго и четвертого видов с вероятностью 1/8 каждое. Они заключаются в добавлении новой вершины к одному из двух внешних, соответственно, выходящих или входящих ребер.

Особый интерес представляет образование структур в процессе последовательного роста. По этому поводу можно высказать следующее предварительное замечание. Предлагаемый алгоритм в среднем сохраняет пропорции между слабосвязанными подграфами. Слабая связь в данном случае является качественной характеристикой, означающей, что маршрутов, соединяющих подграфы, мало. Рассмотрим граф, состоящий из двух слабосвязанных подграфов. В пределе – это два несвязанных подграфа. Пусть они состоят из N1 и N2 вершин. Тогда вероятность добавления новой вершины к первому подграфу равна N1/(N1+N2), а ко второму – N2/(N1+N2). В среднем отношение числа вершин в подграфах сохраняется в процессе последовательного роста. Однако эта пропорция неустойчива. При случайном изменении пропорции алгоритм не имеет тенденции восстанавливать исходную пропорцию.

Причинность

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

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

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

Доказательство. Рассмотрим добавление двух вершин. Первая вершина добавляется к внешним выходящим ребрам, инцидентным вершинам a и b исходного графа G, а вторая добавляется к внешним выходящим ребрам, инцидентным вершинам g и d исходного графа G (рис. 6). Некоторые из вершин a, b, g и d могут совпадать. В процессе последовательного роста эти вершины могут добавляться в двух последовательностях: сначала первая вершина, а затем вторая и наоборот. Вероятность добавления двух вершин равна произведению вероятностей добавления каждой вершины. Вероятность добавления вершины состоит из произведения элемента матрицы вероятностей на коэффициент нормировки. Элементы матрицы вероятностей не зависят от порядка добавления вершин, так как одна новая вершина не попадает в прошлое другой. Коэффициент нормировки зависит только от числа вершин N в G и пропорционален 1/N для вершины, добавляемой первой, и 1/(N+1) для вершины, добавляемой второй, независимо от порядка добавления вершин. Следовательно, вероятности обеих последовательностей добавления вершин равны. Аналогичное свойство справедливо для внешних входящих ребер. Очевидно, что это свойство справедливо для произвольного числа добавляемых вершин. Теорема доказана.

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

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

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

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

Литература

1.     Вяльцев А.Н. Дискретное пространство-время. М.: Наука, 1965, 432 с.

2.     G.'t Hooft Quantum gravity: a fundamental problem and some radical ideas, in Recent Development in Gravitation, Proceedings of the 1978 Cargese Summer Institute, ed. by M. Levy and S. Deser, Plenum, N.Y./London, 1979, pp. 323–345.

3.     Myrheim J. Statistical Geometry. CERN preprint TH-2538, 1978. 13 p.

4.     Krugly A.L. A sequential growth dynamics for a directed acyclic dyadic graph. URL: http://arxiv.org/abs/1112.1064v1 (дата обращения: 03.06.2012).

5.     Krugly A.L. and Stepanian I.V. An example of the stochastic dynamics of a causal set, in Foundations of Probability and Physics-6, Växjö-Kalmar, Sweden, 14–16 June 2011, AIP Conference Proceedings. 2012. Vol. 1424, pp. 206–210.

6.     Лоэв М. Теория вероятностей. М.: Иностранная лит-ра, 1962, 720 с.

7.     Krugly A.L. Discrete mechanics: a kinematics for a particular case of causal sets. URL: http://arxiv.org/abs/1008.5169v1. (дата обращения: 03.06.2012).

8.     Rideout D.P. and Sorkin R.D. A classical sequential growth dynamics for causal sets. Phys. Rev. D, 2000, Vol. 61, pp. 024002-1–16.