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

 

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

 

  

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

 

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

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

 

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

 

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

 

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

 

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

 


 

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

 

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

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

 

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

 

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

 

     ADJVOUT(CC2)={CC1,CC3,CC4,CC8} - подмножество соседей-получателей затрат

 

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

 

     NADJOUT(CC2)=4

 

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

 

     ADJVIN(CC2)={CC1,CC3} - подмножество соседей-источников затрат

 

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

 

     NADJIN(CC2)=2

 

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

 

     ADJV(CC2)=ADJVIN(CC2)+ADJVOUT(CC2)={CC1,CC3,CC4,CC8} - подмножество соседей

 

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

 

     NADJ(CC2)=4

 

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

 

      ADJVIN(CC2) ∩  ADJVOUT(CC2)={CC1,CC3}

  

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

 

   

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