Изометрические полиэдральные подграфы в гиперкубах и кубических решетках

М.Деза, В.П.Гришухин, М.И.Штогрин

Изометрические
полиэдральные подграфы
в гиперкубахи кубических
решетках

Перевод с английского
Н.А.Шиховой
Электронное издание

Москва
Издательство МЦНМО
2014

УДК 519.1
ББК 22.176
Д26

Деза М., Гришухин В. П., Штогрин М. И.
Изометрические полиэдральные подграфы в гиперкубах
и кубических решетках
Перевод с английского
Электронное издание
М.: МЦНМО, 2014
379 с.
ISBN 978-5-4439-2070-2

Предмет этой монографии есть идентификация полиэдральных графов, которые могут быть вложены в некоторый гиперкуб
или кубическую решетку так, что графическое расстояние соответствует квадрату евклидова расстояния. Рассматриваются различные обобщения правильных многогранников (включая некоторые
4-многогранники) и разбиений пространства, а также многогранников, возникающих в химических приложениях. Книга может
служить справочником по таким многогранникам.
Книга развивает материал, изложенный в ранее опубликованной монографии М. Деза и М. Лоран «Геометрия разрезов и
метрик» (М.: МЦНМО, 2001)

Подготовлено на основе книги: Деза М., Гришухин В. П., Штогрин М. И.
Изометрические полиэдральные подграфы в гиперкубах и кубических решетках / Перевод с англ. Н. А. Шиховой. — М.: МЦНМО, 2008. — 192 с.

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)241–74–83.
http://www.mccme.ru

ISBN 978-5-4439-2070-2
c⃝ М. Деза, В. П. Гришухин, М. И. Штогрин, 2008.
c⃝ МЦНМО, 2014.

Оглавление

Введение
7

Глава 1
Введение. Графы и их изометрические вложения
со шкалой
9
1.1. Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2. Вложения графов . . . . . . . . . . . . . . . . . . . . . . . .
11
1.3. Вложения плоских графов . . . . . . . . . . . . . . . . . . .
19
1.4. Типы регулярности многогранников и паркетов . . . . . . .
25
1.5. Операции на многогранниках
. . . . . . . . . . . . . . . . .
28
1.6. Разбиения Вороного и Делоне . . . . . . . . . . . . . . . . .
30
1.7. Бесконечные графы . . . . . . . . . . . . . . . . . . . . . . .
31

Глава 2
Пример: вложение фуллеренов
36
2.1. Вложимость фуллеренов и двойственных им
полиэдров . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.2. Бесконечные семейства ℓ1-невложимых фуллеренов
. . . .
41
2.3. Модель Кацуры для пузырьковых клеток . . . . . . . . . .
43

Глава 3
Правильные паркеты и соты
45
3.1. Правильные паркеты и соты . . . . . . . . . . . . . . . . . .
45
3.2. Планарный случай . . . . . . . . . . . . . . . . . . . . . . . .
46
3.3. Звездные соты . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.4. Случай размерности d ⩾ 3 . . . . . . . . . . . . . . . . . . .
51

Глава 4
Полуправильные полиэдры и многогранники,
родственные призмам и антипризмам
55
4.1. Полуправильные полиэдры . . . . . . . . . . . . . . . . . . .
55
4.2. Московский граф, графы глобуса и паутины
. . . . . . . .
59

Оглавление
5

4.3. Звездные k-угольники, куполы и антипаутины . . . . . . .
61
4.4. Каппингованные антипризмы и колонки из антипризм
. .
63

Глава 5
Усечение, каппинг и шамферинг
66
5.1. Усечения правильных разбиений
. . . . . . . . . . . . . . .
66
5.2. Частичные усечения и каппинги платоновых тел . . . . . .
68
5.3. Шамферинг платоновых тел . . . . . . . . . . . . . . . . . .
72

Глава 6
92 правильногранных полиэдра (не полуправильных)
76

Глава 7
Полуправильные и правильногранные n-многогранники
(n ⩾ 4)
83
7.1. Полуправильные (но не правильные) n-многогранники
. .
83
7.2. Правильногранные n-многогранники (но не полуправильные) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
7.3. Архимедовы 4-многогранники . . . . . . . . . . . . . . . . .
84
7.4. Вложимость снаб-24-ячейки . . . . . . . . . . . . . . . . . .
86

Глава 8
Полициклы и другие графы, имеющие химические
приложения
87
8.1. (r, q)-полициклы . . . . . . . . . . . . . . . . . . . . . . . . .
87
8.2. Квази-(r, 3)-полициклы . . . . . . . . . . . . . . . . . . . . .
90
8.3. Координационные полиэдры и металлополиэдры . . . . . .
92

Глава 9
Плоские паркеты
96
9.1. 58 вложимых мозаик
. . . . . . . . . . . . . . . . . . . . . .
96
9.2. Другие специальные плоские паркеты
. . . . . . . . . . . . 107
9.3. Правильногранные двугранные плоские паркеты . . . . . . 110

Глава 10
Однородные разбиения 3-пространства
и родственные им
112
10.1. 28 однородных разбиений . . . . . . . . . . . . . . . . . . . 113
10.2. Другие специальные разбиения . . . . . . . . . . . . . . . . 116

Глава 11
Решетки, бирешетки и паркеты
121
11.1. Неприводимые решетки корней . . . . . . . . . . . . . . . . 121
11.2. Случай размерности 3 . . . . . . . . . . . . . . . . . . . . . 122

Оглавление

11.3. Дайсинги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
11.4. Паркетины решетчатых разбиений . . . . . . . . . . . . . . 125

Глава 12
Малые полиэдры
130
12.1. Полиэдры, у которых не больше семи граней
. . . . . . . 130
12.2. Простые полиэдры, у которых не больше восьми
граней . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Глава 13
Полиэдры с двумя типами граней
134
13.1. Медиальные полиэдры Гольдберга . . . . . . . . . . . . . . 137
13.2. Правильногранные полиэдры с двумя типами граней . . . 140
13.3. Операции над полиэдрами с двумя типами граней
. . . . 143
13.4. Полиэдры 3n и 4n . . . . . . . . . . . . . . . . . . . . . . . . 144
13.5. Еще раз о полиэдрах 5n (фуллеренах) . . . . . . . . . . . . 149
13.6. Полиэдры ocn (октаэдриты) . . . . . . . . . . . . . . . . . . 150

Глава 14
Специальные ℓ1-графы
153
14.1. Эквиразрезные ℓ1-графы
. . . . . . . . . . . . . . . . . . . 153
14.2. Вложения со шкалой один . . . . . . . . . . . . . . . . . . . 162

Глава 15
Некоторые обобщения ℓ1-вложимости
171
15.1. Квазивложения . . . . . . . . . . . . . . . . . . . . . . . . . 171
15.2. Липшицево вложение
. . . . . . . . . . . . . . . . . . . . . 175
15.3. Полиэдральные гиперметрики
. . . . . . . . . . . . . . . . 175
15.4. Симплициальные n-многообразия . . . . . . . . . . . . . . 178

Литература
180

Предметный указатель
188

Введение

Эта монография служит продолжением книги М.Деза и М.Лоран
«Геометрия разрезов и метрик», опубликованной в 1997 году издательством Springer-Verlag, Берлин (русский перевод появился в 2001 году,
издательство МЦНМО, Москва). Предметом изучения той книги были
ℓ1-метрики, то есть такие метрики, которые изометрически вложимы
со шкалой в некоторый гиперкуб Hm, а если они бесконечны — то
в некоторую кубическую решетку Zm. За последние шесть лет большой успех был достигнут в изучении специального случая ℓ1-метрики:
расстояния на графе остова многогранника (конечного или бесконечного).
Эта монография посвящена в основном выяснению вопроса, являются ли такие многогранники комбинаторно ℓ1-вложимыми для
интересных примеров графов многогранников. Это такие графы, что
соответствующие им многогранники либо хорошо известны в математике (регулярные разбиения, решетки корней, правильные многогранники и т. д.), либо имеют химические приложения (фуллерены,
полициклы и т. п.). Вложимость, если она имеет место, применима
к химическим графам и приводит к новым комбинаторным перспективам для аффинных многогранных объектов с известным ℓ2-вложением.
Примеры графов многогранников в этой книге возникли из самых
разных областей геометрии, кристаллографии и теории графов. Только для того, чтобы ввести их, требуется много определений. В книге
уделяется особое внимание таким точным и по возможности независимым определениям. Изометрическая вложимость со шкалой —
главный вопрос, объединяющий их; все изученные примеры графов
рассматривались с этой точки зрения. Эта вложимость будет представлена с минимальными техническими подробностями.
Основные семейства рассмотренных графов возникли из разнообразных обобщений правильных многогранников (или паркетов), из
(точечных) решеток и из химических приложений.

Введение

В частности, были получены такие результаты:

1. Все вложимые правильные паркеты и соты размерностей d > 2,
за исключением гипер-симплексов и гипер-октаэдров, — это в точности такие разбиения и соты, у которых двудольный остов:
гиперкубы, кубические решетки и 11 специального вида паркетов
в гиперболическом пространстве.
2. Если P — архимедов полиэдр или плоское разбиение, отличное от
треугольной призмы, тогда в точности один из двух — либо P,
либо двойственный к нему — вложим.
3. Для правильного 4-мерного многогранника 24-ячейки его обыкновенное и золотое усечение (полуправильный 4-многогранник

Госсета) вложены в куб H12 и полукуб 1

2H12, соответственно.
4. Остовы паркета Вороного для решетки An и двойственной ей
решетки A∗
n вложимы в Zn+1 и Z(
n+1
2 ), соответственно.

Книга организована следующим образом.
В довольно длинном введении (глава 1) приведены основные обозначения, а также методы вложений. Ознакомившись с ним, остальные главы можно читать в независимом порядке.
Главы 14 и 15 рассматривают соответственно частные случаи
и обобщения понятия вложимости. Каждая из глав 2—15 посвящена вложимости определенных видов графов. Мы попытались дать
точное и по возможности независимое описание этих видов; так что
у читателей с различной подготовкой будет возможность читать по
отдельности те главы, предмет которых им знаком и которые им
интересны.
Главы 2, 4, 5, 6, 12, 13 имеют дело с разными видами трехмерных
многогранников. В главах 9, 10 и 11 рассматриваются бесконечные
графы, к которым приводят паркеты R2, R3 и решетки. В главах 3,
7, 11 рассматриваются графы в Rn. И наконец, главы 2, 8 и 11 могут быть интересны для тех, кто работает в области математической
химии и кристаллографии.
Авторы благодарны Марии Гриндель, Жаку Бейгбедеру и в особенности Матьё Дютуру за разнообразную помощь по созданию иллюстраций и редактированию, а также за поддержку.

Глава 1

Введение. Графы и их изометрические
вложения со шкалой

В этой главе мы введем некоторые основные определения, относящиеся к графам, вложениям и многогранникам. Здесь мы представим
только базовые понятия, дальнейшие определения будут приведены
позднее. За более детальной информацией читатель может обратиться
к книгам [Gr¨un67], [Coxe73], [CoSl88], [DeLa97], [Crom97].

1.1. Графы

Простой граф G = (V , E) состоит из множества V вершин и
множества E ребер. Каждое ребро e ∈ E представляет собой пару вершин u и v, которые мы называем его концами, при этом мы полагаем
e = (u, v). Такие две вершины называются смежными, и каждая из
них инцидентна ребру e. Степень вершины v ∈ V — это число ребер,
содержащих v.
Если любые две вершины G смежны, то такой граф называется
полным. Полный граф с n вершинами обозначается Kn. Если у графа
нет ребер, то он называется пустым. Для U ⊆ V обозначим EU
множество ребер, оба конца которых принадлежат U. Тогда граф
GU := (U, EU) называется подграфом графа G, индуцированным U.
Граф G называется двудольным, если его вершины можно разбить на две непустые части,

V = V1 ∪ V2,

таким образом, что оба графа, индуцированные V1 и V2, пусты.
Если граф G — двудольный с биразбиением (V1, V2) и если каждая
вершина V1 смежна каждой вершине V2, то G называется полным
двудольным графом. Обозначим Km,n полный двудольный граф, если
|V1| = n и |V2| = m. Полный двудольный граф K1,m (m ⩾ 1) называется звездой.
Множество E′ ребер называется паросочетанием, если ни у какой
пары ребер из E′ нет общих вершин. Паросочетание называется совершенным, если каждая вершина является концом этого паросочетания.
(Только у графов с четным числом вершин могут быть совершенные
паросочетания.)

Глава 1. Введение. Графы и их изометрические вложения

В этой книге мы часто будем использовать такие графы:

Многодольный граф Kn1,n2,...,nk, множество вершин которого можно
разбить на k частей, состоящих из n1, n2, . . . , nk вершин соответственно, причем концы каждого ребра принадлежат разным частям. Примером может служить полный двудольный граф Km,n
(k = 2).

Путь Pn = P{v1,v2,...,vn} с множеством вершин V = {v1, v2, . . . , vn}
и с ребрами (vi, vi+1) при 1 ⩽ i ⩽ n − 1.

Цикл Cn = C{v1,v2,...,vn} (или n-угольник) получается из пути Pn =
= P{v1,v2,...,vn} добавлением ребра (v1, vn).

Граф гиперкуба Hn с множеством вершин
V = {0, 1}n, ребра которого — пары векторов (x1, . . . , xn) и (y1, . . . , yn) из {0, 1}n такие,
что |{i : xi ̸= yi}| = 1.

Граф полукуба (1/2)Hn с множеством вершин

V =
(x1, . . . , xn) ∈ {0, 1}n :

n
i=1
xi четна
(в четных представлениях, и n
i=1 xi нечетна в нечетных преставлениях), ребра которого — это такие пары x, y ∈ {0, 1}n, что
|{i : xi ̸= yi}| = 2.

Граф кубической решетки Zn — бесконечный граф с множеством вершин
Zn = {(x1, x2, . . . , xn): xi ∈ Z}
и с ребрами ((x1, . . . , xn), (y1, . . . , yn)) такими, что
1⩽i⩽n
|xi − yi| = 1.

Граф полукубической решетки 1

2Zn — бесконечный граф с множеством вершин

V =
(x1, . . . , xn) ∈ Zn :

n
i=1
xi четна
,

ребра которого — это пары векторов x, y ∈ V такие, что
1⩽i⩽n
|xi − yi| = 2.

(У графа 1

2Zn то же самое множество вершин, что и у решетки
корней Dn; см. гл.11).

Граф вечеринки Kn×2 получается из полного графа K2n удалением
ребер совершенного паросочетания.

1.2. Вложения графов
11

Имеются изоморфизмы среди таких графов:

K2,2 = C4 = H2 = K2×2,
K2 = P2 = 1

2H2,

1
2H3 = K4,
1
2H4 = K3×2.

В обозначениях Коксетера αn, βn, γn и 1

2γn обозначают соответственно следующие n-мерные выпуклые многогранники: правильный
n-симплекс, n-ортаэдр, n-куб и n-полукуб. Им соответствуют графы
1-остовов (см. раздел 1.4 ниже) Kn+1, Kn×2, Hn и 1

2Hn.
Граф G называется связным, если для любых двух вершин u, v
из G имеется путь в G, связывающий u и v. Если это не так, то граф
называется несвязным.
Пусть заданы два графа

G1 = (V1, E1)
и
G2 = (V2, E2).

Их прямым произведением G1 ×G2 называется граф G := (V1 ×V2, E)
с множеством вершин

V1 × V2 = {(v1, v2) : v1 ∈ V1 и v2 ∈ V2},

ребра которого — это пары ((u1, u2), (v1, v2)), где u1, v1 ∈ V1 и u2, v2 ∈
∈ V2, так что либо (u1, v1) ∈ E1 и u2 = v2 либо (u2, v2) ∈ E2 и u1 = v1.
Надстройкой
▽G графа G называется граф, полученный из G
добавлением новой вершины (называемой отмеченной точкой ▽G),
соединенной со всеми вершинами G. Графы ▽Cn и Cn × K2 называются n-колесом и n-призмой, соответственно.
Реберным графом L(G) графа G называется граф, вершинами
которого служат ребра графа G. Причем две вершины L(G) смежны
в L(G), если у соответствующих ребер в G есть общая вершина.
Для L(Kn) мы используем обозначение T (n). Этот граф представляет
собой специальный случай графа Джонсона J(n, k), соответствующий k = 2. Множеством вершин графа Джонсона J(n, k) служит
семейство всех k-элементных подмножеств множества из n элементов.
Две вершины графа J(n, k) смежны, если и только если мощность
пересечения соответствующих k-элементных подмножеств равна k−1.
В частности, J(n, 1) = Kn.

1.2. Вложения графов

Прежде чем напомнить некоторые понятия метрик, связанных
с графами, мы коротко обсудим важность такого вложения. Граф G
может быть изометрически вложен в полукуб 1

2Hm, если мы можем

Глава 1. Введение. Графы и их изометрические вложения

пометить или занумеровать вершины G строками длины m из нулей
и единиц с четным числом единиц так, что квадрат евклидового
расстояния между двумя такими строками вдвое больше длины пути,
соединяющего вершины в графе G.
Кроме того, вложение называется ℓ1-жестким, если такой способ
нумерации единственный. Такое помечивание вершин может быть
очень полезно в химии для перечисления фуллеренов (см. гл.2), а также для вычисления молекулярных параметров, зависящих только от
расстояний в графах, таких как индексы Винера J и другие (см.,
например, [BLKBSSR95]).
Полуметрикой на множестве V называется действительная симметрическая функция d(x, y), определенная на всех парах точек
x, y ∈ V , удовлетворяющая уравнению d(x, x) = 0, а для всех упорядоченных троек (x, y, z) точек множества V — следующему неравенству треугольника:

d(x, y) + d(y, z) − d(x, z) ⩾ 0.

Просуммировав два таких неравенства для троек (x, y, z) и (x, z, y),
мы получим неравенство 2d(y, z) ⩾ 0. Следовательно, любая полуметрика d неотрицательна, то есть принимает только неотрицательные значения. Метрикой называется положительная полуметрика,
то есть такая, что d(x, y) = 0, если и только если x = y.
Пусть G = (V , E) — связный граф (конечный или нет), а V и E —
множества его вершин и ребер, соответственно. Определим метрику
кратчайшего пути dG, ассоциированную с графом G, как метрику с
целыми значениями на парах вершин графа G, такую, что для двух
вершин v и u величина dG(v, u) равна длине кратчайшего пути в G,
соединяющего v и u, где длина пути измеряется числом его ребер.
Сумма всех n(n−1)/2 расстояний между вершинами n-вершинного графа G обозначается W(G). Химики называют его числом Винера.
Связный подграф G1 графа G называется изометрическим подграфом G, если dG = dG1 на вершинах G1, то есть если расстояния
из G сохраняются в G1. В таком случае записывают G1 ≺ G.
Геодезической в G называется простой путь P (возможно, бесконечный в одном или двух направлениях), обладающий тем свойством,
что dP (x, y) = dG(x, y) для всех x, y ∈ P. Длина максимальной
геодезической в G называется его диаметром d(G).
Метрика dG позволяет нам ввести выпуклые подмножества на V.
Подмножество S ⊆ V называется выпуклым подмножеством, если для
любых вершин u, v ∈ S все вершины каждого кратчайшего (u, v)-пути
(то есть геодизической соединяющей u и v) принадлежат S.

1.2. Вложения графов
13

Множество Zn естественным образом снабжено ℓ1-метрикой. А
именно, для x = (x1, . . . , xn) и y = (y1, . . . , yn) из Zn, ℓ1-расстояние
между x и y выражается как

d(x, y) =

n
i=1
|xi − yi|.

Zn — это граф множества Zn, метрика кратчайшего пути которого
совпадает с ℓ1-метрикой d. Аналогично, граф гиперкуба Hn — это подграф Zn, индуцированный {0, 1}n. (Метрика кратчайшего пути dHn
является также квадратом евклидовой l2-метрики.)
ℓ1-граф — это такой граф G, метрика кратчайшего пути dG которого с точностью до шкалы λ изометрически вложима в гиперкуб Hm,
или, если G бесконечен, — в Zm. Другими словами, для некоторых
λ, m ∈ N существует отображение φ: V → Hm или Zm такое, что

λ · dG(vi, vj) = ∥φ(vi) − φ(vj)∥ℓ1 =

m
k=1
|φk(vi) − φk(vj)|,

где vi ∈ V и φ(vi) = (φ1(vi), . . . , φm(vi)) ∈ Hm или Zm. Наименьшее
целое λ называется минимальной шкалой вложения.
Например, граф полукуба 1

2Hn и граф полукубической решетки
естественно вкладываются соответственно в Hn и Zn со шкалой λ = 2.
Следовательно, 1

2Hn и 1

2Zn суть ℓ1-графы.
Напомним, что 2m вершин m-куба Hm можно пометить с помощью всех 2m подмножеств множества {1, 2 . . . , m}, так что две
вершины с метками A и B смежны, если и только если |A△B| = 1,
где A△B — симметрическая разность множеств A и B. Следовательно,
существование вложения φ : V
→ Hm со шкалой λ эквивалентно
помечиванию каждой вершины v ∈ V (G) с помощью множества φ(v)
таким образом, что вершины v и u смежны, если и только если
|φ(v)△φ(u)| = λ. С другой стороны, такой способ помечивания порождает помечивание ребер (v, u) с помощью множеств φ(v)△φ(u). Для
i ∈ {1, 2, . . . , m} назовем i-зоной или просто зоной множество ребер,
метки которых содержат i. Оба такие помечивания вершин и ребер G
используются, например, в рисунках гл.2.
Если G вложен в гиперкуб, то любое разбиение Hm на противоположные фасеты порождает разбиение S ∪S = V множества вершин G.
Такое разбиение S ∪ S = V называется разрезом {S, S}. Множество
ребер E(S, S) разреза {S, S} состоит из ребер, один конец которых
принадлежит S, а другой — S. Очевидно, что удалив E(S, S) из G,
мы получим граф по крайней мере с двумя связными компонентами;

Глава 1. Введение. Графы и их изометрические вложения

другими словами, E(S, S) — разрезное множество ребер. Ребра множества E(S, S) разрезаны разрезом {S, S}.
Разрез {S, S} определяет разрезную полуметрику δ(S) на множестве V :

δ(S)(i, j) = δ{S,S}(i, j) =

0,
если i, j ∈ S или i, j ∈ S,

1
в противном случае.

Спроектируем гиперкуб Hm с вложенным графом G вдоль ребер, соединяющих две противоположные фасеты. Тогда мы получим
вложение G в Hm−1, причем некоторые расстояния из G уменьшатся
на единицу. Другими словами, мы вкладываем G с новой полуметрикой dG − δ(S).
Таким образом мы получаем разложение метрики кратчайшего
пути dG некоторого ℓ1-вложимого графа G (на самом деле, любой
ℓ1-метрики) в неотрицательную линейную комбинацию разрезных полуметрик.
Все ℓ1-полуметрики на n вершинах (т. е. все ℓ1-полуметрические пространства (Vn, d), для которых |Vn| = n), рассматриваемые

как точки некоторого
n
2

-мерного пространства, образуют
n
2

-мер
ный конус, который называется разрезным конусом. Он порождается
2n−1−1 крайними лучами. Каждый такой луч — это ненулевая разрезная полуметрика δ(S) для некоторого собственного подмножества S
множества Vn = {1, 2, . . . , n}.
Другими словами, граф G (или произвольная метрика) ℓ1-вложим, если и только если метрика кратчайшего пути является линейной комбинацией с неотрицательными коэффициентами разрезных
полуметрик

dG =
S⊂Vn
aSδ(S),
где aS ⩾ 0 для всех S.

Если G вложим в Hm со шкалой λ, то тогда описанное выше
разложение можно переписать следующим образом:

λdG =
S⊂Vn
aSδ(S),
где aS ⩾ 0 целые для всех S.
(1.1)

У формулы (1.1) есть то преимущество, что она позволяет классифицировать ℓ1-вложения G с точностью до эквивалентности: разные
решения (1.1) с целыми неотрицательными aS такими, что

НОД(λ, aS) = 1,