Матрица обратной достижимости
Автор: Александр Поляков
Матрицей обратной достижимости MRA[NG,NG] Графа затрат G(NG) будем называть квадратную матрицу размерности NG, значения элементов которой формируются в соответствии со следующими правилами:
Наличие матрицы обратной достижимости MRA[NG,NG] позволяет ввести такое понятие для Графа затрат G(NG), как подмножество обратной достижимости.
Подмножество обратной достижимости ADJRA(CCi) - представляет собой подмножество центров затрат, для которых в Графе затрат G(NG) существуют обратные орпути из центра затрат ССi. Другими словами, подмножество обратной достижимости центра затрат ССi формируется всеми центрами затрат, из которых потоки вторичных затрат могут попасть на вход центра затрат CCi. Состав данного подмножества определяется ненулевыми элементами столбца CCi матрицы обратной достижимости MRA[NG,NG].
Рассмотрим Граф затрат G(10,10): (обратные дуги)
и его матрицу обратной достижимости MRA[10,10]:
Например, центр затрат CC2 достижим из любого центра затрат, входящего в подмножество:
ADRRA(CC2)={CC1,CC2,CC3,CC4}
Это значит, что в рассматриваемом Графе затрат G(10,10) потоки вторичных затрат с выхода каждого из перечисленных центров затрат обязательно поступят на вход центра затрат CC2.
Данное подмножество играет важную роль в выделении процессов в Графе затрат. Отметим также, что матрица обратной достижимости получается путем транспонирования матрицы прямой достижимости.
Дата: 16 июня 2014 года