Матрица обратной достижимости

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

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

Наличие матрицы обратной достижимости M_RA[N_G,N_G] позволяет ввести такое понятие для Графа затрат G(N_G), как подмножество обратной достижимости.

Подмножество обратной достижимости ADJ_RA(CC_i) - представляет собой подмножество центров затрат, для которых в Графе затрат G(N_G) существуют обратные орпути из центра затрат СС_i. Другими словами, подмножество обратной достижимости центра затрат СС_i формируется всеми центрами затрат, из которых потоки вторичных затрат могут попасть на вход центра затрат CC_i. Состав данного подмножества определяется ненулевыми элементами столбца CC_i матрицы обратной достижимости M_RA[N_G,N_G].

Рассмотрим Граф затрат G(10,10): (обратные дуги)

и его матрицу обратной достижимости M_RA[10,10]:

Например, центр затрат CC₂ достижим из любого центра затрат, входящего в подмножество:

     ADR_RA(CC₂)={CC₁,CC₂,CC₃,CC₄} 

Это значит, что в рассматриваемом Графе затрат G(10,10) потоки вторичных затрат с выхода каждого из перечисленных центров затрат обязательно поступят на вход центра затрат CC₂.

Данное подмножество играет важную роль в выделении процессов в Графе затрат. Отметим также, что матрица обратной достижимости получается путем транспонирования матрицы прямой достижимости.

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