Маршрутизация в геометрических сетях: различия между версиями

Граф единичных дисков (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором две вершины <math>u, v \in V</math> соединены ребром e в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.

Модель с A-точностью /£?(1) или «цивилизованный граф» – это граф G = (V, E), вложенный в пространство <math>\mathcal{R}^2</math>, у которого для любого фиксированного A > 0 две вершины u, v 2 V находятся на расстоянии не менее A.

Граф Гэбриэла (Gabriel Graph, G G) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором для любых u, v 2 V ребро (u, v) 2 E в случае, если u и v – единственные вершины в V, принадлежащие к кругу диаметром (u, v) as diameter.