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

UptoLike

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

Рубрика:

Глава 2. Плоские и планарные графы 53

Кэли установил, что числа Каталана перечисляют все плоские

корневые кубические деревья, которые порождает триангуляция

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

Формула (1) получена Эйлером в 1758 г. для связного выпуклого

многогранника в трехмерном пространстве с n вершинами, m ребра-

ми и f гранями. Выпуклый многогранник можно представить на сфе-

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

2 ребра не пересекаются в точках, отличных от вершины. Стерео-

графическая проекция такого графа является связным плоским гра-

фом [35]. Формула (1), отражающая фундаментальные свойства

трехмерного пространства, не связана с расстоянием и углами, она

стала основой для двух математических дисциплин – топологии и

теории графов [34]. Известно, что существует только 5 правильных

многогранников (пять Платоновых тел), плоские графы которых

изображены на рис. 2.9.

Тетраэдр Куб Октаэдр Икосаэдр Додекаэдр

(огонь) (земля) (воздух) (вода) (вселенная)

Рис. 2.9

Если на ребра планарного (или непланарного) графа нанести про-

извольное число вершин степени 2, то полученный граф останется

планарным (непланарным). Свойство планарности графа позволяет

упростить, например, изготовление электронных схем по технологии

напыления, создавать транспортные сети с минимальным числом

пересечений.

2.2. Эйлеровы графы

Можно ли нарисовать графы, изображенные на рис. 2.10, не от-

рывая карандаша от бумаги и не проходя по каждому ребру более

одного раза? Очевидно, что это можно сделать не для любого из

этих графов [1 – 4].