Ресурсная сеть. 
Основные определения

Ресурсная сеть представляет собой ориентированный граф, вершинам vi которого приписаны неотрицательные числа qi (t), называемые ресурсами, и изменяющиеся в дискретном времени t.

Сеть двусторонняя, т. е., если существует ребро (vi, vj), то существует и противоположно ориентированное ребро (vj, vi).

Ребра графа взвешены — каждому ребру (vj, vi) приписано неотрицательное число rij, называемое его проводимостью. Проводимость ребра отвечает за его способность передавать ресурс от вершины к вершине. Каждая вершина имеет петлю (vi, vi) с проводимостью, равной rii. Петля отвечает за ресурс, который будет возвращен в вершину в процессе его перераспределения. Вершины обладают способностью удерживать неограниченное количество ресурса.

Матрицей проводимости называется матрица R = ||rij||nn, где rij — проводимость ребра (vi, vj).

Если пары не существует, rij = 0 и rji = 0.

Из определения ресурсной сети вытекают следующие свойства матрицы R:

• 1. R — неотрицательная матрица: i, jrij 0
• 2. i rii> 0
• 3. i, j (rij> 0 rji > 0)

Суммарной проводимостью сети, rsum, называется сумма проводимостей всех ее ребер:

.

Суммарную проводимость входных ребер вершины с номером i будем называть ее входной проводимостью; суммарную проводимость выходных ребер назовем выходной проводимостью и обозначим их через и соответственно. Проводимость петли входит в обе суммы.

=; = .

Сеть функционирует в дискретном времени t.

Распределение ресурса в сети происходит по одному из двух правил, выбор которых зависит от величины ресурса в вершинах. В момент t + 1 вершина vi в ребро, соединяющее ее с вершиной vk, отдаст:

правило 1: rik единиц ресурса, если ;

правило 2: в противном случае.

По правилу 1 вершина отдаст за такт работы всего: = ресурса. По правилу 2 вершина отдает весь свой ресурс. Если ресурс в вершине равен выходной проводимости вершины: , — то применение обоих правил даст один и тот же результат.

Суммарный ресурс, находящийся во всех вершинах, обозначим через W. В сети выполняется закон сохранения: при ее функционировании ресурс не поступает извне и не расходуется: t = W.

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

Ресурсная сеть называется симметричной, если симметрична ее матрица проводимости.

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

i: = .(1.1).

Если сеть не квазисимметрична, в ней существует хотя бы пара вершин, для которых выполнится:. Для произвольной вершины vi обозначим эту разность через ri: ri = -. Тогда все вершины сети можно разделить на три класса:

вершины-приемники, для которых ri> 0;

вершины-источники, для которых ri< 0;

нейтральные вершины, для которых ri = 0.

В симметричных и квазисимметричных сетях все вершины нейтральны.

Сеть будем называть несимметричной, если она не удовлетворяет условию квазисимметричности (1.1). Несимметричная сеть обладает как минимум одним источником и одним приемником.

Состоянием Q (t) сети в момент tбудем считать вектор Q (t) = (q1(t), …, qn (t)), состоящий из значений ресурсов в каждой вершине.

Состояние Q (t) называется устойчивым, если Q (t) = Q (t + 1) = Q (t + 2) = Q (t + 3) = …

Состояние Q*= (q1*, …, qn*) называется асимптотически достижимым из состояния Q (0), если для любого > 0 существует t такое, что для всех t > t.

qi* - qi (t) <, i = 1, 2, …, n.

Состояние сети называется предельным, если оно либо устойчиво и достижимо из Q (0) за конечное время, либо асимптотически достижимо из Q (0).

Распределение ресурса в сети представляет собой Марковский процесс. На основании свойств регулярных стохастических матриц [Гантмахер, 2004] доказана сходимость процесса распределения ресурса для любой конфигурации сети.