Interested Article - Жадное вложение графа

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

Идея географической маршрутизации на основе координат в виртуальном пространстве вместо физических координат узлов принадлежит Рао (Rao) (с соавторами) . Исследования потом показали, что любая сеть имеет жадное вложение со сжатыми координатами в гиперболической плоскости , что некоторые графы, включая полиэдральные графы , имеют жадное вложение в евклидову плоскость , и что графы единичных кругов имеют жадное вложение в евклидовы пространства средних размерностей с низкими коэффициентами растяжения.

Определения

При жадной маршрутизации сообщение из передающего узла s в узел назначения t проходит за ряд шагов через промежуточные узлы, каждый их которых находится ближе всего к t . Если сообщение достигает промежуточного узла x , не имеющего более близкого соседа к t , то оно не может быть передано и жадная маршрутизация терпит неудачу. Жадное вложение — это вложение заданного графа, в котором потери сообщения такого типа невозможны. Таким образом, это вложение можно описать как вложение графа, при котором для любых двух узлов x и t существует сосед y узла x , для которого d ( x , t ) > d ( y , t ), где d обозначает расстояние в пространстве, в которое вкладывается граф .

Графы без жадного вложения

Не любой граф имеет жадное вложение в . Простой контрпример — это звезда K _1,6 , дерево с одной внутренней вершиной и шестью листьями . Если вложить этот граф в плоскость, пара его листьев должна образовать угол в 60 градусов или меньше, откуда немедленно следует, что по меньшей мере один лист не имеет соседа, более близкого к другому листу из этой пары.

В евклидовых пространствах более высоких размерностей больше графов могут иметь жадное вложение. Так, K _1,6 имеет жадное вложение в трёхмерном евклидовом пространстве — располагаем внутренний узел в начале координат, а остальные узлы (листья) располагаем на единичном расстоянии по осям координат. Однако для любого евклидового пространства фиксированной размерности существуют графы, которые не имеют в нём жадного вложения — если число n больше контактного числа пространства, граф K _{1,

n} не имеет жадного вложения .

Гиперболическое и сжатое вложения

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

Специальные классы графов

Деревья

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

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

Планарные графы

Нерешённые проблемы математики : Имеет ли любой полиэдральный граф плоское жадное вложение с выпуклыми гранями?

Пападимитру и Ратайджак высказали предположение, что любой полиэдральный граф ( вершинно 3-связный граф планарный граф , или, что эквивалентно, согласно теореме Штайница , граф выпуклого многогранника ) имеет жадное вложение в евклидову плоскость . Исследуя свойства графов-кактусов , Лейтон и Мойтра доказали гипотезу . Жадное вложение этих графов можно определить сжато, с логарифмическим количеством бит на координату . Однако жадное вложение, построенное согласно этому доказательству, не обязательно планарно и может содержать пересечения пар рёбер. Для максимальных планарных графов , в которых любая грань является треугольником, жадное планарное вложение может быть найдено с помощью применения к взвешенной версии алгоритма Шнайдера вложения с прямыми рёбрами . Строгая гипотеза Пападимитру — Ратайджака , что любой полиэдральный граф имеет планарное жадное вложение, в котором все грани выпуклы, остаётся недоказанной .

Графы единичных кругов

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

Примечания

, с. 96–108.
↑ , с. 3–14.
↑ , с. 1571–1580.
↑ , с. 1902–1909.
, с. 326–331.
, с. 171–182.
.
↑ , с. 686–705.
.
.
, с. 19–51.
, с. 781–791.
, с. 138–148.
, с. 375–392.
, с. 47–69.
, с. 1737–1745.

Литература

Christos H. Papadimitriou, David Ratajczak. On a conjecture related to geometric routing // . — 2005. — Т. 344 , вып. 1 . — doi : .
Martin Nöllenburg, Roman Prutkin, Ignaz Rutter. On self-approaching and increasing-chord drawings of 3-connected planar graphs // Journal of Computational Geometry. — 2016. — Т. 7 , вып. 1 . — doi : .

Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati. Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. — 2010. — Т. 5849. — (Lecture Notes in Computer Science). — doi : .
Patrizio Angelini, Fabrizio Frati, Luca Grilli. An algorithm to construct greedy drawings of triangulations // . — 2010. — Т. 14 , вып. 1 . — doi : .
Lei Cao, A. Strelzoff, J. Z. Sun. 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN 2009). — 2009. — doi : .
Raghavan Dhandapani. Greedy drawings of triangulations // . — 2010. — Т. 43 , вып. 2 . — doi : .
D. Eppstein, M. T. Goodrich. Succinct greedy geometric routing using hyperbolic geometry // . — 2011. — Т. 60 , вып. 11 . — doi : .
Michael T. Goodrich, Darren Strash. Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009, Proceedings. — Berlin: Springer, 2009. — Т. 5878. — (Lecture Notes in Computer Science). — doi : .
R. Flury, S.V. Pemmaraju, R. Wattenhofer. IEEE INFOCOM 2009. — 2009. — doi : .
R. Kleinberg. Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007). — 2007. — doi : .
Tom Leighton, Ankur Moitra. Some results on greedy embeddings in metric spaces // . — 2010. — Т. 44 , вып. 3 . — doi : .
Martin Nöllenburg, Roman Prutkin. Proc. 21st European Symposium on Algorithms (ESA 2013). — 2013.
Christos H. Papadimitriou, David Ratajczak. On a conjecture related to geometric routing // . — 2005. — Т. 344 , вып. 1 . — doi : .
Ananth Rao, Sylvia Ratnasamy, Christos H. Papadimitriou, Scott Shenker, Ion Stoica. Proc. 9th ACM Mobile Computing and Networking (MobiCom). — 2003. — doi : .
Walter Schnyder. Embedding planar graphs on the grid // Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990.