Вестник Кольского научного центра РАН. 2016, №4.

Ю. Л. Войтеховский перестановками строк и столбцов матрицы смежности. Выбор имени зависит от решаемой задачи и того, насколько позволяет развить теорию. Доказано, что с ростом n при любом выборе имен классы n-акров строго (без перекрытий) упорядочены на числовой прямой. В этой статье исследуются упорядочение n-акров внутри класса (при данном n) и его связь с алгоритмом Е. С. Фёдорова генерирования комбинаторного многообразия выпуклых полиэдров [7-9]. Алгоритм Е. С. Фёдорова Алгоритм Е. С. Фёдорова состоит из трех процедур отсечения (а — простой вершины, в — ребра, соединяющего две простые вершины, у — двух ребер, последовательно соединяющих три простые вершины) и процедуры ю редукции ребра. Отсечения применяются только к простым полиэдрам: а порождает 3-угольную, в — 4-угольную, у — 5-угольную грани, вместе реализуя известную теорему: не выпуклом полиэдре одновременно не могут отсутствовать 3-, 4- и 5­ угольные грани. Редукция ю важна в связи с дальнейшим. Она состоит в стягивании ребра в точку (вершину), если при этом не уничтожается ни одна из контактирующих по нему граней. Она может применяться несколько раз, порождая непростые полиэдры 1-го, 2-го и т. д. порядков с тем же числом граней. Результаты компьютерного генерирования комбинаторного многообразия выпуклых полиэдров с помощью алгоритма Е. С. Фёдорова даны в таблице. Сегодня известны все 4- ... 12- эдры и простые 13- ... 16-эдры. Числа простых полиэдров для каждого F стоят в рядах справа: Ѵп = 2F - 4. (Равенство легко получить, решая совместно уравнения: 3 V = 2E и F - E+V = 2, где Е — число ребер). Каждая редукция ю уменьшает V на 1. Поэтому число редукций, нужных для получения полиэдра из некоторого простого с тем же F, равно: ю = Ѵп - V = 2F - V- 4. Для простого полиэдра ю = 0. Максимальное значение ю для данного F равно: ютах = F + [F/2] - 6, где [ . ] — целая часть числа. В эквивалентной форме: ютах = 3F/2 - 6 для четных^ ютах = 3F/2 - 6.5 для нечетных F. Используя ю, конкретизируем задачу: исследовать согласование упорядочений n-акров внутри класса (при данном n) по именам и по ю. Числа комбинаторно различных полиэдров с F -гранями и V-вершинами IF, 4 5 6 7 8 9 10 11 12 13 14 15 16 4 1 5 1 1 6 1 2 2 2 7 2 8 11 8 5 8 2 11 42 74 76 38 14 9 8 74 296 633 768 558 219 50 10 5 76 633 2635 6134 8822 7916 4442 1404 233 11 38 768 6134 25626 64439 104213 112082 79773 36528 12 14 558 8822 64439 268394 709302 1263032 1556952 1338853 IF, 17 18 19 20 22 24 26 28 11 9714 1249 12 789749 306470 70454 7595 13 49566 14 339722 15 2406841 16 17490241 6 http://www.kolasc.net.ru/russian/news/vestnik1.html