Решение многогранников: теоретические и вычислительные аспекты Михалев Сергей Николаевич

Данный автореферат диссертации должен поступить в библиотеки в ближайшее время
Уведомить о поступлении

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - 240 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Михалев Сергей Николаевич. Решение многогранников: теоретические и вычислительные аспекты : диссертация ... кандидата физико-математических наук : 01.01.04.- Москва, 2003.- 110 с.: ил. РГБ ОД, 61 03-1/1316-X

Содержание к диссертации

Введение

1. Метрические октаэдры Брикара 1-го и 2-го типа и их реализуемость в Л3 19

1.1. Постановка задачи 19

1.2. Реализуемость положительных корней многочленов для объёма октаэдров Брикара 1-го и 2-го типа 27

1.3. К вопросу о выпуклости изометрической реализации с максимальным объемом 36

2. Компьютерные методы решения многогранников 38

2.1. Программа для решения задачи изометрической реализации (по алгоритму Сабитова) 38

2.2. Некоторые необходимые метрические условия изгибаемости подвесок 51

3. Об одном методе решения задачи изометрической реализации развёрток 66

3.1. Задача изометрической реализации развёртки и методы ее решения 66

3.2. Понятие 5-комплекса и некоторые свойства 5-комплексов 69

3.3. Системы уравнений для решения задачи изометрической реализации 75

3.4. Об алгоритмическом решении задачи изометрической реализации 86

3.5. Примеры применения предложенного метода решения задачи изометрической реализации 90

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

Реализуемость положительных корней многочленов для объёма октаэдров Брикара 1-го и 2-го типа
Некоторые необходимые метрические условия изгибаемости подвесок
Понятие 5-комплекса и некоторые свойства 5-комплексов
Об алгоритмическом решении задачи изометрической реализации

Введение к работе

В той области геометрии, которая раньше называлась "геометрией в целом", а теперь все чаще называется метрической геометрией, основными являются следующие вопросы:

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

Изометрические реализации заданных многообразий с метриками в евклидовых или других римановых пространствах.

Изгибания данных поверхностей и многогранников.

Различные свойства данных поверхностей и многогранников в целом. (Этот круг вопросов составляет предмет внешней геометрии поверхностей.)

В известном смысле второй и третий вопросы являются связующим звеном между первым и четвертым вопросами; в дифференциальных уравнениях и других областях математики второму и третьему вопросам соответствуют вопросы существования и единственности искомых объектов.

По каждому из перечисленных направлений имеются многочисленные результаты, нашедшие отражение в обширной литературе. Среди геометров, внесших наиболее значительный вклад в геометрию в целом, можно назвать таких классиков как А.Лежандр, О.Коши, Д.Гильберт, Г.Либман, В.Бляшке, С.Э.Кон-Фоссен, Г.Минковскнй, А.Д.Александров, Н.В.Ефимов, А.В.Погорелов, Ю.Г.Решетняк и др.

Наша диссертационная работа посвящена главным образом второму и третьему вопросам, связанным с изометрическими реализациями многогранных метрик и изгибаниями многогранников.

В метрической теории многогранников имеется ряд важных принципиальных достижений, среди которых, несомненно, заслуживают упоминания такие классические результаты, как теорема Коши об однозначной определённости выпуклого многогранника своей метрикой, доказательство Брикара существования изгибаемых многогранников с треугольными гранями, теорема Александрова о реализуемости в виде многогранника всякой заданной на сфере многогранной метрики положительной кривизны и др.

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

С момента построения Брикаром в 1897 году его изгибаемых (имеющих самопересечения) октаэдров ( [17]; см. также [20] и — на русском языке — [11]) на протяжении 80 лет не было известно ни одного примера вложенного изгибаемого многогранника. В 1978 г. такой пример был построен Коннелли (см. [18]).

Вскоре было замечено, что изгибаемый многогранник Коннелли, а также все построенные после него изгибаемые многогранники обладают следующим замечательным свойством: их объём в ходе изгибания остаётся неизменным. Это дало Коннелли основание в своём докладе на Математическом Конгрессе в Хельсинки в 1978 г. высказать так называемую гипотезу кузнечных мехов ("Bellows Conjecture"), состоящую в том, что свойство неизменности объёма является общим для всех изгибаемых многогранников; образно это можно сформулировать как невозможность изготовить идеально точные кузнечные меха из изгибаемых многогранников.

Проблема кузнечных мехов оставалась нерешённой в течение почти 20 лет. Более того, не сущестовало не только доказательства справедливости гипотезы, но не было даже уверенности в том, что гипотеза справедлива. Многие математики, по-видимому, искали ее опровержение, но все попытки найти контрпримеры только подтверждали гипотезу (см., например, [2]).

Справедливость гипотезы кузнечных мехов была доказана И.Х.Сабитовым (см. [13, 14, 22]¹). В этих работах доказывается даже более общая теорема, из которой справедливость гипотезы вытекает как простое ее следствие: для всякого многогранника (изгибаемого, или нет) устанавливается существование некоторого нетривиального полиномиального уравнения, такого, что его коэффициенты зависят только от комбинаторного строения и метрики данного многогранника, а объём этого многогранника является его корнем. Так как в ходе изгибания комбинаторное строение и метрика изгибаемого многогранника не меняются, то и объём, будучи ^ХВ этих работах даются разные доказательства основной теоремы; в дальшейшем мы будем ссылаться только на работу [13], поскольку именно в [13] впервые появилось полное доказательство теоремы о многочлене для объёма многогранника (см. далее). корнем полиномиального уравнения с постоянными коэффициентами, не может меняться в ходе изгибания.

Это полиномиальное уравнение позволяет находить объём многогранника по его метрике, точнее, оно дает конечный набор чисел, одно из которых является значением объема многогранника. Рассматриваются только многогранники с треугольными гранями (что не является серьезным ограничением, поскольку нетреугольные грани можно дополнительно триангулировать), следовательно, можно считать, что метрика многогранника с данным комбинаторным строением полностью определяется длинами его рёбер. Таким образом, уравнение для объёма позволяет находить объём многогранника с данным комбинаторным строением, исходя только из длин его рёбер, подобно тому как известная формула Герона позволяет находить площадь треугольника по длинам его сторон.

Продолжая аналогию с планиметрией, ту часть метрической теории многогранников, в которой решаются задачи, связанные с нахождением одного набора метрических характеристик многогранника на основании знания некоторого другого, достаточно богатого, набора метрических характеристик, — своего рода развитие "решения треугольников" — мы будем называть "решением многогранников"². Теорема об объёме многогранника играет в решении многогранников самую существенную роль.

Поскольку многогранники (в отличие от треугольников) могут быть комбинаторно устроены сколь угодно сложно, неудивительно, что до недавнего времени сколь-нибудь полной теории решения многогранников не существовало вовсе. Однако попытки получить результаты в этом направлении предпринимались довольно давно. Так, например, ещё Ле-жандр в [21] поставил следующий вопрос: какими своими параметрами многогранник с данным комбинаторным строением определяется однозначно? Сам же Лежандр показал (см. [21]), что число таких параметров равно числу рёбер многогранника, но предположение, что в качестве этих параметров можно взять просто сами рёбра, неверно. (Последнее очевидно в силу существования изгибаемых многогранников: в ходе изгибания все рёбра остаютсяпостоянными, а форма многогранника меняется.) Интересной задачей является нахождение некоторого универсального способа выбора параметров Лежандра. ²термин предложен И.Х.Сабитовым Лежандр неявно предполагал многогранник выпуклым, но не обязательно с треугольными гранями

В [13] даётся конструктивное доказательство теоремы об объёме многогранника: предлагается алгоритм, который позволяет исходя из комбинаторного строения и метрики многогранника Р найти все коэффициенты уравнения Q(V) = 0 для объёма. Никакой другой информации о Р не требуется (в частности, не нужно знать длины диагоналей), поэтому найденное уравнение "обслуживает" сразу все изометричные Р многогранники с таким же как у Р комбинаторным строением, в том смысле, что объёмы всех таких многогранников являются корнями одного и того же уравнения Q(V) = 0. Можно сказать, что уравнение Q(V) = 0 со-ставялется лишь по развёртке многогранника. Более того, уравнение для объёма можно составить по методу из [13] ещё до того, как развёртка реализована в виде многогранника, и независимо о того, возможна ли такая реализация в принципе.

Теорема об объёме многогранника, будучи сама по себе фундаментальным результатом, имеет многочисленные применения. Так, в работе [15] для одной из основных задач метрической теории многогранников — задачи изометрической реализации данной развёртки — предлагается решение, основанное на составлении уравнения для объёма.

В работах [13], [14], [15], [22] и в нашей диссертации под развёрткой понимается набор евклидовых треугольников с заданным законом отождествления ("склейки") сторон и вершин, который после отождествления окажется гомеоморфным некоторому компактному ориентируемому многообразию без края, а под изометрической реализацией данной развёртки понимается такой многогранник в і?³, для которого данная развёртка является натуральной развёрткой, то есть треугольники развёртки изо-метричны истинным граням многогранника. Таким образом, развёртка и многогранник, являющийся её изометрической реализацией, должны иметь одинаковое комбинаторное строение, а соответствующие треугольники развёртки и грани многогранника должны быть конгруэнтны.

Решать задачу изометрической реализации данной развёртки (или задачу изометрической реализации данной многогранной метрики) в такой постановке до недавнего времени никто не пытался. Так, классическая теорема Александрова [1], которая для всякой заданной на сфере многогранной метрики / положительной кривизны устанавливает существование выпуклого многогранника с внутренней метрикой /, не даёт никакой информации о комбинаторном строении этого многогранника.

Более того, если метрика I была задана как внутренняя метрика некоторой развёртки, гомеоморфнои сфере, то, вообще говоря, комбинаторное строение найденного многогранника, будет отличаться от комбинаторного строения исходной развёртки.

Сказанное относится также к работам Бураго и Залгаллера [6, 7], в которых они доказывают, что всякая развёртка (неважно, есть ли у неё край, и является ли она ориентируемой) допускает изометрическое кусочно-линейное погружение в Л³. В ходе конструктивного доказательства этой теоремы, треугольники исходной развёртки много раз "ломаются" по новым рёбрам, и получаемый многогранник в В^2, имеет по сравнению с исходной развёрткой иное (как правило, существенно более сложное) комбинаторное строение.

Таким образом, работа [15] является, по-видимому, первой попыткой решения задачи изометрической реализации развёртки, когда реализация ищется среди многогранников, для которых данная развёртка является натуральной развёрткой. Недостатком метода работы [15] является тот факт, что с его помощью невозможно находить изгибаемые реализации данной развёртки (конечно, речь идет о случае, когда развёртка допускает такие реализации).

Особенностью современной метрической теории многогранников является её ярко выраженная алгоритмическая направленность. С одной стороны, это выражается в широком применении конструктивных доказательств: для того, чтобы доказать сущестовование того или иного объекта, мы просто в явном виде составляем алгоритм построения этого объекта. Таковы, например, доказательства основных теорем в [3], [4], [6], [7], [13], [15]. С другой стороны, в тех случаях, когда нужно проверить, обладает ли данный объект определённым свойством (например, изгибаем ли данный многогранник, реализуема ли в І?³ данная развёртка), мы зачастую не можем заранее дать теоретически полученный ответ, однако можем составить некоторый алгоритм, следуя которому этот ответ в каждом конкретном случае можно получить за конечное число шагов. Такого рода алгоритмический подход используется, например, в [10], [12], [15].

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

Однако, помимо того очевидного соображения, что мы можем использовать компьютер как мощный "вычислитель", т.е. прибор, необходимый для реализации алгоритмов и получения таких конечных результатов, которые интересны сами по себе, существует и другая идея применения компьютера в решении многогранников. Эта идея не нова: компьютер используется для того, чтобы правильно сформулировать ("угадать") теорему. Сначала с помощью компьютера предполагаемое утверждение проверяется для нескольких частных случаев (не слишком сложных, но таких, что вручную соответствующие вычисления провести не удалось бы), а затем формулируется общее утверждение, которое доказывается уже без применения компьютера, теоретически.

В нашей диссертации будут продемонстрированы оба эти подхода.

Помимо исследования свойств многочлена для объёма многогранника и решения задачи изометрической реализации развертки в виде многогранника мы также уделяем внимание изучению изгибаемости многогранников. (Под нетривиальным изгибанием многогранника в R³ понимается такая его непрерывная деформация, при которой грани перемещаются как абсолютно твердые тела, а двугранный угол хотя бы при одном ребре непрерывно изменяется; многогранник, допускающий нетривиальное изгибание называется изгибаемым.) В этой области метрической геометрии есть следующие результаты:

1) Классическая теорема Копій утверждает, что всякий строго выпуклый многогранник неизгибаем. (Доказательство теоремы Копій можно найти, например, в книге [5]).

2 Глюк в [19] доказал, что изгибаемых многогранников в некотором смысле очень мало: в пространстве всех многогранников они заполняют подпространство меры нуль.

Брикар в [17] дал полную классификацию изгибаемых октаэдров.

Коннелли в [18] построил пример изгибаемого вложенного многогранника.

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

Диссертация состоит из введения, трех глав и списка литературы из 30 наименований. Полный объём диссертации — 110 страниц.

Дадим теперь краткий обзор содержания работы по главам и сформулируем основные полученные результаты.

В главе 1 "Метрические октаэдры Брикара 1-го и 2-го типа и их реализуемость в Л³" исследуется геометрический смысл корней уравнения для объёма на примере уравнений, составленных по некоторым конкретным развёрткам. До недавнего времени в этом направлении не было известно ни одного результата, хотя сам вопрос ставился практически на каждом обсуждении теоремы о многочлене для объёма. По-видимому, доказанные в главе 1 теоремы 1 и 2 являются первыми результатами такого рода.

В качестве развёрток берутся так называемые метрические октаэдры Брикара 1-го и 2-го типа.

Определение 1. Метрический октаэдр Брикара 1-го типа —развёртка К\_х, комбинаторно изоморфная натуральной развёртке К октаэдра NABCDS (см. рис. 1, а), такая, что длины её ребер удовлетворяют следующим условиям: АВ = CD, ВС = DA,ND = SB,NB = SD,NC = SA, NA = SC.

Квадраты длин рёбер метрического октаэдра Брикара 1-го типа мы будем обозначать буквами а, 6, с, d, e,f: АВ² = CD² = а, ВС² = DA² — b,ND² = SB² = c,NB² = SD² = d,NC² = SA² = e,NA² = SC² = f. Ha рис. 1, 5, таким образом, при каждом ребре стоит квадрат его длины.

Определение 2. Метрический октаэдр Брикара 2-го типа —развёртка Ki₂, комбинаторно изоморфная натуральной развёртке К октаэдра NABCDS (см. рис. 1, а), такая, что длины её ребер удовлетворяют следующим условиям: АВ = ВС, CD = DA,ND = SD,NB = SB,NC = SA,NA = SC.

Рис. 1.

Квадраты длин рёбер метрического октаэдра Брикара 2-го типа мы также будем обозначать буквами a,b,c,d,e,f: АВ² — ВС² = f,CD² = DA² = е, ND² = SD² = с, NB² = SB² = d, NC² = SA² = a, NA² = SC² = b. При этом путаницы не возникнет, поскольку в каждый момент времени будет ясно, о каком именно октаэдре Брикара идёт речь. На рис. 1, е при каждом ребре стоит квадрат его длины.

В обоих случаях мы будем предполагать, что числа а,&, с,

Развёртки К^ и К\₂ изображены на рис. 1 в виде выпуклых октаэдров лишь для удобства; реальные развёртки при некоторых допустимых а, 6, с, cf, е, / могут быть вообще нереализуемы в виде многогранников (даже и невыпуклых).

Алгоритм нахождения уравнения для объёма из [14], будучи применен к развёрткам К\_х и Л'/₂, даёт уравнение Q(V) = 0 очень большой степени. Поэтому вместо того, чтобы применять этот алгоритм, мы воспользуемся результатом работы [3], в которой для развёрток А'/₁ и Ki₂ найдены соответствующие уравнения Qi(V) — 0 и Qi(y) = 0 для квадрата V объёма, имеющие минимальные степени.

Сформулируем теперь основные теоремы главы 1.

Теорема 1. Если многочлен Q\(V) имеет положительный корень Vq, то метрический октаэдр Ki_x допускает изометрическую реализацию в R в виде октаэдра, квадрат объема которого равен Vq.

Таким образом, в случае, когда развёртка является метрическим октаэдром Брикара 1-го типа, положительный корень многочлена для объёма всегда реализуется как объём реально существующего октаэдра.

Теорема 2. Пусть многочлен Qi(V) имеет положительный корень V\. Тогда метрический октаэдр Ki₂ допускает изометрическую реализацию в Fft в виде октаэдра, квадрат объема которого равен \\, если выполняется одно из следующих условий:

Корень V\ имеет кратность 1. V\ имеет кратность 2 и выполняется условие -ab + cd-ed- fc + ef фО. (1)

Таким образом, в случае, когда развёртка является метрическим октаэдром Брикара 2-го типа, положительный корень многочлена для объёма заведомо реализуется только в том случае, если он имеет кратность 1.

В случае, когда — ab + cd — ed— fc + ef = О (т.е. если условие (1) не выполнено) и многочлен Q2OO имеет ненулевой корень V\, то V\ обязательно имеет кратность 2, и в этом случае положительность V\ не является достаточным условием реализуемости метрического октаэдра Л'/₂: в главе 1 будут приведены примеры таких метрических октаэдров Брикара 2-го типа К\ и К\ , для каждого из которых —ab-\-cd — ed — fc-\-ef = 0, в обоих случаях многочлен Q2(V) имеет единственный положительный корень (кратности 2), но Щ допускает реализацию в виде октаэдра с ненулевым объёмом (т.е. имеем случай реализуемости положительного корня), а К\ не допускает реализации с ненулевым объёмом (т.е. имеем случай нереализуемости положительного корня).

Можно привести пример такого метрического октаэдра Брикара 2-го типа К{₂, что для него многочлен Qi(V) имеет два различных положительных корня кратности 1. Тогда из теоремы 2 следует, что каждый из этих корней реализуется как квадрат объёма, т.е. данная развёртка К\₂ имеет две различные реализации в виде октаэдров с разными ненулевыми объёмами.

Предположим, известно, что одна из этих реализаций является выпуклой (тогда другая реализация не может быть выпуклой по известной теореме Коши). Можно ли в этом случае сказать, какой именно из двух положительных корней многочлена Q^iV) является квадратом объёма выпуклой реализации? Из наглядных соображений как будто напрашивается предположение, что среди всех реализаций данной развёртки именно выпуклая реализация имеет максимальный объём, поэтому выпуклой реализации развёртки К\₂ соответствует больший корень многочлена Q2(V). Оказывается, это предположение неверно.

Ещё Бураго и Залгаллер в [7] предложили и теоретически обосновали идею построения пары изометричных вложенных многогранников с одинаковым комбинаторным строением, один из которых строго выпуклый, а другой невыпуклый, но при этом объём невыпуклого больше объёма выпуклого. Однако, попытки реализовать эту идею в конкретном виде приводят к многогранникам с сотнями вершин, и представляется затруднительным дать чёткое описание подобных многогранников. Мы же приводим пример пары многогранников с шестью вершинами, обладающих нужными свойствами (при этом многогранники заданы в явном виде: указаны координаты их вершин). Именно, оказывается, справедливо следующее утверждение:

Теорема 3. Существует метрический октаэдр К\, такой, что он может быть изометрически реализован ей³ б виде строго выпуклого октаэдра P\(Ki) и в виде невыпуклого вложенного октаэдра P2(Ki). При этом объём невыпуклого октаэдра Р2{К{) больше объёма выпуклого октаэдра P\(Ki): vol(P₂) > vol(Pi).

Реализуемость положительных корней многочленов для объёма октаэдров Брикара 1-го и 2-го типа

Сформулируем основные результаты главы 1 (теоремы 1 и 2): Теорема 1. Если многочлен Q\{V) имеет положительный корень VQ, то метрический октаэдр К допускает изометрическую реализацию в і?3 в виде октаэдра, квадрат объема которого равен VQ. Таким образом, в случае, когда развёртка является метрическим октаэдром Брикара 1-го типа, положительный корень многочлена для объёма всегда реализуется как объём реально существующего октаэдра. Теорема 2. Пусть многочлен Q2CV) имеет положительный корень V\. Тогда метрический октаэдр /1/2 допускает изометрическую реализацию в і?3 в виде октаэдра, квадрат объема которого равен V\, если выполняется одно из следующих условий: 1) Корень V\ имеет кратность 1. 2) V\ имеет кратность 2 и выполняется условие Таким образом, в случае, когда развёртка является метрическим октаэдром Брикара 2-го типа, положительный корень многочлена для объёма заведомо реализуется только в том случае, если он имеет кратность 1. В случае, когда —ab + cd—ed — fc+ef = 0 (т.е. если условие (1.4) не выполнено) и многочлен QiiV) имеет ненулевой корень Vi, то V\ обязательно имеет кратность 2, и в этом случае положительность V\ не является достаточным условием реализуемости метрического октаэдра К{2 (см. ниже примеры 4 и 5). Пример 4. Пусть Щ — метрический октаэдр Брикара 2-го типа К\2, такой, что а — 14,6 = 6, с = 24, d = 8,е = 10, / = 2. Легко проверить, что необходимые неравенства треугольника в этом случае выполняются, a —ab + cd — ed — fc + ef = 0.

Многочлен Q2{V) для развёртки Щ выглядит следующим образом: Q iV) = VQ(V — 256/9)2 и, таким образом, имеет положительный корень V\ — 256/9. Развёртку Щ можно реализовать в В? в виде октаэдра N\AiBiC\D\S\, квадрат объёма которого равен 256/9. Укажем координаты вершин такой реализации: Легко доказать, что октаэдр N\AiB\CiD\Si действительно является изометрической реализацией развёртки К\ . Для этого необходимо лишь непосредственным вычислением убедиться в том, что N\C2 = S\A\ = a = 14,iViAf = SiCf = Ь = 6,7ViL ? = SXD\ = с = 2 NYB\ = Si2 = d = 8,CiD2 = D\A\ — e — 10,AiB2 = B\C\ — f = 2. Кроме того, легко проверить, что квадрат объёма октаэдра N\AiBiCiDiS\ действительно равен 256/9. Пример 5. Пусть Л г — метрический октаэдр Брикара 2-го типа К\2, такой, что а = 140,6 = 168,с = 642,с? = 129, е = 446,/ = 9. Легко проверить, что необходимые неравенства треугольника в этом случае выполняются, a —ab+cd—ed—fc+ef = 0. Многочлен Q iy) для развёртки К\ выглядит следующим образом: QiiV) = V6( -1311152/3)2 и, таким образом, имеет положительный корень V\ — 1311152/3. Докажем, что развёртку Щп нельзя изометрически реализовать в В? в виде октаэдра, квадрат объёма которого равен 1311152/3. По теореме 2 из [15] квадрат, и длины диагонали B\D\ любой изометрической реализации NiA\B\C\D\S\ (с данным объёмом) развёртки Щ удовлетворяет некоторому полиномиальному уравнению. Используя метод работы [15], вычислим коэффициенты этого уравнения для случая V = V\ = 1311152/3; оказывается, уравнение имеет вид: (7и2 — 6426м + 2060949)2(35м2 - 32130м + 10796427)2(7м2 - 6426м + 88105299)(м2 - 918м + 224181) = О5. Легко проверить, что оно не имеет действительных решений. Следовательно, развёртка К\ не может быть реализована в виде октаэдра, квадрат объёма которого равен 1311152/3, ч.т.д. Сформулируем и докажем теперь лемму, которой мы будем пользоваться при доказательстве теорем 1 и 2. Пусть в пространстве имеется тетраэдр ABCD.

Обозначим квадраты длин его рёбер следующим образом: АВ2 = с, ВС2 — а, АС2 = 6, AD2 = d, BD2 = е, CD2 = / (см. рис. 6). Правая часть формулы (1.5) определена для любых чисел a,b,c,d,e,f, а не только для квадратов длин рёбер некоторого тетраэдра. Оказывается, положительность выражения Vr(u,b,c,d,e,f) (вместе с некоторыми дополнительными условиями) указывает на существование тетраэдра, квадраты длин рёбер которого равны а, 6, с, d1 е, /. Точнее, справедлива следующая лемма: Тогда d 0 и в Л3 существует тетраэдр ABCD квадраты длин рёбер которого равны а, 6, с, d, е, /; АВ2 = с, БС2 = а, AC2 = b1 AD2 = d, BD2 = е, CD2 = f (см. рис. 6) Замечание 2. Если числа а,Ь,с являются квадратами длин сторон некоторого треугольника, то выражение в левой части неравенства (1.6) равно 16S2, где S — площадь этого треугольника. Каждое из неравенств (1.6) и (1.7) — удобная форма записи неравенств треугольника для соответствующей тройки положительных чисел. Доказательство леммы 1. Если бы неравенство d О входило в условие, то лемма 1 была бы просто ослабленной формулировкой хорошо известного утверждения (см. [16]) (В этом случае условие (1.6), или условие (1.7) можно было бы отбросить.) Поэтому остается показать, что в условиях леммы d 0. Выражение VT(CL, Ь, С, d, е, /) является квадратным трёхчленом относительно d. Коэффициент при d2 равен —а/144 0, т.е. парабола направлена ветвями вниз. Мы хотим доказать, что Vr(a, Ъ1 с, d, е, /) может быть положительным только при d 0. Докажем, что свободный член а0 полинома Vr(a,b,c,d,e,f) неположителен. Имеем 144а0 = -be2 + e-(-b2 + bc+cf + ab-af + bf) + (-cf2-abc-fc2 + acf + bcf). Пусть D - дискриминант ао как полинома от е. Имеем Поэтому в силу условия (1.6) D 0. Следовательно, так как коэффициент при е2 в «о отрицателен, ао 0 при любом е. Итак, свободный член ао полинома Vr{a, 6, с, d, е, /) неположителен. Поэтому либо все значения d, при которых Vr(a16, с, d, е, /) 0, положительны, либо все они отрицательны. Последнее невозможно, так как существует такое do 0, что Vr(a,b,c, do,e,/) 0 (В силу (1.6) и (1.7) в it 3 существуют треугольники, квадраты длин сторон которых равны а, 6, с и а, е, / соответственно. Расположим эти треугольники так, чтобы они лежали в разных плоскостях, а их стороны длины л/а совпали. Квадрат расстояния do между вершинами этих треугольников, на лежащими на совпавших рёбрах, положителен. Объем Vr(a,b,c,do,e,f) тетраэдра, натянутого на эту пару треугольников, также положителен.) Итак, доказано, что в условиях леммы d 0. Лемма 1 тем самым доказана.

Некоторые необходимые метрические условия изгибаемости подвесок

С помощью алгоритма из [15], программная реализация которого приведена в предыдущем разделе, нельзя найти изгибаемые реализации данной развёртки (речь, конечно же, идёт о случае, когда развёртка допускает изгибаемые реализации). Дело в том, что многочлены вида (2.3) для тех малых диагоналей искомого изгибаемого многогранника, которые непрерывно меняются в ходе изгибания, становятся тождественно нулевыми. Это обстоятельство, с одной стороны, является препятствием для решения задачи изометрической реализации методом из [15], а с другой стороны позволяет получить некоторые необходимые метрические условия изгибаемости многогранников в терминах коэффициентов уравнений вида (2.3). В самом деле, пусть уравнение вида (2.3) составлено для одной из малых диагоналей d многогранника с данным комбинаторным строением К. Коэффициенты этого многочлена зависят от метрики многогранника, т.е. от длин его рёбер. В работе [15] показано, что коэффициенты многочлена для диагонали являются однородными полиномами от квадратов длин рёбер многогранника.

Предположим, что при данных длинах рёбер многогранник изгибается, и в ходе этого изгибания диагональ d непрерывно меняется. Утверждается, что в этом случае все коэффициенты построенного многочлена для диагонали d обращаются в нуль. В самом деле, в противном случае диагональ d, будучи корнем не равного тождественно нулю многочлена, могла бы принимать лишь конечное число значений, и не могла бы непрерывно меняться в ходе изгибания. Итак, обращение в нуль всех коэффициентов многочлена для малой диагонали многогранника, непрерывно меняющейся в ходе изгибания, является необходимым условием изгибаемости данного многогранника. Заме тим, что многочлен для диагонали с коэффициентами, полиномиально зависящими от длин рёбер многогранника, можно находить любым удобным способом (не обязательно использовать универсальный метод, предложенный в [15]). Ниже для многогранника определённого типа — подвески — будет предложен некоторый специальный (отличный от предложенного в [15]) способ получения многочленов для диагоналей, затем будет найден вид старших коэффициентов многочленов для диагоналей подвески, получаемых предложенным способом, и будет сделан вывод, что обращение в нуль найденных однородных полиномиальных функций от длин рёбер подвески является необходимым условием изгибаемости подвески. Изложение будем вести по нашей работе [24]. Подвеской, или бипирамидой называется многогранник, комбинаторная структура которого изображена на рис. 10, а. Вершины N и S называются полюсами подвески, а ломаная VQV\...vn — экватором подвески. Известно (см., например, [5]), что для произвольной пятёрки точек А\, А2, A3, А4, А5 в і?3 квадраты d i,j — 1,2,3,4,5 (djj = dji 0, da = 0) попарных расстояний между ними удовлетворяют уравнению Кэли- (2.5) Детерминанат в левой части равенства (2.5) называется определителем Кэли-Менгера для точек А\, А Аз, Aj, А. Рассмотрим подвеску, изображённую на рис. 10, а. На рис. 10, б изображён экватор этой подвески, а на рис. 10, е — её фрагмент, содержащий 5 вершин. Последние два рисунка сделаны лишь для того, чтобы не загромождать обозначениями основной чертеж (рис. 10, а) Запишем уравнения Кэли-Менгера для следующих пятёрок точек: (N,S,vQ,vi,v2y, .- ; (iV,5, 0, -, +1)5 ... ; (N,S,v0,vn-i,vn). В этих уравнениях кроме известных длин рёбер подвески, ещё участвуют неизвестные длины её диагоналей D2, D$,..., Dn-2, Dn-i, Н := \NS\ (рис. 10). Получаем систему для п — 1 неизвестных с п — 1 полиномиальными уравнениями вида: В левой части каждого из уравнений системы (2.6) в качестве аргументов указаны неизвестные, входящие в данное уравнение. Здесь и далее в этом разделе длина отрезка обозначается заглавной латинской буквой, квадрат этого же расстояния — соответствующей строчной буквой; так, например, d{ = D2,h = Н2. Замечание 5.

В случае п = 3 подвеска является октаэдром, и в системе (2.6) только два уравнения ("первое", и "последнее"). В случае п = 2 подвеска является пятивершинником, и система (2.6) вырождается в единственное уравнение, левая часть которого представляет собой определитель Кэли-Менгера для точек (JV, 5, і о, г ъ i )- Единственной неизвестной в этом уравнении является h, таким образом в случае пя-тивершинника многочлен для (единственной) диагонали Н = \NS\ мы имеем уже на первом шаге алгоритма без каких бы то ни было вычислений. Известно, что из двух полиномиальных уравнений, содержащих общую переменную х, можно исключить ж, взяв в качестве нового уравнения (не содержащего х) приравненный нулю результант (т.е. детерминант матрицы Сильвестра) двух многочленов по х. Поэтому последовательным исключением любых п — 2 неизвестных в системе (2.6) можно получить уравнение с левой частью в виде многочлена от длин рёбер и оставшейся неизвестной диагонали. Так можно получить многочлен для любой диагонали подвески, в том числе для любой её малой диагонали. В частности, многочлен для диагонали Н = \NS\ мы получим последовательным исключением G?2, 3v? dn-i: а многочлен для диагонали Dn_\ — последовательным исключением б?2, 4-і n-2, h. Предложенный способ получения многочлена для диагонали подвески далее будем называть "способ 1". Для доказательства теорем 4 и 5 (см. ниже) необходимо будет изучить структуру промежуточных выражений, получаемых при решении системы (2.6) способом 1. Введём следующие обозначения: где i?( _3(dm_2,/ ),i?m_2(dm-2,dm--i,/0) — результант выражений -Е"га-з( -25 h) и Em-2(dm-2, с?т-ь h), рассматриваемых как многочлены относительно с?т_2, т = 4,5,..., п. Теперь промежуточные системы уравнений, получаемые при последовательном исключении неизвестных в системе (2.6) способом 1, можно записать следующим образом:

Понятие 5-комплекса и некоторые свойства 5-комплексов

Основной целью этого раздела является введение понятия 5-комплекса, исследование вопроса о существовании б -комплексов и доказательство некоторых необходимых в дальнейшем утверждений о -комплексах. Следует помнить, что все утверждения данного раздела носят чисто комбинаторный характер, несмотря на то, что большинство из них допускает простую геометрическую интерпретацию. Пусть К — произвольный симплициальный комплекс, с носителем, го-меоморфным некоторому двумерному связному ориентируемому многообразию М2. Комплекс К можно представлять себе как некоторое множество евклидовых треугольников с заданным законом отождествления сторон и вершин, при этом после отождествления должно получиться многообразие, гомеоморфное М2. Симплексы размерностей 0,1 PI 2 комплекса К нам будет удобно называть, соответственно, вершинами, рёбрами и гранями комплекса

К. Множество вершин, множество рёбер и множество граней комплекса К мы будем обозначать V(K), Е{К) и F(K), соответственно. Поскольку supp/i М2, где М2 — двумерное многообразие (в общем случае одно с краем), можно утверждать, что всякое ребро комплекса К принадлежит либо ровно одной грани, либо ровно двум граням комплекса К. Те рёбра комплекса К, которые принадлежат только одной грани комплекса К, мы будем называть граничными, остальные рёбра — внутренними. Одномерный симплициальный комплекс, который образуют граничные рёбра комплекса К мы будем обозначать дК и будем его называть граничным комлексом. Наконец, мы скажем, что две грани комплекса К, имеющие общее (внутреннее) ребро, являются смежными по этому ребру. При этом комплекс К\ мы будем называть S-диском S-комплекса К. Пример 6. Любой S-диск является S-комплексом. Пример 7. Пусть К — комплекс, задающий комбинаторное строение октаэдра (см. рис. 11). Легко видеть, что изображённый нарис. 11 комплекс К\ С К является S-диском, и, так как V(K\) — {v\, г 2, г з, VA-, vbi 6 } = V(K), можно сделать вывод, что К является S-комплексом. Каждый из изображённых на рис. 11 комплексов А , Л з и К\ также является S-диском S-комплекса К. Пример 7 показывает, что 5-диск данного 5-комплекса может быть не единственным. Более того, оказывается, что для любого 5-комплекса с носителем, гомеоморфным двумерной сфере 52, всегда можно указать по крайней мере два 5-диска: Лемма 6. Пусть дан 5-комплекс К, такой, что supp А 52. Пусть К\ С К — его S-диск. Тогда у К имеется ещё по крайней мере один S-диск ІІ2 ф К\. Доказательство. В самом деле, поскольку границей диска D2 является окружность S1, то из того, что supp А і D2, следует, что suppdA i S1. Окружность 51 разбивает сферу S2 на два диска D21 следовательно, граница дК\ 5-диска Л і С К разбивает комплекс К на два комплекса, носитель каждого из которых гомеоморфен диску D2. Одним из этих комплексов является комплекс К\.

Докажем, что второй комплекс К2 является 5-диском для S -комплекса К. Действительно, во-первых, по доказанному suppK2 D2; во-вторых V(K2) С V(K) = V(KX) С dV(KL) = dV(K2). Лемма доказана. Заметим, что в примере 11 дК\ = дК2, и дКч — дК Напомним теперь определение гамильтонова цикла: Определение 9. Пусть К — некоторый двумерный симплициальный комплекс. Мы будем говорить, что одномерный симплициальный комплекс Н С К является гамилътоновым циклом е К, если он обладает следующими свойствами: йными словами, гамильтонов цикл — простой цикл из рёбер, прохо дящий через все вершины. Пример 8. Комплекс К из примера 7 (см. рис. 11) имеет по крайней мере два гамилътоновых цикла: Н\ — ( 1, 5, 2,1 ,173, 4) 11 Щ = (V1,V2,V3,V4,U6,V5). Лемма 7. Пусть К — некоторый симплициалъный комплекс. Тогда, если К является S-комплексом, то в К имеется по крайней мере один гамилътонов цикл. Доказательство. Пусть К\ С К — некоторый 5-диск 5-комплекса К. Тогда комплекс Н = дК\ является гамильтоновым циклом в К. Лемма 8. Пусть К — некоторый симплициалъный комплекс, такой, что supp A S2. Тогда, если в К имеется гамилътонов цикл, то К является S-комплексом. Доказательство. Пусть Н С А — гамильтонов цикл. Подобно тому, как это было сделано в доказательстве леммы б, рассмотрим комплекс К\ С К — один из двух комплексов, на которые цикл Н разбивает комплекс А , и сделаем вывод, что К является S-комплексом, а К\ является S-диском -комплекса К. Лемма доказана. В дальнейшем нам понадобится следующее понятие: следуя [13], мы будем говорить, что трехзвенный цикл из рёбер комплекса К является пустым, если он не является границей ни для какой грани комплекса К. Так, например, комплекс А , изображённый на рис. 11, не имеет ни одного пустого трехзвенного цикла, а комплекс, изображённый на рис. 12, имеет пустой трехзвенный цикл ( 2, 3, 4) Доказанная в [23] теорема о существовании гамильтонова цикла у комплекса, обладающего некоторыми свойствами (см. ниже), позволяет нам получить условия, выполнение которых достаточно для того, чтобы данный симплициальный комплекс К являлся 5-комплексом. Эти условия даются следующей леммой: Лемма 9. Пусть К — произвольный симплициальный комплекс с носителем, гомеоморфным сфере S2. Тогда если в К нет пустых трехзвенных циклов из ребер, то К является S-комплексом.

Об алгоритмическом решении задачи изометрической реализации

Теорема 7. Пусть дана некоторая развёртка К[, такая, что suppil/ S2. Тогда решение задачи изометрической реализации развёртки К\ в виде многогранника в Rs сводится к нахождению всех решений некоторой системы полиномиальных уравнений, или к решению нескольких таких систем. Доказательство. Докажем теорему индукцией по числу вершин к комплекса ii/. Основание индукции: если к = 4, то комплекс К\ комбинаторно изоморфен тетраэдру. Тетраэдр, очевидно, является 5-комплексом, и к Л/, таким образом, применима теорема 6. Предположим теперь, что утверждение доказано для всех комплексов с числом вершин к п. Пусть дан комплекс К і с п вершинами. Докажем, что решение задачи изометрической реализации развёртки К[ в виде многогранника в Л3 сводится к нахождению всех решений некоторой системы полиномиальных уравнений, или к решению нескольких таких систем. Рассмотрим два случая. Случай (А). В К\ имеется пустой трёхзвенный цикл ( -,1 , ) из рёбер. Разрежем А / по этому циклу; получим два комплекса Kf и Kf, такие, что suppA / — D2, і — 1,2, и дЩ = (vj,Vk,vi), і = 1,2. В каждом из комплексов Kf и Kf заклеим имеющуюся треугольную дырку, добавив грань (vj,Vk,vi); получим комплексы Kf и Kf, такие, что suppA/ — $2i і = 1,2. Число вершин каждого из метрических комплексов А 1 и Kf меньше п, поэтому для каждого РІЗ НИХ ПО предположению индукции решение задачи изометрической реализации в виде многогранника в І?3 сводится к нахождению всех решений некоторой системы полиномиальных уравнений, или к решению нескольких таких систем. Рассмотрим некоторые изометрические реализации Pi и / комплексов Kf и Kf в Л3 в виде многогогранников P\{Kf) и / (- 2) соответственно. "Склеив" многогогранники P\(Kf) и P Kf) по их изометричным граням Pi((vj,Vk,V{)) и P2((vj,Vk,vi)), мы, очевидно, получим некоторую изометрическую реализацию исходного комплекса А/. Очевидно также, что любая изометрическая реализация комплекса Ki может быть получена "склейкой" некоторых изометрических реализаций комплексов Kf и Kf. Тем самым доказано, что решение задачи изометрической реализации развёртки Ki в виде многогранника в R5 сводится к решению систем уравнений для комплексов Kf и Kf, и шаг индукции в случае (А) сделан. Случай (Б). В Ki нет ни одного пустого трёхзвенного цикла из рёбер. Тогда к Ki применима лемма 9 (см. раздел 3.2), согласно которой А / является 5-комплексом. По теореме 6 (см. раздел 3.3) решение задачи изометрической реализации 5-комплекса А/ сводится к решению некоторой системы полиномиальных уравнений (системы вида (3.6) или (3.8)), или нескольких таких систем. Шаг индукции в случае (Б) сделан. Теорема тем самым доказана.

Доказательство теоремы 7 даёт рекурсивное описание алгоритма сведения задачи изометрической реализации данной развёртки К\ в виде многогранника вй3к решению некоторой системы полиномиальных уравнений, или нескольких таких систем: 1) Если в данной развёртке имеется пустой цикл, то разрезав развёртку по этому циклу и заклеив в каждом из полученных кусков образовавшиеся при этом треугольные дыры, мы получим две развёртки с носителем, гомеоморфным 52, в каждой из которых вершин меньше чем в исходной развёртке. К каждой из полученных разверток применить данный алгоритм. 2) Если в данной развёртке нет ни одного пустого трёхзвенного цикла, то методом перебора найти некоторый 5-диск, содержащий все вершины развёртки К\ (по лемме 9 из раздела 3.2 такой 5-диск существует). 3) В качестве параметров выбрать величины двугранных углов при рёбрах искомого многогранника, соответствующих внутренним рёбрам найденного 5-диска. 4) В соответствии со схемой, предложенной в разделе 3.3 (см. доказательства лемм 12 и 14) составить систему уравнений относительно введённых параметров. 5) Свести составленную систему уравнений к системе полиномиальных уравнений, или к нескольким таким системам (см. леммы 16 и 17). Таким образом, нахождение изометрических реализаций данной развёртки сводится к нахождению реализаций некоторых других развёрток, в каждой из которых вершин меньше, чем в исходной развёртки, до тех пор, пока каждая из новых развёрток не станет « -комплексом. Ко всякому (S-комплексу уже применим метод решения задачи изометрической реализации, основанный на составлении систем полиномиальных уравнений, предложенный в разделе 3.3.

На неформальном уровне предложенный алгоритм можно представлять себе следующим образом: пустые трёхзвенные циклы разбивают данную развёртку типа сферы на несколько кусков, каждый из которых (после заклейки дырок) уже не имеет пустых трёхзвенных циклов, а потому является 5-комплексом, задача изометрической реализации которого сводится к решению систем полиномиальных уравнений методом, предложенным в разделе 3.3; всякая реализация исходной развёртки — результат склейки по пустым трёхзвенным циклам некоторых реализаций её фрагментов, являющихся S-комплексами. Отметим, что несмотря на то, что теорема 7 доказана только для развёрток топологического рода д = 0, предложенная методика в принципе позволяет работать и с развёртками высших топологических родов (g 0). В частности, каков бы ни был род развёртки it/, при условии, что комбинаторная структура её задаётся 5-комплексом К (то есть в К имеется некоторый 5-диск, содержащий все вершины комплекса), к задаче изометрической реализации развёртки К\ применим метод раздела 3.3. При д 0 в системе (3.3) число уравнений больше числа неизвестных (см. также замечание 10). Вопрос о том, как устроен класс 5-комплексов с носителем, гомео-морфным многообразию произвольного топологического рода д 0, нами не изучался. Предложенный выше метод позволяет свести решение задачи изометрической реализации к решению системы полиномиальных уравнений, или нескольких таких систем, однако не даёт никакого способа решения найденных с его помощью систем уравнений. Вопрос о решении систем полиномиальных уравнений остается за рамками нашей диссертации; по этой теме существует обширная литература (см., например, [8] и [9]). Необходимо отметить, что во многих случаях задача нахождения всех решений системы полиномиальных уравнений с любой наперёд заданной точностью является алгоритмически разрешимой. Однако, всё же следует признать, что абсолютно универсального алгоритма нахождения всех решений данной системы полиномиальных уравнений не существует (сложность решения таких систем связана с тем, что помимо изолированных решений, системы алгебраических уравнений могут иметь целые многообразия решений, каждое из которых, в свою очередь, описывается некоторой системой алгебраических уравнений). Однако, для многих систем полиномиальных уравнений может быть получен полный список решений. Для решения систем полиномиальных уравнений можно использовать как общую теорию, основанную на составлении т.н. базиса Грёбнера (см. [8] и [9]), так и какие-либо специальные методы. В следующем разделе данной главы будет продемонстрировано, что предложенный в разделе 3.3 метод сведения решения задачи изометрической реализации к решению систем полиномиальных уравнений во многих случаях приводит к таким системам, для которых можно получить полный список их решений. Заметим, что большинство задач, решённых в следующем разделе, не удаётся решить ни методом, основанным на составлении системы вида (3.1), ни с помощью алгоритма Сабитова.