автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Теоретико-числовые, алгебраические и геометрические основы арифметических графов

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

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

ГРИГОРЯН Юрий Георгевич

ТЕОРЕТИКО-ЧИСЛОВЫЕ, АЛГЕБРАИЧЕСКИЕ И ГЕОМЕТРИЧЕСКИЕ ОСНОВЫ АРИФМЕТИЧЕСКИХ ГРАФОВ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1992

Работа выполнена в Армянском научно-исследовательском институте энергетики

Официальные оппоненты: член-корр. РАН и АН Украины СТОГНИЯ А. А., доктор физико-математических наук,профессор МАРКОСЯН С. Е. доктор физико-математических наук ГАЛИУЛИН Р. К

Ведущая организация:

на заседании специализированного совета Д002.32.06 при Вычислительном центре Российской АН по адресу: 117967, Москва, ул. Вавилова, 40, конференц-зал.

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

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

Автореферат разослан

Ученый секретарь

Специализированного совета Д002.32.06 при Вычислительном центре РАН, -кандидат физико-математических наук

чи/ С. Ы. Швартин

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

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

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

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

Цель работы. Разработать математические методы специального кодирования дискретных объектов - графов, многогранников,

булевских функций, связанных с их минимальными представлениями, обработкой и преобразованием. Показать, что булевское и арифметическое кодирование графов наделяет их теоретико-групповыми свойствами, отличающимися от классических свойств, и является ис точником формирования новых конечных групп и групповых композиций. Установить, что параметризация графов, осуществляемая предложенным методом кодирования порождает множества подстановок, укладывающихся в ноше группы с ранее неизвестными свойствами, и обеспечивает реализуемость этих графов в евклидовых пространствах. Показать, что арифметическое кодирование графов является перспективным научным направлением в области применения математических методов и ЭВМ в научных исследованиях. Обосновать концепцию кодирования дискретных объектов как наиболее общего объединяющего начала, играющего важную роль в различных процессах и явлениях природа. Применить инфорлационные, статистические и геометрические свойства дискретных объектов к решению некоторых задач по автоматизации проектирования вычислительных систем.

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

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

ческим моделированием сложных систем.

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

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

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

На основе геометрических свойств арифметических графов, а также многовариантности представления одного и того же графа в определенной системе кодирования впервые исследованы статистические свойства графов на примере задачи по определению наиболее вероятной '"длины графа".

Проведенные теоретико-числовые, алгебраические и геометрические исследования над графами, представленными в определенной системе, характеризуются единством взаимосвязанных свойств, объединяющей основой которых является концепция кодирования дискретных объектов как нового направления в области применения математических методов и ЭВМ в научных исследованиях по автома-

тизации проектирования вычислительных' систем, кристаллографии и др.

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

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

В области теоретико-числового описания неориентированных графов впервые введено понятие арифметического графа и изучены основные его свойства. Показано, что всякий неориентированный граф может быть представлен в виде арифметического графа (универсальность) . Ддна классификация графов на натуральные и ненатуральные арифметические граф*.

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

циклов.

Для целей практического применения некоммутативной группы 66 (р) в области кристаллографии, квантовой механики и др. полностью решена задача представления этой группы. Указан метод получения всех неприводимых представлений и таблиц характеров этой группы для любого простого р .

Показано, что арифметические многогранники, как новые геометрические тела, обладают противоположными качествами: в трехмерном евклидовом пространстве они абсолютно асимметричны, в

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

Информационные, статистические и геометрические свойства д.н.ф., арифметических графов, многогранников нашли практическое применение при решении задач оценки сложности дискретных объектов, минимального покрытия, оценки качества размещения модулей и др. в области автоматизации проектирования вычислительных систем,, разрабатываемых в Ереванском НИИ математических машин (ЕрНИШМ).

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

-мерном линейном пространстве они симметричны. В

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

5. Апробапия работы. Результаты диссертации докладывались с 1975-1989 гг. на семинарах в городах Ереване (ЕрГУ, ВЦ АН АрмССР, ЕрНИИММ, Армянский НИИ энергетики), Москве (ВЦ АН СССР, Институт кристаллографии АН СССР), Киеве (Институт кибернетики АН УССР), на Федоровской сессии (Ленинград, 1984) , на второй Всесоюзной конференции "Математические методы распознавания образов" (Дили-жан, АрмССР, 1985 ), на второй Всесоюзной конференции "ИНФОРМА-ТИКА-8?" (Ереван, 1987), на Советско-Германском семинаре по дискретной математике (Ереван, 1989).

6. Публикации. По теме диссертации имеется 14 публикаций.

7. Объем работы. Диссертация состоит из введения, пяти глав, заключения, двух приложений и библиографии из 40 наименований. Работа изложена на 183 страницах машнописаного текста. Иллюстрационный материал представлен.II таблицами и 18 рисунками.

СОДЕРЖАНИЕ РАБОТЫ

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

I. Глава I посвящена вопросам отображения сокращенных дизъюнктивных нормальных форм (сок.д.н.ф.) на графы и построения новых групп автоморфизмов, порождаемых этими графами [5,9,13] .

В §1 определяется понятие булевского графа как типичного примера представления графа в определенной системе кодирования. В шестидесятых годах в наших работах [2,з] по арифметизации логических задач, вызванных необходимостью автоматизации проектирования цифровых автоматов [I] , было отмечено, что максимальные интервалы Ыи ранга z , являющиеся {тп-Ь) -мерными подкубами тп -мерного единичного куба Ет , могут быть полностью, представлены

всеми своими главными диагоналями (, rij) , где Nj- ,

Tii + 7ij - const' по всевозможным 2.тп~ъ * главным диагоналям h/u {ni+rij называется весом Nu ).

Пусть R - $ Ui сок.д.н.ф., соответствующая заданной бу-J=f

левской функции ffcc,, асг>..,} JCm) , Nf - множество истинности f, \Nj[=p . Введем на /7^ некоторую коммутативную операцию о , называемую обобщенным склеиванием [2,3] , которая каздой паре (щ.тг^) , щ ,rij g Nf ставит в соответствие некоторое" элементарное произведение Q = ОС^' ЭС*гкк

где i11 iz t.„> iK - номера одноименных двоичных разрядов векторов TLI , 71 j ,

f ас при о( =0 при с< = I

Сок.д.н.ф. R булевской функции / поставим однозначным образом в соответствие граф B(Nf,K) . где Nj - множество вершин с числом элементов р , К - множество ребер (7ii, 71 j) . 711, пj eNf » удовлетворяющих следующему условию:

К={(щ,ъ), (menjl^QeR}. Полученный B(Nj.,K) граф называется булевским графом. Очевидно, что на таком графе допускаются изолированные петли. Если - ранги максимальных интервалов Л/«. , J = /, t булевской функции '/ , то число ребер графа о=

J=i

Легко показать, что типу по Поварову (1955) соответствует

один и тот яё булевский граф с точностью до изоморфизма. Поэтому

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

2

дает с числом типов и равно —- (± + Е>т) . где О

2. тп{

при тп ОО .

Определение 1.1. Булевская функция /(6г,ЗСт) называется пучковой, если существует хотя бы один пучок И(п,И) , 72 е Д^е в смысле Журавлева (1962) такой, что = М Пучковая булевская функция называется тривиальной пучковой функцией, если z(гlj)= }7~£.

Теорема 1.1« Булевский граф В(Ы^,К) . соответствующий нетривиальной пучковой булевской функции, является несвязным графом.

Полученный результат говорит о разреженности булевских графов. Непланарнне булевские графы построены при т 5.

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

Ч = 2 2 и имеет показательней порядок, в то время

1 +

как вся информация об этом графе содержится в £ простых импли-кантах 11] .

Приведенные результаты были первыми в плане развития концепции кодирования графов с целью их компактного представления.

В § 2 определяются понятия булевского автоморфизма и булевской группы [9.13] . Показано, что группа булевских автоморфизмов графов принципиально отличается от группы автоморфизмов графов в классической понимании.

Пусть В(Ы^,К) - булевский граф функцииу Ы/ С Ет • Матрицу смежности графа В(Щ,К) размерности запишем в виде

Г I, если '(Щ,71)) $&6у>В(Щ,К) \о. если (Щ, Т1]) не ребро В(Щ,К).

Зададимся некоторой подстановкой

fO, /. . • Vi ... 7lj... 2m-i )

ci={ to tf... K... £ ...

Определение 2.1. Под действием подстановки о< на матрицу

будем понимать следующее преобразование:

о(оА =\\(щ, * (nßT II = II (щ

Определение 2.2..Последовательность процедур над матрицей А

о(о А - о/о £<о Л fco (оСоАУУ

назовем умножением матрицы А на подстановку Ы. и обозначим А*с{ ( т - знак транспонирования матрицы). Операция А * является обобщением известного алгебраического преобразования вида Ы Дс<-< , играющего важную роль в теории групп. ,

Пусть £ (ccf, ЗСг у ..., -Хтп ) - некоторая булевская функ-^' j'i-f у f2' • ■' fs} ~ шожество булевских функций, получаемых, из у с помощью всевозможных преобразований Поварова

1 ,j - ттг . Булевские графы, соответствующе мно-

жеству функций , > ■■ ■> и образующие один и

тот же тип, обозначим

причем Nfi ^ ц ^ к. ^ к. } ß. щ > к.) о ßj Щ , Kj ).

Определение 2.3. Подстановка oi называется булевским автоморфизмом булевского графа ß1 f/Vff, Ki) , если В^ ■

Нетрудно видеть, что множество j- всевозможных подстановок, являющихся булевскими автоморфизмами одного и того же булевского графа 3f (Л^, , Ki) , образует группу.

В качестве примера показано, что для всех 16 булевских функций от двух переменных, имеющих 6 типов, группой булевских автоморфизмов является группа .изоморфная группе диэдра ¿6 л .

- 10 - 4 .

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

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

2. В главе Д введено понятие арифметического графа и рассмотрены задачи, связанные с изучением этого понятия. Устанавливается универсальность арифметического кодирования графов, приводится классификация графов на натуральные ж ненатуральные арифметические графы. Формулируется задача существования натурального арифметического-графа и доказывается положительный результат о непрерывности "спектра" натуральных арифметических графов относительно числа вершин и ребер {4,6,8] .

Дал описания теоретнко-чнсловых свойств арифметических графов рассматривается более сложный, с позиций изоморфизма графов, класс регулярных натуральных арифметических графов. В этом классе исследуются различные вопросы, отражающие топологи» графа в зависимости от разложения числа вершен р графа С на простые множители и других параметров [12] .

В § 3 приводится понятие арифметического графа и исследуются основные свойства [4] .

Пусть даны два множества целых положительных чисел

Определение 3.1. Арифметическим графом (а.г.) называется пара б (Ы> М) . где М - множество вершин графа, а

(п.; , 72;) п;,П.еМ- его ребро, если + П;е.М . Множество М

I V ' у/9 I' J

называется поровдавдим множеством, а число + - весом ребра (111,71}).

Для отличия от обычных графов арифметический граф обозначим

В § 4 устанавливается универсальность арифметического'кодирования и дается классификация арифметических графов.

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

Данная теорема устанавливает универсальность арифметического кодирования.

Определение 4.1. Арифметический граф называется минимальным, если для любого графа ¿¡'(//'¡М'), изоморфного графу &(Ы\М) • имеет место соотношение . Минимальный арифметический

граф обозначается &(Ы IМ).

Определение 4.2. Граф £ называется натуральным арифметическим графом, если он может быть представлен арифметическим графом вида

t

Число ребер графа б(ЫР\И) равно тп5) , где

Н \2р'т**\ .если т3 >р+{

Для р - 1,2,3 все графы являются натуральными; для р = 4 из II неизоморфных грофов 9 являются натуральными и 2 - ненатуральными (трехлучевая звезда и ее дополнение), для р = 5 из 34 графов 26 являются натуральными и 8 - ненатуральными (рис.6).

Пусть задан граф б (Ы,М) , ^(гц) - степень вершины щ .

д = 7Псг.хР(т) - максимальная степень и 'cófiSTj - диаме-т&ы

тр графа в обычном смысле.

Утверждение 4.1. Для минимального арифметического графа име ет место оценка

i-1

Теорема 4.2. Для любого арифметического графа G(?/1М),

гДе A/{niJ,í=/Tp ' j = i7K • 1111661 шсто соотноше-

ше Р к •

^ifínO^TUj^CTTlj). <4'7)

ifs1 J-1

Рис.6 . •

Эта теорема связывает известные классические параметры графа, как число вершин Р , локальные степени У*^») с арифметическими параметрами К , т^ , $(т^) ,■ и применяется в дальнейшем при исследовании различных вопросов.

В заключении этого параграфа приведен эффективный критерий

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

Теорема 4.3. Для того, чтобы граф & с числом вершин р , ребер ^ и максимальной степенью А (р>А+1) был ненатуральным а.г., достаточно, чтобы выполнялось условие

гЫ

£<2 ["г]- (4.13)

В §5 показано, что при фиксированном числе вершин р графа для любого заданного числа ребер % е [О существует хотя

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

+ 1" ]-.,+ [ 2 К[.Е] =2 (5.7)

Р- нечетное

^ + + ПК^] = Ч (5.8)

М >р 'Ч0ТНое

Теорема 5.1. Числа ввда (5.7) и (5.8) соответственно при р нечетном и четном заполняют весь целочисленный отрезок [О, С р].

Если через <о(<^) обозначить число всевозможных решений рассматриваемых диофантовых уравнений для каждого фиксированного ^ , то число решений Б (р) для всевозможных целых [0,Ср] и любого р выразится формулой

2 Г Л

ей при р нечетном

2-5 при р четном

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

В § 6 дается описание и исследуется свойства класса регулярных натуральных арифметических графов, характерные дош кристаллографических структур [12] .

Лемма 6,1, Классы (6.1), (6.2) натуральных арифметических графов являются К -регулярными графами.

тг+2р,...:>тк+2р}) (6.1) С'(//2р1{щ',т{,..., т'^гр^,т{+2Р, 7п'г+2р,.~,7П42р}) (6.2)

Теорема 6,1. Графы 0(Ы2р\{т1, 771 г, ...,7Пк) 7П1+2р, ™г+2р, ■> 7Пк+2р}) &'(Нгр\{т\,т1> ■>7п'К}7п'1+2р) т'2+2рУ; тгС+2р})

изоморфны, если для каждого £ = 2,3,...,к имеет место 771 ¿- 772Н = 771?-т^

Теорема 6.2. Если (Р, , то компонента связнос-

ти 2-регулярного натурального арифметического графа

^гр I 7Пг,77г,+2р>77г2+2р})

равна Ш (граф & состоит из $ изолированных простых циклов 2Р

с — вершинами в каждом).

к

Следствие 6.1. Если числа р и 17*2'™' взаимно простыв,то граф б(Ыгр\{тпитпг, 7П,+2р>> 7Яг+2р}) представляет собой осто-вный цикл.

Следствие 6.2. Еслир -простое число, то граф б(Нгр\{ть ть Щ+2р, тпг+ 2р}) представляет собой простой остов-

ный цикл при любых | 3.5....,2р-1}

Сладотвие 6.3. Два регулярных натуральных арифметических графа

G(b/zpWm^mz,7n,+ 2p, тг+2рУ) G'(NZp\{m'1}mit т;+2р, ml+2p})

изоморфны , если (Р: mi-mi)

¿г 2

Показано, что если разложение Р на простые множители имеет вид Р = 7if' .. , то число неизоморфных графов, представи-мых натуральными арифметическими графами вида

б(Ызр I {т,, тпг, т,-г 2р, 7пг+2рУ)

равно

Тр = z+i(ci - ici.) . ГД9 .

Аналогичные результаты получены и для класса регулярных натуральных арифметических графов вида (6.2).

Теорема 6.4. При простом р и К = 2 число всевозможных представлений простых остовных циклов в виде (6.1) и (6.2) равно

Р(Р-1) -_.

Теорема 6.5. Компонента связности графа (6.1) равна с/ ,

где

¿ш НОД (^р-, . . , ТПк-ЪЪм, р).

Теорема 6.6. Компонента связности графа (6.2) равна d .где

^нод (z£±, zéjL.pb

Следствие 6.6. Если Р -простое число, то графы ввда (6.1) и (6.2) являются связными.

Следствие 6.9. Если граф! (6.1) и (6.2) связные, то они со-

держат хотя бы один гамильтоновый цикл.

3. Глава Ш посвящена вопросам построения и исследования конечных групп) порождаемых арифметическими графами [п] .

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

В § 7 дается определение и исследуются свойства группы арифметических автоморфизмов графов. Приведем понятия, аналогичные некоторым понятиям из главы I. Цусть задана подстановка

01 = 11 и'.'.Ьр)

и некоторый помеченный граф

с множеством Л' из Р вершин и множеством М из ^ ребер. По аналогии с Определением 2.2 введем следующее понятие.

Орредвление 7.1. Перенумерованный в соответствии с подстановкой о( помеченный граф вида

(1),,«(р)}>М{(ы(и),огО*))}),

называется умножением графа 6 на подстановку оС и

обозначается (?*о(.

По аналогии с булевскими графами пусть

множество всевозможных.натуральных представлений графа, б , причем М1 * М] б;ДЛЯ любых ¿,j .

Определение 7.2. Подстановка << называется арифметическим автоморфизмом натурального арифметического графа б , если имеет место

Нетрудно видеть, что множество {р^} всевозможных подстановок, являющихся арифметическими автоморфизмами одного и того же натурального арифметического графа б , образует группу Гд .

Следствие 1Для графов, допускающих единственное натуральное представление, группа /¡5 арифметических автоморфизмов совпадает с его обычной вершинной группой Г(£) .

Например, доя трех различных натуральных арифметических графов с четырьмя вершинами N -[1,2,3,4]- со своими всевозможными порождающими множествами М{ , приведенными в таблице 3, группой арифметических автоморфизмов является группа диэдра $64 .

Таблица 3

б >--

Н£,5,6,7} М, {3,4,6} М5{5.7} М1{3,5,6}

М{ N¿3,5,6,8} М2 [3,4,7} МД5.6} Мг{4,5,7}

^,4,5,7} М*{4»6»7} М713'5! Иь{5'6»7}

^(3,4,5,6} М4 13,6,7} М,{4,5} м4 {3,4,5}

В § 8 на основе арифметического кодирования графов синтезируется группа арифметических автоморфизмов простых циклов с четырехзначной операцией, обладающая новыми свойствами [II*] ..

Рассмотрим множество всевозможных пар > =

= 0,1,...,2р -I, где р - простое число.

Определим на следующую операцию (•)

. £ъ+гпг п-*}) » если ./ четное, тп четное

(1+тп,71-з) , если 3 четное, тп нечетное

(¿-тп, ) , если ^ нечетное, тп четное

к (г-Шу п) , если ^ нечетное, тп нечетное, где сложение и вычитание берутся по чтьоо£2Р

Непосредственной проверкой можно убедиться, что множество пар 6 •|(i,j)j■ с указанной операцией удовлетворяет всем

требованиям группы: введенная операция ассоциативна, во множестве б {(I, ] )} существует единичный и обратный элементы.

Построенную группу арифметических автоморфизмов простых циклов обозначим 66 (р) ( />5^2 простое число).

Обозначим через Ъ -четное число, а через Н -нечетное число, £ = 0,2,...,2Р -2; // = 1.3.....2р -I.

Для изучения строения группы б б (Р) установлены следующие результаты.

Теорема 8.1. Коммутантом К группы 66 (Р) является абе-лева подгруппа . Ьг = 0,2,...,2 Р -2 порядка Р2 .

Теорема 8.2. Множества вида

Т={(1,Щи{(гг,Н)}

являются нормальными делителями порядка Zp2 группы GG (р) , где t 0,2,...,2p-2i Н,НиН2 = /,3,...,2р-/

Теорема 8.3. Множества вида

являются нормальными делителями порядка Р грушш 66 (Р) Аналогично можно показать, что подмножество порядка 2.р

&{{(0,ф{(р,г)}}, tip {{(г,о)}и{М}},Ъ=0,2,...,2р-2 также являются нормальными делителями группы 66 (р). Таким образом установлено, что группа 6G (р) имеет восемь собственных нормальных делителей.

К(рг), T(2ff), Т(2рг),Т(2р*), S(P), §(р>),й'р(2р), ЪрСгрКъ. 35) порядков рг, />, 2р , образующих полную систему.

На основе (8.35) следует, что группа GG(p) имеет 3 • 2 + 2 • I = 8 нормальных рядов длины 5

GG(p) => Т(2рг) о К(рг) з S(P)=>E в6(Р.) =>Т(2рг) =>К(рг) = 5(Р) => Б GGСР) => Т(2р2) ^%'p(3p)z>S(pj=>Е (8*36)

66(Р) => Т(2рг) "р(2р) => S (Р) => Е

Так как факторы этих рядов имеют простые порядки (2,2,р , р ) и (2,р , 2 ,р ), то построенные нормальные ряды являются композиционными.

Поэтому факторы полученных композиционных рядов являются

циклическими группами простых порядков 2 и р . Отсюда следует

Теорема 8.4. Группа (Р) сверхразрепшма.

2 2 '

Так как порядок группы (Р) равен 2 Р , то теорема 8.4 является частным, при £ = с* -2 , усилением классической теоремы Бернсайда о разрешимости групп порядка ра- е^ , где р, ф - простые числа. ■

В частности, непосредственным перебором всевозможных подстановок на ЭВМ можно убедиться, что группа ££ (Р) (случай р - 3) является группой арифметических автоморфизмов графов октаедра и треугольной призмы в смысле определения 7.2.

Множество подстановок, образующих группы 66 (з) и 66(5) приведены в приложении А.

Показано, что подмножество р{(и>,V-)}, и,У- =/, 3,. ..у2р-1 группы вВ (Р) , открытое относительно введенной четырехзначной -операции, при любом фиксированном (Х,у) £ 1/)} образует абелеву группу порядка Р2 относительно следующей тернарной операции

(и,У)(х,у)(и,,Щ)= (¿¿,V)ъХши,-*,г+Ч-уХ

Так как (х,у) может быть любым элементом из то группа V-)} является вместилищем рг изоморф-

ных групп порядка р2 . Такие группы будем называть тернарными группами.

Как известно, практическое применение теории групп в кристаллографии, физике твердого тела, квантовой механики и других областях естествознания связано с решением задачи пред-

отдаления этой группы. Указанное положение основывается на том, что всякая симметрия молекулярной структуры описывается неприводимыми представлениями группы и ее характерами.

В этой связи § 9 рассматривается задача представления группы б£> (. Для нахождения линейных представлений группы бб(Р) найдем классы сопряженных элементов (к.с.э.) этой группы. Показано, что элементы группы бр) можно разбить на II семейств

(¿= ■/,//) к.с.э., -удовлетворяющих условию

$гП 5/ = ¿^ , ¿?Л£ = бб(Р). 1=1

Описание семейств к.с.э., их строение и значения соответ-

ствующих параметров приведено в таблице 4.- .

Для нахождения характеров неприводимых представлений группы б б (Р) установлены следующие теоремы, раскрывающие

особенности ее структуры.

Теорема 9.1. Нормальные подгруппы

Щ(о,г)}и{(Ы}}, %"р{{(г,о)}м{(1,р)}> г=о,2р-2

изоморфны группе диэдра обр

Теорема 9.2. Группа бб(р) есть прямое произведение своих нормальных подгрупп об'р я %'р , т.е.

(р)^ Яр* Яр

Таблица 4

Збозн. 51 Описание множества семейства классов сопряженных элементов (к.с.э.) группы б ССР) Значения параметров Число элементов в к.с.э. Число К« С•3• в Число элементов во МН0Ж. 51 Структура подстановки

{(0,0)} - 1 1 1 (12р)

52 Ъ=0.2,...,2р-2 Р 1 Р <2Р)

{(Р>*)} Р 1 Р С2Р)

{(Н,Н$ Н = «,5,...,2р-1 Н1=1,3,-,2 р-1 Рг 1 Р2 (1*2Р'<)

Шо,г),(о,-Щ г*2,ц, 2 р-1 2 Р-1 (Рг)

Шъоиы)}} г= 2,1»,..., р-1 2 р-1 г Р-1 (Рг)

г=2,ь,..,р-1 ч 2(Р-1) ОррО

ъ < ъ, * = 2Г4..Г., р-а С,» 4.6,..., р-1 (Р-И(Р-З) & (Р-1)(Р-3) 2. (рг)

г. - р-1 (Р-1ХР-3) в (Р-1УР-3) г. (Рг)

Б«» Р+1 НИ,3,..., г 2р р-1 2 Р(Р~1) (2Р.)

5,< й(Н,0),(Н,2)1.../Н)2р-2)/-Н,0),(-НЛ..,(-Н,2р-2)}} ННД...,^ 2Р Р-1 2 р(р-0 (2Р)

ъ-т 2 =

(О

го

- 23 -

Теорема 9.3. Число неприводимых представлений группы Эв(р)

/Р+3 \2 равно {-¿г;

Расположение к.с.э. для групп: &£(з) и 66(5) приведены на рис.12.

Легко показать, что степени неприводимых представлений группы && (/>) удовлетворяют соотношению

На основании полученных результатоы приведем как пример таблицу характеров для группы С?в(з) (таблица 7).

Таблица 7

I 3 2 3 9 6 2 6 , 4 '

66(5) /с, к* к* К6 к, Кб К* К, к4

(0,0) (0,3) (2,0) (3,0) (3,3) (5,0) (0,2) (0,5) (2,2)

х,(о,о) I I 1 I I I I I I

Ыо,1) I -I I I -I I I -I I

Ыг.о) 2 о г 0 -I 2 0 -I

Х*(з,о) I I I -I -I -Т I I I

^(з.з) I -I I -I I -I I -I I

? <? -X -2 0 1 2 0 -I

? ? 2 Р 0 0 -I -I -I

2 -2 2 0 0 0 -1 I -I

X9(2.2) 4 0 -2 0 9 0 -2 0 I

Глава 1У. посвящена вопросам математического синтеза арифметических многогранников в трехмерном евклидовом пространстве и свойствам этих тел [7] .

Пространственная структура или кристаллическая решетка того или иного вещества в математической интерпретации является некоторым параметризированным графом (в частности, многогранником)^ котором длины ребер,координаты вершин и др. элементы взаи-

(1,1) (1,3) (1,5) (3,1) (3,3) (3,5) (5,1) (5,3) (5,5)

(1,4).(1,0) (1,2) ^(5,4) (5,0) (5,2)

(4,1) (4,5) (0,1) (0,5) (2,1) (2,5)

(4,3) (0,3) (2,3)

(4,4) (4,2) (2,4) (2,2)

(3,4) (3,0) (3,2)||(0,4) (0^2)

\

Л

(4,0) (2,0)

(0,0)

3?

3,

(3,3) (3,1) (3,5) (3,9) (3,7) (8,3) (8,1) (8,9) (8,7) (8,5)

(1,3) (1,1) (1,5) (1,9) (1,7) (6,3) (6,1) (6,9) (6,7) (6,5)

(5,3) (5,1) (5,5) (5,9) (5,7) (0,3) (0,1) (0,9) (0,7) (0,5)

(9,3) (9,1) (9,5) (9,9) (9,7) (4,3) (4,1) (4,9) (4,7) (4,5)

(7,3) (7,1) (7,5) (7,9) (7,7) (2,3) (2,1) (2,9) (2,7) (2,5)

/

Рис .12. А - расположение множеств в группе в6 (з) , в - в группе

мосвязанн и удовлетворяют соответствующим условиям, отражавдим геометрию этой структуры.

Физические, химические и др.методы синтеза кристаллов являются типичным примером закономерного построения структур. По аналогии, задача математического синтеза геометрических тел означает: заданный граф (многогранник) параметризировать так, чтобы по этим параметрам и некоторым условиям, накладываемым на вершины, найти координаты этих вершин в трехмерном евклидовом пространстве. Данная задача существенно основывается на следующем понятии:

Определение 10.1. Многогранник называется арифметическим,

если

1) соответствующий ему граф является арифметическим графом

2) длины ребер

удовлетворяют условию 1(4,4)1= \рщрп3 = урт<: , щ , п} еУ, т± &М.

Исходя из определения ЮЛ и ~евклидовой метрики в трехмерном пространстве задача математического синтеза сводится к решению системы алгебраических уравнений вида

П >Ч)> П} (зги, Щ), Щ +713 = ем

при определенных предположениях в виде условий нахождения четырех точек на плоскости.

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

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

5. Глава У посвящена информационным и статистическим свойствам дискретных объектов и их применению к задачам по автоматизации проектирования вычислительных систем [б,14] .

В § II исследуется проблема установления критериев оценки сложности дискретных объектов, являющаяся одной из важных в области теоретической информатики и ее приложений. Согласно определению информации, данному В.М.Глушковым (1964), как меры неравномерности в распределении материи или энергии в пространстве и времени, оценка сложности дискретных объектов основана на получении эффективных критериев, характеризующих степень неравномерности, содержащейся в структуре дискретного объекта. В настоящее время имеются работы в различных областях естествознания, в частности в химии (Бончев, 1984), где используются методы теории информации и теории графов дая решения задач оценки сложности химических и физических структур. Вопросы оценки информационной сложности (ранжирование) системы конечных множеств играют основополагающее значение при решении наиболее распространенной комбинаторной экстремальной задачи минимального покрытия.

В § 12 приводится алгоритм минимального покрытия, основанный на вычислении информационной сложности элементов исходной системы подмножеств [14] . Эта задача имеет многочисленные применения в различных областях - автоматизации проектирования вычислительных систем, распознавания образов, построения сетей связи и др.

Пусть на множестве N {п.^ из V- элементов задана некоторая система ..., подмножеств, обладающая свойством

0Х£ = /V . Требуется найти такую систему ¿^{Х^ ,Х{г,...,Х1\ ,

состоящую из минимального числа 5 поданожеств, входящих в & , для которых _0Х1К=// . Система ,Хг, ..^Х^} подмно-

жеств называется связной, если дая любых , Х-}, г^ ¿ существует система подмножеств {Хг, ,Х[2,..., .обладающая свойством

В дальнейшем предполагается, что семейство с?{Х1гХг,.--,Хт} удовлетворяет следующим двум условиям:

а) семейство ¿Р является связным;

б) в семейство имеет место упорядоченность подмножеств

- подселействоядровых (если оно имеется) предшествует подсемейству остальных или наоборот.

Согласно классификации подмножеств Х[ е (Р • данной Ю.И.Журавлевым (1962), семейство можно разбить на 3 взаимно непересекающихся класса А , В , С .

А (2М) - множество подмножеств из , входящих в объединение всех минимальных покрытий.

В(2Т\ ^.М) - множество подмножеств из ф , входящих в объединение всех тупиковых покрытий, минус множество поданожеств, входами* в объединение всех минимальных покрттий.

СС^^) - множество всех поданожеств, являющихся регуляр-

ными.

Следовательно

£Р= А и Б и С

Если через Э^еА • ^Х^В • • З^еФ соответственно обоз-

начить информационную сложность подмножеств, входящих в классы А • В • С , (ядро), то с содержательной точки зрения между этими величинами будут иметь место важные соотношения

^ХеЯ^хед » ^«л^хев • ^ХеА > ^Хес- (12.3) Пусть матрица инцидентности, соответствующая походной системе подмножеств б5{Х1 ,Х2,.„, » ™еет ВДД

(12.4)

Так как каждому столбцу матрицы (12. 4) можно поставить в соответствие два десятичных числа

_ ТП ^ ■

2 ' .5=1,71 (12.5)

Л/2(12.6)

с "прямым" и "обратным" порядками расположения двоичных разрядов,

то матрице (12.4) также поставим в соответствие два набора ,

{■}*}■ , состоящих^из п целых положительных чисел с суммами п п „

Величины ^

назовем соответственно прямой (У) и обратной (С7*) информационной сложностью матрицы Н ^ ||.

назовем информационной сложностью матрицы Р- II ^ II • Эта веж чина может интерпретироваться как аналог работы в термодинамических системах.

Выбрасывая по очереди { -ую строку а°Ьт) из матрицы р , получим матрицы размерности (тп-1)хП , каадой из

которой можно поставить в соответствие некоторую д.н.ф. (точнее псевдо д.н.ф., в которой возможны повторяющиеся конъюкции), состоящую из п нонъюкций И^ рангом ^(^¿^ = 7П .

т.е.

= у т.

1-1

(12.7)

Не нарушая общности, перенося понятие булевского графа из главы I на д.н.ф. , получим, что соответствует булевский граф, состоящий из т. изолированных ребер, с "прямым" ( ) и "обратным" (771%) весами, определяемыми в следующем порядке.

* и

По формулам (12.5), (12.6) вычисляются . .

Для всевозможных ь , 1, п вычисляются гэг,- Д.. по следующим формулам:

.если = 0 .если Тц- 1 « 7г

(12.8)

4И

4

л**

171-I

если = { если у^у =» О,

(12.9)

а* V

2ТП

, если /-. я О

Л]

, если^у = / , если/^/

* г1'1

* - г-1

(12.10)

Ч

, если ■£..

, если « V

(12. И)

- 30 -

= + ¿1} , т*- = ¿>*. (12.12)

Мь = % -ту , М*- 2 -тЪ (12.13)

По аналогш о 3 , £7* величины

о 71 0

= М1 (12.14)

соответственно назовем "прямой" ( ££ ) и "обратной" ( 3* ) информационной сложностью I -ой строки матрицы Р . На основе и 3* определим значение величины

(12Д6)

которую назовем информационной сложностью ь -ой строки матрицы р (или подмножества Х-в£/> ).

Многочисленные расчеты, проведенные на ЭВМ, показывают«что минимальное соответствует минимальной информативности ¿с-ой строки матрицы Р .

Следует отметить также, что в качестве меры информационной сложности двоичной матрицы (12,4) можно принять величину

, т ¿г-

¿-а < • (12д9)

которая хорошо отражает ее содержательную сложность.

Полученный результат позволяет построить эффективный алгоритм минимального покрытия, основанный на последовательном удалении из матрицы Р строк с минимальным 5{о . Построенный алгоритм был использован при решении некоторых задач по автоматизации проектирования вычислительных систем, разрабатываемых в ЕрНИйШе.

В § 13 исследуется статистические свойства арифметических

графов [?] и способы их применения к решению задач оценки качества размещения модулей при проектировании вычислительных систем.

Одной из основных областей применения методов теории графов являются задачи автоматизации проектирования вычислительных систем. Теоретические основы этого направления оказались связанными со многими разделами дискретного математического моделирования (Глушков и др., 1977; Горбатов, 1986). В частности, вопросы ароматизации и кодирования дискретных объектов, лежащие в основе данной работы, возникли из потребностей моделирования процедур синтеза цифровых автоматов на ЭВМ [1,2,3] . Особенностью задач из этой области является наличие нескольких критериев оптимальности, носящих, как правило, .взаимно противоречивый, конфликтующий характер, многовариантность решений и др. сложности, не гарантирующие оптимальности. Отсюда возникает необходимость широкого использования различных эвристических методов, обеспечивающих, как правило, локальную оптимальность. Комплекс задач по автоматизации проектирования включает в себя задачи разбиения и компановки, размещения, межсоединения и трассировки, которые тесно связаны между собой. Однако, ввиду наличия больших трудностей в решении общей задачи, они рассматриваются в отдельности.

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

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

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

Геометрические свойства а.г., в первую очередь их реализуемость в евклидовых пространствах [V] , показанная в предыдущей главе, и наличие универсальных кодирующих множеств (например множество Фибоначчи), над которыми любое представление графа является а.г. [б] , создали определенную формализованную среду, удобную для статистического моделирования задачи определения наиболее вероятной "длины схемы (графа)".

В связи с изложенным задача определения наиболее вероятной "длины графа" формально может быть описана следующим образом. Пусть б(фр I Му) - а. г. с р вершинами и ^ ребрами, пред-

-Заставленный над множеством Фр чисел Фибоначчи Фр= {1.2,3.5.....ир}г

3,4,6,..., Ыр^ + ЦрУ

и соответствующий заданному графу смежности модулей. В силу свойства чисел Фибоначчи [ = С р . Поэтому любое кодирование вершин заданного графа числами Фибоначчи обеспечивает его представление в виде а.г. Каждой случайной выборке (Ы^ , ,1Цр) состоящей из р различных чисел Фибоначчи, кодирующих вершины заданного графа £ , ставится в соответствие число

= (13.4)

которое согласно результатам предыдущей главы выражает сумму длин ребер а.г. б(Фр ¡М^) , соответствующую $ -му испытанию. Указанным способом может быть сформирован статистический ряд

аз.5)

из "длин графа" (б) . Ввиду отсутствия информации относительно вида теоретической функции распределения использованы методы аппроксимации экспериментальных данных эмпирическими распределениями Джонсона (Хан, Шапиро), характеризующиеся тремя семействами распределений , , Эи . Аппроксимация экспериментальных данных эмпирическими распределениями Джонсона осуществляется с помощью разработанной в Армянском НИИ энергетики программы на ЗВМ-1022. Блок-схема статистического моделщювания по нахождению наиболее вероятной "длины графа" представлена на рис.16.

В результате статистического моделирования определяются основные статистические параметры, как математическое ожидание £ о,

средне-квадратичное отклонение & и тип аппроксимируемой кривой. Полученные параметры 60£> приняты за основу формирования нового варианта алгоритма итеративного размещения модулей (Брейер), с улучшением 1фитерия длины и оценкой качества размещения.

Рис.16. I. Датчик псевдослучайных перестановок

(Яе, > >■■■> п1р 2' Кодирование вершин (¿,,г2,..Л°) графа б числами ФибоначчиФр{ 1,2,3,5,..., ир} . 3. Формирование представления а.г. 6(Фр I Му) 4. Вычисление (6) по формуле (13.4). 5. Проверка условия достаточности статистики. 6. Вычисление значения статистических параметров по распределению Джонсона и данных наиболее вероятной "длины графа". 0. Окончание.

Показатель качества размещения характеризуется величиной |/--£о| , где ^ длина проводника "на I -см шаге. Наиболее оптимальный вариант размещения соответствует условию •

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

Разработанные алгоритмы оценки информационной сложности д.н.ф. минимального покрытия, определения средней длины графа и др. реализованы комплексом Фортран 1У - программ на ЭВМ серии ЕС, нашедших применение в системах по автоматизации проектирования вычислительных систем.

Основное содержание диссертации опубликовано в работах:

1. Григорьян Ю.Г. Использование вычислительных машин для синтеза цифровых автоматов. Известия АН АрмССР (серия техн.наук), Ш. № 6, 1963, с.41-47.

2. Григорьян Ю.Г. Арифметический метод минимизации булевских функций, - Материалы научных семинаров по теоретическим и прикладным вопросам кибернетики. - Серия "Теория автоматов". - Киев,1964, с.3-24.

3. Григорьян Ю.Г. Вариационная задача функций алгебры логики и метод ее реализации на ЭВМ. - Кибернетика, 1967, й I, с.26-30.

4. Григорьян Ю.Г., Маноян Г.К. Некоторые вопросы арифметической интерпретации неориентированных графов. - Кибернетика, 1977,

№ 3, с.129-131.

5. Григорьян Ю.Г. Отображение сокращенных дизъюнктивных нормальных фощ на графы. - Кибернетика, 1979, Л 3, с.105-107.

6. Григорьян Ю.Г. Классификация и статистические свойства арифметических графов. - Кибернетика, 1979, № 6, с.9-12.

7. Григорьян Ю.Г, Геометрия арифметических графов. - Кибернетика, 1982, Ji 4, с.1-4.

8. Григорьян Ю.Г. Задача существования и вопросы представления натуральных арифметических графов. - Журнал выч.матем.и матем. физики АН СССР. 1984, й II, с.1751-1756.

9. Григорьян Ю.Г. Группы автоморфизмов булевских графов. -Вторая Всесоюзная конференция "Математические методы распознавания образов" (тезисы докладов), Дилижан, (АрмССР), 1985, с.47-19.

10. Григорьян Ю.Г., Адонц A.M. Группы автоморфизмов арифметических графов. - Труды ВЦ АН АрмССР и ЕГУ, Математические вопросы

кибернетики и вычислительной техники, том 15, 1988, с.174-175.

11. Григорьян Ю.Г. Группы арифметических автоморфизмов простых циклов. - Кибернетика, 1990, № 4, с.9-15.

12. Григорьян Ю.Г. Свойства регулярных натуральных арифметических графов. - Кибернетика, 1990, 1 5, с.112-113.

13. Григорьян Ю.Г. Группы, индуцируемые булевскими графами. - Кибернетика, 1990, № 6, с.Ш-ИЗ.

14. Григорьян Ю.Г. Информационные^ методы оценки сложности, дискретных объектов в стандартных представлениях. - П Всесоюзная конференция по актуальным проблемам информатики и вычислительной техники "ИНФОРМАТИКА-87" (тезисы докладов), Ереван, 1987, с.69-70.

Ю. Г. Григорян Теоретико-числовые, алгебраические и геометрические основы арифметических графов Подписано в печать 22.12.92 Формат бумаги 60x84 1/16 Тира» 100 экз. Заказ I. Бесплатно Отпечатано на ротапринтах в ВЦ РАН. 117333, Москва, ул. Вавилова, 40.