Синтез и сложность синтеза графов выпуклых 3-многогранников тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

РГб ОД

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

БИТЮЦКАЯ Наталья Ивановна

УДК 519.95

СИНТЕЗ И СЛОЖНОСТЬ СИНТЕЗА ГРАФОВ ВЫПУКЛЫХ 3-МНОГОГРАННИКОВ

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

АВТОРЕФЕРАТ

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

Москва — 1994

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

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

доктор физико - математических наук, профессор А. К. Пулатов

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

доктор физико - математических наук, А. А. Сапоженко

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

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

Защита диссертации состоится «. » 1ОД4 г

в ¿3 . часов ^^ мин. на заседании специализированного Совета К 002.32.02 при Вычислительном Центре РАН по адресу: 117967, Москва, ГСП-1, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Математического института РАН.

Автореферат разослан « ^ » тещ г

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

К- В. РУДАКОВ

ОКШЬ ХАРШЕП1СТНКА ГАГО'Ш.

vejbjiocj.kji инц. Рыпуоия многогранник явно или неявно •nonr..':-::'!ici! со roex • направлениях КаТРИПТИКИ. Большинство тещетячк-кнх задач Сзадачн лшимигаиии, дискретной и кокби-каюрной г^-истрии и т.д.] славятся для выпуклых тел, и для ИХ рек«1!5Ш КСП0:'ЬЗУР1СЯ СВ0ЯС1ВЯ выпуклых многогранников. Мпспдо лпшршлич': калачи "атас приводят к задачам на выну г л их НИ'..Г0!ТШ1И1!КЗХ. Этим ОбЬИСНЯЙТСЛ постояннее снимание, КССЛСЛУСЧТСЛСЯ К "ЫЛУКЛОМУ многограннику.

Ипсюящая диссертация' нсквлцеио изучению комбинаторных И KCMi»!иатотсю-жл рмчееккч свойств выпуклого xttoroi р&иника в н1 чл-ниогсграин'ика) . посредсгвом построения алгибри гра-ф,:г. много-раннихшз на основе специальной операции - склейки ,чо i'p-'iii.'iM. Естественным является стремление выделить в класс» вссч гр?4<зв З-кпогогранюисов базис относительно' этой операции так, '¡та';!) детой граф 3-многогранника с точностью до изомор-фнома чожнэ било синтезировать из элеменгой базиса.

Лнятогиччсне исспе.аования в теории натуральных чисел, Kai: иэьеспю, приведи к выделению щостых чисел, с помощью кого-рух w-roiu представить, любое натуральное число. Такого рода иссяедснанил проводились к в метрической теории выпуклых многогранников, где г. к?чесш? операция гэсскцтришл&сь сунна Минковского,

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

Общая задача синтеза связных планарннх графов на основе операции склепки но подграфам ручалась pquee H.A. Иорданским. йи найдены конечные базисы относительно этой cnepai-цин для трех классов связных планерных графев: класса есох деревьев, каксикаяьных вневшелдакаркых гра:',сз и максимальных триангулированных плана рннх гр&фсв. Только последний из этих классов содержится в классе всех грд-дсс сылуклых многогранников СЗ-связкых ллаиарпих vpaace). М.А. Иорданский показал, что пх<'оя какехкалышя триангуяирсЕашшй граф с числом вер-

шин п>з мсйно получить склепкой но ррашт графой к( , (где к, - полный граф с 4-мл вершинами). С^ако, задача (юхокдашя базиса дли других графов «ногограииккоь намного сложнее.

Исследование тех или иных сло::;!юстнцх характеристик объектов составляет важнее направленно математической кибернетики. Одной из. основных задач диссертации является лзу-чеаие.сложноетнцх . характеристик синтеза (склейки) гр&1»в З-миогосрашшков. В коде исследования аадачи синтеза графов •'З-иногограшшков было обнаружено, что один и тот ке граф, воосао говоря, ножет бить синтезирован нескольким способами н из различного числа базисных гра^од, т.е. инее г место своего Рида кногиэкстренальпасть. Пад сложностью юпиеротиого синтеза графи многогранника понимается число базисных графов, участвующих в этом синтезе. Изучаютсн максиуальнан и ыи-иииальнан сложности синтеза, а такл:е разброс сложнсеги синтеза графи многогранника как (л-кошшо ьашшшыюги числа базисных графов, из'которых одкно склеить ыот 1'раф, к минимуму этого числа, максимальную и минимальную сшшюти синтеза, разброс слоашости сшпеза графа 3-кногограшшка можно рассматривать как сто новые слопиюстаыо характеристику.

В теории графов ¿'выпуклых многогранников числа возникает необходимость пострсстш последовательное«;}! грифов или' многогранников с растущик числом вершин," удовлетворяющим определенным условиям, например, принимающих экстремальные значении, таких своих характеристик, как диаметр, толщина, радиус, неплотность, сложность покрытия вериин многогранника его К-мерными грандии, мощность совершенных сНгодов графов Многогранников.' В диссертации изучается возможность лрикене-> Ним сшпезного подхода при построении таких после,доьателыюс-тей выпуклых многогранников.

Цель работы состоит:

- в исследовании комбинаторной структуры выпуклого многогранника посредством построения алгебры графов многогранников

' на основе операции склепки но граним;

- в нахождении критериев неразложимости графов многогранников относительно операции склейки по граним и описании класса базисных (неразложимых) графов;

- а установлении оценок сложности, синтеза и разброса

сдсякнесш синтеза произвольного графа многогранника с п гранями на базе склсякн по граням; .. ...

- в изучении взаимосвязи между--нёкоторини известными своп-• ствамк к характеристика«:«- графов- многогранников и .операцией

склепки но граним-.

1,1!1тодц^сследоваи!»1. В работе -иснояьзуотся магсди дискрет ноя натенатики- и математической кибернетики

Наулш.ая_новизна диссертации состоит в. следующей;

- найдены критерии неразложимости графов многогранников относительно склепки но граням:

- описаны некоторые классы неразложимых и раздожиных графов многогранников;..

- установлены дости;пиннз верхние опенки сложности синтеза и разброса сложности синтеза произвольного к-связного, к - планарнсго .графа с п гранями'.

. - предложен, новый (сштшншО подход к'установлению К-свя-зкости, к - 3,-1.5, гаиильтоновосли .или эйлеровести графа нно-гогранника;

- описаны последовательности с растущим нислок вершин или граней к-связных» к -'3,4,5, пленарных графов, гаиилмшовых, эйлеровых графов многогранников.'

!1ЕаКП!ческа^л1^су:рэтщес1Ж Диссертация в ос-

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

Апробация работы. Результаты диссертации докладывались на Всесоюзной школе по сложности управляющих сдстек (Новосибирск, 1039), на и Гсесоезиоя качфзрениии по' проблемам 'тоо-ротичсскоЯ: кибернетики (.Волгоград, 1990), на 3 'школе-семинаре • "Синтез и сложность управляющих систем" СГьякзит, 1291), на семинарах по дяскрелюк катеиата.к к ее п"!иккеияяк в ТашГХ С1080-19иЗ).

УУ.(Ш£ё$Ш* йюише, разуиьтахи дассергаци» опуьдахиоанк и 4-х раоотах, сшюж которых приводился в ксшие -автореферата. В работа и) постановка додачи к некоторой идеи -ревшш пдододпсшаг А.1С. Иупатоьу.

Цгпуктурв-К ойьец ьаботы. Диссертация сссто;:; из введения, четырех глао (3 ракелей) и саиски лтестури, (килнл 1.ёчвн рабош 88. страниц. Слисок литературы содержит 43 ицилягоздшш.

ОСНОВНОЕ СОДЕРЖАНИЕ РЛБОТи.

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

'В )л.;',шой улавв ириаоднтса нредваритешша сведении, кс-«ольауеиив.в работе.

Во вторая главе ьссдедутсл алгеора -графой 3 -многогран? ников на • («ново рассиот рения операции склвйки -таких градов но границ. .

В параграфе 2.1 вводится необходипье определения и обоз*-падения, изучаются вопросы замкнутости класса № всех 3-связних шшиарных графов ошссмсеяшо операция склепки по граням и реализуемости склеяки графов З-шюгогранников склея-коА выпуклых многогранников в И3.

Пусть графы с;,, с2« « имехя граня соатьетствеиио в, и ^ равной степени а,'¡из. Скяейкой графов С4 и по граняи в, и & (обозначается о, * ) называется граф"!, вершит и ребра которого есть ьев 'варглнш и ребра графов и С2 при ус-шш, что вершины и ребра гран« в, отовдсствлншся с сохранением ишшдшшюсш с вершинами и рс-орами грани Ес-тиственьын сбраьол определяется обратная операция - расклейка графа л.« на графи 04, аг * ю. граф г. н », к тгоршу, нельзя прии&иип. олбрацмю'раасмйисм, называется элекшп арным. Элементарные гради обр&ауят базис в классе и сшюстеиьно операций еккойкп графой по гранях, т.е. тх)й З-шмшыи нла-нпрпип граф иоашо сиик^нровать С склеить но граняи) из элв-

;i>.;■'.;(.!(,¡my. rpat|,OB.

Доказывается замкнутость класса .ад относительно операции пеленки по граням ¡1 реализуемость склепки графов из га склепкой выпуклых многогранников б R",'тсесть справедливо следующее ■

ПРёРЖДИШЕ 2.3. Пусть графи О,. G2 « m имеют грани ссслч:.лс1'кеи1!0 и gj равной степени. Скшш к г., по граням «,, яг> лалуодга граф G. Тогда графи ot и «. можно реализовать в Л3 выиукпихн мношграшшкани М, и М2 соответственно rai-, что грани многогранников м, и и , соотсогствущие граням g, »! fc',» равна, и многогранник м, пояучешшл склейкой многогранники Mt и по эти« граням, является выпуклой реализацией графа G.

В параграфе 2.2 изучается злементарние (базисные) и не-эдешиарнив графи, находятся'два критерия нсэлементаррости гра ра. Множество s вершин графа G называется разделяющим мно жествен графа с, если- граф fl-S имеет больше компонент, чем G. Простоя цист I' гра(|й G нагшваеюя разделяющим циклом, если • его вершили образуют разделавшее множестеспйфа .G.

Получена сведущие ici¡итерии• неэленентарнссш графа. •

ТЕ0РЕИА 2.6. Граф G «.-и лголенемтарен тогда и только №г.ва, когда он ' кисет лрсстол цикл- с- такой, • чао никакая ■ грань графа G н&'рэдзрашт две неенешше вершину цикла с.

ТЕОРЕМА 2.?. Граф G V м леэленшггарен тогда и только тогда, когда он имеет простоя цикл, вершины которого образует минимально« (по включении)) 'разделявшей множество.

СЛЕДСТВИЕ 2.10. Если граф (ч, « и содержит треугольник, не нвлящияся краем никакоя грани графа ;G, то g - ««элемент • тарный граф.

Устшшвшш элеаентаршкггь слеяукщи/ классов графов.

Пусть ж<1»1>> • класг:' З-связных лламармнх графов, :какдоо peépo tcoiopiux .совдплнет всрапну ¿тспани а. с вершиной степени b, a s» - касс З-связаих плаиарних графов,'мнехдих грань, с которой ci«;«nii if» ptfpy вся остальные грани.

1'ТБЕГЖ/ЕШ)." 2i>. !■ l'ii.i граф и .» (¿ч(а,3) U < и,> U'ft(3,S) и si), то G - »ле1шк«а;м.ь» граф. ' '

lia «шоке :;:oiv yi, сдодешия .чплвгяся вывод о тт.*. что lit ¡moor ùxm-.;r -iii'-iil баиис. •

Ь параграф 2."i :,..!-\'|:..ываетс.'! пе-.-.чллг^гтарнс^сь .¡Р/х кляс-

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

ТЕОРЕМА 2.13. Если граф С- « :х имеет более 4-х вершин, то он неэлементарей.

Доказывается. также неэшюнтарнрей». графа с- п т", удовлетворяющего .определенным условиям.

Третья глава■ посвящена слокностным характеристикам; ..синтеза СсккелгаО графов З-миогогранников.

• Пусть 5(G) - множество всевозможных способов синтеза-; >.графа G те. Под.сложностью 1(з(г.)) синтеза в(&) « S(G) пони-нается число .элементарных графов, участвующих в эгом синтезе. Пусть 1 ,,«•) - max l(s(G)), 1 .„.(G) - min J (.-,(«)).. i '

6(o)e s i er) в i a xhs i а >

Разбрссон сложности синтеза графа G « m называется величина y(G) = imfi)i(G)/lmln(0). Требуется оценить максимальные значения ..сложностей синтеза. lmaK (G) и lTOirt(0) и разброса сложности.

1 синтеза в классах (n), к = 3,4,5, всех иелзоморфных, : к-связных пленарных графов с п граняки, т.о. функции Шеннона. ••JL*. (Ii) - шах I . (G), l'V (п) = шах 1 (G>,

min4' rrt n х • " мах , ' ^ тех ^ "

Ot;7U <п> аёЧ'(п)

у' (п) = max y(G)., ■

oeJS10 <r>»

Установлены следующие оценки введенных характеристик. 'ТЕОРЕМА 3.2. 1*„.<п) « t(n-2)/21, ПН.

ТЕОРЕМА 3.4. l*ln(n> . I(n-2)/2), n М,

ТЕОРЕМА 3.6. а Г 1, 4 - п :•• 7.

у | C(n-2)/31/L\ п г 8.

. ТЕОРЕМА 3.8. l*ax(n) = Кп-2)/31, п> 8.

УТВЕРЖДЕНИЕ 3.9. у4(п) = £(п-2)/3]/2, п г 8. ТЕОРЕМА 3.11. '

С(7п-12)/'.ЮЗ-1 s 1* (п) <■ [(7n-l2)/30], п г 20.

а

ТЕОРЕМА 3.12. y°in) ¿ t (7n-1 ?.)/3Q],'¿, n > НО,

уь(п) 2: (т6)/12, n 24, n --- O (moa 12).

3 четвертая главе исследуется взаимосвязь между некоторыми известным» характеристшсани графа многогранника к опера-циел склейки по граням.

В параграфе -¡,1 еспарулшвается, что в некоторых случаях каждга независимей шюл;ество вершин графа G « »» определяет коккрз-пшп способ его синтеза. Множество вершин графа называется независимый, если никакие две вершины из этого множества не сквзкод. Нетюгностыэ графа называется наибольшее число попарно несмежных верзин. Получены следующие результаты.

ТЕОРЕМА 1.2. Если V - произвольное независимое множество ворами S-связноя манарноя триангуляции о, мощность!УJ-к, щ от с. можно отклеить к пирамид так, что кашдаявершииа из ч tíy-i дет вершиной одной на этих пирамид.

Пострг/нш примеры, доказывающие, что для 3-связной и 1-шшоя няанарних 1риаш'уяяцмя анаяогииице утверждения не имеют места.

Доказывается также, что неплотность Jc-cimsuoro, к = 3, 4, 5, гшанарвого '.'графа с п вершинами не превосходит величины сйп-о/к.

В параграфа 4.2 изучается вопрос о том, как склейка графов по граням влияет на их наследственные характеристики -гамильтопов'ость и эйлеровость. Установлены следующие результаты.

УТВЕРЖДЕНИЕ 4.6. Пусть граф G - ж не имеет разделяющего цикла длина 3. Тогда граф G', лояучешш'Я в результате приклейки k-угольной пирамиды к каждой к-угольнск, к>з, грани графа G, является гамильтоновым.

СЛЕДСТВИЕ 4.8. Пусть граф (i в w получен склейкой- но треугольным граням графов с4, &2 е м. Тогда если хотя бы один из графов Gí, G2 исганильшюв, то G также иегашш,тонов.

УТВЕРЖДЕНИЕ 4.3. Пусть число 3-угольных граней' 3--связного планарного rpu-pa G превосходит -число его вершин. Тогда из о .можно получить негамильтонов граф <!' в результате приклепки З-уголыюй пирамиды к каждой З-уголышй грани G.

Строятся плотные последовательности гамипьто.чевых и не-

гамильтоновых графов многогранников с растущим числом. вершин.

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

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

1. Получены критерии.элементарности графов многогранников относительно операции склепки по граням.

2. Описаны некоторые юшзеи злететаршл « улэя'/жлппшы* графов многогранников.

3. Установлены достижимые ведошз ouewai сложности emu esa и разброса сложности синтеза лроизшдыгога k-cr-cnioro, к =•

!), пленарного графа с п гранями.

4. Получены результаты о наследовании синтезлгхзванлшш графами таких свояств и характеристик поролдаадих их базисных гра-•фов, как k-сБЯЗнхть, гамильтокоЕость, эйлзровссть;

ОСНОВНЫЕ МАТЕРИАЛЫ ДИССЕРТAü'-ií! ОПУБЛИКОВАНЫ В 'СЛЕДУЮЩИХ РАБОТАХ.

1. Пулатов А.К., Блтю'цкал Н.Й. Синтез и сложность графов многогранников на основе операции склеяки. - Сб: Пермаие-нты: теория и' приложения, Красноярск, 1991. - С. 53-65.

2. Бигхщкая H.H. О р.т-ц.-циклах 3-полизаралыюго графа.

- Тез. докл. 11 Всесоюз. кенф. по проблемам теоретической кибернетики, Волгоград, сект. i990r. -Волгоград. 1990. -Часть КЗ), - с. ю. .

3. Битицкая Н. И. Нээлемептарность и независимые множества плоских триангуляция, и' 5-связных планерных графов - Ташс. гос. ун-т.- Ташкент, 1993. - 16 с. - Рус. - Доп. в ГФ НТИ ГК.

ИТ РУЗ, 19.11.93, 1913 - Vö 93.

4. Бктвцкая H.H. О сложности синтеза 5-свйзиых. пленарных графов на основе операции склепки. - Сб. : Rcnpoe-ы кибернетики

- Тавкенг, 193-1. Вып.. 150, - с. £И8.