Введение к работе
Актуальность темы . аахача оптимальной геометрической реализации сетей и схем является одног из актуальных задач декретной ыатекзтккк и нзтекзтнческо* кгоернетиж. Згу заделу обычно сводят к задаче о возможности вложения графа, опиенва-алего структуру схемы, в то или иное геометрическое многообразие или соответствующую ему репетку. Вложение, как правило, ходко удовлетворять целому ряд>' требований, связанных с взаиморасположением элементов к разнесением полисов схемы (сети). Если необходимое вложение существует, то ставится задача его оптимизации .по тем или иным параметрам, критериям. Одни?.', из распространенных вадоз енчл: злите льнкх и электронных структур являются дэрзвья, а одкЕК из наиболее распространенных типов решеток, в которых происходит реализация этих структур, являются плоские прямоугольные рё~тк2. Поэтому задача о вложении
ДреВОЕИДННХ ГрафОВ В ПЛОСКИ? ПряноуголЬНЯв решеТКі: ІЛГККМЯЛЬКОЙ
плоцади или минимальных лпнесннх размеров весьма актуальна. Б настоящей диссертации рассматривается, один естественны?, вариант зтой задачи.
Цель работы. Целью рsooth является разработка техники получения точних или аекмптоткчзски точных как kzshkx так. к верхних сценок для. висоти, -длиЕк или . площади - плоской' прямоугольной решетки, в которую возможно вложение графов, близких к деревьям.
Предполагается, что при- влокекки графа его вершины инъектквно отобрахавтея в т.н. основные верзинц рскетки,- а его
ребра — Е т.к. транзитные це як ресеги:, которые соединяют соответствухсие основные вершины и ве имеют oognx реоер. Вложение характеризуется перегрузкой, которая равна максимальному числу различных транзитных цепей, проходящих через одну к ту хе вершину репетки и может принимать, в данном случае, значения 1,2. Предполагается такте, что вкладываемый граф имеет определенный набор выделенных вершин ( полюсов ), которые при елоеєеии должны быть размещены особым образок. Тип репетки определяется тек, на каких сторонах (иди внутри решетки) могут размещаться, полкса вкладываемого графз(полисами дерева считаются его листья).
Научная новизна.
1. Впервые разработана достаточно общая техніка
преобразования вложении изучаемого вида, включающая в себя целый
набор приемов к методов таких, как разложение графа по т.н.
опорной цепи вложения, зквивалектаоэ сжатие рекетки по вертикали
за счет удаления свободной горизонтально-полной цепи и др.
Показано, что эта техника _когзт сыть _успещ*о_ применена к
деревьям и древовидным графам с цельэ получения хороших верхкз:
к нклаих оценок параметров реветкк, допускающей их вложение.
2. Впервые установлено точное значение висоти ПОЛНЫХ дво
ичных к троичных деревьев с заданны?-: числом ярусоЕ, которое,
как оказалось, не зависит от типа решетки и перегрузи:. Выяснены
возможные расхождения мег:ду различными вксотагж.одного и того г:е
дерева, связанные с выбором различных типов решеток и различных
перегрузок. Установлен характер экстремальной зависимости числа
листьев дерева от числа его ярусов к высоты. Доказано, что
построенные при этом деревья во многих случаях к, в частности, Z2?. конструировании т.н. ассоциативных сзте являются более эффективными структурами, чеы полные деревья. Рассмотрена модель случайного дерева и показано, что его шсота с вероятностью, стремящейся к единице с ростом числа ярусоз, мало отличается ст высоты полного дерева.
3. Для большинства типов решеток и перегрузок построены влохения полных деревьев, которые является асимптотически ьакзкальннми как по числу версии репетки, "так и по высоте. Впервые установлена, в частности, асимптотика гаэдзди полных деревьев для всех типов решеток/ на додускаЕсих размещения полисов внутри себя, и всех перегрузок, за исключением случая, когда перегрузка равна единице, а рекекса допускает размевение полюсов на какюс-го противоположных сторонах ( ранее был известен только порядок этой плоЕзди ). Техника построения вложений оптимальных по нескольким параметрам одновременно обойценз на достаточно Екроккй класс произвольных деревьев и древовидных
результаты когут быть использованы для дзльнеиггго изменил вопросов оптимального Едоаенкя грзфзс в рэпетки. Рагрзбстаннно в диссертации приемы и методы существенно расширяя? ВОЗКОлНОСТИ для решения задач подосного типа. Вместе с тек, эти метода
V*TPVT Titafrrrj тч rrr\uvrpxxzjanvr\a ттлпют>атт*'а і*>'» r>onr\f>t^f^^v^ rtr^-nw
вычислительных структур, проектировании топологии интегральных схем и т.п.
Методика исследования. В работе используются " метода
. дискретной математики: и математическое кибернетики, теории вероятностей е математического анализа.
Апробация работы. Результаты - настоящей работы докладывались на Четвертом Международном семинаре по дискретной математике к ее приложениям ( Москва, 19ЭЗ ), на г Международной конференции по теоретическим проблемам кибернетики ( Саратов, 1993 ), на семинаре "Математические вопросы кибернетики" под руководством чл.-корр. РАК, профессора СВ.Яблонского в Московском государственно;,; университете кы. М.В.Ломоносова.
Публикации. Основные результата диссертации опубликованы в работах евторз, список которых пгр;жэдек б конце автореферата. Структура и объем работы. Диссертация состоит из
-введения и трех глав (7 параграфов), а также списка литературы, вкяочакцэго 34 наименования.'Общий объем .работе составляет
gстраниц. Изложение иллюстрируется fz рисунками.
- СОДЕРЖАНИЕ РАБОТЫ
ЕвелеёгёТ- Дается. - сбоор --имзкзкхся- результатов -па~ твие
диссертации, обосновывается ее актуальность, формулируется цель работы и излагается ее краткое содержание. Здесь »:е описывается формальная /модель рассматриваемых вложений, давтся необходимые определения и вводятся соответствующие обозначения.
.Как ysta отмечалась, вложение характеризуется перегрузкой V, т-= -1,2,---3- типом--решетки. Для.. "описания "типов" ревето* рассматривается множество в, которое состоит из множества в — множества всех ненулевых двоичных: наборов длины 4, а также спе-
Шального элемента {*}. Предполагается, что стороны граничного прямоугольника решетки пронумерованы числами от I до 4, считая от левой вертикальной стсрсны го часовой стрелке. Тип решетки, т.е. допустимое положение полюссе яри вложении в нее, задается элементом б из в по следутееыу правилу: при 5=* полюса могут располагаться произвольно, а при б і в —только на тех сторонах решетки, которым соответствуют единичные компонент набора о. Под б-реиеткой понимается резетка типа б, под v-вложенвем — влохениэ с перегрузкой Y, а ПОД ( 7,б)-ЕЛ0йЄНЯЄМ — v-влохеше в 6-реиетку. Предполагается, что рассматриваете граф-: обладают необходимыми для существования изучаемого ьяожекяя свойствами, связанными с естественными ограничениями на степени веріат, а при v = 1 — с требуемой планарностыз.
Рассматривается d-кчные, d = 2, 3, корневые к кекорнавне деревья, то есть деревья, у которых, степень верзкн нэ прегоеходит 1-й, степень корня, если он имеется, не превосходит d, а также системы таких деревьев. Подесаки дерева считаются его листья, т.е. верзквы степени I, отличные от корня. Через Dd(k) обозначается полное й-ичвое, а = 2,э, корневое дерево с к ярусами, е через r>d g(fc) — граф, получ а вбійся из двух деревьев Р,(к) в результате "склейки" is ллстьев с одинаковыми комера.'.:::. Полюсами графз Dd „(t) считаптса "склеенные" листья полках деревьев, участвуадих в его построении.
Для графа G с некоторым множеством полюсов -через-hy(G).
ly(G) и Sy(G), б в, v = 1, 2, обозначается минимальное
значение высоты, длины и числа вершин (пдоашда) решетки соответ-
ственно, где минимум берется по всем б-решеткам, в. которые
еозмохво У-влоление грзфз G. Определяется также условная длша ly(G.h), равная минимальной длине такой репеткк, высота которой не меньше, чем h, и в которую возмокно (V,б)-вложение графа G. Во множестве в выделятся подмкохества:
Б(1* = {(0001), (0011), (1011)},
В(2) = { (0101), (0111), (1111)}, в = в(1) и в(2) и {*}.
Отмечается, что при любом б, S в, как высота hy(G), так у.
длина ly(G) будут совпадать либо с одной кз высот Ьу'(о), где
6 в, либо с одной кз длин 1(^01^(G), 1(у101Чо. а площада
Sy(G),— с одной из площадей Sy(D), где б' Б\{(1011)}.