Русская Википедия:Жадное вложение графа
В теории распределённых вычислений и в Шаблон:Не переведено 5 жадное вложение — это процесс назначения координат узлам коммуникационной сети, с целью использовать жадный алгоритм Шаблон:Не переведено 5 сообщений в сети. Хотя жадное вложение было предложено для использования в беспроводных сенсорных сетях, в которых узлы уже имеют определённое положение в физическом пространстве, эти координаты могут отличаться от координат, даваемых жадным алгоритмом, которые могут в некоторых случаях быть точками в виртуальном пространстве более высоких размерностей или в неевклидовом пространстве. В этом смысле жадное вложение можно рассматривать как форма визуализации графов, в котором абстрактный граф (коммуникационная сеть) вкладывается в геометрическое пространство.
Идея географической маршрутизации на основе координат в виртуальном пространстве вместо физических координат узлов принадлежит Рао (Rao) (с соавторами) Шаблон:Sfn. Исследования потом показали, что любая сеть имеет жадное вложение со сжатыми координатами в гиперболической плоскости, что некоторые графы, включая полиэдральные графы, имеют жадное вложение в евклидову плоскость, и что графы единичных кругов имеют жадное вложение в евклидовы пространства средних размерностей с низкими коэффициентами растяжения.
Определения
При жадной маршрутизации сообщение из передающего узла s в узел назначения t проходит за ряд шагов через промежуточные узлы, каждый их которых находится ближе всего к t. Если сообщение достигает промежуточного узла x, не имеющего более близкого соседа к t, то оно не может быть передано и жадная маршрутизация терпит неудачу. Жадное вложение — это вложение заданного графа, в котором потери сообщения такого типа невозможны. Таким образом, это вложение можно описать как вложение графа, при котором для любых двух узлов x и t существует сосед y узла x, для которого d(x,t) > d(y,t), где d обозначает расстояние в пространстве, в которое вкладывается графШаблон:Sfn.
Графы без жадного вложения
Не любой граф имеет жадное вложение в евклидовой плоскости. Простой контрпример — это звезда K1,6, дерево с одной внутренней вершиной и шестью листьямиШаблон:Sfn. Если вложить этот граф в плоскость, пара его листьев должна образовать угол в 60 градусов или меньше, откуда немедленно следует, что по меньшей мере один лист не имеет соседа, более близкого к другому листу из этой пары.
В евклидовых пространствах более высоких размерностей больше графов могут иметь жадное вложение. Так, K1,6 имеет жадное вложение в трёхмерном евклидовом пространстве — располагаем внутренний узел в начале координат, а остальные узлы (листья) располагаем на единичном расстоянии по осям координат. Однако для любого евклидового пространства фиксированной размерности существуют графы, которые не имеют в нём жадного вложения — если число n больше контактного числа пространства, граф K1,n не имеет жадного вложенияШаблон:Sfn.
Гиперболическое и сжатое вложения
В отличие от случая евклидовой плоскости, любая сеть имеет жадное вложение в гиперболическую плоскость. Первоначальное доказательство этого результата Шаблон:Не переведено 5 требовало задания положения точек с высокой точностьюШаблон:Sfn, но потом было показано, что при применении разложения остовного дерева сети на Шаблон:Не переведено 5 можно представить каждый узел сжато с использованием лишь логарифмического числа бит на точкуШаблон:Sfn. В качестве контраста существуют графы, допускающие жадное вложение в евклидову плоскость, но такое вложение требует полиномиального числа бит декартовых координат для каждой точкиШаблон:SfnШаблон:Sfn.
Специальные классы графов
Деревья
Класс деревьев, позволяющий жадное вложение в евклидово пространство, может быть полностью охарактеризирован, и жадное вложение дерева может быть найдено за линейное время, если таковое вложение существуетШаблон:Sfn.
Для более общих классов графов некоторые алгоритмы нахождения жадного вложения, как, например, алгоритм КлейнбергаШаблон:Sfn, начинают с поиска остовного дерева заданного графа, а затем строят жадное вложение этого остовного дерева. В результате, в обязательном порядке, получаем жадное вложение для всего графа. Тем не менее, существуют графы, имеющие жадное вложение в евклидову плоскость, но стягивающие деревья для этих графов жадного вложения не имеютШаблон:Sfn.
Планарные графы
Шаблон:Unsolved Пападимитру и РатайджакШаблон:Sfn высказали предположение, что любой полиэдральный граф (вершинно 3-связный граф планарный граф, или, что эквивалентно, согласно теореме Штайница, граф выпуклого многогранника) имеет жадное вложение в евклидову плоскостьШаблон:Sfn. Исследуя свойства графов-кактусов, Лейтон и МойтраШаблон:Sfn доказали гипотезуШаблон:SfnШаблон:Sfn. Жадное вложение этих графов можно определить сжато, с логарифмическим количеством бит на координатуШаблон:Sfn. Однако жадное вложение, построенное согласно этому доказательству, не обязательно планарно и может содержать пересечения пар рёбер. Для максимальных планарных графов, в которых любая грань является треугольником, жадное планарное вложение может быть найдено с помощью применения Шаблон:Не переведено 5 к взвешенной версии алгоритма Шнайдера вложения с прямыми рёбрамиШаблон:SfnШаблон:Sfn. Строгая гипотеза Пападимитру — Ратайджака, что любой полиэдральный граф имеет планарное жадное вложение, в котором все грани выпуклы, остаётся недоказаннойШаблон:Sfn.
Графы единичных кругов
Сети беспроводных датчиков, являющиеся целью алгоритмов жадного вложения, часто моделируются как графы единичных кругов, в которых каждый узел представлен единичным кругом, а каждое ребро соответствует паре кругов с непустым пересечением. Для этого специального класса графов можно найти сжатое жадное вложение в евклидово пространство полилогарифмической размерности с дополнительным свойством, что расстояния в графе аккуратно аппроксимируются расстояниями во вложении, так что пути, проложенные жадным маршрутом, являются короткимиШаблон:Sfn.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
Шаблон:Изолированная статья Шаблон:Rq
