Графы правильных многогранников

Теория графов позволяет решать задачи из традиционных разделов математики, например, исследовать некоторые свойства правильных многогранников. При этом, используя элементы теории графов, многогранники могут быть рассмотрены с точки зрения, отличной от традиционной. Изображение фигур при этом могут стать более простыми и наглядными.

Правильные многогранники (платоновы тела) – это выпуклые многогранники, гранями которых являются правильные плоские фигуры. Всего существует пять правильных многогранников: тетраэдр, куб, октаэдр, икосаэдр, додекаэдр. Гранями тетраэдра, октаэдра и икосаэдра являются правильные треугольники, гранями куба – правильный четырёхугольник (квадрат). Гранями додекаэдра есть правильные пятиугольники. Других платоновых тел не существует.

Вместо объёмных изображений правильных многогранников можно использовать их плоские изображения (графы). Графы правильных многогранников внешне напоминают сами многогранники. Их можно рассматривать, как проэкции объёмных тел на плоскость, проходящую через произвольную грань. Из рисунка видно, что графы всех правильных многогранников являются симметрическими, связными и плоскими. Они не содержат самопересечений рёбер, кроме пересечений в вершинах. Эйлерова характеристика каждого из этих графов равна 2.

Графы правильных многогранников содержат циклы. Их количество можно подсчитать, используя формулу цикломатического числа: . Цикломатическое число – это количество независимых циклов на графе. Оно указывает на число рёбер, которые нужно удалить, чтобы граф стал нециклическим (деревом).

Особый интерес представляют задачи, связанные с отысканием на графах циклов различных видов. Гамильтонов цикл – это цикл, проходящий через каждую вершину по одному разу. Эйлеров цикл – это цикл, проходящий через каждое ребро по одному разу (существует не для всякого графа).