Матрица прямой достижимости. Компоненты связности

 

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

  

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

 

MatrixDA01

 

Если существует орпуть из центра затрат ССi в центр затрат ССj, то будем говорить, что центр затрат ССj достижим из центра затрат ССi. Центр затрат ССi считается достижимым сам из себя.

 

Если орпуть из центра затрат ССi в центр затрат ССj не существует, то будем говорить, что центр затрат ССj не достижим из центра затрат ССi.

 

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

 

Подмножество прямой достижимости ADJDA(ССi) – подмножество всех центров затрат, достижимых из центра затрат ССi. Состав данного подмножества определяется ненулевыми элементами матрицы прямой достижимости MDA[NG,NG] в столбце CCi.

 

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

 

GraphG89 

 

и его матрицу прямой достижимости MDA[8,8]:

 

MatrixDA02

 

Например, из центра затрат СС2 достижим любой центр затрат, входящий в его подмножество прямой достижимости ADJDA(CC2):

 

     ADJDA(CC2)={CC1,CC2,CC3,CC4,CC5,CC6

 

Это значит, что в Графе затрат G(8,9) можно найти орпути, ведущие из центра затрат СС2 к остальным центрам затрат данного подмножества. Напомним, что центр затрат СС2 достижим сам из себя, поэтому в ячейке на пересечении строки и столбца для центра затрат СС2 в матрице MDA[8,8] стоит единица.

 

Найдем орпути, ведущие из центра затрат СС2 к остальным центрам затрат Графа затрат G(8,9):

  • OrChain1(CC2,CC1)=(e6,e5,e4,e2)=(CC2,CC3,CC4,CC5,CC1)
  • OrChain2(CC2,CC3)=(e6)=(CC2,CC3     
  • OrChain3(CC2,CC4)=(e6,e5)=(CC2,CC3,CC4     
  • OrChain4(CC2,CC5)=(e6,e5,e4)=(CC2,CC3,CC4,CC5   
  • OrChain5(CC2,CC6)=(e6,e5,e7)=(CC2,CC3,CC4,CC7
  • OrChain6(CC2,CC7)=(e6,e5,e7,e9)=(CC2,CC3,CC4,CC6,CC7

 

С понятием достижимости в теории Графов затрат тесно связано понятие связности, которая может быть трех видов:

  • сильно связный Граф затрат
  • односторонне связный Граф затрат
  • слабо связный Граф затрат

Сильно связный Граф затрат – в котором любые два центра затрат CCi и CCj взаимно достижимы. Это означает, что существуют орпути – как из центра затрат CCi в центр затрат CCj, так и из центра затрат CCj в центр затрат CCi.

 

Односторонне связный Граф затрат – в котором для любой пары центров затрат CCi и CCj выполняется условие – хотя бы один центр затрат из пары достижим из другого центра затрат пары.

 

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

 

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

 

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

 

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

 

Рассмотрим Граф затрат G(10,10)

 

GraphG1010KS 

 

и его матрицу прямой достижимости MDA[10,10]:

 

MatrixDA03 

 

В Графе затрат G(10,10) можно выделить четыре компоненты связности:

  • G1(5,8)
  • G2(1,0)
  • G3(1,0)
  • G4(3,2)

 

 

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