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

'''Планарный граф'''. Граф G = (V, E) является ''[[Планарный_граф|планарным]]'', если вершины V могут быть ''[[Embedding_of_a_graph|вложены]]'' в двумерное евклидово пространство R2, т. е. каждая вершина из V получает уникальные координаты, а ребра между каждой парой вершин из E изображаются таким образом, что они не пересекают друг друга в R2.

Граф единичных дисков (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в R2, в котором две вершины u, v 2 V соединены ребром (u, v) 2 E в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.

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

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

Триангуляция Делоне Л множества вершин V, вложенных в R2, представляет собой геометрическую двойственную конструкцию для диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в A, если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне A является единичной, если длина ребер в ней не превышает 1.