О сложностных характеристиках способов задания и комбинаторной неоднородности выпуклого многогранника в R3 тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

САМАТОВА Нагиза Фаридовна

УДК 519.95

О СЛОЖНОСТНЫХ ХАРАКТЕРИСТИКАХ СПОСОБОВ ЗАДАНИЯ И КОМБИНАТОРНОЙ .НЕОДНОРОДНОСТИ ВЫПУКЛОГО МНОГОГРАННИКА В И3

Специальность 01.01.09—Математическая кибернетика

Автореферат диссертации на соискание степени кандидата физико-математических наук

Москва—1993

Работа выполнена на кафедре прикладной математики факультета прикладной математики и механики Ташкентского государственного университета.

Научный руководитель —

кандидат физико-математических наук,

доцент А. К. Пулатов

Официальны« оппоненты:

доктор физико-математических наук, Н. П. Редькнн

кандидат физико-математических, наук Н. Н. Кузюрин

Ведущая организация — Московский педагогический государственный университет им. В. И. Ленина.

Защита диссертации состоится 1993 г.

в ¡2) часов ОО мин. на заседании специализированного Совета К 002.S2.02 при Вычислительном Центре РАН по адресу: 117967, Москва, ГСП-1, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке

Математического института РАН,

Автореферат разослан « / ¥ > ¿¿М^ 1993 г.

УченьгЗ секретаре специализированного Совета доктор физико-математических

наук К. В. Рудаков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальнхть тени. Известно, что выпуклый иногогранник, как один из фундаментальных объектов математики, привлекает вникание ммогих исследователей. Это объясняется, по-видимому, следующими моментами: непустое множество решений конечной системы линейных неравенств является выпуклым многогранником} выпуклая оболочка конечного множества точек евклидова пространства есть также выпуклый многогранник; выпуклые тела аппроксимируются выпуклыми многогранниками: многие природные образования и технологические изделия имеют форму многогранника (алмазы, ювелирные изделия, разного рода детали , И предметы) и др.

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

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

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

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

Значительный интерес в комбинаторной теории многогранников представляет решение проблемы о необходимых и достаточных условиях существования 3-свяэного пленарного графа, каждая из вершин и граней которого имеет заданное число смежных (проблема Эберхарда). Естественным является вопрос о том, сколько максимум (показатель ' неоднородности многогранника) вершин различной степени может иметь граф многогранника.

Одно из классических направлений в метрической теории многогранников связано с вопросами существования и единственности многогранника с теми или иными данными. Классическая теорема О.Кошн гласит: два комбинаторно эквивалентных многогранника, у которых равны соответствующие элементы (ребра и плоские углы), равны. Теорему Коши можно отнести к комбинаторно-метрической теории выпуклых многогранников, т.к. ока рассматривает многогранник в к3- как граф, на котором заданы значения его метрических параметров.

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

Диссертация посвящена исследованию вопросов комбинаторной и комбинаторно-метрической теории выпуклых многогранников, имеющих естественное теоретическое, либо практическое значение. Центральное место в ней занимает изучение новых, комбинаторно-метрических, способов задания выпуклого многогранника в к3. Такое двухуровневое задание многогранника описывается совокупность!) двух типов параметров: комбинаторным, каким является граф многогранника, и достаточным числом метрических параметров. При этом исследуются характе-■ ристики сложности этих способов задания и "устойчивости" многогранника к малый деформациям, т.е. изменениям определяющих

его параметров. На значение этих характеристик, оказывается, существенно влияет "неоднородность" многогранниы, которая изучается посрьдством исследования числа вершин различной степени 3-связного пленарного графа (комбинаторная неоднородность) и покрываености подмножества вершин графа многогранника его К-мерными гранями. Изучение равномерной линейной деформации продиктовано приложениями теоретических результатов диссертации к практическим задачам.

Цель работ». Исследование характеристик неоднородности выпуклого многогранника на основе изучения, с одной стороны, степенного спектра вершин 3-связного пленарного графа, с другой, - сложности покрытия поднножес""а вершин графа многогранника его К-иерныни гранями.оУстановление оценок сложности способов задания выпуклого многогранника, базирующихся на графе многогранника. Исследование меры комбинаторной неустойчивости многогранника к налым изменениях его метрических параметров при различных способах его задания. Рассмотрение ласса деформированных многогранников, порождаемых равномерными линейными деформациями исходного многогранника. Описание комбинаторно нсизменчивых многогранников при" таких деформациях.

Методы исследований. В работе используются методы дискретной математики и математической кибернетики.

Научная новизна. В диссертации установлены оценки максимального числа вершин различной степени, которые ножет иметь граф многогранника, максимального значения меры комбинаторной неустойчивости многогранника к малым изменениям параметров его задания, при этом получены окончательные результаты о сложности комбинаторно-метрических способов задания при рассмотрении различных типов метрических параметров: а также найдены оценки максимальных значений неко- торнх характеристик сложности покрытия подмножества вершин графа многогранника его к-гранями №=0,1.2): в качестве приложений рассмотрен процесс "растворения" многогранника при его равномерных линейных деформациях и получен критерий комбинаторной неиэменчивости многогранника при таких деформациях.

шестая и теоретическая ценность. Диссертация в сс-

козион носит теоретический характер. Результаты диссертации могут быть использованы в теоретических работах при изучении комбинаторно-метрической структуры выпуклых многогранников. • Комбинаторно-метрические способы задания представляют также и практический интерес, например. при вводе в память ЭВМ серии ■ многогранников заданного комбинаторного типа, что позволяет во многих случаях сэкономить число метрических параметров задания многогранника. Следует также сказать, что моделирование * процессов горения и растворения однородных тел формы выпуклого многогранника приводит к рассмотрении равномерной линейной деформации.

Апробация работа Результаты диссертации докладывались \ ка вколе-семинаре "Дискретная математика и ее приложения" (Москва, 1988), на Всесоюзной школе "Дискретная катекатика и ее применение при.моделировании сложных систем" (Иркутск, 1931), на И школе-семинаре "Синтез к сложность управляхидих систем" (Ташкент, 1991), на IV Межгосударственном семинаре по дискретной математике и ее приложениям (Москва, 1993), на семинарах по дискретной математике и ее приложениям в ТаиГУ (1988-19^2).

С-^уктура и обьеи работы. Диссертация состоит из введения, четырех глав и списка литературы, включающего 44 наименования. Первая глава разбита на 2 параграфа, вторая - на 2, третья - на з, четвертая - на 3. Объем работы 84 страницы.

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

По те*в диссертации опубликовано 4 работы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

предварительные сведения,

используемые в работе.

б

Вторая гласа посвящена исследования« комбинаторной структуры выпуклых многогранников, т.е. графоа многогранников.

В параграфе 2.1 изучается степенной спектр верзнн З-сзязшго пленарного графа посредство» решения следующей задачи. Пусть множество вершин У многогранника М разбито на классы эквивалентности так, что все верпинц с одинаковой степенью образуют один класс. Тогда для многогранника И число l:(ü) таких классов будем называть погазателек неоднородности !i. Требуется оценить максимальное значение R(ü) в множестве 5JCDD всех комбинаторно различных многогранников с D взр-пинами, то есть функцию Шенноня:

К(В) = пах К(й) Mt Э(В)

В теореме 2.1 устанавливаются следующие оценки введенной характеристики:

. . - 2/d+IOMS s К(В) S -L + 2/B-79^16, В*5.

D параграфе 2.2 вводятся необходимые определения и обоз-, начения, приводится постановка задачи покрытия вершил графа выпуклою многогранника его к-мерными гранями (fc-o.i;2) и формулируются результаты.

Пусть я (В) и я СП ~ классы комбинаторно-различных З-мнсгограиников с В вершинами и Г гранями соответственно, VXM) - множество вершин 3-многогранника Ке ^CD) или te п СП. Требуется найти значение следующей характеристики слозшостн покрытия подмножества верпин 3-нногогршшнка его к-гранякн:

1 (В)= и азе пах 1_(М.Г),

Vd»(D) V'£V(И) ^

где 1C(H,V') - максимально возможное число Ссложность тупикового покрытия) иаксииалышх.огнссителыш вложения в множество V, к-граней 3-многогранника Иеи (В), содержащихся к в совокупности покрывающих множество V', причем никакое подхнокзет-во этих к-граней не образует покрытие множества V'. Аналогичная характеристика, но в класса ЗСГ) изучалась Пулатовын А.К. и Кондратьевой О.Б. (Сроке того, кнк, а также В.Я.Памунловын, проводились исследования по оценке максимального н типичного

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

Исследование задачи покрытия всех вершин многогранника его 2-мерными гранями представляет особый интерес, так как сложность таких покрытий раскрывает меру неоднородности данного многогранник? Введем следующее обозначение:

к„(В)= шах к.(К), где к.(И) - максимальное значение

с меИ(в) с ■ ь

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

Получены следующие основные оценки макимальных значений характеристик сложности покрытия подмножеств вершин 3-мно-гогранииков их к-гранями (к=о,1,2):

а) 1С(В) = 1-|-(В-2)). В£ 5.

® ^М1' * кс(В> * 3 " -§-'Вг4'

Т|>етья глава посвящена комбинаторно-метрическим исследованиям гыпуклого многогранника, продиктованы* рассмотрением и

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

Б шраграфе 3.1 приводятся традиционные способы задания

выпуклого многогранника в к3 и их сложность.

В параграфе 3.2 исследуется задача сложности задания выпуклого многогранника в к3 при условии, когда известен граф многогранника (комбинаторный тип многогранника). Способ задания выпуклого многогранника как графа, на котором определены значения метрических параметров, называется комбинаторно-метрическим. В качестве метрических параметров рассматриваются следующие варианты:

1) расстояние между вершинами;

2) тройка декартовых координат, определяющая положение вершины многогранника;

3) четверка коэффициентов линейного уравнения, определяющая положение плоскости грани (этот случай двойственен

случаю 2}) многогранника.

Получены следующие результаты:

а) минимальное число Ь,Ш(Р)) расстояний меаду вершинами. по которым однозначно определяется выпуклый многогранник ИСР) с Р ребрами при условии, когда известен его граф

Х.,(ИСР» = Р.

Разработан алгоритм подбора тех Р расстояния, с помощью которых однозначно определяется и с данным графом.

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

+ 2 4 ь2<ю» а в.

Отметим, что о оценки достинимы.

^ В параграфе 3.3 исследуется вопрос "устойчивости" многогранника и к малым изменениям определяющих его параметров при данном способе задания X. В этом параграфе рассматриваются две формы задания многогранника: первая - в виде выпуклой

оболочки своих вершин, вторая зг - как мноаество решения конечной системы неравенств. Кроме того, рассматриваются описанные способы задания выпуклого многогранника при условии, что известен граф многогранника, т.е. соответствующие им комбинаторно-метрические способы З3 и 5Д.

Многогранник 11 будем называть комбинаторно неустойчивым при данное способе задания в , если существуют сколь угодно

малые изменения определяющих его параметров, приводящие к многограннику другого комбинаторного типа. При этом, число всех комбинаторно неэквивалентных многогранников, порождаемых от исходного многогранника ¡1 при всевозможных сколь угодно малых изменениях метрических параметров задания Н, будем назывшь мерой комбинаторной неустойчивое!и II при данном способе задания 31 и обозначать ).

Требуется оценить значения следующих характеристик;

Р(Г,8г)=иш: 1(Г)=ва1 "¡¡'V .

г Ы(Г) г М(Г, нк.в^

где максимум берется по всем многогранникам с Г гранями; и двойственных им характеристик:

УШ.Б.Нши ?(М.Б ), У(В)=ша1 ,

1 И(В) 1 «(В) г<"'8э''

где максимум берется по всем многогранникам с В вершина«;. Установлены следующие основные результаты: а) справедлива следующая оценка

Г(Г.З-) Й ----, г>103.

2 2(/гТ-Ч|)1о-1,Г

Л—9

б) ЦГ) > —-. Г*К.

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

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

В параграфа. 4.1 приводятся постаноока задачи и предва-р«пелышо результаты. Пусть вапуклыя многогранник в декартовой системе координат задан с помощью конечной 1 системы линейных нераЕ'.^ста:

А1х + + 01с +С1 з 0. Ь-ГГг.

где СА1,В1,01) - нормаль 1-о? грани, спрэд глягг.ая угловой па-

•4 раматр 1-ой грани, С, - г.инешшя параметр 1-оп грани и качано

координат распопоаеко вкутрк многогранника.

Изменение линейного параметра кахдая грани многогранника

И!

ка одну п ту гл есяичииу в зтлравлешш вилряикй лормаяя рнзсэтся рззксаериой лаиеккоа десрориащ. л яюгсграшжка (РЯД).

Пусть многогранник Ы0 подергается рашюмернол ямнейзюя

А&Ьориацнз!, т.е. дазю зшпреривное семейство шюгогразншков ЪЦ, где Иг - многогранник, порожденный от зшсгограшшзса Ц0 а

момент времени ь. Обозначим через гкон иоиент полного

"растворения" исходного многогранника И0, а через 3(М0,РЛД) -

зсласс комбинаторно различных многогранников в семейства иногогранннков Мг, г«1го,гкон ]. Нерол комбинаторной изкенчн-

рости многогранника Н0 при его равномерной линейной дефор-

нацнн будем называть мощность класса. 3(М0,РЛД) и обозначать

||1(Н0.РЛД)||.

Параграф 4.2 нацелен на локально описание деформации шюгограшшка в окрестности каждой его верзины и установлена качественных харазстеристик равномерной линейной деформации выпуклого многогранного угла.

Пус;ь боковые грани п-гранного угла Мп описнвазотся згор-

кальЗшми уравнениями плоскостей

А1Х + В1у + С1а +С1 = 1=1Тп, п1=(А1,в1,с1) - внешняя нормаль 1-ой боковой грани Г1, причем

Г1пГ1+1. 1=1,п, Г^^Г.,, есть ребро этого многогранного угла.

Показано, что НЭСМ^ЛД)||=1 тогда и только тогда,

когда точкз! с координатами (А1,В1,С1) лежат в одной

плоскости (теорема 4.1).

В этом параграфе также установлено, что при изучении влияния равномерной линейной деформации многогранного угла на изменение его комбинаторной структуры достаточно рассматривать лишь малые ("начальные") деформации, т.е. бесконечзю малые изменения линейных параметров боковых граней мзюз-огранного угла (теорема 4.2). Кроме того, для каждого многогранного угла Ип „мера его кпмбинатот-'чпй изменчивости

п

IIS (кп.РДГОП *■ г (теорема 4.3).

В параграфе 4.3 описаны возможные комбинаторные изменения, происходящие с многогранником при его равномерной линейной деформации, а также описан класс комбинаторно неизменчивых многогранников: 119 (II,, РЛД) 11-1 тогда и только тогда, когда в многогранник М„ можно вписать шар.

Автор выражает искренних) благодарность А. К. пулатову за научное руководство и помощь при подготовке диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИЙ

Шлучепы оценки максимального значения к(В) числа вершк; различной степени в классе многограинигаэв с В вершинок;.

Получены окончательные результаты о сложности (минимальное число метрических параметров) комбинаторир-мэтрическк спосоГ' >в задания многогранника.

Оценены максимальные значения F(I\S4) и Y( Г) моры комбинаторной неустойчивости многогранника U к малый изменениям его метрических параметров при данной способе S4 задания М и разброса мер комбинаторной неустойчивости I! при его традиционных способах гадания и соответствупвртх 1соибинаторно-метрических.

ПУБЛИКАЦИИ ПО TEVE ДИССЕРТАЦИИ

1. Цулатов А. К , Саматова Е Ф. О сложности • задания выпуклого многогранника в R*. - Дискр. мат., том 3, вып. 2, 1091. - С. 148-156.

2. Саматова Н. Ф. О мере комбинаторной изменчивости многогранника в ^при его равномерной линейной деформации. Рук. деп. в ГОНГИ ГКНГ РУз. - Ташкент, 17.0Е. 03, N 1798-УзЭЗ.

3. Саматова Е Ф., Пулатов А. К Оценка меры комбинаторной изме! чивости выпуклого многогранника при ограниченных деформациях. Рук. деп. в Г НОТ И ГКНТ РУя. -Ташкент, 17.02.93, N 1799 - Уэ93.

4. Саматова Е Ф., Ойрокова О. В. Шк^имальнк? значения некоторых характеристик покрытия вершин З-мяогограникта. й>тоды дискретного анализа в теории грчфпр и сложности. ■ Hi-цогибирск, 1В9" - Run. - С. 85 -93.

U