СРАВНИТЕЛЬНЫЙ АНАЛИЗ РАЗЛИЧНЫХ ТИПОВ ДЕФОРМАЦИИ МНОГОГРАННИКОВ

АННОТАЦИЯ

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

ABSTRACT

The article analyzes deformations of polyhedrons. Since a convex polyhedron is a fundamental object of mathematics and is of constant interest to researchers. Many natural formations and technological products have the form of a convex polyhedron (minerals, household items, machine parts, etc.); the set of all solutions to a system of linear inequalities is a convex polyhedron [1]; the convexity of a body is approximated by convex polyhedrons.

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

Keywords: discrete mathematics, polyhedron, deformation, convex polyhedron, geometry, inequality.

В предыдущей статье определены понятие линейно угловая ограниченная деформация (ЛУОД), ограниченная деформация (ОД), линейно ограниченная деформация и полярно угловая ограниченная деформация (ПУОД), полярно ограниченная деформация (ПОД), сферическая ограниченная деформация (СОД)

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

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

                                                                      (1)

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

ТЕОРЕМА 1.1. Для каждого многогранника из класса М(М,ЛУОД) в классе М(,ПУОД) существует двойственный ему многогранник и, наоборот, для любого многогранника из класса М(,ПУОД) в классе М(М,ЛУОД) существует двойственный ему многогранник.

ДОКАЗАТЕЛЬСТВО. Рассмотрим произвольный 3-многогранник с р гранями, заданный следующей системой линейных неравенств,

                                                           (2)

где - нормаль i-ой грани, - линейный параметр i-ой грани, i=1,p.

Нетрудно убедится, что из любого неравенство системы (1) можно получит посредством ЛУОД любое неравенство системы (2). То есть от многогранника М посредством ЛУОД порождается многогранник . Значит посредством ЛУОД от М порождаются все р - гранники.

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

многогранник  двойственен к многограннику . Поскольку  двойственен к , имеет р граней. Тогда М(М,ЛУОД), так как класс М(М,ЛУОД) содержит все комбинаторно неэквивалентные р – гранники . Значит каждый многогранник класса М(М,ЛУОД) в классе М(, ПУОД) имеет двойственный многогранник и наоборот.

Теорема доказана.

СЛЕДСТВИЕ. Класс М(М,ЛУОД) содержит все комбинаторно неэквивалентные р – гранники.

Из определений линейной зависимости вершин, полярной зависимости граней, ограниченной деформации и сферическо ограниченной деформации непосредственно следуют следующие положения.

ЛЕММА 1.1. При любой ЛОД (ПОД) многогранника М() семейства множеств вершин (граней), порожденных от каждой вершины (грани) многогранника М(), попарно не имеют общих (граней) тогда и только тогда, когда М() является многогранником типа М(0)(Р(0)), где М(0) и Р(0) - порождающие многогранники для ЛОД и ПОД соответственно.

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

ЛЕММА 1.2.

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

Далее докажем следующую лемму.

ЛЕММА 1.3. Пирамида является многогранником типа М(0) относительно ЛОД, и типа Р(0) относительно ПОД.

ДОКАЗАТЕЛЬСТВО. Пусть пирамида задана в сферической системе координат с координатами вершин и . Покажем, что является многогранником Р(0) относительно ПОД. Пусть  и - произвольные смежные треугольные грани многогранника . Пусть вершины ,, инцидентны к грани , вершины ,, инцидентны к  и - имеет степень t. Через ,,, обозначим полярные векторы вершин ,,, соответственно (см. рис.1).

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

Покажем, что такая ПОД многогранника  не существует, т.е. грани  и  полярно не зависимы.

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

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

Также по определению ПОД вершина  не будет совпадать с началом системы координат при любых ПОД. Следовательно, при любых ПОД многогранника , вершина  не будет принадлежать плоскости .

Значит в этом случае грани  и  полярно независимы.

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

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

Лемма доказана.

ЛЕММА 1.4. Пусть обобщенный клин  порожден от пирамиды посредством ЛОД. Тогда от  применением ОД порождается обобщенный клин  , который является комбинаторно эквивалентным к и , наоборот, если  порожден от  посредством ОД, тогда от  посредством ЛОД порождается обобщенный клин , который является комбинаторно эквивалентным к .

ДОКАЗАТЕЛЬСТВО. Лемма 1.3 утверждает, что пирамида  является многогранником типа М(0). Значит, согласно лемме 1.1 при любой ЛОД пирамиды множество вершин, порожденные от вершин попарно не имеет общие вершины. То есть сохраняются смежности граней пирамиды  при любом ЛОД.

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

Отсюда следует, что для любого обобщенного клина, порожденного от применением ЛОД, порождается комбинаторно эквивалентный обобщенный клин от применением ОД. Теперь пусть от пирамиды посредством ОД порожден обобщенный клин . Пусть  и  - грани обобщенного клина , смежность которых определяет ребро , i=1,k,  Через  и  обозначим прообразы (грани пирамиды ) граней  и , соответственно i=1,k,  Покажем, что от пирамиды  посредством ЛОД порождается обобщенный клин , который является комбинаторно эквивалентным к . Гранями  и  множество граней (кроме основания) пирамиды разделяется на два множества граней  и , не содержащие грани  и , так чтобы никакая грань множества  не смежно никакой грани множество . Потому что грани  и многогранника  образуют ребро

Изменяем линейный параметр граней множества  так, чтобы порождался ребро и грани множества  пересекались в одной точке. Тогда эта точка двигается по линии, являющейся пересечением опорных плоскостей определяющих грани  и .

Также является вершиной порожденного многогранника. То есть образуем .

Нетрудно видеть, что при образовании ребра  не избыточность граней обеспечивается изменением линейного параметра основания пирамиды  (т.е. основание удаляется на достаточно большое расстояние от вершины В пирамиды ), 3. Значит эти изменения линейных параметров граней является ЛОД. Теперь относительно порожденных вершин применяя этот подход, образуем ребро .

Продолжая этот процесс, образуем все ребра , i=1,k и получим обобщенный клин , который по построению, является комбинаторно эквивалентным к , 3.

Лемма доказана.

ЛЕММА 1.5. Если ломаная пирамида порождена от пирамиды посредствам ПОД , тогда от посредством СОД порождается ломанная пирамида , которая является комбинаторно эквивалентной многограннику  и, наоборот, если ломанная пирамида порождена от посредством СОД тогда от применением ПОД порождается ломанная пирамида , которая является комбинаторно эквивалентной к , где - t-угольная пирамида, заданная в сферической системе координатами вершин и .

Теперь введем некоторые обозначения.

Пусть  - множество номеров всех вершин (граней) смежных вершине  (к грани ) многогранника , l=1,n. Для определенности будем считать , что в множестве элементы упорядочены так, что вершины  и   (грани  и ) обе инцидентны из граней (вершин) многогранника , где i и j – произвольные элементы множества , расположенные друг за другом ,  Ясно, что при таком упорядочены элементов множества , вершины (грани), соответствующие первым и последним элементам обе инцидентны одной из граней (вершин) многогранника . Пусть  и - произвольные подмножества множества  такие, что каждый имеет более одного элемента, элементы которых упорядочены как элементы , =, =J. Также  и  для вершин, не имеющие степени три (для нетреугольных граней). Если при деформации (ЛОД, ОД, ПОД,СОД) от смежных вершин (граней) Х и У , некоторого многогранника, порождены более одной вершины (грани) то будем говорить, что несохранена смежность вершин (граней) Х и У при деформаций, иначе – сохранена. Если при деформаций некоторого многогранника от вершин (грани ) Х порождается одна вершина (грань), то эту вершину (грань) порожденного многогранника обозначим также через Х. Пусть посредством деформаций для любых подмножеств  и множества  порождается две вершины и (грани  и ) от вершины (грани ) многогранника при сохранении смежности остальных вершин (граней) такие, что  смежно с вершинами , i,  смежно с , ( смежно с , i, смежно с , ),  Тогда будем говорить, что от вершины (грани ) порождаются две вершины (грани) произвольными смежностями при сохранении смежности остальных вершин (граней).

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

Также от куба посредством ПОД не порождается многогранник  (рис.2.б).

Но при помощи СОД порождается этот многогранник от куба. Отметим, что многогранники  и  взаимно двойственны.

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

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

Для деформации типа ОД и СОД на поставленный вопрос отвечают следующие леммы.

ЛЕММА 1.6. Если степень вершины многогранника М больше трех, то посредством ОД от его вершины порождаются две вершины произвольными смежностями при охранении смежности остальных вершин.

ДОКАЗАТЕЛЬСТВО. Очевидно, что если степень вершины многогранника М имеет степень три , то от этой вершины не порождается две вершины. Пусть многогранник М имеет хотя бы одна вершина, не имеющая степень три. Предположим, что вершина  не имеет степень три. Лемму докажем только для вершины (ясно, что это не ограничивает общности).

Пусть G - граф многогранника М и его подграф  получен удалением вершины . Рассмотрим теперь некоторый граф . Пусть он сконструирован следующим образом. Добавлены две вершины  и  к подграфу  так чтобы они смежный. Также вершина  смежен с вершинами ,  , а  с вершинами   где  и - вышеопределенные множества. То есть граф  имеет вершины ,  , …,  , ,  . Очевидно, что граф  планерен и трёхсвязной.

Значит по теореме Штейница граф  изоморфен графу некоторого многогранника  . являющего р - гранником. т.е. существует многогранник , имеющий вершины ,  ,….,  такой, что матрица смежности вершин ,  ,….,  совпадает с матрицей смежности вершин

 многогранника М и вершина  смежная с . . Также вершины B, , смежный с  и В,  смежный с B, для произвольных подмножеств  ,  множества .

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

Применяя ЛУОД к многограннику М, порождается многогранник  . так как  р - гранником .

Пусть посредством ЛУОД от i-ой грани М порождена i - ая грань , i=1, p. Тогда согласно нумерации граней  при ЛУОД сохраняются смежности граней М в многограннике . То есть такая ЛУОД . порождающая  от М, является ОД .

Лемма доказана.

ЛЕММА 1 .7. Если грань многогранника М* не треугольная, то посредством СОД от его грани образуются две грани произвольными смежностями при сохранении смежности остальных граней.

Доказательство леммы 1.7 аналогично доказательству леммы 1.6.

В дальнейшем, если некоторыми деформациями некоторого многогранника от вершины (грани) X порождены вершины (грани) , то будем говорить, что при деформации от X порожден обобщенный клин (ломанная пирамида ).

Очевидно следующая.

ЛЕММА 1.8. Порождение многогранника М от многогранника М(М*) посредством ОД ( СОД) не зависит от метрических параметров многогранника М(М*).

Поскольку многогранники М и М* двойственны, существуют нумерации вершин многогранника М и граней многогранника М*, что матрица смежности вершин многогранника М равна матрице смежности граней М* .

Пусть матрица смежности вершин  многогранника М равна матрице смежности граней ,       многогранника  М*.

Тогда ясно. что число углов грани Г равно степени вершины В, i=1,n. Предположим, что вершина В не имеет степень три. Пусть многогранник  порожден от М посредством ОД . При этом две вершины  , Bпорождены от вершины В при сохранении смежности остальных вершин так что, вершина  смежно с вершинами В, ,  смежно с вершинами В, , где  ,  - вышеопределенные произвольные подмножества множества .

Также многогранник  порожден от многогранника М* посредством СОД, при которой две грани ,  порождены от грани  при сохранении смежности остальных граней, где грань  смежно граням Г, , а Г смежно с Г,

(Согласно леммам 1.6 и 1.7 ясно, что многогранники  и  порождаются от многогранников М и М* посредством ОД и СОД . соответственно).

ЛЕММА 1.9. Многогранники  и  двойственны.

ДОКАЗАТЕЛЬСТВО. Пусть - элемент матрицы смежности вершин ммногогранника М,  - элемент матрицы смежности граней многогранника М*, i,j=1,n.

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

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

Например, нетрудно показать что класс всех комбинаторно неэквивалентных многогранников порожденных от октаэдра применением ОД содержит (в комбинаторном смысле) класс всех комбинаторно неэквивалентных многогранников порожденных от октаэдра посредством ЛОД . В этом примере ЛОД является частным случаем ОД.

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

ТЕОРЕМА 1. .2. Класс М(M(0),ОД) содержит ( в комбинаторном смысле) класса М(M(0),ЛОД) .

ТЕОРЕМА 1.3. Класс М(P(0),ПОД) содержит ( в комбинаторном смысле ) класса М(P(0),ПОД) .

Из лемм 1.6.,1.7 и 1.9 непосредственно вытекает следующее следствие .

СЛЕДСТВИЕ. Пусть посредством ОД от некоторой вершины, не имеющей степень три, многогранника М порождены две вершины некоторыми смежностями при сохранении смежности остальных вершин и порожден некоторый многогранник M . Тогда двойственный к многограннику M многогранник порождается от многогранника М* посредством СОД.

ТЕОРЕМА 1.4. При любых метрических параметрах двойственные многогранники М и М* являются двойственными относительно ОД и СОД.

ДОКАЗАТЕЛЬСТВО. Пусть многогранник М простой. Применением ОД к многограннику М не порождаются комбинаторно неэквивалентные ( к М ) многогранники, так как ясно, что от вершины, имеющей степень три не порождается более одной вершины. Многогранник М* также как М при помощи СОД комбинаторно неэквивалентные ( к М*) многогранники не порождает, так как он симплициальный . Значит для таких многогранников М и М* теорема очевидна. Рассмотрим случай, когда хотя бы одна вершина В, многогранника М, не имеет степень три.

Пусть от многогранника М посредством ОД порожден многогранник  следующим образом. Посредством ОД от вершины  порождены две вершины некоторыми смежностями при сохранении смежности остальных вершин и порожден многогранник Р₁. Применением ОД многограннику Р₁, от одной из вершин, кроме вершин , порождены две вершины некоторому смежностями при сохранены смежности остальных вершин и порожден многогранник . И так далее, применением ОД многограннику Рк-1 от одной из вершин, кроме вершин , порождены две вершины некоторому смежностями при сохранены смежности остальных вершин и порожден многогранник , т.е. М₁, где к - число шагов которое нужно для рекуррентного получения М₁, от М посредством ОД, основываясь на лемме 1.6 . Другими словами, М порожден от М посредством ОД при порождении некоторого обобщенного клина только от . Согласно следствию для многогранника Р₁ от М* порождается двойственный многогранник Р₁* посредством СОД .

Также для многогранника Р от Р* порождается двойственный многогранник Р* посредством СОД . И так далее. основываясь на следствии, имеем. что для Р т.е. для М₁ посредством СОД от Рк-1 порождается двойственный многогранник М₁* . По рекуррентным получением многогранник М* является многогранником, порожденный от М* посредством СОД. Значит, если посредством ОД от некоторой вершины порождается обобщенный клин при сохранении смежности остальных вершин, то двойственный многогранник порожденного многогранника порождается от М* посредством СОД.

В рассматриваемой случае хотя бы одна вершина многогранника М не имеет степень три. Поэтому, не ограничивая общности предположим . что вершины   многогранника М имеют степень более трех и многогранник M₀ порожден от М посредством ОД порождением некоторых обобщенных клиньев от вершин  , 1.

Порождение многогранника M₀ от М посредством ОД можно понимать следующим образом. От многогранника М порожден многогранник К₁ посредством ОД . порождением обобщенного клина от В₁.

Посредством ОД от вершины В₂ многогранника К₁ порожден обобщенный клин и порожден многогранник К₂. И так далее посредством ОД от В_i многогранника К_i-1 порожден обобщенный клин и порожден многогранник К_i т.е. M₀. где i – число шагов которое нужно для рекуррентного получения M₀ от М посредством ОД .

Показали, что двойственный многогранник К₁* к многограннику К₁ порождается от М* посредством СОД . Также для многогранника K двойственный многогранник К₂* порождается от К₁* посредством СОД . И так далее имеем, что двойственный многогранник К_i* к многограннику К_i (т.е. к M) порождается посредством СОД от ОД К_i-1.

Значит двойственный многогранник К_i* многогранника M₀ порождается от М* посредством СОД .т.е. двойственный многогранник многогранника  принадлежит классу (М

Аналогично легко доказывается, что двойственный многогранник некоторого многогранника из класса М(М*,СОД) принадлежит классу М(М,.ОД). То есть многогранники М и М* двойственные относительно ОД и СОД. Лемма 1.3 утверждает, что порождение некоторого многогранника от М (М*) посредством ОД ( СОД) не зависит от метрических параметров М (М* ) . Значит, при любых метрических параметрах двойственные многогранники М и М* являются двойственными относительно ОД и СОД .

Теорема доказана.

Так как двойственный многогранник единственен ( в комбинаторном смысле), из теоремы 1.3 непосредственно вытекает.

ТЕОРЕМА 1.5. Мощность классов М(М.ОД) и М(М*,СОД) равны.

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

1. Емеличев В.А., Ковалев М.М. , Кравцов М.К. Многогранники, графы, оптимизации. –М.: Наука, 1981. -344 С.
2. Люстерник Л.А. Выпуклые фигуры и многогранники. – М.,1956
3. Лейхтвейс К. Выпуклые множества.-Пер. с нем. -.: Наука,1965.-336 С.
4. Александров А.Д. Выпуклые многогранники.-М.-Л.: Гостехиздат.-1950.-478 С.
5. Погорелов Л.В. Внешная геометрия выпуклых поверхностей.-М.: Наука.-1969.
6. Александров П.С. Курс аналитической геометрии и линейной алгебры.- М: Наука. -1979. -511 С.