Ориентированные цепи в Графах затрат

    

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

 

В любом Графе затрат можно выделить различные виды последовательностей центров затрат и инцидентных им дуг, т.е. элементарных потоков вторичных затрат. Эти последовательности используются, например, для выделения маршрутов движения затрат, принимающих участие в формировании себестоимости отдельных видов продукции, работ и услуг.

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

OrChain(CCi,CCj) - орцепь

где:

CCi - начало орцепи (источник затрат)

CCj - конец орцепи (получатель затрат)

Простая орцепь или орпуть представляет собой орцепь, у которой различны не только дуги, но и все входящие в нее центры затрат.

Ормаршрут определяется так же как орцепь, только в ормаршруте отсутствует ограничение на повторение дуг, т.е. по одной и той же дуге можно проходить более одного раза:

OrRoute(CCi,CCj) - ормаршрут

где:

CCi - начало ормаршрута (источник затрат)

CCj - конец ормаршрута (получатель затрат)

При решении задач на Графах затрат также представляют интерес последовательности центров затрат и инцидентных им дуг, которые начинаются и заканчиваются на одном и том же центре затрат:

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

простой контур - замкнутая простая орцепь

замкнутый ормаршрут – у которого совпадают начальный и конечный центры затрат

Рассмотрим примеры перечисленных последовательностей, выделив их в Графе затрат G(6,10):

    

GZ61 1

    

На рисунке вверху выделена орцепь:

OrChain1(CC1,CC5)=(CC1,CC2,CC4,CC6,CC3,CC1,CC5)=(e1,e6,e8,e9,e7,e3) - орцепь начинается в центре затрат CC1 и заканчивается в центре затрат CC5. Все дуги орцепи различны и проходятся только в одном направлении – от источника затрат СС1 к получателю затрат СС5. Центр затрат CC1 встречается в орцепи дважды.

   

GZ61 2

   

На рисунке вверху выделена простая орцепь (орпуть):

OrChain2(CC1,CC5)=(CC1,CC2,CC4,CC6,CC5)=(e1,e6,e8,e10) - орпуть начинается в центре затрат СС1 и заканчивается в центре затрат СС5. Все дуги орпути различны и проходятся только в одном направлении – от источника затрат CC1 к получателю затрат CC5. Каждый центр затрат встречается в орпути только один раз.

   

GZ61 3

   

На рисунке вверху выделен контур:

OrChain3(CC2,CC2)=(CC2,CC1,CC3,CC1,CC2)=(e4,e2,e7,e1) - контур начинается и заканчивается в центре затрат СС2. Все дуги контура различны и проходятся только в одном направлении. Центр затрат СС1 встречается в контуре два раза.

   

GZ61 4

   

На рисунке вверху выделен простой контур:

OrChain4(CC2,CC2)=(CC2,CC4,CC6,CC3,СС1,CC2)=(e6,e8,e9,e7,e1) - простой контур начинается и заканчивается в центре затрат СС2. Все дуги контура различны и проходятся только в одном направлении. Каждый центр затрат встречается в контуре только один раз.

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

обратная орцепь

обратный орпуть

обратный ормаршрут

обратный контур

обратный простой контур

обратный замкнутый ормаршрут

Мы не будем подробно рассматривать эти виды последовательностей, т.к. они получаются из уже изученных нами последовательностей путем замены дуг на обратные дуги.