Граф Яо (Ijgs Xk)

Перейти к навигации Перейти к поиску

Граф Яо — вид геометрического остова, взвешенный неориентированный граф, соединяющий множество геометрических точек со свойством, что для любой пары точек в графе кратчайший путь между ними имеет длину не превосходящую на постоянный множитель их евклидова расстояния.

Назван в честь Эндрю Яо.

Основная идея построения двухмерного графа Яо заключается в окружении каждой точки равномерно распределёнными лучами, разбивая плоскость на сектора с равными углами, и соединении каждой точки с её ближайшими соседями в каждом из этих секторов[1]. С графом Яо связан целочисленный параметр , который равен числу лучей и секторов, описанных выше. Большее значение k даёт более точное приближение к евклидову расстоянию[2]. Коэффициент растяжения не превосходит , где равен углу секторов[3]. Та же идея может быть распространена на множества точек в размерностях, больших двух, но число требуемых секторов растёт экспоненциально с ростом размерности.

Эндрю Яо использовал эти графы, чтобы строить евклидовы минимальные остовные деревья в пространствах высокой размерности[3].

Программы рисования графов Яо

[править | править код]

Примечания

[править | править код]
  1. Overlay Networks for Wireless Systems. Дата обращения: 27 марта 2019. Архивировано 20 ноября 2021 года.
  2. Simple Topologies. Дата обращения: 27 марта 2019. Архивировано 20 ноября 2021 года.
  3. 1 2 Yao, 1982, с. 721–736.

Литература

[править | править код]