Метрические характеристики Графов затрат

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

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

  • Length(OrChain(CCi,CCj)) - длина орцепи между центрами затрат CCi и CCj
  • OrDist(CCi,CCj) - оррасстояние между центрами затрат CCi и CCj
  • OrSpread(CCi,CCj) - орпротяженность между центрами затрат CCi и CCj
  • OrEcc(CCi) - орэксцентриситет центра затрат CCi
  • VORCEN(G) - орцентр Графа затрат G
  • VORRIM(G) - орокраина Графа затрат G
  • OrRad(G) - оррадиус Графа затрат G
  • OrDiam(G) - ордиаметр Графа затрат G

Длина Length(OrChain(CCi,CCj)) орцепи определяется числом дуг, составляющих орцепь.

Оррасcтояние OrDist(CCi,CCj) между центрами затрат CCi и CCj определяется как длина кратчайшего орпути, соединяющего центр затрат CCi с центром затрат CCj. Если два центра затрат Графа затрат не соединены орпутем, то оррасстояние между ними считаем бесконечным.

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

 

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

Метрические характеристики Графа затрат

 

Определим длину орцепи OrChain1(CC1,CC5)=(e1,e4,e8) как:

      Length(OrChain1(CC1,CC5))=3 - т.к. эта орцепь формируется тремя дугами

 

Определим оррасстояние и орпротяженность между центрами затрат CC1 и CC5. Для этого составим перечень всех орпутей, ведущих из центра затрат CC1 к центру затрат CC5, и определим их длины:

  • OrChain1(CC1,CC5)=(e1,e4,e8)   →  Length(OrChain1(CC1,CC5))=3
  • OrChain2(CC1,CC5)=(e3,e6,e8)  →  Length(OrChain2(CC1,CC5))=3
  • OrChain3(CC1,CC5)=(e3,e7)       →  Length(OrChain3(CC1,CC5))=2

Определим длину кратчайшего орпути, ведущего из центра затрат CC1 к центру затрат CC5, и найдем оррасстояние между центрами затрат CC1 и CC5:

      OrDist(CC1,CC5)=min Length(OrChaink(CC1,CC5))=2   где: k=1..3

 

Определим длину самого длинного орпути, ведущего из центра затрат CC1 к центру затрат CC5, и найдем орпротяженность между центрами затрат CC1 и CC5:

      OrSpread(CC1,CC5)=max Length(OrChaink(CC1,CC5))=3   где: k=1..3 


 

Орэксцентриситетом OrEcc(CCi) центра затрат CCi будем называть оррасстояние от этого центра затрат до самого удаленного от него центра затрат Графа затрат:

      OrEcc(CCi)=max OrDist(CCi,CCj)     

Орцентром VORCEN(G) Графа затрат G или подмножеством его орцентральных центров затрат будем называть подмножество всех центров затрат Графа затрат G с наименьшей величиной орэксцентриситета.

 

Орокраиной VORRIM(G) Графа затрат G или подмножеством его орпериферийных центров затрат будем называть подмножество всех центров затрат Графа затрат G с наибольшей величиной орэксцентриситета.

 

Оррадиусом OrRad(G) Графа затрат G называется наименьшая из величин орэксцентриситетов центров затрат, формирующих данный Граф затрат:

 

      OrRad(G)=min OrEcc(CCi)      

 

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

 

Ордиаметром OrDiam(G) Графа затрат G называется наибольшая из величин орэксцентриситетов центров затрат, формирующих данный Граф затрат:

 

      OrDiam(G)=max OrEcc(CCi)      

 

Ордиаметр Графа затрат G определяет, что в Графе затрат G есть хотя бы одна пара центров затрат {CCi,CCj}, связанных между собой орпутем, оррасстояние которого равно ордиаметру Графа затрат G.

Рассмотрим процедуры получения метрических характеристик на примере Графа затрат G(5,8) из предыдущего примера. Сначала определим значения орэксцентриситетов центров затрат Графа затрат G(5,8). Для этого, найдем оррасстояния от каждого центра затрат Графа затрат G(5,8) до всех остальных его центров затрат и сведем их в следующую таблицу:

 

Метрические характеристики Графа затрат  

Затем, выбрав максимальные значения оррасстояний для каждого центра затрат CCi, т.е. максимальное значение в каждом столбце таблицы, получим величины орэксцентриситетов:

  • OrEcc(CC1)=max OrDist(CC1,CCj)=2 
  • OrEcc(CC2)=max OrDist(CC2,CCj)=2
  • OrEcc(CC3)=max OrDist(CC3,CCj)=3
  • OrEcc(CC4)=max OrDist(CC4,CCj)=3
  • OrEcc(CC5)=max OrDist(CC5,CCj)=∞ 

Значение орэксцентриситета OrEcc(CC5)= мы получили потому, что центр затрат CC5 является в Графе затрат G(5,8) стоком, т.е. из него не существует ни одного орпути к другим центрам затрат. Следовательно, оррасстояние от центра затрат CC5 до любого другого центра затрат Графа затрат G(5) равно бесконечности.

Теперь мы можем определить значение оррадиуса Графа затрат G(5,8):

 

      OrRad(G)=min OrEcc(CCi)=min(2,2,3,3,∞)=2 

и орцентр Графа затрат G(5,8), т.е. подмножество его орцентральных центров затрат:

 

      VORCEN(G)={CC1,CC2} 

Перед тем, как перейти к определению значения ордиаметра Графа затрат G(5,8), обсудим ранее полученное значение орэксцентриситета для центра затрат CC5, являющегося стоком. С формальной точки зрения, значение орэксцентриситета стока CC5 действительно можно считать равным бесконечности. Однако, нас интересует не формальная сторона дела, а получение возможности количественной оценки топологического каркаса Графа затрат G(5,8). Исходя из этого посыла, для практической оценки величины орэксцентриситета, мы будем пользоваться максимальным из конечных значений оррасстояний.

Принятое решение позволит нам определить значение ордиаметра Графа затрат G(5,8):

 

      OrDiam(G)=max OrEcc(CCi)=max(2,2,3,3)=3 

 

и орокраину Графа затрат G(5,8), т.е. подмножество его орпериферийных центров затрат:

 

      VORRIM(G)={CC3,CC4} 

 

Орцентр и орокраина Графа затрат 

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