Русская Википедия:Перестановочный многогранник

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Symmetric group 4; permutohedron 3D; l-e factorial numbers.svg
Перестановочный многогранник порядка 4

Перестановочный многогранник (или пермутоэдр) порядка <math>n</math> — это (<math>n-1</math>)-мерный выпуклый многогранник, вложенный в <math>n</math>-мерное евклидово пространство, который является выпуклой оболочкой <math>n!</math> точек, получающихся перестановками координат вектора <math>(1, 2, 3,\ldots,n)</math>.

История

Согласно Циглер, Гюнтер[1], перестановочный многогранник впервые появляется в работах Шутэ в 1911 году. Сам термин «перестановочный многогранник» (точнее, его французский вариант «permutoèdre») впервые появился в статье Гуибуда (G.-T.Guibaud) и Розенштэхл, Пьер в 1963 году. Предлагая его, авторы писали, что «permutoèdre» выглядит варварски, но легко запоминается и что они оставляют использование этого термина на усмотрение читателя.

Близким понятием является многогранник Биркгофа, определяемый как выпуклая оболочка матриц перестановок. В более общей ситуации Боуман (V.-J.Bowman) в 1972 году использовал термин «перестановочный многогранник» («permutation polytope») для любого многогранника, вершины которого находятся во взаимно однозначном соответствии с перестановками некоторого множества.

Свойства

  • Перестановочный многогранник порядка n имеет n! вершин, каждая из которых соединена с n − 1 другими вершинами, так что общее число рёбер равно (n − 1)n!/2.
  • Каждое ребро имеет длину √2 и соединяет две вершины, получающиеся друг из друга перестановкой двух координат при условии, что значения этих координат различаются на единицу.[2]
  • Перестановочный многогранник имеет одну гипергрань для каждого непустого собственного подмножества S множества {1, 2, 3, …, n}, состоящую из всех вершин, у которых все координаты с номерами, вошедшими в S, имеют меньшие значения, чем все координаты с номерами, не вошедшими в S. Отсюда следует, что общее число гиперграней равно 2n − 2.
  • Перестановочный многогранник является вершинно-транзитивным, а именно: симметрическая группа Sn действует на множестве вершин перестановочного многогранника посредством перестановок координат.
  • Неориентированный граф, образованный вершинами и рёбрами перестановочного многогранника, изоморфен графу Кэли симметрической группы.[1]

Замощение пространства

Файл:Bitruncated cubic honeycomb2.png
Замощение пространства перестановочными многогранниками

Перестановочный многогранник порядка n полностью содержится в (n − 1)-мерной гиперплоскости, состоящей из всех точек, сумма координат которых равна

1 + 2 + … + n = n(n + 1)/2.

Более того, эта гиперплоскость может быть замощенаШаблон:Ref-en бесконечным количеством параллельных копий перестановочного многогранника. Каждая из этих копий отличается от исходного перестановочного многогранника на элемент некоторой (n − 1)-мерной решётки, образованной n-мерными векторами, все координаты которых целочисленные, их сумма равна нулю, причём все координаты принадлежат одному классу вычетов по модулю n:

x1 + x2 + … + xn = 0,     x1 ≡ x2 ≡ … ≡ xn (mod n).

Например, перестановочный многогранник порядка 4, изображённый на рисунке, замощает 3-мерное пространство посредством параллельных переносов. Здесь 3-мерное пространство рассматривается как аффинное подпространство 4-мерноего пространства R4 с координатами x, y, z, w, которое образовано четвёрками вещественных чисел, сумма которых равна 10, то есть

x + y + z + w = 10.

Легко проверить, что для каждого из следующих четырёх векторов

(1,1,1,−3), (1,1,−3,1), (1,−3,1,1) и (−3,1,1,1),

сумма координат равна нулю и все координаты сравнимы с 1 по модулю 4. Любые три из этих векторов порождают решётку параллельных переносов.

Замощения, построенные таким способом из перестановочных многогранников порядка 3 и 4, являются замощением правильными шестиугольниками и замощением усечёнными октаэдрамиШаблон:Ref-en соответственно.

Галерея

Порядок 2 Порядок 3 Порядок 4
2 вершины 6 вершин 24 вершины
Файл:Permutohedron order 2.svg Файл:Permutohedron order 3.svg Файл:Symmetric group 4; permutohedron 3D; l-e factorial numbers.svg
Перестановочный многогранник порядка 2 — это отрезок на диагонали единичного квадрата. Перестановочный многогранник порядка 3 — это правильный шестиугольник, являющийся сечением 2×2×2 куба. Перестановочный многогранник порядка 4 — это усечённый октаэдр.
Порядок 5 Порядок 6
120 вершин 720 вершин
Файл:Omnitruncated 5Cell as Permutohedron.svg Файл:Omnitruncated Hexateron as Permutohedron.svg
Перестановочный многогранник порядка 5. Перестановочный многогранник порядка 6.

Замечания

Шаблон:Reflist

Литература

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Günter M. Ziegler, `Lectures on Polytopes', Springer-Verlag, 1995.
  2. ↑ P.Gaiha and S. K.Gupta, `Adjacent vertices on a permutohedron', SIAM Journal on Applied Mathematics, Vol. 32, issue 2, P. 323—327 (1977).
  3. ↑ Günter M. Ziegler, `Lectures on Polytopes', Springer-Verlag, 1995. P. 200.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Перестановочный_многогранник&oldid=10577863