Матрица смежности Графа затрат

Автор:  Александр Поляков

Матрицей смежности M_C[N_G,N_G] Графа затрат G(N_G) будем называть квадратную матрицу размерности N_G, элементы которой формируются в соответствии со следующими правилами:

Ненулевые элементы матрицы смежности, содержащиеся в столбце источника затрат СС_i, определяют состав подмножества его соседей-получателей затрат ADJ_V^OUT(СС_i).

Ненулевые элементы матрицы смежности, содержащиеся в строке получателя затрат СС_j, определяют состав подмножества его соседей-источников затрат ADJ_V^IN(СС_j).

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

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

Столбцы и строки матрицы смежности, соответствующие изолированным центрам затрат, содержат исключительно 0-вые элементы. Это центры затрат, которые в рассматриваемом периоде не отдают другим центрам затрат элементарные потоки вторичных затрат и не получают их. Изолированный центр затрат может получать потоки первичных затрат.

Рассмотрим Граф затрат G(8,13):

и его матрицу смежности M_C[8,8]:

Например, в столбце матрицы смежности, соответствующем источнику затрат СС₂, содержатся четыре единицы. Сформируем для центра затрат СС₂ подмножество соседей-получателей затрат, т.е. центров затрат, которые получают элементарные потоки вторичных затрат от центра затрат CC₂:

     ADJ_V^OUT(CC₂)={CC₁,CC₃,CC₄,CC₈} - подмножество соседей-получателей затрат

и определим число центров затрат в нем:

     N_ADJ^OUT(CC₂)=4

В строке матрицы смежности, соответствующей получателю затрат СС₂, содержится две единицы. Сформируем для центра затрат СС₂ подмножество соседей-источников затрат, т.е. центров затрат, от которых центр затрат CC₂ получает элементарные потоки вторичных затрат:

     ADJ_V^IN(CC₂)={CC₁,CC₃} - подмножество соседей-источников затрат

и определим число центров затрат в нем:

     N_ADJ^IN(CC₂)=2

Общая сумма единиц в строке и в столбце центра затрат СС₂ равна шести. Подмножества соседей-источников затрат ADJ_V^IN(СС₂) и соседей-получателей затрат ADJ_V^OUT(СС₂) пересекаются, т.е. в множество соседей ADJ_V(СС₂) войдут всего четыре центра затрат:

     ADJ_V(CC₂)=ADJ_V^IN(CC₂)+ADJ_V^OUT(CC₂)={CC₁,CC₃,CC₄,CC₈} - подмножество соседей

Число центров затрат в множестве соседей ADJ_V(CC₂) составит:

     N_ADJ(CC₂)=4

Тот факт, что подмножества соседей-получателей затрат и соседей-источников затрат пересекаются:

      ADJ_V^IN(CC₂) ∩  ADJ_V^OUT(CC₂)={CC₁,CC₃}

говорит о том, что между центром затрат CC2 и центрами затрат {СС1,СС3} существуют встречные элементарные потоки вторичных затрат.

Дата:  16 июня 2014 года