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

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

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

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

имеют жадное вложение в евклидовы пространства средних размерностей с низкими коэффициентами растяжения.

Определения

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

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

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

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

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

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

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

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

Деревья

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

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

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

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

плоское жадное вложение с выпуклыми гранями?

Пападимитру и Ратайджак

вложения с прямыми рёбрами^[13]^[14]. Строгая гипотеза Пападимитру — Ратайджака, что любой полиэдральный граф имеет планарное жадное вложение, в котором все грани выпуклы, остаётся недоказанной^[15]

.

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

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