Планарные остовы ограниченной степени с малыми весами: различия между версиями

Перейти к навигации Перейти к поиску
Строка 88: Строка 88:
1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в <math>S \Theta\ GG</math> как необработанные.
1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в <math>S \Theta\ GG</math> как необработанные.


2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей <math>E_2 (x) \; </math>, определяемое следующим образом: <math>E_2 (x) = \{ uv \in S \Theta\ GG | u</math> или <math>v \in N_{UDG}(X) \} </math>. Иными словами, ЕгМ представляет собой набор дуг в <math>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x.
2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей <math>E_2 (x) \; </math>, определяемое следующим образом: <math>E_2 (x) = \{ uv \in S \Theta\ GG | u</math> или <math>v \in N_{UDG}(x) \} </math>. Иными словами, <math>E_2 (x) \; </math> представляет собой набор дуг в <math>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x.


3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в <math>E_2 (x) \; </math>, он удаляет дугу xy в случае, если существует дуга <math>uv \in E_2 (x) \; </math> (где u и v отличны от x и y), такая, что <math>\big\| xy \big\| > max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|)</math>; в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при помощи широковещательного сообщения UPDATESTATUS(XY).
3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в <math>E_2 (x) \; </math>, он удаляет дугу xy в случае, если существует дуга <math>uv \in E_2 (x) \; </math> (где u и v отличны от x и y), такая, что <math>\big\| xy \big\| > max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|)</math>; в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при помощи широковещательного сообщения UPDATESTATUS(XY).
Источник — http://pco.iis.nsk.su/wega/index.php/Планарные_остовы_ограниченной_степени_с_малыми_весами