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

г \ и

САНКТ-ПЕ1ВР5УРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи УДК 519.1+517.9

ГОРЬКОВОЙ Валерий Федорович

ПРИНЦИП ФАКТОРИЗАЦИИ В ЗАДАЧАХ ДЕКОМПОЗИЦИИ

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

исследованиях

АВТОРЕФЕРАТ

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

Санкт-Петербург 1993

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

университета

Официальные оппоненты: доктор физико-математических наук,

профессор Валаев К.Г. доктор физико-математических наук, профессор Колбин В.В. доктор технических наук,профессор Розенберг В.Я.

Ведуиая организация - СанкрПетербургский Государственный

технический университет

Защита состоится Ш^6**- 1993 г.

на заседании специализированного совета Д-063.57.33 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете

Адрес:Санкт-Петербург,В.О.,Ю линия,Д.33,ауд.88

Сдиссертацией можно ознакомится, в библиотеке им.А.М.Горького СГ.бГУ,Университетская наб.,7/9

Автореферат разослан " " 1993 г>

Учений секретарь докто р физико-матемз-тиччсуих наук

Яабко - А.П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Диссертация посвящена разработке математического аппарата для решения различных задач декомпозиции графов Бержа.

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

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

Все перечисленные проблемы рассматриваются и решаются как задачи декомпозиции графа.

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

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

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

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

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

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

К настоящему времени достаточно конструктивных критериев (кроме очевидных) решения этой задачи нет.

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

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

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

С одной стороны принцип построения общей системы на графах позволил указать эффективные способы ргшения некоторых задач на экстремум,в частности,задачи о виде /У] «критического графа,с другой стороны.при решении этой задачи оказалось ,что лучше всего эту задачу решать в терминах разложения

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

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

Сдругой стороны принцип разложения вераин на классы об»е-диняет все перечисленные задачи в одну - задачу декомпозиции.

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

Основные результаты диссертации состоят в следувщем.

1.Разработан математический аппарат для решения задач описания необходимого вида /У] -критических графов,минимальной раскраски,декомпозиции графов,описания изоморфизма и автоморфизмов графов и автоматов.

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

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

обцую систему на графах.

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

3.Выяснена структура минимальной раскраски относительно некоторых преобразований,

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

5^Сформухирован критерий изоморфизма графов Берна. Описана структура автоморфизмов графа относительно графовс-кого отображения.

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

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

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

Апробация работы. Материалы,представленные в диссертации докладывались на УП Всесоюзной конференции по проблемам теоретической кибернетики (Иркутек,1985),УШ Всесоюзной конференции по проблемам теоретической кибернетики (Горький,1988), Всесоюзной научно-практической конференции по по прикладным аспектам управления сложными системами (Кемерово,1983),Между народной школе-семинаре по методам оптимизации и их приложениям (Иркутек,1989),XI Всесоюзной конференции по проблемам теоретической кибернетики (Волгоград,1990);семинаре по теории графов факультета Вычислительной математики' и кибернетики Московского универоитета,Семинаре по дискретной математике Одесского технологического института,Семинаре по дискретной

математике Самаркандского университета,Семинаре по прикладной математике-процессам управления факультета прикладной математики-процессов управления Ленинградского университета под руководством члена-корреспондента АН СССР В.И.Зубова, Публикации. По теме диссертации опубликовано 14 работ." Основные результаты диссертации опубликованы в работах I - 8 .

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

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

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

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

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

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

Центральным,при выяснении вида Ю -критического графа, является случай /7? «4.0н является базой индукции.Случай

■3 для этой роли мало пригоден,так как только при 1Т> становится ясно как сопрягаются между собой входящие в критический граф подграфы гомоморфные 5-критическим.

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

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

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

Результаты,полученные для графов можно с незначительными изменениями распространить на автоматы.

В ранее известных работах,принадлежащих в основном Мелихову А.Н.,Дворянцеву Ю.А.,Карелину В.П.,Берштейну Л.С.,для решения указанных задач используется: локальная информация о графах,сводящаяся к численной характеризации вершин.

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

В 1974 году В.Г.Визингом была предложена идея сведения задачи об изоморфизме графов к задаче о плотности некоторого другого графа.Эта задача в вычислительном плане не менее проста чем иоходная.

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

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

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

Близкой к задаче оЗизоморфияме графов является задача об автоморфизмах.Этой проблемой занимались Фрухт Р.,Сабидуси Г., Харари Ф.,Кёниг Д.,Кэли А.,Избицкий Г..Карпов Ю. и другие. В этих работах,в основном,рассматриваются вопросы согласования групп автоморфизмов графов с операциями над графами, а также способы вычисления всей группы автоморфизмов.

Использование идеи построения специального разбиения версии графа и описания сэязн между классами этого разбиения позволило -охарактеризовать структуру автоморфизма в терминах графовского отображения.

Глава I посвящена общим системам на графах и минимальной

раскраске.

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

Определение. Будем говорить,что фактор-степень вершины ЗС из класса С* относительно минимальной раскраскиТ^С^ь^)-. ) графа С- равна .если имеется X. классов

(г . г С • \ таких,что

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

1.Перемещение верьин ) 5 С' фактор-степени меньше УЦ-1 из одного класса С^ в другой Су ,с вершинами которого они несмежны.

2.Если С* из - и С из С/ таковы,что подграф ((С'С/С"*)^ ) графа (у- является максимальным связным двудольным подграфом, то одновременное перемещение С* в Су и Сл в называется инверсией.Здесь Р сужение отображения р графа О- на (С/1УС^~)

Определение. Минимальную раскраску графа бу-

дем называть 1-приведенной относительно С{ и обозначать ,если вершины из С; имеют фактор-степень Яп-1 и никакие преобразования над (Ь^..., — изменялт их фактор-степеней. 2-приведенная раскраска относительно Су',\-*С определяется точно также как и 1-приведенная относительно раскраски Х/^) - C¿ . г Аналогично определяется ^Глп . Определение. Подмножества Хс - £ с и £ раскраски графа С- будем называть К -связными и обозначать »если в С{ и Су существуют подмножества ^ Х^ X. ¿' -и X¡^■X¡ такие,что подграф ( У X] р) является связным двудольным подграфом. ^ . ~

Определение. Два подмножества вершин С-,' и Ск из классов С< и Ск раскраски „Тон-) соответственно

будем дазывать Z -связными и обозначать С¿7. ,есди ^ R. Ск и для некоторых ¿Г. и Ct из Q. и С-к. соответственно подграф ( С. {/¿ю^) графа С. является максимальным по числу ^ершин связным двудольным подграфом над Ci- U С к, .Если £¿-£-1 '< J, то убудем писать Q. 2. С< «а соответствующий подграф (^d U С^,?) будем называть Z-кой и обозначать /7t-K • Z -номер 7 -ки над С; и С» /с •

Каждая Z.-ка П^^ порождается парй подмножеотв_вершин \ CJ£j и поэтому будем писать Пг] С г/ ). Положим ^ .

Из элементарных свойств минимальной приведенной раскраски следует,что в каждом классе Cj такое подмножество'с номером £ найдется.

Если -приведенная минимальная 3-рас-

краска графа Q- ,то имеет место соотношение

c;[s*-s 4'" ^

где ^ А,£> ^X означает,что в Д и ■£> найдетоя

по крайней мере одна пара смежных вершин,т.е. S -отношение смежности. • f[- ^ Из приведенного соотношения ( ) и того,чтоПfi^C^fn^ti) следует,что Cf£ , C-ti вместе с образует граф,содержащий цикл нечетной длины.Таким образом,если 3-критичесхий граф,то он является циклом нечетной длины,а так как цикл нечетной длины 3-хроматический,то все 3-критические графы исчерпываются циклами нечетной длины. Обозначим полученную конструкцию через

f35 (ос) .

В § 2 строится общая система на графах.Используя элементарные преобразования из § I можно получить частичные приведения, определенные для одного класса.Процесс приведения раскраски состоит из некоторого количества шагов,где Ь-0 это, шаг,которчй оставляет раскраску неизменной,а функция F^Jilï) реализующая этот процесс,является тождественной,т.е.

F^OD-r, X некоторая раскраска. " t

Из процесса приведения следует,что Ftc есть *^ство р-приведенных раскрасок о i р т .

Каждая последовательность приведений порождает окрестность некоторой раскраски X и следовательно топологию на множестве раскрасок ACO графа С-

Определение. Будем говорить,что в топологическом пространстве СА Ой-) V задана общая система,если определено

Ft -двупараиетрическое семейство преобразованийСА^Д) на себя,обладающее следующими свойствами

I) для любого Tí 6 А-Cff") и "t^ O множество

Ft.«) íAW) „р„ t»t0 г) FcV.CTl-x, _ _

3) для любого 7Г tJ'J множество «Ч. сл

¿г-!« таково,что

Определение. Множество И С Л ÍG-) называется инвариантным по отношению к общей системе,если из X é íl следует, что е ^ при любом to^0 .

Определение. Инвариантное множество М общей системы над (/1С&) ,J.) называется уо|ойчивым,если для любой раскраски ТГ fc ACG.)множество FtcK (7Г) при максимально возможном к. принадлежит М .

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

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

Для простоты,не влияющей на общность,мы будем рассматри-

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

В § 3 рассматривается минимальная раскраска 4-критйческих графов.

Если минимальную раскраску привести сначала относительно »а затем ,то раскраска- Т^ - С^ будет со-

держать в качестве подграфа ^ <?); $-<=£1 общем

случае С С-<) 3 ^ будет содержаться в пересечении неко- -торых I -ок Х1К ,а конструкция,содержащая )

будет иметь вид

I. [¡¿р •

71 ^ЗОС.З) - ^ Xj.Ot.cjj

Уг

Очевидно,в общем случае подмножества >

можно представить объединением подмножеств и

^■¡(¿¡Р) .приписав индексам ¿- значения! 0,1,3,5.. .,а индексам р значения 0^2,...И если положить Х-Кк^^^к, то формула для становится вполне определенной.

Имеет место теорема.

Теорема Г. Если С- -4-критический.то он содержит подграф который с точностью до гомоморфизма совпадает с

о £ ос £ ^(¿-¿ о)'

'Х-ю^хЯ к««'» > ХиглЗхЯХзсш/})] гц*,... . . Ъщо) I 2 Хле«,*) Ъ ;

Конструкция

¿ЯП«) СХ)

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

порождает еще по крайней мере два замечательных ^(-критических подграфа

' Щ!^ СЮ * I: х(к *0Г} Х^г К,к. Т.

СХ)[ ж, : и $ I),

Пусть СЮ

задается с помощью соотношений (I), тогда систему соотношений

К«*,») ) ;

1 ; ) Z^¿Л;^ Ъ

р '

будем называть ~7- -триангуляцией пары (Ос и <£НА/(3) ) относительно X. такого,что

Я«*,» ;

^¿с*,} ') & * £ у); г«1.1 ] % 3,...

а результат -триангуляции обозначать

где «С -неупорядоченная тройка индексов классов(С/. С, С Л Как уже отмечалось .процесс получения из

сводится к замене ребер инцидентных -X. -ми¿Поэтому смысл очевиден.Имеет место

следующая теорема.

Теорема 2. Если Сг- -5-критический,то он содержит подграф,который с точностью до гоморфизма совпадает о

где с(. пробегает множество индексов классов (2,3,4),(2,3,5), (2,4, 5),(3, А, 5),а 6 С/ удовлетворяет соотношениям

Здесь £ '

С помощью гомоморфизма из полученной конструкции можно получить, например, л

или

<2

41;

хЬгххаъЬгх*, л .

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

Имея в виду соотношение (о вершине X. можно говорить, что она опирается на X -ку П•

Если граф построен, то ^^¿/ь) (X)

строится по аналогии с ^ (X) .Здесь доказывается

теорема

Теорема 3. Бели

£ - ь

-критический граф (Я} т -Г ), то он содержит подграф,с точностью до гомоморфизма совпада. ющий а

где пробегает множество неупорядоченных троек индексов . классов из множества ( С^, £ $ , С. м ) .Здесь считается, что раскраска >ч) приведена последовательно относительно

С С Сл.). (-уп-х. ) #а опорные для ОС Х-ки определяются по тому же правилу,что и для м «5.

Процесс триангуляции по каждой тройке классов относительно

% порождает новую -ку и поэтому имеет место лемма.

Лемма. X -триангуляция

Г71кг

порождает ~2_ -ку ''С к при каждом фиксированном С .

Проблемам описания1 свойств минимальной раскраски посвящен § б.

Последовательность подмножеств вершин называется ^^-подвижной относительно раскраски ,если их одновременное перемещение по классам минимальной раскраски в некотором направлении не изменяет ее правильности.

Каждая! вершина Х- в образе ^ос относительно графов-ского отображения содержит как некоторую совокупность следов классов минимальной раскраски,так и возможно следы ](„,) -подвижных последовательностей.

Каждый клас минимальной раскраски до и после сдвига ^СЫ) ~ подвижных последовательностей содержит вершины фактор-степени ^У¡~i .Для таких вершин указывается структура их образа в терминах взаимодействия следов классов и следовательно Тему -подвижных последовательностей.

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

В § 7 рассматривается вопрос о структуре одной специальной раскраски.Здесь вершинная раскраска графа такова,что в каждом классе раскраски,кроме одного,содержится по две вершины и о,",ну вершину содержит один класс."Эта вершина смежна со всеми вершинами фактор-степени /и- / .содержащимися по одной в каждом классе,а все остальные классы связаны между собой с помощью одного из соотношений

Здесь означает,что вершина имеет фактор-сте-

пень Ъ , £ -отношение смежности.

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

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

Для каждой допустимой начальной тройки указаны соответст- • вующие 'замыкания.

В § 8 помещено приложение некоторых из рассмотренных в первой главе задач.Здесь речь идет об оптимальной загрузке оборудования.Рассматривается некоторое множество деталей и станков.О деталях известно,что в общей случае они могут обрабатываться на разных станках.Каждой детали и станку соответствует свое время обработки на данном станке.Рассматривается несколько'задач:время обработки любой детали на любом ' станке одно и тоже;каждая деталь обрабатывается на нескольких станках в л сбои порядку;для каждой детали указываются альтернативные варианты обработки с разным временем обработ-

ки.

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

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

Глава П посвя1цена декомпозиции графов Бержа по алгебраи ческим операциям умножения,суммы и композиции.

В §1 приводятся определения операций,а также определение представления графа,являющегося заданием взаимосвязи локальных характеристик графа.

Определение. Представлением графа называет-

ся пара П^О^Ар) .где ^

и Ар'.Тх-—Тх

ставит в соответствие каждой паре (Л^^рТх некоторое подмножество' из Тх по следующему правилу

Далее описываются некоторые общие свойства операций,их согласование.

В § 2,определенные в § I операции распространяются на представления.

Так,например,если Ю; Н О таковы,что ,а Н " X—»2. задается для любого С*> & Т- с помощью соотношения

1/2 - Рэс *

то имеет место теорема.

Теорема I. Представление графа есть пара Па = (Тг,Ди) .где Т^-Тх*!^ есть множество всевозможных произведений пар из Тх и Т^ таких, что

а Аи "Тт. —Т-^ таково,что

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

В § 3 указанные операции определяются над матрицами смеж-ноети графов.

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

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

При разложении используются некоторые вспомогательные по строения,позволяющие разбивать множество вершин графа на классы.Это так называемое правильное разбиение.

Имеет место теорема. _

Теорема 5. Граф раЗЛ0ЯИН

по операции $ тогда и только тогда,когда разбиение X множества X на классы Ъ , X ^ является правиль-

ным'.Здесь # любая из рассматриваемых операций.

В § 5 приводятся алгоритмы разложения графов.

В § 6 помещено приложение полученных результатов к задаче декомпозиции автоматов.

Рассматриваемые операций распространяются на автоматы и приводятся алгоритмы декомпозиции.

Глава Ш посвящена проблеме изоморфизма графов Бержа,

В § I обсуждается историческая и проблемная особенность . рассматриваемой задачи.

В § 2 доказывается теорема об изоморфизме графов Бержа. Принцип доказательства основывается на разбиении вершин ■

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

Теорема. Два графа gu(x,f) и н ml р> ,1x1*1*1

изоморфны тогда и только тогда,когда существует разбиение f и биекция •. X/j> —' Н.1 ? такие,что для любых<SeX/j?

и 2 £ .удовлетворяющих соотношениям ¡6| -|Z\ и

^(S) ZI коммутативна следующая диаграмма

х

А

л

рг

( с1 ^ Ц 1 ) ---{¿2-«,.- ]

Здесь Х/р и У/р -мтожества классов разбиения;

, - раз повторенные упорядо-

^ I ' -Ь • ^ --

ченные множества ' 1 С.) £ С. -перестановка;

^ и Рр соответствия между классами,порожденные отображениями Р и Р соответственно,

в § Э,в качестве близкой к проблеме изоморфизма графов, рассматривается задача об автоморфизмах автоматов без выходов,т.е. такой тройки А Р) ,где есть однозначное отображение.

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

Теорема. Разбиение. X множества и. порождает автоморфизм тогда и только тогда,когда

где '-к означает,что образ при каждом X пред-,

ставляет собой р раз повторенное упорядоченное множество а р -есть распространение Р на элементы 7Г

В § 4 доказывается теорема об автоморфизмах графа Бержа.

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

Теорема. Разбиение ? множества Л графа £«ад порождает автоморфизм тогда и только тогда,когда для любого класса £ и любого т>0 найдется такой,что

при I | ^ \ и при I «\<.1 - 1 .

Здесь означает,что левая часть,представляющая собой

множество элементов,принадлежащих одноку и тому же кл'аосу в образе относительно ¡- ,есть р раз повторенный

класс ^с.^ .порядок на котором с точностью до циклического сдвига совпадает с исходным порядком на нем.

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

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

Основные результаты диссертации опубликованы в следующих работах:

1.Горьковой В.Ф. О минимальной раскраске графов-В кн.Управ-ление динамическими системами,ЛГУ,1984,с.147-149.

2.Горьковой В.Ф. О минимальной раскраске 5-критических гра-фов-В кн.УП Всесоюзна® конференция по проблемам теоретической кибернетики. -Иркутск,1985,с.62-63.

3.Горьковой В.Ф.Необходимые условия М -критичности-В кн. Управление динамическими системами.ЛГУ,1991,с.57-61,

4.Горьковой В.Ф.Устойчивость общих систем на графах.-В кн. XI Всесоюзной конференции по проблемам теоретической кибернетики.- Волгоград,1990,с.32.

5.Горьковой В.Ф.О гипотезе Хадвигера.-В кн.Математические методы оптимизации и управления в сложных системах,Калинин, 1967,с.43-46.

6.Горьковой В.Ф.Минимальная раскраска 5-критических графов. - Вестник ЛУ,серия I,вып.1,1989,с.14-18.

7.Горьковой В.Ф..Егоров .М.Ю.О декомпозиции графов.-В кн,-Математические методы анализа управляемых процессов.ЛГУ, 1986,0.70-76.

в.Горьковой В.Ф.Обавтоморфизмах конечного автомата и изоморфизме графов.-В кн.Управление динамическими системами,вып.2, ЛГУ,с.34-43.

Подписано к печати 2G.01.D3. Заказ 525. Формат 60x84/10. Объем 1,25 п. л. Тираж 100.

Ломоносовская типография. 189510, г. Ломоносов, пр. Юного ленинца, О.