В распределенных вычислениях и теории геометрических графов жадное внедрение — это процесс присвоения координат узлам телекоммуникационной сети , позволяющий использовать жадную географическую маршрутизацию для маршрутизации сообщений внутри сети. Хотя жадное встраивание было предложено для использования в беспроводных сенсорных сетях , в которых узлы уже имеют позиции в физическом пространстве, эти существующие позиции могут отличаться от позиций, заданных им посредством жадного встраивания, которые в некоторых случаях могут быть точками в виртуальном пространстве. более высокого измерения или в неевклидовой геометрии . В этом смысле жадное встраивание можно рассматривать как форму рисования графа , при которой абстрактный граф (сеть связи) внедряется в геометрическое пространство.
Идея выполнения географической маршрутизации с использованием координат в виртуальном пространстве вместо использования физических координат принадлежит Рао и др. [1] Последующие разработки показали, что каждая сеть имеет жадное вложение с краткими координатами вершин в гиперболической плоскости , что некоторые графы, включая многогранные графы, имеют жадное вложение в евклидовой плоскости и что графы единичного диска имеют жадное вложение в евклидово пространство умеренные размеры с низким коэффициентом растяжения.
При жадной маршрутизации сообщение от узла-источника s к узлу назначения t перемещается к месту назначения, пройдя последовательность шагов через промежуточные узлы, каждый из которых передает сообщение соседнему узлу, который находится ближе к t . Если сообщение достигает промежуточного узла x , у которого нет соседа ближе к t , то оно не может продвигаться вперед, и процесс жадной маршрутизации завершается неудачно. Жадное вложение – это вложение заданного графа со свойством невозможности отказа данного типа. Таким образом, его можно охарактеризовать как вложение графа со свойством, что для каждых двух узлов x и t существует сосед y узла x такой, что d ( x , t ) > d ( y , t ), где d обозначает расстояние во встроенном пространстве. [2]
Не каждый граф имеет жадное вложение в евклидову плоскость ; простой контрпример даёт звезда K 1,6 , дерево с одним внутренним узлом и шестью листьями. [2] Всякий раз, когда этот граф вкладывается в плоскость, некоторые два его листа должны образовывать угол 60 градусов или меньше, из чего следует, что хотя бы один из этих двух листьев не имеет соседа, который находится ближе к другому. лист.
В евклидовых пространствах более высоких измерений большее количество графов может иметь жадные вложения; например, K 1,6 имеет жадное вложение в трехмерное евклидово пространство, в котором внутренний узел звезды находится в начале координат, а листья - на расстоянии единицы вдоль каждой оси координат. Однако для любого евклидова пространства фиксированной размерности существуют графы, которые не могут быть вложены жадно: всякий раз, когда число n больше числа поцелуев пространства, граф K 1, n не имеет жадного вложения. [3]
В отличие от случая с евклидовой плоскостью, каждая сеть имеет жадное вложение в гиперболическую плоскость . Первоначальное доказательство этого результата Робертом Кляйнбергом требовало указания положений узлов с высокой точностью [4] , но впоследствии было показано, что, используя декомпозицию тяжелых путей остовного дерева сети, можно представлять каждый узел кратко, используя только логарифмическое количество битов на точку. [3] Напротив, существуют графы, которые имеют жадные вложения в евклидову плоскость, но для которых любое такое вложение требует полиномиального числа бит для декартовых координат каждой точки. [5] [6]
Класс деревьев , допускающих жадные вложения в евклидову плоскость, полностью охарактеризован, и жадное вложение дерева может быть найдено за линейное время , когда оно существует. [7]
Для более общих графов некоторые жадные алгоритмы внедрения, такие как алгоритм Кляйнберга [4], начинают с поиска остовного дерева данного графа, а затем строят жадное вложение остовного дерева. Результатом также является жадное встраивание всего графа. Однако существуют графы, имеющие жадное вложение в евклидову плоскость, но для которых ни одно остовное дерево не имеет жадного вложения. [8]
Каждый ли многогранный граф имеет плоское жадное вложение с выпуклыми гранями?
Пападимитриу и Ратайчак (2005) предположили , что каждый многогранный граф ( планарный граф с 3-связными вершинами или, что то же самое, по теореме Стейница, график выпуклого многогранника ) имеет жадное вложение в евклидову плоскость. [2] Используя свойства кактусовых графов , Лейтон и Мойтра (2010) доказали гипотезу; [8] [9] жадные вложения этих графов могут быть определены кратко, с логарифмическим количеством битов на координату. [10] Однако жадные вложения, построенные в соответствии с этим доказательством, не обязательно являются плоскими вложениями, поскольку они могут включать в себя пересечения между парами ребер. Для максимальных планарных графов , в которых каждая грань представляет собой треугольник, жадное плоское вложение можно найти, применив лемму Кнастера – Куратовского – Мазуркевича к взвешенной версии алгоритма линейного вложения Шнайдера. [11] [12] Сильная гипотеза Пападимитриу–Ратайчака о том, что каждый многогранный граф имеет плоское жадное вложение, в котором все грани выпуклы, остается недоказанной. [13]
Беспроводные сенсорные сети, являющиеся целью жадных алгоритмов внедрения, часто моделируются как графы единичных дисков , графы, в которых каждый узел представлен как единичный диск , а каждое ребро соответствует паре дисков с непустым пересечением. Для этого специального класса графов можно найти краткие жадные вложения в евклидово пространство полилогарифмической размерности с дополнительным свойством, заключающимся в том, что расстояния в графе точно аппроксимируются расстояниями во вложении, так что пути, по которым следует жадная маршрутизация, равны короткий. [14]