Теория замощений. 
Геометрическая теория графов

Замощением плоскости называется разбиение плоскости на бесконечное число областей — элементов замощения, удовлетворяющее трем условиям:

• 1) Каждый элемент замощения является топологическим многоугольником.
• 2) Каждая точка плоскости принадлежит хотя бы одному многоугольнику.
• 3) Два многоугольника или имеют общую сторону, или имеют общую вершину, или вообще не имеют общих точек.

Менее строго, замощение плоскости — это покрытие плоскости многоугольными «плитками» без взаимных наложений и просветов.

Типичное представление о замощениях плоскости дают паркеты (см. пример на рис. 141). Существует бесконечное число способов замощения плоскости. Так,.

Рис. 141.

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

Кроме замощений плоскости, можно аналогично определить замощение любой поверхности. В этом случае граф замощения будет графом на этой поверхности. Например, при замощении сферы мы получим сферический граф. Отметим, что в отличие от плоского случая, замощение сферы содержит лишь конечное число элементов замощения. Заметим, что любой связный граф на сфере определяет некоторое замощение. Например, петля на сфере определяет сферическое замощение, состоящее из двух «одноугольников». Граф такого замощения состоит из одной вершины, одного ребра и двух граней.

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

Замощение называется однородным относительно вершин, если каждая вершина графа замощения имеет одну и ту же степень. Если рассмотреть граф, двойственный для графа замощения, однородного относительно вершин, то получим граф, каждая грань которого ограничена одним и тем же количеством ребер. Этому графу соответствует замощение, однородное относительно граней. Обратно, любому замощению, однородному относительно граней, соответствует двойственное замощение, однородное относительно вершин. Любое правильное замощение является однородным как относительно вершин, так и относительно граней.

Частным случаем однородных замощений являются так называемые полуправильные замощения. Замощение называется полуправилъным относительно вершин, если к каждой вершине графа замощения примыкает одинаковое количество однотипных граней (одинаковое количество треугольных граней, одинаковое количество четырехугольных граней и т. д.), и эти грани примыкают к каждой вершине в одном и том же порядке. Двойственным образом определяется полуправильное замощение

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

На рис. 142 приведен пример полуправильного замощения относительно вершин. Каждая вершина этого замощения имеет степень 5 (это замощение однородно относительно вершин), и к каждой вершине примыкают 2 четырехугольные и 3 треугольные грани. При этом грани, примыкающие к каждой вершине, следуют в одном и том же порядке: треугольная, треугольная, четырехугольная, треугольная, четырехугольная (3, 3,4, 3,4). На рис. 143 показан процесс построения двойственного замощения.

Рис. 142.

Рис. 143.

Рис. 144.

Это двойственное замощение (см. рис. 144) является полуправильным относительно граней. Оно состоит только из пятиугольных граней (это замощение однородно относительно граней), и к каждой его грани примыкают две вершины степени 4 и три вершины степени 3. При этом степени вершин, примыкающих к каждой грани, следуют в одном и том же порядке: третья, третья, четвертая, третья, четвертая (3, 3,4, 3,4).

На рис. 145 приведен пример замощения плоскости, однородного относительно вершин. Несмотря на то, что к каждой вершине этого замощения примыкает одинаковое количество однотипных граней (2 треугольные и 2 шестиугольные), тем не менее оно не является полуправильным, так как не сохраняется порядок следования граней. Например, в вершине А грани следуют в порядке (3,6,3,6), а в _{Рис J45}

вершине В — в порядке (3,3,6,6).

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