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