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

UptoLike

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

Рубрика:

52 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

ходится либо внутри одной из треугольных граней либо вне ее, как

на рис. 2.7, в. ■

аб в

Рис. 2.7

Следствие из формулы Эйлера. Плоский граф с числом вершин

n ≥ 3 имеет не более 3n – 6 ребер. Триангулированный граф с n вер-

шинами имеет 3n – 6 ребер.

Доказательство. Каждая грань графа ограничена не менее тремя

ребрами, а каждое ребро является границей не более двух граней,

тогда 3f ≤ 2 m. Но из (1) следует, что

2 = n – m + f ≤ n – m + 2m/3 ⇒ m ≤ 3n – 6. ■

Отметим, что для плоского графа со степенями граней не меньше

четырех имеет место оценка m ≤ 2n – 4.

Рассмотрим выпуклый многоугольник, ограниченный, например,

простым циклом С

. На рис. 2.8 представлены примеры его триангу-

ляции непересекающимися диагоналями.

Рис. 2.8

Эйлер получил, что количество вариантов триангуляции L

вы-

пуклого многоугольника с n вершинами (n > 3) его непересекающи-

мися диагоналями находится в последовательности Каталана [38]

1, 2, 5, 14, 42, 132, 429, ...,

где а

= 1, а

= (2 n)! / [n! (n + 1)!], n > 1, L

= а

n–2