Математическое моделирование на графах. Часть 1. Берцун В.Н. - 70 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

70 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
и для координат вершин ячейки V(i) получим
,
22
bc
xy
aa
−
==
.
Рассмотрим теперь граф, двойственный диаграмме Вороного, т.е.
граф, уложенный на плоскости и получаемый в результате соедине-
ния отрезками каждой пары
точек множества S, много-
угольники Вороного которых
имеют общее ребро. В резуль-
тате получается граф с верши-
нами в n точках множества S,
как это показано на рис. 2.26.
Делоне показал, что граф,
двойственный диаграмме Во-
роного, является триангуляци-
ей множества S.
Утверждение 2.8. Диаграм-
ма Вороного множества из n
точек имеет не более 2n – 5
вершин и 3n – 6 ребер.
Доказательство. Каждому ребру графа, двойственного диа-
грамме Вороного, соответствует единственное ребро диаграммы.
Двойственный граф является триангуляцией, а значит, планарным
графом с n вершинами. В соответствии с формулой Эйлера он имеет
не более 3n – 6 ребер и 2n – 4 граней. Следовательно, диаграмма Во-
роного имеет не более 3n – 6 ребер. Однако лишь ограниченные гра-
ни (их не более 2n – 5) соответствуют вершинам этой диаграммы
при отображении двойственности. ■
Диаграмма Вороного является регулярным графом (все ее верши-
ны имеют одну и ту же степень) со степенью вершин, равной трем.
Любой многоугольник Вороного может иметь до n – 1 ребер, но
полное число ребер не превосходит 3n – 6, при этом каждое ребро
принадлежит в точности двум многоугольникам. Это значит,
что среднее число ребер многоугольника Вороного не превосходит
шести.
Рис. 2.26

Страницы