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