ВЕРОЯТНОСТЬ  НЕСВЯЗНОСТИ  ПЛАНАРНОГО  ГРАФА  С  ВЕСАМИ

Цициашвили  Гурами  Шалвович

д-р  физ.-  мат.  наук,  зав.  лаборатории  вероятностных  методов  и  системного  анализа  ИПМ  ДВО  РАН,  профессор  ДВФУ,  РФ,  г.  Владивосток

E-mail:  guram@iam.dvo.ru

Осипова  Марина  Анатольевна

канд.  физ.-  мат.  наук,  доцент  ДВФУ,  РФ,  г.  Владивосток

E-mail:  mao1975@list.ru

Лосев  Александр  Сергеевич

канд.  физ.-  мат.  наук,  мнс  лаборатории  вероятностных  методов  и  системного  анализа  ИПМ  ДВО  РАН,  РФ,  г.  Владивосток

E-mail:  alexax@bk.ru

DISCONNECTION  PROBABILITY  OF  PLANAR  GRAPH  WITH  WEIGHTS

Tsitsiashvili  Gourami  Shalvovich

doctor  of  physical  and  mathematical  sciences,  head  of  laboratory  of  probability  methods  and  systems  analysis,  IAM  FEB  RAS,  Professor  of  FEFU,  Russia  Vladivostok

Osipova  Marina  Anatolievna

candidate  of  physical  and  mathematical  sciences,  associate  professor  of  FEFU,  Russia  Vladivostok

Losev  Alexandr  Sergeevich

candidate  of  physical  and  mathematical  sciences,  junior  research  fellow  of  laboratory  of  probability  methods  and  systems  analysis,  IAM  FEB  RAS,  Russia  Vladivostok

АННОТАЦИЯ

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

ABSTRACT

In  this  paper  an  algorithm  of  a  calculation  of  a  disconnection  probability  for  a  planar  weighted  graph  with  high  reliable  edges  is  constructed  on  a  base  of  special  asymptotic  relations.  Asymptotic  constants  (a  minimal  volume  of  cross  sections  and  a  weighted  coefficient)  are  calculated  by  known  formulas  and  their  modifications.  Suggested  algorithm  is  convenient  in  a  realization  and  has  cubic  complexity  by  a  number  of  the  graph  nodes. 

Ключевые  слова:  вес;  грань;  цикл;  вероятность  несвязности.

Keywords:  a  weight;  a  face;  a  cycle;  a  disconnection  probability.

Введение

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

Основной  результат

Рассмотрим  неориентированный  связный  граф  G  без  петель  и  кратных  ребер  с  конечным  множеством  вершин  U  и  ребер  W.  Пусть  каждому  ребру  графа  wW  соответствует  вес  .  Обозначим  L  множество  разрезов  графа,  d(L)  число  ребер  (объем)  разреза  L,  D  минимальный  объем  разрезов.  Предположим,  что  ребра  графа  G  отказывают  независимо  с  вероятностями  ,  wW.  Для  вероятности  несвязности    графа  G  (отсутствия  хотя  бы  между  двумя  вершинами  графа  работающего  пути)  в  работе  [3]  была  сформулирована  теорема. 

Теорема.  Если    то

  (1)

Доказательство  этой  теоремы  аналогично  доказательству  теоремы  1  в  работе  [3].  В  настоящей  работе  построен  алгоритм  вычисления  параметра    для  планарного  графа  G,  каждое  ребро  которого  принадлежит  какому-либо  простому  циклу. 

Ребра  планарного  графа  G  разбивают  плоскость  на  грани,  обозначим  n  число  граней  (включая  внешнюю),  m  число  ребер  графа.  Графу  G  сопоставим  двойственный  граф  G*:  грани  z  графа  G  соответствует  вершина  z  графа  G*,  ребру  w  графа  G,  принадлежащему  граням  ,  соответствует  ребро  w,  соединяющее  вершины  nbsp; графа  G*. 

Пусть  элементы    i,  j=1,…,n,  матрицы  A  определяют  число  ребер,  содержащихся  в  пересечении  граней    Известно  [1],  что 

D=min  (k:  2  k    5:  >0),

где    число  простых  циклов  длины  k  в  G*  и  определяетcя  оно  в  случае  k>2  по  формулам  из  [2],  в  случае  k=2  по  формуле  из  [3]  следующим  образом

где    элементы  степени  матрицы  а    след  матрицы  A. 

Обозначим  K*  множество  циклов  K*  графа  G*,  d(K*)  длину  цикла  K*,  D*  минимальную  длину  цикла.  Известно  [1],  что  циклам  минимальной  длины  графа  G*  соответствуют  разрезы  минимального  объема  графа  G,  причем  D*=D.  Тогда

Пусть  константы    определяют  веса  ребер  содержащихся  в  пересечении  граней    графа  G,  при  этом    В  частности,  в  случае  D>2,    

Теорема.  Для  планарного  графа  G,  каждое  ребро  которого  принадлежит  какому-либо  простому  циклу,  имеют  место  соотношения

  (2)

где    а    элементы  матрицы 

Доказательство  теоремы  основано  на  доказательствах  формул  вычисления    предложенных  в  [3],  [2].

Вычислительный  эксперимент

В  работе  был  проведен  вычислительный  эксперимент  на  примере  планарного  графа  с  D=4  (рис.  1).  Зададим  веса  ребер  графа,  находящихся  в  пересечении  граней  :  (ребра  выделены  фиолетовым  цветом),  остальные  веса  положим  равными  1.02. 

Рисунок  1.  Пример  графа  с  D=4

Из  формулы  (2)  нетрудно  получить  8.56190839.  Положим  h=0.05  и  вычислим  вероятность  несвязности    по  асимптотической  формуле  (1)  и  методом  Монте-Карло,  обозначив  ее  ,  с  числом  реализаций 

  0.0000535119,    0.0000523.

Время  счета  по  формуле  (1)  составляет  несколько  секунд,  а  методом  Монте-Карло  -  несколько  часов. 

Список  литературы:

1.            Прасолов  В.В..  Элементы  комбинаторной  и  дифференциальной  топологии.  2004.  М.:  МЦНМО  —  с.  352.

2.            Harary  F.,  B.  Manvel.  On  the  Number  of  Cycles  in  a  Graph  //  Matematicky  casopis  —  1971.  —  Vol.  21,  —  №  1.  —  55—63  с.

3.            Tsitsiashvili  G.Sh..  Complete  calculation  of  disconnection  probability  in  planar  graphs  //  Reliability:  Theory  and  Applications  —  2012.  —  Vol.  7,  —  №  1.  —  154—159  с.