ИССЛЕДОВАНИЕ КОМБИНАТОРНОЙ СТРУКТУРЫ КЛАССОВ ДЕФОРМИРОВАННЫХ МНОГОГРАННИКОВ

АННОТАЦИЯ

В статье исследовано комбинаторной структуры классов деформированных многогранников. Так как выпуклый многогранник является фундаментальным объектом математики и привлекает постоянный интерес исследователей. Причиной тому является практическая и теоретическая роль, которую играют выпуклые многогранники: многие природные образования и технологические изделия имеют форму выпуклого многогранника (минералы, предметы быта, детали машин и т.д.); множества всех решений системы линейных неравенств является выпуклым многогранником [1]; выпуклие тела аппроксимируются выпуклыми многогранниками.

ABSTRACT

The article investigates the combinatorial structure of classes of deformed polyhedrons. Since a convex polyhedron is a fundamental object of mathematics and attracts constant interest of researchers. The reason for this is the practical and theoretical role played by convex polyhedrons: many natural formations and technological products have the form of a convex polyhedron (minerals, household items, machine parts, etc.); the set of all solutions of a system of linear inequalities is a convex polyhedron [1]; the convexity of a body is approximated by convex polyhedrons.

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

Keywords: research, combinatorial structure of classes of deformed polyhedra.

ВВЕДЕНИЕ

Евклид свою XIII книгу посвятил пяти правильным многогранникам (платоновым телам) : куб, тетраэдр, октаэдр, додекаэдр, икосаэдр.

Первым результатом комбинаторной теории выпуклых многогранников можно считать результат принадлежащий Эйлеру, т.е. формула

где  - соответственно число вершин, ребер и граней многогранника.

В работе [2], Штейниц обобщил теорему Эйлера, т.е. доказал, что

вектор  является f-вектором выпуклого многогранника тогда и только тогда, когда целые неотрицательные числа  удовлетворяет следующим условиям

На основе исследование фигур, образованных вершинами и ребрами некоторого трехмерного многогранника, возникла теория графов [1] .

Фундаментальным здесь является другая теорема Штейница [2]. Она утверждает, что граф изоморфен графу некоторого выпуклого многогранника тогда и только тогда, когда он планарен и трехсвязен.

Многогранник задается как выпуклая оболочка своих вершин. С другой стороны теорема Вейля-Минковского [3,4] показывает, что всякий выпуклый многогранник в определенной системе координат может быть задан с помощью системы, состоящей из конечного числа линейных неравенств.

Геометрическими исследованиями кристаллографа Федорова Е.С. возник класс задач о многогранниках - задачи о распределении целых точек в многогранниках. Классические теоремы Г. Минковского и Л. Кронекера дают критерии существования целой точки в выпуклом теле, симметричном относительно начала координат.

А.Д. Александровым [5] были завершены исследования в метрической теории многогранников. Известная теорема утверждает, что если известны угловые параметры и площади всех граней многогранника, то многогранник однозначно определяется. Также доказана следующая теорема Коши о жесткости выпуклых многогранников: пусть Р и Р-комбинаторно эквивалентные выпуклые многогранники, у которых соответствующие элементы-ребра и плоские углы равны.

Тогда многогранники равны. В частности, соответствующие двугранные углы многогранников Р и Р равны.

Эффективным является характеризуя выпуклых тел посредством выпуклых многогранников. Это связано с тем, что многогранники характеризуются конечным числом данных. В работе [6] доказано, что для 0,001 всякое выпуклое подмножества единичного шара n-мерного евклидова пространства можно с точностью Е приблизить многогранником, число вершин которого не больше, чем  .

Над перечислением всех комбинаторно неэквивалентных многогранников с n вершинами работали Эйлер, Я. Штейниц [7], А.К.Кэли [8], В работе [9], дается следующее асимптотическое число выпуклых многогранников с n вершинами

≈

где

Аналогичный результат справедлив для асимптотического числа выпуклых многогранников с р гранями.

В работе [10] разработан алгоритм для перечисления комбинаторно неэквивалентных многогранников с n вершинами.

Настоящая работа посвящена следующим задачам.

1. Исследованию меры комбинаторной неустойчивости выпуклых многогранников к изменениям его различных метрических параметров (деформации многогранников). Естественным является рассмотрение следующих типов деформаций многогранников:

1) Выпуклый многогранник задается системой линейных неравенств.

Изменениям подвергаются положения (четверки параметров) плоскостей граней многогранника. Например, изменяются лишь линейные параметры граней многогранника.

2.  Выпуклый многогранник задается выпуклой оболочкой своих вершин. Изменениям подвергается положения (тройки координат) вершин многогранника.

Основная цель работы - изучение комбинаторной структуры классов деформированных многогранников, разработка алгоритмов перечисления таких классов.

Сравнительно анализируются различные типы деформаций. Изучается класс М(n,p) всех комбинаторно неэквивалентных многогранников с n вершинами и p гранями как класс деформированных многогранников. Описаны способы построения всех комбинаторно неэквивалентных многогранников, порожденных от исходного многогранника при определенных деформациях.

Отметим, что классы деформированных многогранников использованы в некоторых работах при решении задачи определения параметров выпуклых многогранников по их Р-проекции (лазерных рефлектограмм).

Основные сведения и определения

Пусть некоторый 3-многогранник М с n вершинами задан следующей системой линейных неравенств,

                                   (1)

где нормаль i-ой грани, определяющая угловые параметры i-ой грани, расстояние от начало координат до i-ой плоскости – линейный параметр i-ой грани, i=[11-15].

 Неравенство, которое можно выбросить из системы (1), не изменив при этом многогранника, называется избыточным неравенством [1]. Геометрически избыточное неравенство определяет плоскость  

которая либо не имеет общих точек с многогранником М, либо несмотря на то, что имеет, не является опорной плоскостью, определяющей некоторую грань многогранника [11-15].

Предположим, что система (1) не имеет избыточных неравенств.

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

ОПРЕДЕЛЕНИЕ. Изменение линейных и угловых параметров граней многогранника М, при котором порождается непустое ограниченное множества (т.е. многогранник) и никакое неравенство системы, соответствующего этим изменениям, не является избыточным, называется линейно-угловой ограниченной деформацией (ЛУОД).

Таким образом, деформации типа ЛОД и ЛУОД не приводят к исчезновению граней многогранника М. Отметим, что поскольку совокупность решений любой (конечной и бесконечной) системы линейных неравенств либо выпуклое, либо пустое множество (если система несовместна) то ЛОД и ЛУОД не порождают невыпуклые многогранники.

ОПРЕДЕЛЕНИЕ. Линейно-угловая ограниченная деформация многогранника М, при которой сохраняются смежности граней по ребру, называется ограниченной деформацией (ОД).

 По определению ОД является частным случаем ЛУОД. Тем самым ОД также как ЛУОД не приводит к исчезновению граней многогранника и не порождает невыпуклых многогранников.

Напомним понятия комбинаторной эквивалентности и двойственности многогранников.

Пусть  и  - матрицы смежности граней (вершин) многогранников  и . Если при некоторых пере нумерациях граней (вершин) многогранника  и  соответствующие матрицы  и совпадают, то многогранники  и  называются комбинаторно эквивалентными, иначе – комбинаторно неэквивалентными.

Если матрица смежности граней многогранника при некоторых пере нумерация его граней совпадает с матрицей смежности вершин многогранника  и наоборот, если матрица смежности граней многогранника  при некоторых пере нумерациях его граней равняется матрице смежности вершин многогранника , то многогранники и называются двойственными, иначе - не двойственными.

Пусть некоторый 3-многогранник , заданный координатами вершин в сферической системе координат, двойственен к многограннику М, заданному системой (1) и начало координат является внутренней точкой многогранника . То есть i-ая вершина многогранника  задана координатами  и , где - полярный радиус, - широта, - долгота вершины,  Далее для удобства широту и долготу вершины условно будем называть угловыми параметрами вершины. Известно [1], что выпуклая оболочка точек  из  является многогранником с р вершинами, то будем говорить, что существует р вершинная выпуклая оболочка точек .

ОПРЕДЕЛЕНИЕ. Изменение лишь полярных радиусов многогранника , при котором существует р вершинная выпуклая оболочка порожденных вершин (точек) и начало системы координат является внутренней точкой, называется полярно-ограниченной деформацией (ПОД).

ОПРЕДЕЛЕНИЕ. Изменение полярных радиусов и угловых параметров вершин многогранника , при котором существует р вершинная выпуклая оболочка порожденных вершин, называется полярно-угловой ограниченной деформацией (ПУОД).

ОПРЕДЕЛЕНИЕ. Полярно-угловая ограниченная деформация многогранник , при которой сохраняются смежности вершин по ребру, называется сферически ограниченной деформацией (СОД).

Далее, когда речь идет о смежности вершин и граней, будем понимать смежность по ребру.

Предположим, что граням многогранника М и вершинам многогранника  приписаны номера 1,2,3,…….р.

Введем некоторые обозначения:

def – любая из деформаций типа ЛОД,ЛУОД,ОД если речь идет о многогранника М, заданном системой (1); любая из деформаций типа ПОД, ПУОД, СОД если речь идет о многограннике ;

М(,def) – класс всех комбинаторно неэквивалентных многогранников, порожденных от произвольного фиксированного многогранника М, посредством деформации def.;

В, l=- вершины многогранника М;

Г, l=-грани многогранника ;

N(l) – множество номеров граней многогранника М, инцидентных вершине

В, l=;

 - множество номеров граней многогранника М, инцидентных грани

Г, l=;

M - t-угольная пирамида, t<∞.

Также предположим, что

а) грани любого многогранника ММ(М,def) пронумерованы так, что i-ая грань многогранника М образована изменением параметров i-ой грани многогранника М, i=1,p.

б) вершины любого многогранника ММ(М,def) пронумерованы так,  что i-ая вершина многогранника М образована изменением параметров i-ой вершины многогранника М, i=1,p.

Пусть В – вершина многогранника ММ(М,def). Если множество номеров граней многогранника М инцидентных к вершине В является подмножеством множества N(l), то будем говорить, что вершина В многогранника М порождена деформацией def от вершине В многогранника М.

Пусть Г – грань многогранника ММ(М,def) . Если множество номеров вершин многогранника М инцидентных грани Г является подмножеством множества N(l), то будем говорить, что грань Г многогранника М порождена деформацией def от грани Г многогранника М.

Пусть V и V - множества вершин порожденные некоторой деформацией от вершин B и B многогранника М , соответственно. Множества V и V имеют общие вершины если хотя бы для одного элемента v V найдется элемент vV такой, что N=N,иначе – не имеют общие вершины, где Nи N - множества номеров граней порожденного многогранника инцидентных вершинам v и v, соответственно.

Пусть G и G - множества граней порожденные не которой деформацией от граней Г и Г многогранника М.

Множества G и G имеют общие грани, если хотя бы для одного элемента g Gнайдется элемент g G такой, что N=N, иначе – не имеют общие грани, где N и N - множества номеров вершин порожденного многогранника инцидентных грани g и g, соответственно.

При определение ОД и СОД требуется сохранение смежности граней многогранника М и сохранение смежности вершин многогранника М, соответственно. Отметим, что сохранение смежности граней (вершин) многогранника М (М) не влечет за собой сохранение комбинаторного типа многогранника М (М), так как при многогранника некоторых ОД (СОД) вершины (грани) многогранника М (М) могут порождать вершины ( грани).

ОПРЕДЕЛЕНИЕ. Многогранник, порожденный от пирамиды М некоторой деформацией типа ЛОД или ОД, называется обобщенным клином.

Пусть М задан в сферической системе координат и 0 М( начало координат – внутренняя точка многогранника М).

ОПРЕДЕЛЕНИЕ. Многогранник, порожденный от пирамиды Мнекоторой деформацией типа ПОД и СОД называется ломанной пирамидой.

Очевидно, что исходная пирамида М является частным случаем обобщенного клина, также ломанной пирамиды.

Пусть def и def некоторые деформации.

ОПРЕДЕЛЕНИЕ. Если для любого многогранника  в классе  существует двойственный многогранник и наоборот, для любого многогранника  в классе  существует двойственный многогранник, то многогранники М и М называются двойственными относительно деформаций def и def- иначе – не двойственными относительно деформаций def и def.

Если многогранник  получен от исходного многогранника М путем изменения его некоторых параметров, то многогранник называется деформированным многогранником, порожденным от многогранника М.

Порождающие многогранники некоторых классов деформированных многогранников

Для определенности предположим, что никакими ЛОД многогранника М, имеющего n вершины, невозможно уменьшить число его вершин, т.е. любой многогранник имеет не менее, чем n вершин.

ОПРЕДЕЛЕНИЕ. Если существует некоторый многогранник и найдется не менее чем по три элемента из множеств N(k) и N(l) , k что грани многогранника  соответствующие этим элементам инцидентны некоторой вершине В (многогранника ), то вершины и многогранника М называются линейно зависимы, иначе – линейно независимыми, .

Допустим, что вершины  многогранника М между собой линейно зависимы,  а любая вершина из остальных вершин с любыми вершинами линейно независимо, где - натуральные числа, q- неотрицательное целое число.

Такой многогранник М далее будем обозначать через M(q). Многогранник вида М(q) назовем порождающим многогранником для ЛОД. При q=0 будем понимать, что любая вершина многогранника М(0) с любыми другими вершинами линейно не зависима.

Не каждый многогранник может служить в качестве порождающего многогранника. Например, многогранник , полученный из куба путем специального среза, с 8 вершинами (рис.1,а) не может служить в качестве порождающего многогранника, потому что посредством ЛОД можно получить многогранник М(рис.1,б) с 7 вершинами и 6 гранями. В свою очередь, никакими ЛОД нельзя уменьшить число вершин многогранника М, поэтому многогранник М является порождающим многогранником.

Легко проверить, что у многогранника Мвеличина q=0. У многогранника  (рис.1,в) посредством ЛОД также нельзя уменьшить число вершин. Вершины с номерами 1,2 и 5,6 являются линейно зависимыми (у многогранника  расстояние между вершинами с номерами 1 и 2 больше расстояния 5-ой и 6-ой вершинами и многогранник не имеет параллельные грани ). Поэтому, многогранник  является порождающим многогранником и q=2.

Пусть  класс всех порождающих многогранников типа М(q). Отметим, что два комбинаторно эквивалентных, порождающих многогранники  и  могут принадлежать различным классам, т.е.

 и . Например, многогранники  и  (рис.2,а и б) комбинаторно эквивалентны (у многогранника  грани А и В параллельные), но нетрудно проверить, что  и .

Многогранник  порождает многогранник изображенный на рис.2.в , а многогранник  не может породить такой многогранник.

Рисунок 1. Пример

Рисунок 2. Пример

Аналогично дадим следующие определения.

ОПРЕДЕЛЕНИЕ. Если существует некоторый многогранник ,ПОД) и найдется по крайней мере по три элемента из множеств и  что вершины многогранника  соответствующих этим элементам инцидентны некоторой грани Г, то грани Ги Г многогранника  называются полярно зависимыми, иначе полярно независимыми,

Предположим, что никакими ПОД невозможно уменьшить число граней многогранника .

Пусть грани  между собой полярно зависимы i=1,, а остальные грани с любыми другими гранями полярно независимы, где  натуральные числа. Такой многогранник  будем обозначать через P(). Многогранник вида P() назовем порождающим многогранником для ПОД. При =0 будем понимать, что любая грань многогранника P(0) с любыми другими гранями полярно независима.

Список литературы:

1. Емеличев В.А., Ковалев М.М. , Кравцов М.К. Многогранники, графы, оптимизации. –М.: Наука, 1981. -344 С.
2. Steinitz E. Polyhedra und Raumeinteilungen.- Enzykl. Math. Wiss., 1922.3.
3. Минковский Г. Общие теоремы о выпуклых многогранников. – Успехи матем. наук, 1936. Вып. 1,2.
4. Вейль Г. Элементарная теория выпуклых многогранников. – В кн.: Матричные игры, М.,1961
5. Александров А.Д. Выпуклые многогранники. М.-Л.; Гостехиздат. -1950.-428 С.
6. Бронштейн Е.М., Иванов Л.Д. О приблежении выпуклых множеств многогранниками. “Сиб. Мат.ж.”, 16Т3N С1110-1112
7. Steiner J. Von Krummungsschwerpuntle Curven. –Ges.Werke.Berlin 882. 2.
8. Cayley A. On the faced polyacrons in reference to tne problem of the enumeration of polyhedral. – Mem. His. Philos. Soc. 1862.1.
9. Edward A. Bender and Nicols C. Wordmald. Almost all convex polyhedra are asymmetric. Can. J.Math. v-27, N-5. Pp.854-871
10.  Engel P. On the enumeration of polyhedral/ discrete matemat
11.  Люстерник Л.А. Выпуклые фигуры и многогранники. – М.,1956
12.  Лейхтвейс К. Выпуклые множества.-Пер. с нем. -.: Наука, 1965.-336 С.
13. Александров А.Д. Выпуклые многогранники.-М.-Л.: Гостехиздат.-1950.-478 С.
14. Погорелов Л.В. Внешная геометрия выпуклых поверхностей.-М.: Наука.-1969.
15. Александров П.С. Курс аналитической геометрии и линейной алгебры.- М: Наука. -1979. -511 С.