Полуправильные плоские графы

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

Ясно, что графы полуправильных замощений плоскости являются бесконечными полуправильными графами. Существуют и конечные полуправильные графы.

Более того, легко видеть, что три следующие задачи являются эквивалентными с точки зрения теории графов.

Задача 1. Найти все конечные полуправильные плоские графы.

Задача 2. Найти все топологически полуправильные замощения сферы.

Задача 3. Найти все топологически полуправильные многогранники. •.

Предположим, что задан некоторый конечный плоский граф G (V, E, F), полуправильный относительно вершин. Пусть к каждой вершине графа G примыкает т/ «/-угольных граней, m2 «2-угольных граней, …, nit и*- угольных граней. Ясно, что степень каждой вершины одинакова и равна «г = /и, + т₂ +. .+т_к.

Обозначим через / - количество «/-угольных граней в графе G и предположим, что /и, >т₂ >…>т_к, а если т_х = /и₂, то л, <�я₂, если т₂ =т₂, то п₂ <�п₂, …, если Щ-1 = Щ, то и*-, < п_к.

Так как граф G является однородным степени т, то 2е — mv. Выражая отсюда е и подставляя в формулу Эйлера, получим:

Мы знаем, что в любом конечном плоском графе из многоугольников существует вершина, степень которой меньше или равна пяти. Но так как в нашем случае степени всех вершин равны, то степень каждой вершины графа G меньше или равна пяти. Итак, к каждой вершине примыкает не более пяти граней.

Все л₍ -угольные грани имеют в общей сложности, с одной стороны, n_:f_l, с другой стороны, mv вершин степени т₍, так что «,/,=w, v. Отсюда имеем ряд уравнений.

Подставляя эти значения в очевидное равенство.

получим.

С использованием (2.5.14) равенство (2.5.11) примет вид:

Здесь m = m_i + т₂+…+т_к может принимать одно из значений — 3,4 или 5.

Полуправильные графы, у которых все грани имеют одинаковое число сторон, являются правильными (это рассмотренные выше графы правильных многогранников).

Поэтому при т = 3 мы должны рассмотреть графы с двумя типами граней (т₁ =2;т₂ = 1) или с тремя типами граней (/и, = т₂ = т_г — 1).

Пусть теперь т = 4 и граф имеет грани четырех различных типов (/и, = щ = щ = w₄ = 1; и, < п₂ < п_г < п_А). В таком случае уравнение (2.5.15) примет вид, но и, > 3; «₂ > 4; п_ъ >5; и₄ > 6, и потому.

2 19.

откуда 1 + — < —, что невозможно. Поэтому и при т — 4 v 20.

нам придется рассматривать граф с двумя (/и, = 3; т₂ =1 или /и,=/и₂=2) или с тремя (т_] — 2; т₂ = т_ъ = 1) типами граней.

Рассмотрим, наконец, последнюю возможность: т = 5. Если при этом граф имеет три, четыре или пять типов граней, то.

3 2 29.

и в силу (2.5.15) получаем —+ —<�—, что невозможно.

2 v 20.

Таким образом, при т — 5 придется рассматривать граф с двумя типами граней. Если при этом /и, = 3;т₂ = 2, то.

что невозможно. Поэтому при т = 5 достаточно рассмотреть случай двух типов граней, причем,.

m_t = 4; т₂ = 1.

Из сказанного выше следует, что определение всех типов графов, полуправильных относительно вершин, сводится к решению в натуральных числах уравнения

с неизвестными n_t, п₂ и v в следующих предположениях: а также уравнения с неизвестными п, п₂, п_} и v в следующих предположениях:

Определив из уравнения (2.5.16) значения n_t, n₂ и v, или из уравнения (2.5.17) значения и, и₂, и, и v, мы определим далее по формулам (2.5.12) значения // и /₂ или Д/г и Д, а по формулам (2.5.13) — значение/. После этого определим значение е по формуле 2е = mv. Решая поставленную задачу и отбрасывая целочисленные решения, не имеющие геометрической реализации, придем к следующей таблице возможных решений.

Каждой строке таблицы (за исключением восьмой строки) соответствует (для строк 1 и 7 для фиксированного и) единственный тип плоского графа, полуправильного относительно вершин. Строке 8* соответствует два типа таких графов. Ясно, что каждому полуправильному графу соответствует единственный топологически полуправильный многогранник. Таким образом, можно сформулировать следующий результат.

Теорема 25. Существует 16 типов конечных графов, полуправшьных относительно вершин, и 16 типов конечных графов, полуправильных относительно граней. Столько же существует полуправильных многогранников и полуправильных замощений сферы.

Изображения полуправильных многогранников можно найти например в [23) или [24]. Мы приведем ниже лишь геометрические реализации полуправильных графов (в виде прямолинейных графов) и укажем соответствующие названия полуправильных многогранников. При этом на каждом из рисунков 176(1)—176(15) изображен граф, полуправильный относительно вершин, который представляет соответствующую строку таблицы.

Рис. 176(5) Рис. 176(6)

Граф п-угольной антипризмы (п=4) Граф ромбокубооктаэдра

Граф икосододекаэдра Граф «курносого» куба

Рис. 176(86) Рис. 176(9)

Рис. 176(12)

Г раф усеченного кубооктаэдра

Рис. 176 (13)

Рис. (14)

Г раф ромбоикосододекаэдра

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

Если теперь построить графы, двойственные для графов, изображенных на рис. 176(1)-176 (15), то получим 16 графов, полу правильных относительно граней. В силу теоремы Фари эти графы также допускают геометрическую реализацию в виде прямолинейных графов. На рис. 177(1) — 177(15) построены прямолинейные графы, двойственные лля 176 111−176 1151 соответственно.

Рис. 177(1) Рис. 177(2)

Рис. 177(3)

Рис. 177(4)

Рис. 177(5) ^Рис— ¹⁷⁷'(б).

Рис. 177(7) Рис. 177 (8а)

Рис. 177(86)

Рис. 177(9)

Рис. 177(10) Рис. 177(11)

Рис. 177(12)

Рис. 177(13)

Рис. 177(15)

Рис. 177(14)