Википедия

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

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

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

Определения править

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

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

 
Граф K1,6 не имеет жадного вложения в евклидовой плоскости

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

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

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

В отличие от случая евклидовой плоскости, любая сеть имеет жадное вложение в гиперболическую плоскость. Первоначальное доказательство этого результата Робертом Клайнбёргом[en] требовало задания положения точек с высокой точностью[4], но потом было показано, что при применении разложения остовного дерева сети на тяжёлые пути[en] можно представить каждый узел сжато с использованием лишь логарифмического числа бит на точку[3]. В качестве контраста существуют графы, допускающие жадное вложение в евклидову плоскость, но такое вложение требует полиномиального числа бит декартовых координат для каждой точки[5][6].

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

Деревья править

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

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

Планарные графы править

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

Пападимитру и Ратайджак[9] высказали предположение, что любой полиэдральный граф (вершинно 3-связный граф планарный граф, или, что эквивалентно, согласно теореме Штайница, граф выпуклого многогранника) имеет жадное вложение в евклидову плоскость[2]. Исследуя свойства графов-кактусов, Лейтон и Мойтра[10] доказали гипотезу[8][11]. Жадное вложение этих графов можно определить сжато, с логарифмическим количеством бит на координату[12]. Однако жадное вложение, построенное согласно этому доказательству, не обязательно планарно и может содержать пересечения пар рёбер. Для максимальных планарных графов, в которых любая грань является треугольником, жадное планарное вложение может быть найдено с помощью применения леммыа Кнастера – Куратовского – Мазуркевича[en] к взвешенной версии алгоритма Шнайдера вложения с прямыми рёбрами[13][14]. Строгая гипотеза Пападимитру — Ратайджака, что любой полиэдральный граф имеет планарное жадное вложение, в котором все грани выпуклы, остаётся недоказанной[15].

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

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

Примечания править

  1. ↑ Rao, Ratnasamy, и др., 2003, с. 96–108.
  2. ↑ 1 2 3 Papadimitriou, Ratajczak, 2005, с. 3–14.
  3. ↑ 1 2 Eppstein, Goodrich, 2011, с. 1571–1580.
  4. ↑ 1 2 Kleinberg, 2007, с. 1902–1909.
  5. ↑ Cao, Strelzoff, Sun, 2009, с. 326–331.
  6. ↑ Angelini, Di Battista, Frati, 2010, с. 171–182.
  7. ↑ Nöllenburg, Prutkin, 2013.
  8. ↑ 1 2 Leighton, Moitra, 2010, с. 686–705.
  9. ↑ Papadimitriou, Ratajczak, 2005.
  10. ↑ Leighton, Moitra, 2010.
  11. ↑ Angelini, Frati, Grilli, 2010, с. 19–51.
  12. ↑ Goodrich, Strash, 2009, с. 781–791.
  13. ↑ Schnyder, 1990, с. 138–148.
  14. ↑ Dhandapani, 2010, с. 375–392.
  15. ↑ Nöllenburg, Prutkin, Rutter, 2016, с. 47–69.
  16. ↑ Flury, Pemmaraju, Wattenhofer, 2009, с. 1737–1745.

Литература править

  • Christos H. Papadimitriou, David Ratajczak. On a conjecture related to geometric routing // Theoretical Computer Science. — 2005. — Т. 344, вып. 1. — doi:10.1016/j.tcs.2005.06.022.
  • 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:10.20382/jocg.v7i1a3.
  • 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:10.1007/978-3-642-11805-0_17.
  • Patrizio Angelini, Fabrizio Frati, Luca Grilli. An algorithm to construct greedy drawings of triangulations // Journal of Graph Algorithms and Applications. — 2010. — Т. 14, вып. 1. — doi:10.7155/jgaa.00197.
  • Lei Cao, A. Strelzoff, J. Z. Sun. 10th International Symposium on Pervasive Systems, Algorithms, and Networks (ISPAN 2009). — 2009. — doi:10.1109/I-SPAN.2009.20.
  • Raghavan Dhandapani. Greedy drawings of triangulations // Discrete and Computational Geometry. — 2010. — Т. 43, вып. 2. — doi:10.1007/s00454-009-9235-6.
  • D. Eppstein, M. T. Goodrich. Succinct greedy geometric routing using hyperbolic geometry // IEEE Transactions on Computers. — 2011. — Т. 60, вып. 11. — doi:10.1109/TC.2010.257.
  • 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:10.1007/978-3-642-10631-6_79.
  • R. Flury, S.V. Pemmaraju, R. Wattenhofer. IEEE INFOCOM 2009. — 2009. — doi:10.1109/INFCOM.2009.5062093.
  • R. Kleinberg. Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007). — 2007. — doi:10.1109/INFCOM.2007.221.
  • Tom Leighton, Ankur Moitra. Some results on greedy embeddings in metric spaces // Discrete and Computational Geometry. — 2010. — Т. 44, вып. 3. — doi:10.1007/s00454-009-9227-6.
  • 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 // Theoretical Computer Science. — 2005. — Т. 344, вып. 1. — doi:10.1016/j.tcs.2005.06.022.
  • Ananth Rao, Sylvia Ratnasamy, Christos H. Papadimitriou, Scott Shenker, Ion Stoica. Proc. 9th ACM Mobile Computing and Networking (MobiCom). — 2003. — doi:10.1145/938985.938996.
  • Walter Schnyder. Embedding planar graphs on the grid // Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA). — 1990.
Источник — https://ru.wikipedia.org/w/index.php?title=Жадное_вложение_графа&oldid=135549294