Введение к работе
Диссертация посвящена разработке математического аппарата для решения различных задач декомпозиции графов Бержа.
Актуальность темы. Одной из особенностей применяемых методов в теории графов является ориентация их на манипулирование с легко вычисляемыми локальными характеристиками графа с целью представить решение данной задачи в их терминах.
В диссертации рассматривается системный подход к решении таких задач как выяснение вида критических относительно вершинной раскраски графов,декомпозиции графов,изоморфизма и автоморфизмов графов.
Все перечисленные проблемы рассматриваются и решаются как задачи декомпозиции графа.
Понятие общей системы для раскрасок естественным образом возникает,если в качестве функции ее порождающей взять последовательность преобразований,изменяющих раскраску. Среди этих преобразований имеются и элементарные,играющие роль малых возмущений раскраски.В этой ситуации множество минимальных раскрасок представляет собой инвариантное множество и оно считается устойчивым,если любая последовательность элементарных преобразований приводит к минимальной раскраске.
Такой критерий на практике реализовать слоено и поэтому необходимо описать с единых позиций все минимальные раскраски.Сделать это удобнее всего с критическими относительно вершинной раскраски графами.
Введенное Дираком в 1952 году понятие критического графа играет важную роль в характеризации ҐЦ -хроматических графов и представляет собой минимальный в графе подграф, обладающий тем же хроматическим числом.Выяснение его вида имеет огромное прикладное значение и в математическом смысле представляет собой задачу на экстремум,решений которых в теории графов почти нет.К настоящему времени известен вид лишь 3-критческого графа.
В диссертации приводится вид ҐП -критических графов, В связи с этим следует отметить,что важным результатом этой части работы является распространение идей традиционной классической математики на графы,что и позволило достич указанных результатов.
Несмотря на длительную историю проблемы раскрашивания графов,к настоящему времени структура минимальной раскраски не известна.В диссертации сделана попытка описать эту структуру в терминах взаимосвязанности классов.
следующая задача декомпозиции графов - это задача декомпозиции по различным алгебраическим операциям.Она является разложением графа по данной операции на более простые графы. Известны многочисленные приложения этих задач в теории автоматов.
К настоящему времени достаточно конструктивных критериев (кроме очевидных) решения этой задачи нет.
В диссертации разработана арифметика пар,которая позволяет сформулировать критерий декомпозиции,основанный,как и в предыдущей задаче,на разложении множества вершин графа на классы.Аналогичная идея разложения вершин графа на классы используется и в другой задаче декомпозиции - задаче об изоморфизме и автоморфизмах графов и автоматов.
Исследование этих проблем ведется,в основном, в направлении создания более эффективных алгоритмов.база которых либо эвристическаяЕ.либо-очевидные свойства изоморфных графов.
В диссертации описана структура изоморфных графов в терминах взаимосвязи классов специальных разбиений.Такой подход позволяет распространить эти результаты на задачу описания автоморфизмов графов и автоматов.Соответствующее разбиение имеет свои особенности,позволяющие ответить на вопрос,можно ли по совпадению групп автоморфизмов графов сделать вывод об их изоморфизме.
С одной стороны принцип построения общей системы на графах позволил указать эффективные способы ргшения некоторых задач на экстремум,в частности,задачи о виде /У] -критического графа,с другой стороны,при решении этой задачи оказалось,что лучше всего эту задачу решать в терминах разложения
множества вершин графа на классы,в данном случае попарно несмежных вершин.
Дальнейшие исследования задач на графах показали,что с одной сторони принцип разложения вершин на классы по различным критериям можно эффективно использовать при решении задач об изоморфизме графов и об их автоморфизмах,прирешении задач декомпозиции графов по различным алгебраическим операциям и других задач,
Сдругой стороны принцип разложения вершин на классы объединяет все перечисленные задачи в одну - задачу декомпозиции.
Цель работы состоит в разработке математического аппарата для решения проблем декомпозиции и получения важных следствий,связанных с задачей минимальной раскраски,описания критических относительно вершинной раскраски графов,декомпозиции графов по различным операциям,изоморфизма и автоморфизмов графов.
Основные результаты диссертации состоят в сдедувщем.
I.Разработан математический аппарат для решения задач описания необходимого вида /У] -критических графов,минимальной раскраски,декомпозиции графов,описания изоморфизма и автоморфизмов графов и автоматов.
Это позволило показать,что в таких бедных информацией системах как граф можно пополнить ее за счет выделения в ней специальных частей и связей между ними,которых оказывается достаточно для решения поставленной задачи.В частности,введение понятия приведенной раскраски позволило использовать идеи классической математики для решения задач на экстремум,авведение гонятия представления графа позволило формализовать и арифметизировать задачу декомпозиции графа.И в том и другом случае для решения указанных задач существенно использовалась в различных аспектах информация о структуре графа.
2.Установлен необходимый вид 4,5 и fyj -критических графов, который в рамках необходимых условий критичности графа может служить критерием минимальности раскраски,а методом направленного спуска,по аналогии о классическими задачами, может служить процесс приведения раскраски,который порождает
обцув систему на графах.
Решение этой проблемы позволило продвинуть вперед вопрос о решении задач на экстремум в теории графов.
З.Выяснена структура минимальной раскраски относительно некоторых преобразований,
4.Приводится решение задачи декомпозиции графа по некоторым алгебраическим операциям.Для этого разработана арифметика пар чисел,в терминах которой формулируются критерии декомпозиции. Это позволило применить полученные результаты для решения задачи декомпозиции автоматов.
5іСформухирован критерий изоморфизма графов Берна. Описана структура автоморфизмов графа относительно графовс-кого отображения,
Это позволило распространить данные результаты на автоматы без выходов,а так же,используя структуру циклов автоморфизма относительно графовского отображения на задачу декомпозиции сети связи.
Научная новизна работа заключается в создании математического аппарата,позволяющего решить перечисленные выше зада-чи;создание методик моделирования задач оптимальной загрузки оборудования;дехомпозиции автоматов;декомпозиции сетей связи на базе результатов о автоморфизмах графа.
Практическая значимость. Результаты проведенных исследований используются при выполнении научно-технических разработок в ряде организаций.
Апробация работы. Материалы,представленные в диссертации докладывались на УП Всесоюзной конференции по проблемам теоретической кибернетихи (Иркутек, 1985),УШ Всесоюзной конференции по проблемам теоретической кибернетихи (Горький,1988), Всесоюзной научно-практической конференции по по прикладным аспектам управления сложными системами (Кемерово,1983),Международной школе-семинаре по методам оптимизации и их приложениям (Иркутек,1989),XI Всесоюзной конференции по проблемам теоретической кибернетики (Волгоград,1990);семинаре по теории графов факультета Вычислительной математики и кибернетики Московского универоитета,Семинаре по дискретной математике Одесского технологического института,Семинаре по дискретной
математике Самаркандского университета,Семинаре по прикладной математик е-процес сам управления факультета прикладной математики-процессов управления Ленинградского университета под руководством члена-корреспондента АН СССР В.И.Зубова, Публикации. По теме диссертации опубликовано 14 работ.' Основные результаты диссертации опубликованы в работах I - 8 .