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

Упорядочение выпуклых полиэдров и алгоритм Е.С. Федорова Упорядочение в классах Рассмотрению подлежат п-акры, располагающиеся в таблице в столбцах (и дуальные п-эдрам, располагающимся в строках — таблица симметрична относительно главной диагонали). Для анализа мы располагаем всеми 4- ... 7-акрами [2, рис. 3; 7, fig. 3]. При упорядочении по min именам 6-акр (7916, ю = 0) следует за (7915, ю = 2). Упорядочение по max именам тоже не согласуется с ростом ю. Так, 6-акр (32531, ю = 2) следует за (31583, ю = 6) и (31582, ю = 4). С ростом ю интервалы имен перекрываются: ю = 0 [29327], ю = 2 [31571, 32531], ю = 4 [31582, 32681], ю = 6 [31583, 32754]. Аналогично, для 7-акров: ю = 1 [1984627, 1990799], ю = 3 [1990871, 2089235], ю = 5 [1993051, 2093699], ю = 7 [2057563, 2095881], ю = 9 [2057567, 2096914]. Но анализ реберных графов показывает, что при ю > 1 max имя п-акра зависит от того, какие валентности у его непростых вершин. При ю = 2 возможны варианты: ю = 2 — одна вершина валентности 5 (избыточны 2 валентности), ю = 1 + 1 — две вершины валентности 4 (в каждой избыточна 1 валентность). Оба реализуются среди 6-акров (по 1 полиэдру). При ю = 3 возможны: ю = 3, ю = 2 + 1, ю = 1 + 1 + 1. Они реализуются среди 7-акров: 1, 2 и 5 соответственно. По-видимому, все разложения любого ю > 1 реализуются в валентностях вершин п-акров для достаточно больших п. На рис. 1 и 2 показаны упорядочения 4 - . 7-акров по max именам с указанием разложений ю. Их анализ позволяет сформулировать утверждение: max избыточные валентности в разложениях ю образуют нестрогое упорядочение п-акров (при данном п), согласованное с их строгим упорядочением по max именам. Рис. 1. Упорядочение 4- ... 6-акров в классах по max именам и разложения ю в суммы избыточных валентностей вершин Доказательство. Пусть i1, i2, i3 — max избыточные валентности в разложениях юі, ю2, ю3 трех п-акров, причем i1 < i2< i3. Они характеризуют вершины с валентностями 3 + i1, 3 + i2, 3 + i3. Пронумеровав их № 1, а смежные — следующими числами натурального ряда, обеспечим в начале первых строк матриц смежности и, далее, в max именах то же число единиц [5, 6]. Следовательно, max имена находятся в том же соотношении, что и max избыточные валентности: max1< max2< max3. Выбор вершины с № 1 (если в разложении ю есть несколько max избыточных валентностей) и упорядочение п -акров с совпадающими разложениями ю определяются более тонкими особенностями их строения. Следствие: при упорядочении по max именам непростые и-акры (> 1) следуют за простыми (ю = 0). Это ясно из того, что в любом разложении ю > 1 max избыточная валентность > 1. Но из таблицы видно, что ю = 0, 2, 4 . реализуются только для п-акров с четными п . Поэтому формулировку можно усилить: при упорядочении по max именам непростые п-акры (ю > 2) следуют за простыми (ю = 0). ВЕСТНИК Кольского научного центра РАН 4/2016(27) 7