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

РГБ OA

,:, феб №

московский государственный университет им. М.В.ЛОЬШОСОВА

Факультет вачкслительной математика и кибернетики

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

Ли Да Мин

УДК 519.7

HDCOTOFtE ОГГЕИМАЛЬШЕ ВЛОЖЕНИЯ ДРЕБОВГДНЫл ГРАФОВ В ПЛОСКИЕ ПРЙМОУГОЛЬНУЕ РЗЯЕПЖ

01.01.09 - математическая ккберк=г.п:2

Автореферат днсс&ртацнм на сокскатш ученой степени кандидата физнко-цатеысткчесюк. наук

М0СКВ&-19Я4

Рйботй кйюлнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М.Б.Ломоносова.

Научные руководители: доктор физико-математических наук,

члея-корр. РАН, профессор яолонскип c.b.

кандидат фкзико-иатематиче craix наук, доцент Лонжи С.А. Офнип&льние оппонента: доктор физико-математических: наук,

профессор Редыа:н Ii.Il. кандидат физкко-}.?этематпчеааа наук, старший научной сотрудник Козцрев Е-.П. Ведущая организация: Институт системного программирования

РАН

Зйпрта диссертада: состоится ______1995 3

в "U____" часов на заседании Специализгоовакного совета

.Д.ээ при Московском государственно« университете ГмМек К.Б.Ломоносова по адресу: 119299, ГСП, Москва, Воробьевы гор: факультет E?>i:K, аудитория вез.

С диссертацией можно ознакомиться Е ОиЗлкот-еке факультета ечиК МГУ.

Автореферат разослан " ____1995 r.

Учений секретарь специализированного совета

профессор К.Л. Трифонов

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

Актуальность темы . Задача оптимальной геометрической реализации сетей и схем является одно£ из актуальных задач екскгйтной к2тзызт;то! е h2trüeth4scko¡i кибззнэткж. Эту задачу обычно сводят к задаче о возможности Елзхенкя графз, огглсьтза-плего структуру схемы, б то нли тазе геометрическое многообразие или соотьетствупу/а еку ресзтку. Вложение, как правило, должно удовлетворять целому ряду трзбоваай, связанных с взаиморасположением элементов к разнесением полюсов схемы (сети). Если необходимое вложение существует, то ставится задача его оптимизации по тем или иным параметрам, критериям. Одни?.', из распространенных ввдоз вычислительных и электронных структур ябляг/гся деревья, а одеек из наиболее распространенных типов решеток, в которых происходит реализация этих структур, являются плоские прямоугольные pes-THi:. Поэтому задача о вложении доевовидннх графов в плоские прямоугольные резеткн отлшмзльноЗ. площади или минимальных лпнесннх размеров весьма актуальна. Б настоящей диссертации рассматривается один естественник вариант &той задачи.

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

Предполагается, что при- ьлокекии графа его верцишы пнъектнвно отобраяавтея в т.н. основные вер^гаи розетки, - а его

pe Opa — e т.к. транзитные шшг pesera:, которые соединяют соответствуйте осноЕкне вершины и не имеют оодпх реоер. Вложение характеризуется перегрузкой, которая равна максимальному та еду различных транзитных цепей, проходяакх через одну к ту хе вершину рэиетки и может принимать, в данном случае, значения 1,2. Предполагается такхе, что Екладызаекый граф имеет определенный набор выделенных вережу ( полюсов ), которые при вдоиении дольни быть размещены оссокк образок. Тип репетки определяется тек, на каких сторонах (или внутри ренет кк) могут размещаться, полюса вкладываемого графз(пол»с8ми дерева считайся его листья).

Научная новизна.

1. Впервые разработана достаточно общая техника преобразования вложени?. изучаемого вида, включающая в себя целый набор приемов к методов таких, как разложение графа по т.н. опорной цепи вложения, еквивалектное сжатие рес.етки по вертикали за счет удаления сеосодной горизонтально-полной цепи и др. Показано, что эта техника _кзжэт сыть _ycnss¡so применена к деревьям к древовидным графам с целья получеки дорогих верхкзе к rksihkx оценок параметров ревет кк, допускающей их вложение.

2. Впервые установлено точное значение висоты полных двоичных к троичных деревьев с заданны?-: числом ярусоЕ, которое, как оказалось, не зависит- от типа решетки и перегрузи:. Выяснены возможные расхождения мегяу различными высота®.одного и того г:е-дерзва, связанные с выборок! различных типов решеток и различных перегрузок. Установлен характер экстремальной зависимости числа листьев дерева от числа его ярусов к высоты. Доказано, что

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

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

результаты могут быть использованы для дзльне^гго изучения вопросов оптимального Едоаенкя грзфзс в рэиеткп. Рагрзбстаннио в диссертации приемы и методы существенно расширяют возможности для решения задач подобного типа. Вместе с тем, эти методы

МТРУТ иой'п* т* ттпаг'*тт.гпп гч^п тчт*о,оа-1т*»а »

вычислительных структур, проектировании топологии интегральных схем и т.п.

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

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

Апробация работы. Результата - настоягей работы докладывались на Четвертом Международном семинаре по дискретной математике к ее приложениям ( Москва, 19ЭЗ ), на х Международной конференции по теоретическим проблемам кибернетики ( Саратов, 1993 ), на семинаре "Математические вопросы кибернетики" под руководством чл.-корр. РАК, профессора С.В.Яблонского в Московском государственном университете км. Н.В.Ломоносова.

Публикации. Основные результата диссертации опубликованы в работах евтора, список которых приведен б конце автореферата.

Структура и объем работы. Диссертация состоит из -введения и трех глав (7 параграфов), а также списка литературы, включающего 34 наименования.'Ойцкй объем .работе составляет ^страниц. Изложение иллюстрируется ^ рисунками.

- СОДЕРГкАНИБ РАБОТЫ

_____вве'деигёТ- даемся. - - обзор, -екзюезпхся- результатов .по""

дзюсертеппи, обосксЕШзаетсл ее актуальность, £ср;*ул:руется цель работы е излагается ее краткое содержание. Здесь ке описывается формальная модель рассматриваемых вложений, давтся необходимые определения и вводятся соответствующие обозначения.

.Как отягчалось, влогениз характеризуется перегрузкой V, т- = 1,2, ' и- типом--решетки. Для.. "описания ~ткпоз~ реието* рассматривается множество в, которое состоит из множества в — множества всех ненулевых двоичных наборов длины 4, а также спе-

Шального элемента {*}. Предполагается, что стороны граничного прямоугольника решетки пронумерованы числами от I до 4, считая от левой вертикальной стсрсны го часовой стрелке. Тпп решетки, т.е. допустимое положение полюсое при вложенки в нее, задается элементом в из в по следующему правилу: при 5=* полюса могут располагаться произвольно, а при ö i в —только на тех сторонах решетки, которым соответствует единичные компонент набора ö. Под ö-реиеткой понимается резетка типа б, под v-вложеЕвем ~ влохениэ с перегрузкой V, а под ( 7,5)-Елокением — v-влокепие в 6-реиетку. Предполагается, что рассматриваете граф: обладают необходимыми для существования изучаемого вдокекия свойствам, связанными с естественными ограничениями на степени версии, а при v = 1 — с требуемой плэиарностыо.

Рассматривается d-кчные, d = 2, 3, корневые к кекорнпвнэ деревья, то есть деревья, у которых степень верзкн нэ превосходит d-и, степень корня, если он имеется, не превосходит d, а также системы таких деревьев. Полисами дерева считаются его листья, т.е. верзкны степени I, отличные от корня. Через Dd(fc) обозначается полное d-ичное, а = 2,9, корневое дерево с к ярусами, е через Pd к) — граф, получавшийся из двух деревьев Pd(k) в результате "склейхк" кг длстьез с одинаковыми номера.'.:::. Полюсами графа Dd 2(k) считается "склеенные" листья полных деревьев, участвующих в его построении.

Для графа G с некоторым • множеством полюсов -через hy(G). ly(G) и Sy(ß), ö € в, У - 1, 2, обозначается минимальное значение высоты, длины и числа вершин (шкжадн) решетки соответ-

ственно, где минимум берется по всем б-решеткам, в. которые

возможно У-вложение грзфз с. Определяется также условная длина 1у(с,ь), равная минимальной длине такой ресетки, Еысота которой не меньше, чем ь, и в которую возможно (V,б)-вложение графа и. Во множестве в выделятся подмнокества:

= {(0001 ), (0011), (1011)}, В(2) = { (0101), (0111), (1111)}, в = в(1) и В(2) и {*}.

V ~

Отмечается, что при любом б, б € в, как высота Ьуф), так к длина 1®(0) будут совпадать либо с одной из высот ь®'(с), где £ б в, либо с одной из длин з.^001^), 1(у101Чо, а площада

1 Л* ^

Бу(0,— с одной из площадей £^(0), где б'€ в\{(Ю11)}.

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

В £1.1 вводится понятие эквивалентности, согласно котором! эквивалентными считаются два вложения одного и того го графа с расположением полюсов на одних к тех сторонах решетки в одно? е той же ( по 'часовой" стрелке") порядке. Рассматривается рл; операций, позволяющих, либо из более простых вложений получат] более сложные, либо переходить от одних влокений к другим <

сохранением эквивалентности Е возмохнкм улучшением параметров. Основное утзэрздевз? Я .1 — лемма 1.1.1, которая дает достаточные условия сккмаемэсти вложения по высоте ( с

сохранением эквивалентности ) за счет удаления т.н. свободной

горизонтально-полной цепи. Доказывается, что для произвольного

графе а высоты ь®(0) одинаковы при всех 5, С е в^К 1 = 1,2, а

для ух общего значения вводится обозначение Ьу^(с). Отмечено, что пз очевидной монотонности вксот по У и б следуют неравен :

К* (О) 1 1-42)(С) <.

ь|са) <ь*(0); < Ь^^О).

В $1.2 вводится понятие т.н. (Т, 1)-достигимости, где V = 1,2. 1 ! 1; < 4, ввриин регаэтки, т. е. возможности соединить эту вершину с некоторой вершиной на t-й стороне решетки цепью, которая состоит ез свободных рэбер к проходит через свободные при У - 1 к транзитные или свободные при V = 2 верспшы. Здесь ке определяются (У^)-канонкческиэ влог-ения деревм-!:, где число г, 0,1,2, характеризует расположение при пдегенпп корня дерева к его достижимость с разных сторон решетки, а также устанавливаются некоторне соотношения мекду каноническими высотами. Описывается процедура разложения дерева по цепи к техника построения влохенкя исходного дерева на основе канонических вложений компонент его разложения.

" Гласа 2. Исследуются оптжальние по впеоте влогения" деревьев и древовидных графов. Основными результатами главы являются точные оценки высот по.тгах и случайных деревьев, оценки возможных

расхождений между различными высотами одного к того *з дерева, а такз:е построение семейства д-реЕьэв, имещих максимально возможной число листьев при заданном числе ярусов и заданной высоте.

В $2.1 изучаются высоты полных дерэзьев, случайных деревьев и графов ^ р(к). Доказано, что при всех а = 2,3, 7 = 1,2, 5 € В и к = 1,2,..., имеет место равенство:

= И(Д.ЭЕ) = ] (К+1 )/(4-<Ш,

которое показывает, что все "основные" высоты полного дерева одинаковы. Отмечено, что некоторые канонические высоты дерева 1)4(к) также равны М<1,к). Показано, что если отображение полюсов при горизонтальной осевой симметрии (ОЮ1)-реиетки задает изоморфизм двух вложенных в нее непересекающихся деревьев вида то высота в той решетки не меньше, чем 2Ь(2,);). Модель случайных ¿-ичннх, <1 = 2, з, деревьев предполагает, что с вероятностью р, о < р < 1, листья полного й-кчного дерева независимо друг от друга остаются в случайном к-ярусном й-ечнс-м --дерзг;5--Ц-Г)(к-) -е -что - ьнутрс-ниял-взрзшна и дерева входит б (к) только тогда, когда в него входит хотя бы один лист дерева 1)^(10, лехацяЕ на цепи, которая проходит через корень дерева и вершину и. Доказано, что при любых У=1,2,

V

к 5 е в, вероятность того, что

^(ей>р(к)) ^ Ь(й,к) - 1оСйк/(4-й) _+0(1) .

стремится к единице при к стремящемся к бесконечности. Показано, что высоты 2(к)) отличаются от величины 2и(с1,к) не больше, чем на единицу.

В 12.2 устанавливаются некоторые соотношения меаду различными высотами произвольного дерева. Для «ьичного, <1=2, 3, дереза В доказана справедливость неравенств:

< + (6.-2), Ь^Ф) <.к!?'(В) + ((1-2),

1 - 1

13 эрвн^ дз 2 кот"ст?<х о зн2х пу*9 что дл** ~ ¿гхвог'с д 6 р^ в 3 i) 71м 9 хуг

Для к=1,г, —, приведены примеры деревьев и 1>£ таких, что = к+1,

причем дерево икает только одну верпашу ст&пек15 4.

3 52.3 рассматривался экстремальные соотношения мэ.Еду высотой, числом ярусов и числом листьев для сьичного дерева с. С

целью ббодятся величины (соответственно п^(к.к)), . ..

определяете как ь&хсимально возможное число листьев а-ичного к-яру ей ого дерева Ь, для кот-орого существует (1, (0001 ))-влс2:екие ( соответственно т.н. правильное 2-каноническое Елояенпо, отличавдаасл тем, что корень дерзиа достижим с верхней стороны решетки, а все листья' лйейт на ее нихнеЕ сторона и явлййтоа так единственными основшп®_ ззрщинаяа.). в креветку высоты ь. Доказано,--что

Н2(к,Ь) = 2К - 2Й Е С* ^ 1=0 л п

-И : , '

Я3(к,Ь) = | с£2\

причем нззнке сценки для величин к2(к,Ю г к3(к,М в указанных соотношениях получены путем конструктивного рекурсивного построения требуемых деревьев, отмечено, что во многих случаях е, в частности, при конструировании т.н. ассоциативных сетей построенные деревья является более вМекткБНыми структурами, чем полные деревья. Так, при ь=[(п+1 )/з]+1 построенное дзоичнэе (п-и)-ярусное дерево высоты к'будет иметь не меньше, чем 2Г\ листьев, в то время как высота полного дерева с таким же

числом листьев раЕна ](п+1)/2[.

Глава 3. Рассматриваются вопросы, связанные с построением оптимальных по длине, 8 тз;ск т.н. дважды оптимальных, т.е. оптимальных кок по высоте, так и по числу верзкн вложений деревьев и древовидных графов. Осноеным результатом главы является построение аспмптстич9с!си дважды сптималънни полных деревьев, а также распространение техники получения такпх вложений ка один случай произвольных деревьев. ------Б $3.1 • для произвольного графа о с р полюсами степени х,

1 ^<3, И ДЛЯ « = ,е2,63.04) € В(1). 1=1,2, у=1,2, Ь1Ь|(0)

полу чека следующая нигняя оценке условной длины:

1у(0,Ь) 1 3(р4 ~ 0,4- С3 ))ЛГ,......

"апрк'6 <(1011Г — книга оценка 'для' шэдедв: .......

Еу<6>'^ь5{С) (РЧ-^ + а3)ь5(0))/1.

Здесь ге рассматривается вопрос о построении оптимальных ю длине iy(D)i где т = 1,2, б = (00015, (0Ю1), влогений произвольного двоичного или троичного дереза е. Доказано, что для всех 7=1,2, и а = о, 1 справедливо равенство:

,(00^1)(3) = ] K(D)/(14C.) [. 3 £3 ■ 2 E3V~£iDTCS ЕСНИ1Г:ОТНЧеСЫН ^СГЛЫ СПТИ1£ЗЛЪНН9 ЕЛОЖеННЯ

деревьев и дээвовихнкх гпгфов, JIoks?sho, что для Лд>"ых 5?511к{(1011)}, 11512, и 7>í, дерево d-cl). k=1,2,..#, b'.osko т-влоггть в асимптотически дзавды оптимальную (с, и--1),0,1 ре-кетку, высота которой асимптотически. равна Ы¿,k), а длина — сг/2. Построено асимптотически оптимальное как по Еысоте, так и по длине (2, (0001 ))-влохенке граф?? г, ,>0:5.

U, t-

Иетоды посттюеккя уч'ззрнеых оптимальных

вложений сообщаются на случай произвольных деревьев следуяща*. образом. Пусть дерево л с N .гсстьвсг получается в результате присоединения к í-му листу, i = 1 ,...,р, доревз D' корня дерева

D", которое веет не кеныпа четырех листъеи,~к пусть- - - • hn = rr.ax h}1)(DV), h'-hj1 5 <D'). Тогда

¡Lilp 1

trw\4 \

> (D,h'+2h"+2) = íí.

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

iвтор í&pas&5T глубокую благодарность член-корреспонденту РАН С. в. Яблонскому и кандидату физкко-метематкч&сккх наук С.А.Лохкину as научное руководство и оодьйуЕ помо&ь при подготовке данной работа.

Основное результаты диссертации опублгкованн в следукЕП?: работах автора:

1 Ли. Да К'лгк. Асимптотически оптимальное по плокади вложенку двоичных и троичных деревьев в плоскую прямоугольна'» реиетку с отображением листьев дерева на гратэд прямоугольника //.Четодц к систем технической диагностики, Ьйгзузсвсккй сборник научных трудов, вып.. is. — Саратов. Издательство Саратовскогс университета — 1УЭЗ — с. 103-ЮЭ.