Правильная карта (теория графов)

Правильная карта — это симметричное замощение замкнутой поверхности. Более точно, правильная карта — это разложение[англ.] двумерного многообразия (такого как сфера, тор или вещественная проективная плоскость) на топологические диски, так что каждый флаг (инцидентная тройка вершина-ребро-грань) может быть переведён в любой другой флаг преобразованием симметрии разложения. Правильные карты являются в некотором смысле топологическим обобщением правильных многогранников. Теория карт и их классификация связана с теориями римановых поверхностей, геометрии Лобачевского и теории Галуа. Правильные карты классифицируются по их роду ориентируемости соответствующей поверхности, по основному графу или автоморфизму группы.

Шестиугольный осоэдр, правильная карта на сфере с двумя вершинами, шестью рёбрами, шестью гранями и 24 флагами.

Правильные карты обычно определяются и изучаются тремя способами: топологически, с точки зрения теории групп и теории графов.

Топологический подход

править

С точки зрения топологии карта является 2-ячейным разложением замкнутого компактного 2-многообразия.

Род g карты M задаётся соотношением Эйлера  , что равно  , если карта ориентируема, и  , если карта неориентируема. Критическим обстоятельством является факт, что имеется конечное (ненулевое) число правильных карт для любого ориентируемого рода, за исключением тора.

Подход теории групп

править

С точки зрения теории групп перестановки представления правильной карты M являются транзитивной группой перестановок C на множестве   флагов, порождённой свободными инволюциями с тремя фиксированными точками  , удовлетворяющими условию  . В этом определении гранями являются орбиты  , рёбрами являются орбиты  , а вершинами являются орбиты  . Более абстрактно, автоморфизм группы любой правильной карты является невырожденным гомоморфным образом группы треугольника <2,m,n>.

Подход теории графов

править

С точки зрения теории графов карта есть кубический граф   с рёбрами, выкрашенными в синий, жёлтый и красный цвета так, что   связен, каждая вершина инцидентна с рёбрами каждого цвета, а циклы рёбер, не окрашенных в жёлтый цвет, имеют длину 4. Заметим, что   является плоским графом или закодированной графом картой[англ.] (англ. graph-encoded map, GEM) карты, определёнными на множестве флагов в качестве вершин   и не являющимися остовом G=(V,E) карты. В общем случае  .

Карта M правильна тогда и только тогда, когда Aut(M) действует регулярно на флаги. Aut(M) правильной карты транзитивна на вершинах, рёбрах и гранях карты M. Говорят, что карта M зеркально симметрична в том и только в том случае, когда Aut(M) правильна и содержит автоморфизм  , который фиксирует как вершиныv, так и грани f, но обращает направление рёбер. Говорят, что правильная карта, не являющаяся зеркально симметричной, хиральна.

Примеры

править
 
Полукуб, правильная карта.
  • Большой додекаэдр является правильной картой с пятиугольными гранями на ориентируемой поверхности рода 4.
  • Полукуб[англ.] является правильной картой типа {4,3} на проективной плоскости.
  • Полудодекаэдр является правильной картой, порождённой пятиугольным вложением графа Петерсена в проективную плоскость.
  • p-Осоэдр является правильной картой типа {2,p}. Заметим, что осоэдры в этом смысле не являются абстрактными многогранниками. В частности, они не удовлетворяют свойству алмаза (англ. diamond property).
  • Карта Дика является правильной картой из 12 октаэдров на поверхности рода 3. Лежащий в её основе граф Дика, может также образовать правильную карту из 16 шестиугольников на торе.

В таблице ниже приведён полный список правильных карт на поверхностях с положительной эйлеровой характеристикой, χ — сфере и проективной плоскости[1].

χ g Шлефли Вершин Рёбер Граней Группа Порядок Граф Примечания
2 0 {p,2} p p 2 C2 × Dihp 4p Cp   Диэдр
2 0 {2,p} 2 p p C2 × Dihp 4p p-кратный K2 Осоэдр
2 0 {3,3} 4 6 4 S4 24 K4   Тетраэдр
2 0 {4,3} 8 12 6 C2 × S4 48 K4 × K2   Куб
2 0 {3,4} 6 12 8 C2 × S4 48 K2,2,2   Октаэдр
2 0 {5,3} 20 30 12 C2 × A5 120   Додекаэдр
2 0 {3,5} 12 30 20 C2 × A5 120 K6 × K2   Икосаэдр
1 n1 {2p,2}/2 p p 1 Dih2p 4p Cp   Полудиэдр[2]
1 n1 {2,2p}/2 2 p p Dih2p 4p p-кратный K2 Полуосоэдр[2]
1 n1 {4,3}/2 4 6 3 S4 24 K4   Полукуб[англ.]
1 n1 {3,4}/2 3 6 4 S4 24 2-кратный K3 Полуоктаэдр[англ.]
1 n1 {5,3}/2 10 15 6 A5 60 Граф Петерсена   Полудодекаэдр
1 n1 {3,5}/2 6 15 10 A5 60 K6   Полуикосаэдр

Изображения ниже показывают три из 20 правильных карт в тройном торе[англ.] с их символами Шлефли.

Тороидальные многогранники

править
Примеры в виде мозаики
 
{4,4}1,0
(v:1, e:2, f:1)
 
{4,4}1,1
(v:2, e:4, f:2)
 
{4,4}2,0
(v:4, e:8, f:4)
 
{4,4}2,1
(v:5, e:10, f:5)
 
{4,4}2,2
(v:8, e:16, f:8)
 
{3,6}1,0
(v:1, e:3, f:2)
 
{3,6}1,1
(v:3, e:9, f:6)
 
{3,6}2,0
(v:4, e:8, f:8)
 
{3,6}2,1
(v:7, e:21, f:14)
 
{3,6}2,2
(v:12, e:36, f:24)
 
{6,3}1,0
(v:2, e:3, f:1)
 
{6,3}1,1
(v:6, e:9, f:3)
 
{6,3}2,0
(v:8, e:8, f:4)
 
{6,3}2,1
(v:14, e:21, f:7)
 
{6,3}2,2
(v:24, e:36, f:12)

Правильные карты существуют как тороидальные многогранники в виде конечных порций евклидовых мозаик, завёрнутых в поверхность дуоцилиндра[англ.] как плоского тора. Они помечены как {4,4}b,c, когда они связаны с квадратной мозаикой {4,4}[3], как  , когда они связаны с треугольной мозаикой {3,6}, и как {6,3}b,c, когда связаны с шестиугольной мозаикой {6,3}. Индексы b и c являются целыми числами [4]. Имеется 2 специальных случая (b,0) и (b,b) с зеркальной симметрией, хотя общие случаи существуют в хиральных парах (b,c) и (c,b).

Правильные карты вида {4,4}m,0 могут быть представлены как конечные правильные косые многогранники {4,4|m}, понимаемые как квадратные грани m×m дуопризмы в размерности 4.

Ниже приведён пример {4,4}8,0, отображённый из плоского листа в виде шахматной доски в цилиндр, а затем в тор. Проекция из цилиндра в тор искажает геометрию в трёхмерном пространстве, но может быть осуществлена без искажения в четырёхмерном.

 
 
Например, карту {6,4}3 можно рассматривать как {6,4}4,0.
Правильные карты с нулевой эйлеровой характеристикой[5]
χ g Шлефли Вершин Рёбер Граней Группа Порядок Примечания
0 1 {4,4}b,0
n=b2
n 2n n [4,4](b,0) 8n Плоский тороидальный многогранник
То же, что и {4,4 | b}
0 1 {4,4}b,b
n=2b2
n 2n n [4,4](b,b) 8n Плоский тороидальный многогранник
То же, что и полноусечённый {4,4 | b}
0 1 {4,4}b,c
n=b2+c2
n 2n n [4,4]+
(b,c)
4n Плоский хиральный тороидальный многогранник
0 1 {3,6}b,0
t=b2
t 3t 2t [3,6](b,0) 12t Плоский тороидальный многогранник
0 1 {3,6}b,b
t=2b2
t 3t 2t [3,6](b,b) 12t Плоский тороидальный многогранник
0 1 {3,6}b,c
t=b2+bc+c2
t 3t 2t [3,6]+
(b,c)
6t Плоский хиральный тороидальный многогранник
0 1 {6,3}b,0
t=b2
2t 3t t [3,6](b,0) 12t Плоский тороидальный многогранник
0 1 {6,3}b,b
t=2b2
2t 3t t [3,6](b,b) 12t Плоский тороидальный многогранник
0 1 {6,3}b,c
t=b2+bc+c2
2t 3t t [3,6]+
(b,c)
6t Плоский хиральный тороидальный многогранник

В общем случае правильный тороидальный многогранник {p,q}b,c можно определить, если p или q чётные, хотя только один евклидов выше может существовать как тороидальный многогранник в размерности 4. В случае {2p,q} пути (b,c) можно определить как грань-ребро-грань на прямой, в то время как в двойственных {p,2q} формах пути (b,c) можно рассматривать как вершина-ребро-вершина.

См. также

править

Примечания

править
  1. Coxeter, Moser, 1980.
  2. 1 2 Carlo Séquin. Symmetrical immersions of low-genus non-orientable regular maps. Berkeley University. Дата обращения: 5 марта 2020. Архивировано 23 сентября 2015 года.
  3. Coxeter, Moser, 1980, с. 8.3 Maps of type {4,4} on a torus.
  4. Coxeter, Moser, 1980, с. 8.4 Maps of type {3,6} on a torus.
  5. Coxeter, Moser, 1980, с. Chapter 8, Regular maps, 8.3 Maps of type {4,4} on a torus, 8.4 Maps of type {3,6} or {6,3} on a torus.

Литература

править
  • Coxeter H. S. M., Moser W. O. J. . — 4th. — Springer Verlag, 1980. — Т. 14. — (Ergebnisse der Mathematik und ihrer Grenzgebiete). — ISBN 978-0-387-09212-6. Перевод:
    • Г.С.М. Коксетер, У.О.Дж. Мозер. Порождающие элементы и определяющие соотношения дискретных групп / Перевод В.А. Чуркина, под редакцией Ю.И. Мерзлякова.. — Москва: «Наука» Главная редакция физико-математической литературы, 1980.
  • Jack van Wijk. Symmetric tiling of closed surfaces: visualization of regular maps // Proc. SIGGRAPH (ACM Transactions on Graphics). — 2009. — Т. 28, вып. 3. — С. 12. — doi:10.1145/1531326.1531355. Архивировано 9 июня 2011 года.
  • Marston Conder, Peter Dobcsányi. Determination of all regular maps of small genus // Journal of Combinatorial Theory, Series B. — 2001. — Т. 81, вып. 2. — С. 224—242. — doi:10.1006/jctb.2000.2008.
  • Roman Nedela. Maps, Hypermaps, and Related Topics. — 2007.
  • Andrew Vince. Maps // Handbook of Graph Theory. — 2004.
  • Ulrich Brehm, Egon Schulte. Polyhedral Maps // Handbook of Discrete and Computational Geometry. — 2004.