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

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

КОНОНОВА Наталия Владимировна

МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА О РАСКРАСКЕ НА ПРЕДФРАКТАЛЬНЫХ

ГРАФАХ

05 13 18 - Математическое моделирование, численные методы и комплексы программ

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

ООЗ164552

Ставрополь - 2008

Работа выполнена в Ставропольском институте экономики и управления имени О В Казначеева (филиал) ГОУ ВПО Пятигорский государственный технологический университет

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

Кочкаров Ахмат Магомедович

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

Семенчин Евгений Андреевич

доктор физико-математических наук, профессор Наталуха Игорь Анатольевич

Ведущая организация: Технологический институт Южного

Федерального Университета в г. Таганроге

Защита состоится « 16 » февраля 2008 г в 16 часов 30 минут на заседании совета по защите докторских и кандидатских диссертаций Д 212 256 08 при Ставропольском государственном университете по адресу 355009, Ставропольский край, г Ставрополь, ул Пушкина, 1, ауд 214

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

Автореферат разослан « 45*» января 2008 г

Ученый секретарь диссертационного совета

Л Б Копыткова

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

Актуальность темы исследования

На протяжении более чем ста лет с момента появления первой публикации Эйлера, заложившей начало теории графов, оптимизационные теоретико-графовые задачи не рассматривались в многокритериальном аспекте В 80-х годах прошлого века в школе профессора Бмеличева В А в Белорусском государственном университете были заложены основы многокритериальной оптимизации на графах, что позволило решить ряд сложных практических задач Интересные исследования по проблемам многокритериальной оптимизации на графах велись в Вычислительном Центре им. А А Дородницына АН СССР и Московском государственном университете имени М В Ломоносова Графы в этих задачах являлись моделями систем с фиксированной структурой Но перед современной наукой стоят новые задачи, которые требуют совершенно новых методов и подходов для моделирования сложных систем К таким системам относятся современные коммуникационные и информационные сети, структура которых претерпевает определенные изменения Вместе с тем, не исчезает необходимость решения классических теоретико-графовых и оптимизационных задач в системах с изменяющейся структурой связей между ее элементами Процесс изменения связей между элементами системы, изменения количества ее элементов и другие структурные преобразования в системе относят к области математического моделирования, называемой структурной динамикой

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

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

Задача минимальной раскраски встречается во многих прикладных проблемах авгоматизированного проектирования, достаточно назвать работы А И Мелихова, Л С Берштейна, ВМ Курейчика, А Я Тетельбаума Такими задачами в своё время занимался профессор ИГ Винтизенко В своей докторской диссертации, посвященной проблеме пространственной декомпозиции монтажно-коммутационного пространства, он описал процесс порождения фрактальных графов, затравкой которых является предложенный им «конверт-граф», и показал, что в основе структурных моделей оптимальной компоновки монтажно-коммутационного пространства лежат предфрактальные графы Он не использовал терминологии теории предфрактальных графов, так как на тот момент в науке не существовало соответствующего понятийного аппарата

Диссертация И Г Винтизенко стала предпосылкой введения понятия фрактальных (предфрактальных ) графов и их практического использования в непростых декомпозиционно-топологических задачах САПР В этих задачах исходной общей моделью является топология монтажно-коммутационного пространства, при оптимальной пространственной декомпозиции которого оказалось необходимым решать задачу о правильной раскраске предфрактальных графов Объектом исследования являются предфрактальные графы с затравками различных типов Предметом исследования являются

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

В соответствии с поставленной целью в диссертационном исследовании решались следующие задачи

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

• сформулировать многокритериальную задачу о раскраске на предфрактальных графах,

• обосновать практическую интерпретацию предложенных критериев,

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

• в случае, если предложенные алгоритмы выделяют неоптимальные решения, должны быть приведены оценки, гарантирующие отличие от оптимального решения на определенную величину,

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

Методы исследования

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

Научная новизна диссертационного исследования состоит в следующем

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

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

3 Предложены полиномиальные алгоритмы (/3, - /?3 и У\~Уг) вершинной раскраски предфрактального графа алгоритм /?, раскраски предфрактального графа, смежность старых ребер которого сохраняется, а затравка - полный граф, алгоритм /?2 раскраски предфрактального графа, смежность старых ребер которого сохраняется, алгоритм у?3 раскраски предфрактального графа, порожденного множеством затравок, смежность старых ребер которого сохраняется, алгоритм ух раскраски предфрактального графа, старые ребра которого не пересекаются, а затравка - полный граф, алгоритм у2 раскраски предфрактального графа, старые ребра которого не пересекаются, алгоритм у3 раскраски предфрактального графа, порожденного множе-

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

Практическая ценность и теоретическая значимость результатов исследования заключается в следующем

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

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

Личный вклад

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

На защиту выносятся следующие положения

1 Установлена связь между хроматическим число фрактального (предфрактального) графа и хроматическим числом его затравки / затравок

2 Обоснована невозможность построения однозначно раскрашиваемого предфрактального графа

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

Апробация и внедрение результатов исследования

Основные результаты работы докладывались

• на Первой Международной научно-технической конференции «Инфотелекоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2004),

• на Международной научной конференции «Системный синтез и прикладная синергетика» (Пятигорск, 2006),

• на V Международной конференции «Математическое моделирование в образовании, науке и производстве» (Тирасполь, 2007);

• на Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Домбай, 2007),

• на Всероссийском симпозиуме по прикладной и промышленной математике (Сочи-Адлер, 2007),

• на 34-ой научно-технической конференции профессорско-преподавательского состава, аспирантов, и студентов СевероКавказского государственного технического университета (Ставрополь, 2005),

• на 8-ой и 9-ой региональных научно-технических конференциях "Вузовская наука - Северо-Кавказскому региону" (Ставрополь, 2004 и 2005),

• на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской государственной технологической академии (Черкесск, 2001-2007),

• на семинарах Северо-Кавказского государственного технического университета (Ставрополь, 2006);

• на семинарах Ставропольского института экономики и управления имени О В Казначеева (Ставрополь, 2004-2007)

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

Публикации

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

Структура и объем диссертации

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

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

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

модели Некоторые синергетические идеи использованы в многокритериальной оптимизации

В первой главе «Многокритериальная задача раскраски пред-фрактального графа» сформулирована и обоснована многокритериальная задача о раскраске на предфрактальных графах Дана постановка классической теоретико-графовой задачи о раскраске графов, представлен обзор задач, сводимых к задаче о раскраске Приведена историческая справка о проблеме четырех красок

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

В основе определения фрактальных графов лежит операция замены вершины затравкой (ЗВЗ) Термином затравка условимся называть какой-либо связный граф Н = (№,0) Суть операции ЗВЗ заключается в следующем В данном графе (7 = (V, Е) у намеченной для замещения

вершины V е У выделяется множество У сУ, 7 = 1,2, ,|к|

смежных ей вершин Далее из графа <? удаляется вершина V и все инцидентные ей ребра Затем каждая вершина \>/ еУ, у =3,2, ,|к|

соединяется ^ребром с одной из вершин затравки Н Вершины соединяются произвольно (случайным образом) или по определенному правилу при необходимости

Предфрактальный граф будем обозначать через О, = (У1, Еь), где У1 - множество вершин графа, а Е1 - множество его ребер Определим его рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе 1 = 1,2,.. ъЬ-\ графе 01=(У!,Е1) каждую его вершину затравкой Н На этапе / = 1 предфрактальному графу соответствует затравка б, = Н •

Об описанном процессе говорят, что предфрактальный граф С1 порожден затравкой Н Процесс порождения предфрактального графа по существу есть процесс построения последовательности предфрактальных графов (7,,С?2, ,С£, называемой траекторией Фрактальный граф О = (У,Е), порожденный затравкой Н, определяется бесконечной траекторией

Сэ

Рисунок - Траектория предфрактального графа, построенного на затравке 17:,

Ребра предфрактального графа С£, появившиеся на / -ом, I е {1,2, ,Ц этапе порождения, будем называть ребрами ранга I Новыми ребрами предфрактального графа Оь назовем ребра ранга Ь, а все остальные ребра назовем старыми

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

/ = 1,2, ,Ь-г получим множество , г е {1,2, ,¿-1} блоков г-

го ранга, где г = 1,2, , п1~' - порядковый номер блока Термином подграф-затравка будем называть блок В\х], 5 = 1 ,«/ч первого ранга предфрактального графа , 1 = \,Ь из траектории Мощность множества 2(0, ) = {г(р}, / = 1,1, х = 1, й/ч всех подграф-затравок из Травкин1 -1

тории графа равна ¡2(0Г )1 = -——

и-1

На рисунке изображена траектория предфрактального графа </3=(К3,£3), порожденного затравкой Я = (IV,0 - полным 5-вершинным фафом Самыми "жирными" линиями нарисованы ребра подграф-затравки г\1) Линиями средней "жирности" нарисованы ребра подграф-затравок г,<2), , , г^, и И наконец, тонкими линиями нарисованы новые ребра предфрактального графа С3, которые образуют подграф-затравки , 5 = 1,25

Предфрактальный граф = (У1, Е,) условимся называть -графом, если он порожден и-вершинной, реберной связной затравкой Я = (IV,О)

Обобщением описанного процесса порождения предфрактального графа О, является такой случай, когда вместо единственной затравки Я используется множество затравок Н = {#,} = {Н1,Н2, ,Я,, ,Я;}, Т >2 Суть этого обобщения состоит в том, что при переходе от графа к графу (7; каждая вершина замещается некоторой затравкой Н, е Н, которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры

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

шинно взвешен, если каждой его вершине V е V, приписано действительное число е [а,Ь], где Ъ> а и а,Ь> О

Сформулируем постановку многокритериальной задачи вершинной раскраски предфрактального графа

Рассмотрим вершинно взвешенный предфрактальный граф Сь = (УЬ,ЕГ). порожденный затравкой Н = {УУ,0), у которой мощность множества вершин = п, а мощность множества ребер |<2| = д

Вершинная к -раскраска графа - это присвоение его вершинам к различных цветов Вершинная раскраска правильная, если никакие две смежные вершины графа не получают одного Цвета Граф называется вершинно &-раскрашиваемым, если он имеет правильную вершинную к -раскраску

Хроматическим числом дг(С) графа С называется минимальное число к, для которого С? - граф вершинно /с -раскрашиваемый Граф й называется к -хроматическим, если %(С) = к

Обозначим через X правильную раскраску (разбиение) множества вершин У! предфрактального графа 01~{У1,Е1) Согласно такой раскраске множество вершин предфрактального графа делится на одноцветные подмножества У1 = ,У[,

Всевозможные правильные раскраски {х} предфрактального графа (7£ образуют множество допустимых решений X = Х(Ос) = {*} (МДР)

Качество раскраски х на графе О, задается векторно-целевой функцией (ВЦФ)

Б(х) = (Р[ (х), Р2(х), ^з (х), /="4 (х), Р5 (х)) (1)

= к(х) ~> тт , (2)

где к(х) - число цветов в раскраске х

XdegvH,'mm, (3)

veV¡

где г = 1,2, ,к{х)

Ръ (х) = юах у - гшп с!е§ V —> тт, (4)

где I =1,2, ,к(х)

(*) X т1П ' ^

у<=К/

где I = 1,2, ,к(х)

Р5(х) = шахшт , (6)

не И/

где г = 1,2, ,к(х)

Все критерии (2)-(6) векторио-целевой функции (1) имеют конкретную содержательную интерпретацию

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

Теорема 2.2 Предфрактальный граф = (У1 , порожденный затравкой Н = (Ж,2), не содержащей простых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер одного ранга в процессе порождения не нарушается

Следствие 2.2.1 Предфрактальный граф Ос , порож-

денный затравкой Н = (РУ, О), не содержащей простых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер в процессе порождения не нарушается

СЛЕДСТВИЕ 2.2.2 Предфрактальный граф С)[ =(У1,Е1), порожденный множеством затравок Н = {#,}= {#,,#2, ,#-/}, Т >2, не содержащих простых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер одного ранга в процессе порождения не нарушается

Следспвие2.2.3 Предфрактальный граф Оь = (¥,_,£,), порожденный множеством затравок Н = {#,}= {#1;#2, ,#,, ,Н1), Т >2, не содержащих простых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер в процессе порождения не нарушается

СЛЕДСТВИЕ2.2.4 Предфрактальный граф порож-

денный затравкой Я = - деревом (звездой или цепью), является

2-хроматическим

Следствие2.2.5 Предфрактальный граф порож-

денный множеством затравок Н = {#,} = {Я,,Я2, ,Я,, ,Я/}, Т>2, где Я, - звезда или цепь, является 2-хроматическим

СЛЕДСТВИЕ 2.2.6 Предфрактальный граф - , Е/ ), порожденный множеством затравок Н = {Я,} = {Я|,Я2, ,Я„ ,Я7}, Т> 2, где Я, - дерево, является 2-хроматическим

Теорема 2.3 Предфрактальный граф ={у,,Ек), порожденный к -хроматической затравкой Я = (Ж,0 с сохранением смежности старых ребер, также является к -хроматическим, те ЛГ(С= *(//) = А

Следствие 2.3.1 Предфрактальный граф С1 = (V, ,Е,), порожденный множеством затравок Н = {я,}= {Я1;Я2, ,Я,, ,Я;}, Г>2 с сохранением смежности старых ребер, является к -хроматическим, т е

> гДе к = тМ ЛГ(Я,) /=1,Г

Множество всех вершин одного цве га раскрашенного графа является независимым и называется одноцветным классом

Пусть 0~(¥,Е) - помеченный граф Каждая его /(С?) -раскраска порождает разбиение множества его вершин на %{0) одноцветных классов Если %(0) = к и каждая к -раскраска графа С порождает одно и то же разбиение V, то (7 называется однозначно к -раскрашиваемым или просто однозначно раскрашиваемым

ТЕОРЕМА2.4 Однозначно к-раскрашиваемых предфрактальных графов О, = (У^, Еь), Ь > 2, порожденных одной затравкой с сохранением смежности старых ребер, для к > 2 не существует

Следствие 2.4.1 Однозначно к -раскрашиваемых предфрактальных графов, порожденных множеством затравок с сохранением смежности старых ребер, для к > 2 не существует

Граф й называется критическим, если %{С - у) < для любой его вершины V, если при этом /((7) = к , то граф О называется к-критическим

Теорема 2.6 Если каждый из блоков В,, г = 1, N связного графа к -раскрашиваемый, то и сам граф О также к -раскрашиваемый или, говоря иначе, ^(С) = шах %(В1)

теорема 2.7 Критических предфрактальных графов = (Уь, ), £ > 2, порожденных с сохранением смежности старых ребер, не существует

Теорема 2.8 Предфрактальный граф О, = (У1,Е1),Ь> 2, порожденный П -вершинной критической затравкой Я = (Ж,£?) с сохранением смежности старых ребер, имеет --- критических подграфов,

и-1

которыми являются его подграф-затравки

следствие2.8.1 Предфрактальный граф О, -(У1,Е1) ^>2, порожденный множеством критических затравок Н = \н,} = {//],Я2, ,Я,, ,Яу}, Т> 2 с сохранением смежности старых ребер, имеечг более чем --- критических подграфов, где п -

п-1

число вершин наименьшее среди вершин затравок Н = {н,}

Следствие 2.8.2 Хроматическое число предфрактального графа О/ = (У1,Е1), Ь>2, порожденного множеством критических затравок Н = {Я,} = {НЬН2, ;Нп , /7/ }, Т >2 с сохранением смежности старых ребер, вычисляется по правилу ) = шах /(Я,)

í=2 ,Т

Лемма 2.5 Для хроматического числа предфрактального графа О, = (У! ,Е1), 1>2, порожденного затравкой Я = (IV, 0 справедливо

неравенство 5:

Примечание 2.1 На основании теорем 2 3, 2 5-2 8, леммы 2 5 и следствий 2 3 1 и 2 8 1 можно утверждать, что для хроматического числа предфрактального графа С1-{у1,Е1'),Ь> 2, порожденного множеством затравок Н = {я,} = {я,, #2, ,Нп , Я/}, Т >2, справедливо неравенс гво ) - тМ х(Н,)

1=2 ,т

Теорема 2.9 Предфрактальный граф С1-{У1,Е1),Ь> 2, порожденный п -вершинной затравкой Я = (IV, (?), такой, что Г(С£) = х(Н) , имеет не менее и7'-1 критических подграфов

Следсгвие 2.9.1 Предфрактальный граф О, - (У, ,Е, ) , /„ > 2, порожденный я-вершинной критической затравкой # = (^,0, такой, что ~ Х(Ю> имеет не менее п1'х критических подграфов

Следствие 2.9.2 Предфрактальный граф С, = ,£■,),/.> 2, порожденный и-вершинной полной затравкой Н-{Ш,0) с непересекающимися старыми ребрами, имеет не менее пс~1 критических подграфов

Примечание 2.2 Интересен тот факт, что равенство хроматических чисел предфрактального графа и его затравки может наблюдаться при различных, в некотором смысле противоположных, условиях С одной стороны, согласно теореме 2 3, равенство хроматических чисел предфрактального графа и его затравки наблюдается при сохранении в процессе порождения смежности старых ребер предфрактального графа С другой стороны, это равенство, согласно теореме б 8 диссертационной работы профессора Кочкарова А М , сохраняется, наоборот, при непересекающихся старых ребрах в процессе порождения предфрактального графа полной затравкой

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

теорема 2.10 Для хроматического числа фрактального графа б = (У,Е), порожденного затравкой Я = (№г,д) с сохранением смежности старых ребер, справедливо равенство ¿(О) = х(Я)

следствие 2.10.1 Фрактальный граф О = {У,Е), порожденный множеством затравок Н = {#,}= {я,, Я2, , Я,, , Я,}, Т >2 с сохранением смежности старых ребер, является А:-хроматическим, те

Ж(<5) = к , где к = шах %{Н,)

ы ,т

Теорема 2.11 Хроматическое число фрактального графа О = (V, Е), порожденного затравкой Я = (РУ, 0 с сохранением смежности старых ребер, достигается на всех его подграф-затравках

Следствие 2.11.1 На фрактальном графе О = (У,Е), порожденном затравкой Я = (IV, (У) с сохранением смежности старых ребер, можно выделить конечные подграфы изоморфные предфрактальный графам <?1,(?2, ,67, из его траектории такие, что

Следствие 2.11.2 Хроматическое число фрактального графа 0=(У,Е), порожденного множеством затравок Н = {Я,}= {Я,,Я2, ,Я,, ,ЯГ}, Т > 2 с сохранением смежности старых ребер, достигается хотя бы на одной его подграф-затравке

Следствие 2.11 Л На фрактальном графе С = {У,Е), порожденном множеством затравок Н = {#,} = {Я,,Я2, ,Я(, ,Я7}, Г >2 с сохранением смежности старых ребер, можно выделить из его траектории конечные подграфы изоморфные предфрактальным графам С7,, 02, ..,0,, такие что х{в,) < ^(О) = шах %(Н,), / = 1,2, , Ь,

/=1,Г

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

Проведен обзор критериев планарности фрактальных графов и описаны классы минимально окрашиваемых фрактальных графов

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

Третья глава «Алгоритмы вершинной раскраски предфракталь-ных графов» посвящена алгоритмам построения вершинной раскраски предфрактальных графов Предложенные алгоритмы Д - Д3 и у] - у3 осуществляют поиск правильных раскрасок на вершинно взвешенных предфрактальных графах, порожденных при различных условиях

Первая группа алгоритмов Д - Д3 выделяет правильные раскраски на предфрактальных графах, порожденных с сохранением смежности старых ребер, а вторая группа у\ ~ У г > наоборот, выделяет правильные раскраски на предфрактальных графах, порожденных при непересекающихся старых ребрах

Общей чертой всех алгоритмов является то, что они выделяют правильные раскраски, оптимизирующие первый критерий (2) ВЦФ (1) сформулированной многокритериальной задачи (2) - (6) о вершинной раскраске на предфрактальных графах По остальным критериям для каждого алгоритма получены оценки

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

ТЕОРЕМА 3.3 Вычислительная сложность алгоритма Д на предфрак-тальном фафе О, = ), порожденном затравкой Н = (IV, О), где = N, равна О(М)

Теорема 3.4 Алгоритм /?, выделяет раскраску х^ на предфракталь-ном графе Оь =(У1,Е1), оптимальную по первому критерию Р} (хх) и оцениваемую по второму (и — 1) и7'"1 < /^(х,) < (и -1) Ь ■ п1^ , третьему Ръ(х,) = (и-1)(£-1) , четвертому п1~1 а < /^(х,) < п1~[ Ь и пятому Р5(х\) = ь-а

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

Теорема 3.6 Алгоритм /?2 выделяет раскраску х2 на предфракталь-ном графе (7Х =(У1,Е1}, оптимальную по первому критерию Р1(х1) и оцениваемую по второму (п -1) п1 / к < Р2(х]) <(п -1) Ь п11 к, третьему Р3(х2) = (п -\)(Ь -1), четвертому п11к а < Р4(х2) ^ пь /к Ь и пятому Р5(х2) = Ь-а

Алгоритм /?3 выделяет правильную раскраску на пред фрактальном графе, порожденном множеством произвольных затравок с сохранением смежности старых ребер

Теорема 3.8 Алгоритм /?3 выделяет раскраску х3 на предфракталь-ном графе йь = оптимальную по первому критерию Р{(х3) и

оцениваемую по второму (и — 1) п11к<Р2(хъ)<(п-\) Ь-п1 /к , третьему Р'ъ(хъ) = (я —1)(£-1), четвертому п11 к-а< Р4(х3)<п1 / к Ь и пятому Р5(х3) — Ь- а

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

ТЕОРЕМА 3.11 Вычислительная сложность алгоритма у1 на предфрактальном графе Оь = (У1 ,ЕЬ), порожденном затравкой Н = (№,£)) , где \УС\ = N, равна п)

ТЕОРЕМА 3.12 Алгоритм ух выделяет раскраску у1 на предфрак-тальном графе GL=(VL,EL), оптимальную по первому F,{ух) и третьему Ръ (у1 ) критерию и оцениваемую по второму (я-1) п1~х <F2(yl)<nL, четвертому nL~l а < F4(y^) <nL~l b и пятому F5(yt) = b-a

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

Теорема 3.15 Вычислительная сложность алгоритма у2 на пред-фрактальном графе Gl=(Vl,El), порожденном затравкой Я = (W,Q), где \VL\ = N, равна 0(N п)

Теорема 3.16 Алгоритм у2 выделяет раскраску у2 на предфракгаль-ном графе GL =(VL,EL), оптимальную по первому Fx{y2) и третьему F3(y2) критерию и оцениваемую по второму (и-1) nL /k<F2(y2)<n!+1 /к, четвертому nL/k а < F4(y7) < п1' /к b и пятому F5(y2) = b-a

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

ТЕОРЕМА 3.18 Вычислительная сложность алгоритма у3 на пред-фрактальном графе Gl =(Vl,El), порожденном множеством затравок H = {Я, = (iVt,Qt)} = {Я!,Я2,. ,Н„ ,НГ}, Т>2, старые ребра которого не пересекаются, равна 0(N я), где п = maxlw, I

isr 1 !

Теорема 3.19 Алгоритм уг выделяет раскраску у3 на предфракталь-ном графе G{ ~(VL,EL), оптимальную по первому Рх(уъ) и третьему F3(y3) критерию и оцениваемую по второму (и-1) п1 ¡к< Р2{уъ) < пш ! к, четвертому nL I к а < F4(y3) < п1 ! к b ипягому F5(y2) = Ь-а

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В ДИССЕРТАЦИОННОЙ РАБОТЕ

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

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

3 Детально рассмотрены и четко определены фрактальные и предфрактальные графы, порождаемые при различных условиях смежности ("несмежности") их старых ребер

4 В процессе исследования различных свойств и характеристик фрактальных и предфрактальных графов, связанных с их вершинной раскраской, установлена связь между хроматическим число фрактального (предфрактального) графа и хроматическим числом его затравки /затравок

5 Обоснована невозможность построения однозначно раскрашиваемого предфрактального графа Определены множества и мощности критических подграфов фрактальных и предфрактальных графов

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

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

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

• ГУП СК «Ставрополькоммунэлектро»,

• ФГУП СК «Крайтеплоэнерго»,

• ООО «Ставропольрегионгаз»;

• Ставропольский институт экономики и управления имени О В Казна-чеева (филиал) ГОУ ВПО Пятигорский государственный технологический университет

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ:

1 Кононова, H В Развитие фрактальных множеств / H В Кононова // Обозрение прикладной и промышленной математики - 2007 Том 14 - Выпуск 4 - С 727-729

2 Кононова, H В Алгоритмы вершинной раскраски предфракталь-ных графов, порожденных с сохранением смежности старых ребер / H В Кононова // Вестник Поморского университета - Серия «Естественные и точные науки» -2006 -№4 - С 126-135

3 Кононова, H В Плоскостная укладка и алгоритмы визуализации фрактальных графов / Т Л Каппушева, H В Кононова, Р А Коч-каров // Известия ТРТУ - Тематический выпуск "Перспективные системы и задачи управления" -2006 -№3 - С 305-312

4. Кононова, H В Алгоритмические вопросы раскраски предфрак-тальных и фрактальных графов / H В Кононова H В, Р А Кочка-ров // Электронный журнал «Исследовано в России», 258, 2500, 2006

5 Кононова H В Предфрактальные графы как модель инфотелеком-муникационной структуры / H В Кононова, С П Никищенко, В В Черняев // Инфотелекоммуникационные технологии в науке, производстве и образовании - Ставрополь Северо-Кавказский государственный технический университет, 2004 - С 57-59

6 Кононова, H В Синергетика и математическое моделирование I Н.В. Кононова // Сборник докладов Международной научной конференции «Системный анализ и прикладная синергетика» Пятигорск РИА-КМВ, 2006 -С 174-178

7 Кононова, H В Моделирование фрактального роста структуры / H В Кононова // Труды V международной конференции «Математическое моделирование в образовании, науке и производстве» -Тирасполь Изд-во Приднестровского университета, 2007 -С 45-46

8. Кононова, И В Алгоритмы вершинной раскраски фрактальных и предфрактальных графов / H В Кононова // Ставрополь СевероКавказский государственный технический университет, 2006 - 39 С. -Деп в ВИНИТИ №1217-В2006

9 Кононова, H В Особенности раскраски предфрактального графа / H В Кононова // Ставрополь Северо-Кавказский государственный технический университет, 2006 - 12 С. - Деп в ВИНИТИ №1218-В2006

10 Кононова, H В Свойства предфрактального графа, порожденного двудольной затравкой / H В Кононова, С П Никищенко, В В

Черняев // Сборник научных трудов СевКавГТУ Серия естественно-научная - 2005 - Выпуск 1 - С 37-46

11 Кононова, Н В Алгоритм раскраски предфрактального (и, ¿)-графа / Н В Кононова, А М Кочкаров // Материалы VIII региональной научно-технической конференции "Вузовская наука - СевероКавказскому региону" Том I - Ставрополь Северо-Кавказский государственный технический университет, 2004 - С 14

12 Кононова, Н В Алгоритм распознавания предфрактального дерева с затравкой /-цепь / Н В Кононова, А М Кочкаров // Материалы VIII региональной научно-технической конференции "Вузовская наука - Северо-Кавказскому региону" Том I - Ставрополь СевероКавказский государственный технический университет, 2004 -С. 15

13 Кононова, Н В Эффективный алгоритм построения р -центра предфрактального графа с затравкой регулярной степени / Н В Кононова, А А Узденов// Материалы XXXIV научно-технической конференции по результатам работы профессорско-преподавательского состава, аспирантов и студентов за 2004 год Том I - Ставрополь Северо-Кавказский государственный технический университет, 2005 - С 21

14 Кононова, Н В О полиномиальной разрешимости задач покрытия предфрактальных графов р-адическими деревьями / М А Тляби-чева, Н В Кононова // Материалы XXXIV научно-технической конференции по результатам работы профессорско-преподавательского состава, аспирантов и студентов за 2004 год Том I - Ставрополь Северо-Кавказский государственный технический университет, 2005 - С 18

15 Кононова, Н В Свойства простейших предфрактальных деревьев / В В Черняев, Н В Кононова // Материалы IX региональной научно-технической конференции "Вузовская наука - СевероКавказскому региону" Том I - Ставрополь Северо-Кавказский государственный технический университет, 2005 - С 8

16 Кононова, Н В ИКТ в системе высшего образования / Н В Кононова // Материалы IX региональной научно-технической конференции "Вузовская наука - Северо-Кавказскому региону". Том II - Ставрополь Северо-Кавказский государственный технический университет, 2005 - С 64

Подписано в печать 10 01 08 Формат 60x84 1/16 Услпечл1,28 Уч-изд л 0,95

Бумага офсетная Тираж 100 экз Заказ 3

Отпечатано в Издательско-полиграфическом комплексе Ставропольского государственного университета 355009, Ставрополь, ул Пушкина, 1

Введение.

Глава 1. Многокритериальная задача раскраски предфрактального графа.

1.1 Задача раскраски графов.

1.2 Фрактальные и предфрактальные графы.

1.3 Многокритериальная задача раскраски предфрактального графа.

• I • >

1.4 Выводы.

Глава 2. Особенности раскраски фрактальных и предфрактальных графов: свойства и характеристики.

2.1 Бихроматические предфрактальные графы.

2.2. Хроматическое число предфрактального графа,. порожденного с сохранением смежности старых ребер.

2.3. Об однозначной раскраске предфрактальных графов.

2.4. О критических подграфах предфрактального графа.

2.5. О раскраске фрактальных графов.

2.6. Раскраска плоских и планарных фрактальных. предфрактальных) графов.

2.6. Выводы.

Глава 3. Алгоритмы вершинной раскраски предфрактальных графов.

3.1. Алгоритмы раскраски простых графов.

3.2 Алгоритм Д раскраски предфрактального графа, смежность старых ребер которого сохраняется, а затравка - полный граф.

3.3 Алгоритм /?2 раскраски предфрактального графа, смежность старых ребер которого сохраняется.

3.4 Алгоритм /?3 раскраски предфрактального графа, порожденного множеством затравок, смежность старых ребер которого сохраняется.

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

3.6 Алгоритм у 2 раскраски пред фрактального графа, старые ребра которого не пересекаются.

3.7 Алгоритм уъ раскраски предфрактального графа, порожденного множеством затравок, старые ребра которого не пересекаются.

3.8 Сетевая модель оптимального монтажно-коммутационного пространства и раскраска её вершин.

3.9 Выводы.

Моделирование [109, 110, 130-132, 143, 158, 166] как способ познания окружающего мира, в современной науке существует недавно. Моделирование представляет собой объединение математических дисциплин (теория графов, исследование операций, математическое программирование, уравнения математической-физики и т.д.), на базе которых осуществляется решение целого ряда задач природы и общества. Естественно, формулировки задач являются отражением реальных процессов и явлений, которые приносят пользу или несут угрожающий характер для деятельности человека. Моделирование сложных процессов и структур вынуждает ученых объединять старые и создавать новые математические аппараты и инструменты.

Начало 70-х годов прошлого века было ознаменовано появлением новой научной парадигмы, называемой синергетикой [12, 23, 45, 50, 115, 122, 172-174] (от греч. synergeia - совместное действие, сотрудничество). Синергетика, основы, которой были заложены, Германом Хакеном и лауреатом Нобелевской премии Иваном Пригожиным, определяется как наука о коллективных статистических и динамических явлениях в закрытых и открытых многокомпонентных системах с «кооперативным» взаимодействием элементов систем. В физике, химии и биологии синергетика занимается структурными особенностями пространственно-временной самоорганизации [12, 23, 45, 50, 115, 122, 172-174] систем. Самоорганизация возникает в системах большой размерности и по сути представляет собой совместное существование взаиморегулируемых и взаимозависимых подсистем. Оказывается, в этом понимании между различными системами существует тесная связь, даже если они состоят из разнородных элементов с существенно отличными элементарными взаимодействиями.

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

Во многих гидродинамических системах ключевое значение имеет наличие в них диссипативных процессов (вязкости, диффузии, теплопроводности). Они позволяют исследуемым системам "забыть" начальные данные и независимо от их "деталей" сформировать с течением времени одни и те же или похожие пространственно-временные структуры. Иными словами, немного (а иногда и сильно) изменив начальный профиль (начальные данные в соответствующей задаче математической физики), в конце концов мы получаем одно и то же стационарное распределение переменных в пространстве. Чтобы подчеркнуть это обстоятельство, такие структуры, с легкой руки И.Р. Пригожина, стали называть диссипативными структурами [23]. В основе большинства исследований научной школы И.Р. Пригожина лежали системы параболических уравнений типа реакция-диффузия ut = I\uxx+ f (и,v\ vt =D2 Vxx+g(u,v), n/=0. t=0,/

0<x</, w(x,0) = mo(^)3 v(x,0) = vq(x), ux,Vx

Если говорить о парадигме диссипативных структур как о подходе к анализу спонтанного возникновения упорядоченности в нелинейных средах, т.е. о самоорганизации, то следует сказать и о научной школе член-корреспондента РАН С.П. Курдюмова. Научная школа С.П. Курдюмова сформировалась в Институте прикладной математики им. М.В. Келдыша РАН, в МГУ им. М.В. Ломоносова, в Московском физико-техническом институте в 80-е годы прошлого столетия. Усилия участников этой научной школы были вложены в построение качественной теории нелинейного уравнения теплопроводности с объемным источником, так называемой модели тепловых структур [50]

Tt = div(k(T) grad T) + 0(T).

Качественная теория, отражающая в основном эффекты, понятые с помощью компьютерного моделирования, потребовала новых математических идей, существенно опирающихся на то, что мы имеем дело с одной переменной Т, а не с их набором. В отличие от стационарных диссипативных структур, которые изучались в брюссельской школе под руководством И.Р. Пригожина, в научной школе С.П. Курдюмова исследовались нестационарные диссипативные структуры, развивающиеся в режиме с обострением. Под режимом с обострением понимают такие законы изменения параметров исследуемой системы, когда одна или несколько описывающих ее величин неограниченно возрастает за ограниченное время. В научной школе С.П. Курдюмова было открыто явление локализации тепла, обнаружены и исследованы так называемые собственные функции нелинейной среды, описывающие, как правило, волны горения, сохраняющие в процессе эволюции свою форму. Они описываются автомодельными решениями исходного нелинейного уравнения теплопроводности, которое имеет вид Т = g(t) f(x! (p{t)), где функция g(t) задает закон роста амплитуды возникающей диссипативной структуры, cp{t) - закон изменения ее полуширины, а функция / - её форму [50].

В 1963 году американский метеоролог Эдвард Лоренц предложил простейшую модель, описывающую конвекцию воздуха (она играет важную роль в динамике атмосферы). Целью этой работы был ответ на вопрос: почему стремительное совершенствование компьютеров, математических моделей и вычислительных алгоритмов не привело к созданию методики получения достоверных среднесрочных (на 2-3 недели вперед) прогнозов погоды. Эта модель описывается внешне очень простыми уравнениями [14] х = — сг(х + -j j — — xz + гх- у, z — xy — bz где переменная х характеризует поле скоростей, у и z — поля температур жидкости. Здесь г = R/Rc, где R — число Рэлея, a Rc — его критическое значение; <7 — число Прандтля; b — постоянная, связанная с геометрией задачи. Компьютерный анализ системы Лоренца привел к принципиальному результату. Им был открыт динамический хаос, т.е. непериодическое движение в детерминированных системах (то есть в таких, где будущее однозначно определяется прошлым), имеющее конечный горизонт прогноза.

Рисунок 1 - Аттрактор Лоренца

Картина, полученная на компьютере (расчет проводился при г=28, сг=10, Ь=8/3), убедила Э. Лоренца, что он открыл новое явление - динамический хаос. Этот клубок траекторий, называемый сейчас аттрактором Лоренца, описывает непериодическое движение с конечным горизонтом прогноза.

С точки зрения математики, можно считать, что любая динамическая система, что бы она ни моделировала, описывает движение точки в фазовом пространстве. Важнейшая характеристика этого пространства - его размерность, или, попросту говоря, количество ортогональных осей, которое необходимо задать для определения состояния системы. Если считать, что точка, двигаясь в фазовом пространстве, оставляет за собой след, то динамическому хаосу будет соответствовать клубок траекторий. Например, такой, как показан на рис. 1. Здесь размерность фазового пространства всего 3 (это пространство х, у, z). Замечательно, что такие удивительные объекты существу

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

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

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

В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и/или нетривиальных связей между ними. А с другой - речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны.

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

Системы с простой структурой, к примеру - иерархической, могут демонстрировать очень сложное нетривиальное поведение [123].

2 /+1 /

-1

Рисунок 2 - Фрагмент иерархической системы

Каждый элемент /-го уровня состоит из трех элементов (7-1)-ого уровня. Элементы системы могут быть исправны или дефектны (показаны заливкой). Состояние каждого элемента определяется состоянием образующих его элементов предыдущего уровня, а также его собственной восприимчивостью к дефектам.

Многие системы обладают простой иерархической структурой, фрагмент которой изображен на рис. 2. Например, литосферу Земли можно представить как систему блоков, разделенных разломами. Каждый из этих блоков делится на более мелкие, те, в свою очередь, на еще более мелкие и т.д. Геофизики выделяют более 30 иерархических уровней в земной коре от тектонических плит протяженностью-в тысячи километров до зерен горных пород миллиметрового размера. Большие землетрясения обычно сопровождаются многочисленными повторными толчками — афтершоками, которые каскадом перераспределяют напряжение вниз по иерархии разломов. А подготовка землетрясения происходит посредством обратного каскада передачи напряжения, восходящего с нижних уровней иерархии к верхним.

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

Иерархической системой является и электорат. Он также делится на несколько групп со своими интересами. Каждая из них складывается из более мелких подгрупп и т.д. — вплоть до отдельного избирателя.

Мы можем наблюдать поведение иерархических систем только на верхних уровнях иерархии (землетрясения, исполнение распоряжений, результаты голосования). Однако причины событий лежат на нижних уровнях, и важно представлять, как происходит взаимодействие уровней.

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

Термин "фрактал" (лат. fractus дроблёный) был введен в обращение французским математиком Бенуа Мандельбротом в 1975 году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, ценность подобных идей в науке была осознана лишь в 70-е годы прошлого столетия. Важную роль в широком распространении идей фрактальной геометрии сыграла книга Б. Мандельброта "Фрактальная геометрия природы" [124]. Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной (под размерностью понимается размерность Хаусдорфа-Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая впоследствии А.С. Безиковичем) [6, 15, 124, 127, 167, 169, 171, 178]. Основой новой геометрии является идея самоподобия [6, 15, 124, 127, 167, 169, 171, 178]. Она выражает тот факт, что иерархический принцип организации фрактальных структур не претерпевает значительных изменений при рассмотрении их с различным увеличением. В результате эти структуры на малых масштабах выглядят в среднем так же, как и на больших. Здесь следует провести разницу между геометрией Евклида, имеющей дело исключительно с гладкими кривыми, и бесконечно изрезанными самоподобными фрактальными кривыми. Элементы кривых у Евклида всегда самоподобны, но тривиальным образом: все кривые являются локально прямыми, а прямая всегда са-моподобна. Фрактальная же кривая в идеале, на любых, даже самых маленьких масштабах, не сводится к прямой и является в общем случае геометрически нерегулярной, хаотичной [6, 15, 124, 127, 167, 169, 171, 178].

Re [с]

А. п=1 п=2 Л

Рисунок 3 - Множество Мандельброта

Фракталами являются, например, странные аттракторы (рис. 1), которые лежат в основе исследования динамических систем с хаотическим поведением. Вообще говоря, существует классификация фрактальных объектов [124]. Среди них можно выделить множество Мандельброта, изображенное на рис. 3, и кривую Коха - на рис. 4. Первое обычно относят к алгеб

Чл? <L/bu раическим фракталам, второе — к гео-Рисучок 4 - Кривая Коха метрическим.

Работы, связанные с исследование фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но не имеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги [178]. В настоящее время о перспективности и значимости исследований, связанных с фрактальными множествами, можно судить по п=4 регулярно проводимым конференциям и периодическим изданиям, целиком посвященным соответствующей тематике. Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрактальных множеств [6, 15, 124, 127, 167, 169, 171, 178]. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабно-инвариантные) графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачивае-мости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких, как коммуникационные сети.

На протяжении более чем ста лет с момента появления первой публикации Эйлера, заложившей начала теории графов, оптимизационные теоретико-графовые задачи [2, 5, 7, 11, 14, 24, 29, 47, 106, 111, 114, 118, 126, 128, 135, 149-154, 159, 161, 163, 164, 168, 170, 175, 176] не рассматривались в многокритериальном аспекте [4, 13, 18, 20-22, 25, 42-44, 49, 84, 112, 116, 117, 134, 142-148, 162, 165, 177, 179]. В 80-х годах в школе профессора Емеличе-ва В.А. в Белорусском государственном университете были заложены основы многокритериальной оптимизации на графах [16, 17, 26-28, 30-41, 46, 96, 97, 102, 108, 138-141, 157, 160], что позволило решить ряд сложных практических задач. Интересные исследования по проблемам многокритериальной оптимизации на графах велись в Вычислительном Центре АН СССР [119121, 125, 133] и Московском Государственном Университете М.И. Ломоносова [1]. Графы в этих задачах являлись моделями систем с фиксированной структурой. Но перед современной наукой стоят новые задачи, которые требуют совершенно новых методов и подходов для моделирования сложных систем. К таким системам относятся современные коммуникационные и информационные сети, структура которых претерпевает определенные изменения. Вместе с тем, не исчезает необходимость решения классических теоретико-графовых и оптимизационных задач в системах с изменяющейся структурой связей между ее элементами.

Процесс изменения связей между элементами системы, изменения количества ее элементов и другие структурные преобразования в системе являются областью интересов структурной динамики [93, 94]. В общем случае можно говорить о различных изменениях структуры системы — о различных сценариях структурной динамики. Особо стоит выделить рост структуры, т.е. появление новых элементов и связей в системе. Такой сценарий присущ многим сетям связи, среди них — информационные, электроэнергетические, WWW (Internet), коммуникационные системы и т.д. В случае, когда структура системы "растет" одинаково и одновременно во всех доступных направлениях, принято говорить, что система имеет фрактальный рост. Фрактальный рост структуры системы моделируется фрактальным графом. Существенное распространение идеи структурной динамики и фрактального роста получилось благодаря»исследованиям [9, 85-92, 95, 98, 99-105, 156], проведенным в школе профессора Кочкарова A.M. При этом своего решения в системах с изменяющейся структурой потребовало значительное количество практических оптимизационных задач с многими критериями. Некоторые из них, такие как многокритериальная задача покрытия предфрактального графа простыми цепями, многокритериальная задача покрытия предфрактального графа звездами ранговых типов, многокритериальная задача о назначениях на предфрактальных графах, многокритериальная задача Эйлера на предфрак-тальных графах, удалось успешно решить [3, 8-10, 48, 68-83, 107, 136, 137, 155]. Одной из таких задач посвящена и настоящая диссертационная работа.

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

В соответствии с поставленной целью в диссертационном исследовании решались следующие задачи:

• сформулировать многокритериальную задачу о раскраске на предфрак-тальных графах;

• обосновать практическую интерпретацию предложенных критериев;

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

• в случае, если предложенные алгоритмы выделяют неоптимальные решения, должны быть приведены оценки, гарантирующие отличие от оптимального решения на определенную величину;

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

На защиту выносятся следующие положения, результаты и выводы:

• установлена связь между хроматическим число фрактального (пред-фрактального) графа и хроматическим числом его затравки / затравок.

• обоснована невозможность построения однозначно раскрашиваемого предфрактального графа.

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

3.9 Выводы

В третьей главе диссертационной работы предложены алгоритмы (Р\~Ръ и У\~7з) вершинной раскраски предфрактального графа. Каждый из алгоритмов оптимизирует один или несколько критериев заданной в первой главе многокритериальной функции.

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

• алгоритм Д раскраски предфрактального графа, смежность старых ребер которого сохраняется, а затравка - полный граф;

• алгоритм /?2 раскраски предфрактального графа, смежность старых ребер которого сохраняется;

• алгоритм /?3 раскраски предфрактального графа, порожденного множеством затравок, смежность старых ребер которого сохраняется;

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

• алгоритм у2 раскраски предфрактального графа, старые ребра которого не пересекаются;

• алгоритм у3 раскраски предфрактального графа, порожденного множеством затравок, старые ребра которого не пересекаются.

Заключение

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

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

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

3. Детально рассмотрены и четко определены фрактальные и предфрактальные графы, порождаемые при различных условиях смежности ("несмежности") их старых ребер.

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

5. Обоснована невозможность построения однозначно раскрашиваемого предфрактального графа. Определены множества и мощности критических подграфов фрактальных и предфрактальных графов.

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

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

1. Абрамова М.В. Некоторые аспекты векторной оптимизации и ее приложения: Автореф. Диссертация на соискание учёной степени кандидата физико-математических наук. — М.: МГУ, ф. ВМиК, 1987.

2. Авондо-Бодино Дж. Применение в экономике теории графов. М.: Прогресс, 1966.

3. Айбазов Б.А., Кочкаров A.M. Экономико-математическая модель с виртуальными каналами // IV Научно-практическая конференция "Решение научно-технических и социально-экономических проблем современности". Труд. конф. Черкесск: КЧТИ, 2002.

4. Айзерма М.А., Алескеров Ф.Т. Выбор вариантов. Основы теории. М.: Наука, 1990.

5. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "РХД", 2001.

6. Ахромеева Т.С., Курдюмов С.П., Малинецкий Г.Г., Самарский А.А. Нестационарные структуры и диффузионный хаос. М:: Наука, 1992'.

7. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

8. Батчаев И.З. Об одной многокритериальной задаче покрытия предфрактальных графов звездами одного рангового типа // Известия Кабардино-Балкарского научного центра РАН. 2002. Т. 8, № 1. - С. 1—5.

9. Березина Л.Ю. Графы и их применение. М.: Просвещение, 1979.

10. Безручко Б.П., Короновский А.А., Трубецков Д.И., Храмов А.Е. Путь в синергетику. Экскурс в десяти лекциях. М.: КомКнига, 2005.

11. Березовский Б.А., Барышкин Ю.М., Борзенко В.И., Кемпнер JI.M. Многокритериальная оптимизация: математические аспекты. — М.: Наука, 1989.

12. БержК. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962.

13. Божокин С.В., Паршин Д.А. Фракталы и мультифракталы. — Ижевск: НИЦ«РХД», 2001.

14. Бугаев Ю.В. Применение прямого обобщения скалярных алгоритмов в векторной оптимизации на графах// Дискретная математика. 2001.Т. 13. - № 3. - С. 110-124.

15. Бухтояров С.Е., ЕмеличевВ.А. Параметризация принципа оптимальности ("от Парето до Слейтера") и устойчивость многокритериальных траекторных задач // Дискретный анализ и исследование операций. -Серия 2. 2003. - Т. 10. - № 2. - С. 3-18.

16. Венцель Е.С. Введение в исследование операций. М.: Сов. радио, 1964.

17. ГафтМ.Г. Принятие решений при многих критериях. М.: Знание, 1979.

18. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

19. ГиллФ., МюрейУ., РайтМ. Практическая оптимизация. М.: Мир, 1985.

20. Гленсдорф П., Пригожин И. Термодинамическая теория структуры, устойчивости и флуктуаций. М.: Едиториал УРСС, 2003.

21. Дистель Р. Теория графов. Новосибирск: Издательство Института Математики, 2002.

22. Дубов Ю.А., Травкин СИ., ЯкимецВ.Н. Многокритериальные модели формирования и выбора вариантов систем. М.: Наука, 1986.

23. Емеличев В.А., Гирлих Э., Янушкевич О.А. Лексикографические опти-мумы многокритериальной задачи // Дискретный анализ и исследование операций. Серия 1. - 1997.- Т. 4. - № 2. - С. 3-14.

24. Емеличев В.А., Кличко В.Н. Об устойчивости паретовского оптимума векторной задачи булева программирования // Дискретная математика. 1999. - Т.11. - № 4. - С. 27-32.

25. Емеличев В.А., Кравцов М.К. О комбинаторных задачах векторной оптимизации // Дискретная математика. 1995. Т. 7, № 1. — С. 3—18.

26. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

27. Емеличев В.А., Пашкевич А. В. О линейной свертке критериев в векторной дискретной оптимизации // Дискретный анализ и исследование операций. Серия 2. - 2000. - Т. 7. - № 2. - С. 12-21.

28. Емеличев В.А., Пашкевич А.В. Об условиях эффективности решения многокритериальной дискретной задачи// Дискретная математика. — 2002. Т. 14. - № 1. - С. 17-29.

29. Емеличев В.А., Пашкевич А.В., Янушкевич О.А. Условия эффективности решения задачи векторной дискретной оптимизации // Дискретная математика. 1999. - Т. 11. - № 1. - С. 140-145.

30. Емеличев В.А., Перепелица В.А. К оценке сложности многокритериальных транспортных задач// Докл. АН БССР. 1986. - Том XXX. -№ 7. - С. 593-596.

31. Емеличев В.А., Перепелица В.А. Многокритериальная задача об остовах графа. // Докл. АН СССР. 1988. - Том 298. - № 3. - С. 544-547.

32. Емеличев В.А., Перепелица В.А. О мощности множества альтернатив в дискретных многокритериальных задачах// Дискретная математика. -1991. Т. 3. - № 3. - С. 3-12.

33. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах // Журнал вычисл. матем. и матем. физ. 1989. - № 2. - С. 171-183.

34. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. Т. 6, № 1. - С. 3-33.

35. Емеличев В.А., Подкопаев Д.П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2. - 2001. - Т. 8. - № 1. -С.47-69.

36. Емеличев В А., Степанишина Ю.В. Многокритериальные комбинаторные линейные задачи: параметризация принципа оптимальности и устойчивость эффективных решений// Дискретная математика. 2001.Т. 13.- №4.-С. 43-51.

37. Емеличев В.А., Янушкевич О.А. О задачах лексикографической оптимизации // Дискретный анализ и исследование операций. Серия 1. -1998. - Т. 5. - № 4. - С. 30-37.

38. Емеличев В.А., Янушкевич О.А. Условия Парето-оптимальности в дискретных векторных задачах оптимизации // Дискретная математика. — 1997. Т. 9. - № 3. - С. 153-160.

39. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. -М.: Знание, 1985.

40. Ермольев Ю.М., Ляшко ИИ, Михайлевич B.C., Тюптя В.И. Математические методы исследования операций. — Киев: Вища школа, 1979.

41. Жуковин В.Е. Многокритериальные модели принятия решений с неопределенностью. — Тбилиси: Мецниереба, 1983.

42. Занг В.-Б. Синергетическая экономика. Время и перемены в нелинейной экономической теории. М.: Мир, 1999.

43. Зинченко О.А. Исследование математических моделей и построение алгоритмов с оценками для векторных задач об остовных деревьях: Авто-реф. Дис. . канд. физ.-математ. наук. Черкесск: Кар.-Чер. Гос. Технолог. Ин., 2000.

44. Зыков А.А. Теория конечных графов. Том 1. Новосибирск: Наука, 1969.

45. КиниР.Л., РайфаХ. Принятие решений при многих критериях: предпочтения и замещения. — М.: Радио и связь, 1981.

46. Князева Е.Н., Курдюмов С.П. Основания синергетики. Синергетическое мировидение. М.: КомКнига, 2005.

47. Кононова Н.В., Каппушева Т.Д., Кочкаров Р.А. Плоскостная укладка и алгоритмы визуализации фрактальных графов//Известия ТРТУ. Тематический выпуск "Перспективные системы и задачи управления". Таганрог: ТРТУ, 2006. - 3.-С. 305-312.

48. Кононова Н.В., Кочкаров Р.А. Алгоритмические вопросы раскраски предфрактальных и фрактальных графов. Электронный журнал «Исследовано в России», 258, 2500, 2006

49. Кононова Н.В. Алгоритмы вершинной раскраски предфрактальных графов, порожденных с сохранением смежности старых ребер//Вестник Поморского университета. Серия «Естественные и точные науки». 2006.-№4.-С. 126-135

50. Кононова Н.В. Алгоритмы вершинной раскраски фрактальных и предфрактальных графов//Деп. ВИНИТИ. №1217-В2006. С. 2-39

51. КононоваН.В. ИКТ в системе высшего образования// Материалы IX региональной научно-технической конференции "Вузовская наука -Северо-Кавказскому региону". Том I. Ставрополь: СевКавГТУ, 2005. -С. 64-64.

52. Кононова Н.В. Моделирование фрактального роста структуры // Тезисы V Международной конференции «Математическое моделирование в образовании, науке и производстве». Тирасполь: Изд-во Приднестр. унта, 2007.-С. 45-46

53. Кононова Н.В. Особенности раскраски предфрактального графа//Деп. ВИНИТИ. №1218-В2006. С. 2-12

54. Кононова Н.В. Развитие фрактальных множеств/Юбозрение прикладной и промышленной математики. Том 14, вв. 3-4. Москва, 2007

55. Кононова Н.В. Синергетика и математическое моделирование// Сборник докладов Международной научной конференции «Системный анализ и прикладная синергетика». Пятигорск: ПГТУ, 2006.-С. 174-178

56. Кононова Н.В., Кочкаров A.M. Алгоритм раскраски предфрактального (п, Ь)-графа// Материалы VIII региональной научно-технической конференции "Вузовская наука Северо-Кавказскому региону". Том I. Ставрополь: СевКавГТУ, 2004. - С. 14-14.

57. Кононова Н.В., Кочкаров A.M. Алгоритм распознавания предфрактального дерева с затравкой 1-цепь // Материалы VIII региональной научно-технической конференции "Вузовская наука Северо-Кавказскому региону". Том I. Ставрополь: СевКавГТУ, 2004. - С. 15-15.

58. Кононова Н.В., Никищенко С.П., Черняев В.В. Свойства предфрактального графа, порожденного двудольной затравкой // Сб. научных трудов СевКавГТУ. Серия естественно-научная. 2005. С. 37-46.

59. Кононова Н.В., Черняев В.В. Свойства простейших предфрактальных деревьев // Материалы IX региональной научно-технической конференции "Вузовская наука — Северо-Кавказскому региону". Том !. Ставрополь: СевКавГТУ, 2005. С. 8-8.

60. Коркмазова З.О. Выделение максимальных эйлеровых подграфов на предфрактальном графе. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. Деп. в ВИНИТИ № 1731-В2004. С. 1-25.

61. Коркмазова 3.0. Многокритериальная задача разбиения на эйлеровые подграфы предфрактального графа. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. Деп. в ВИНИТИ № 1729-В2004. С. 1-25.

62. Коркмазова З.О. Параллельный алгоритм вычисления задачи Эйлера на предфрактальных графах. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. Деп. в ВИНИТИ № 1730-В2004. С. 1-20.

63. КоркмазоваЗ.О., КочкаровА.А. Максимальный Эйлеров подграф// Материалы XXXIV научно-технической конференции по результатам работы профессорско-преподавательского состава, аспирантов и студентов за 2004 год. Ставрополь: СевКавГТУ, 2005. С. 22.

64. Коркмазова З.О., Кочкаров А.А. Эйлеровы предфрактальные графы // Известия ТРТУ. Специальный выпуск. Таганрог, 2004. - № 8. -С. 304-305.

65. Коркмазова З.О., Кочкаров Р.А. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами: Препринт Спец. астрофиз. обсерватории РАН № 208. Нижний Архыз, 2005. 15 с.

66. Коркмазова З.О., Кочкаров Р.А. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами Препринт Спец. астрофиз. обсерватории РАН№ 209. Нижний Архыз, 2005. 27 с.

67. Косоруков О.А., Мигценко А.В. Исследование операций. — М.: Экзамен, 2003.

68. Кочкаров А А., Кочкаров Р. А. О планарности и других топологических свойствах фрактальных графов. Препринт. М.: ИПМ им. М.В. Келдыша РАН, №83, 2003.

69. Кочкаров А.А. Плоские и планарные предфрактальные графы. // V Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2002. - С. 35 - 35.

70. Кочкаров А.А. Число всевозможных предфрактальных графов. // IV Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл., том 2. Кисловодск: КИЭП, 2000. - С. 73 - 74.

71. Кочкаров А.А. Число точек сочленения предфрактального графа. // Вторая международная конференция "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики". Тез. докл. Нальчик: НИИ ПМА КБНЦ РАН, 2001.

72. Кочкаров А.А., Кочкаров Р.А. Исследование связности предфрактальных графов // IV Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл., том 2. Кисловодск: КИЭП, 2000. - С. 74 - 75.

73. Кочкаров А.А., Кочкаров Р.А. О критериях планарности фрактальных графов. // Труды XLVI научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Часть VII. М.: МФТИ, 2003. С. 186 - 186.

74. Кочкаров А.А., Кочкаров Р.А. Предфрактальные графы в проектировании и анализе сложных структур. Препринт. — М.: ИПМ им. М.В. Келдыша РАН, №10, 2003.

75. Кочкаров А.А., Малинецкий Г.Г. Обеспечение стойкости сложных систем. Структурные аспекты: . М.: ИПМ им. М.В. Келдыша РАН, № 53, 2003.

76. Кочкаров А.А., Малинецкий Г.Г. Стойкость, управление риском и обеспечение безопасности сложных технических систем // Проблемы безопасности и чрезвычайных ситуаций. -2005. № 4. - С. 12—25.

77. Кочкаров А.А., Салпагаров С.И. Число мостов предфрактального графа. // V Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2002. - С. 36-37.

78. Кочкаров A.M. Асимптотические точные алгоритмы решения многокритериальной задачи покрытия графа цепями // Известия АН БССР. -1985.-№4.-С. 39-43.

79. Кочкаров A.M. Асимптотический подход к многокритериальной задаче покрытия графа цепями //Доклады АН БССР. 1983. - Т. XXV. - № 10. -С. 911-913.

80. Кочкаров A.M. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998.

81. Кочкаров A.M. Топологические характеристики теоретико-графовой модели крупномасштабной кластеризации материи во Вселенной. Препринт. РАН САО. Нижний Архыз. 1998. С.1 - 6.

82. Кочкаров A.M. Хроматическое число и хроматический индекс фрактальных графов. // Республиканская конференция преподавателей и аспирантов КЧТИ. Тез. докл. Черкесск: КЧТИ, 1997. С.56 - 57.

83. Кочкаров A.M., Перепелица В.А. Многокритериальная задача покрытия графа цепями большой и малой длины // Известия АН БССР. 1985. -№5. - С. 39-44.

84. Кочкаров A.M., Перепелица В.А. О гамильтоновости фрактальных графов. //Международная конференция "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики". Тез. докл. Нальчик: НИИ ПМиА КБНЦ РАН, 1996. С.52-53.

85. Кочкаров A.M., Перепелица В.А. Число внутренней устойчивости предфрактального и фрактального графа. Сб. статей. РАН САО. 1999.

86. Кочкаров A.M., Перепелица В.А., Сергеева JI.H. Фрактальные графы и их размерность. Черкесск: КЧГТИ, 1996г. Деп. в ВИНИТИ, № 3284-В96, С. 1 -34.

87. Кочкаров Р.А., Кочкаров А.А. Формализация целевых программ // Модели экономических систем и информационные технологии: Сб. научных трудов / Под ред. О.В. Голосова. Вып. XII. М.: Финансовая академия, 2004.

88. Кочкаров РА., Салпагаров С.И. Полиномиальные быстрые алгоритмы нахождения остовного дерева минимального веса. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2002. Деп. в ВИНИТИ, №437-В2002. -С. 1-75.

89. Кравцов М.К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев // Дискретная математика. 1996. Т. 8, № 2. - С. 108-117.

90. Краснощеков П.С., Петров А.А. Принципы построения моделей. — М.: Издательство МГУ, 1983.

91. Краснощеков П.С., Петров А.А., Федоров В.В. Информатика и проектирование.-М.: Знание, 1986.

92. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

93. Ларичев О.И. Объективные модели и субъективные решения. — М.: Наука, 1987.

94. Ларичев О.И. Теория и методы принятия решений. М.: Логос, 2000.

95. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паро-сочетаний в математике, физике, химии. — М.: Мир, 1998.

96. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. — М.: Наука, 1990.

97. Лотов А.В. Введение в экономико-математическое моделирование. — М.: Наука, 1984.

98. Лотов А.В., Бушенков В.А., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса: Метод достижимых целей. — М.: Наука, 1997.

99. Майника Э. Алгоритмы оптимизации на графах и сетях. М.: Мир, 1981.

100. Малашенко Ю.Е., Новикова Н.М. Многокритериальный и максимин-ный анализ многопродуктовых сетей. М.: ВЦ АН СССР, 1988.

101. Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. — М.: Эдиториал УРСС, 1999.

102. Малашенко Ю.Е., Новикова Н.М. Суперконкурентное распределение потоков в многопродуктовых сетях// Дискретный анализ и исследование операций. Серия 2. - 1997. - Т. 4. - № 2. - С. 34-54.

103. Малинецкий Г.Г. Математические основы синергетики. Хаос, структуры, вычислительный эксперимент. М.: КомКнига, 2005.

104. Малинецкий Г.Г., Курдюмов С.П. Нелинейная динамика и проблемы прогноза // Вестник РАН. 2001. - т.71. - №3. - С. 210-224.

105. Мандельброт Б. Фрактальная геометрия природы. М.: ИКИ, 2002.

106. Меламед И.И., Сигал И.Х. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. — М;:.ВЦ РАН, 1996.

107. Мелихов А.И., Бернштейн JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974.

108. Мелроуз Дж. Иерархические фрактальные графы и блуждания на них // Фракталы в физике / Под ред. JL Пьетронеро, Э. Тозатти. М.: Мир, 1988.-С. 519-523.

109. Миркин Б.Г., Родин С.Н. Графы и гены. М.: Наука, 1977.

110. Многокритериальные задачи принятия решений. М.: Машиностроение, 1978.

111. Моисеев Н.Н. Алгоритм развития. — М.: Наука, 1987.

112. Моисеев Н.Н. Математика ставит эксперимент. М.: Наука, 1979.

113. Моисеев Н.Н. Математические задачи системного анализа. М.: Наука, 1981.

114. Новикова Н.М., Поспелова И.И. Многокритериальные задачи принятия решений в условиях неопределенности. М.: ВЦ РАН, 2000.

115. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. -М.: Физматлит, 2004.

116. Оре О. Теория графов. М.: Наука, 1968.

117. Павлов Д.А. Нахождение диаметральной простой цепи на фрактальном и предфрактальном графах// XVI Международная научная конференция "Математические методы в технике и технологиях — ММТТ-16". Сб. труд. С.-Пб.: СПбГТИ, 2004.

118. Павлов Д.А. Полиномиальный алгоритм нахождения максимального паросочетания на предфрактальных графах // XVII Международная научная конференция "Математические методы в технике и технологиях -ММТТ-17". Сб. труд. Кострома: КГТУ, 2004.

119. Перепелица В.А. Об одном классе многокритериальных задач на графах и гиперграфах // Кибернетика. — 1984.-№4. — С.62-67.

120. Перепелица В.А., МамедовА.А. Исследование сложности разрешимости векторных задач на графах. — Черкесск: КЧТИ, 1995.

121. Перепелица В.А., Сергиенко И.В. Исследование одного класса целочисленных многокритериальных задач. //Журн. выч. мат. и мат. физ. -1988. Т. 28, №3. С.400-419.

122. Перепелица В.А., Сергиенко И.В. Полиномиальные и NP-полные многокритериальные задачи перечисления альтернатив. В сб. Теор. и прогр. реализ. мет. дискр. оптимиз. Киев: ИК АН СССР, 1989. - С.58-69.

123. Петров А.А. Исследование операций и математическое моделирование// Материалы учредительной конференции Российского научного общества исследования операций. М.: ВЦ РАН, 1996

124. Петров А.А. Экономика. Модели. Вычислительный эксперимент. М.: Наука, 1996.

125. Подиновский В.В. Методы многокритериальной оптимизации / Математические методы в социальных науках. Вильнюс, 1972.

126. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. — М.: Наука, 1982.

127. Полищук Л.И. Анализ многокритериальных экономико-математических моделей. -М.: Наука, 1989.

128. Понтрягин JI.C., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1976.

129. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление.-М.: Сов. радио, 1976.

130. Применение теории графов в химии / Под ред. Зефирова Н.С., Кучано-ва С.И. — Новосибирск: Наука, 1988.

131. Применение теории графов связи в технике / Под ред. Кернопа Д., Ро-зенберга Р. -М.: Мир, 1974.

132. Райншке К. Модели надежности и чувствительности систем. М.: Мир, 1979.k

133. Райншке К., Ушаков И.А. Оценка1 надежности систем с использованием графов. — М.: Радио и связь, 1988.

134. Розенблит А.Б., Голендер А.Е. Логико-комбинаторные методы в конструировании лекарств. -Рига: Зинатне, 1983.

135. Рябинин И.А. Надежность и безопасность структурно-сложных систем.- СПб.: Политехника, 2000.

136. Салпагаров С.И. Задача о назначениях на фрактальных и предфрактальных графах. Многокритериальная постановка. Черкесск, КЧГТА, 2003, Деп. в ВИНИТИ, №2323-В2003. С.1-34.

137. Салпагаров С.И., Кочкаров A.M. Распознавание предфрактального графа с полной двудольной затравкой. Черкесск: КЧГТА, 2003. Деп. в ВИНИТИ, №2322-В2003. - С. 1-43.

138. Самарский А.А., Михайлов А.П. Математическое моделирование: идеи, методы, примеры. М.: Физматлит, 2001.

139. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

140. Сергиенко И.В., Перепелица В.А. К проблеме нахождения множеств альтернатив в дискретных многокритериальных задачах // Кибернетика.- 1987.-№5.-С. 85-93.

141. Сешу С., РидМ.Б. Линейные графы и электрические цели. М.: Высш. шк., 1971.

142. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. -М.: Наука, 1981.

143. СушковЮ.А. Графы зубчатых механизмов. Л.: Машиностроение, 1983.

144. Татт У. Теория графов. М.: Мир, 1988.н

145. Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. М.: Наука, 1984.

146. Турбин А.Ф., Працевитый Н.В. Фрактальные множества. Функции, распределения. Киев: Наукова думка, 1992.

147. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

148. Федер Е. Фракталы. М.: Мир, 1991.

149. Фляйншнер Г. Эйлеровы графы и смежные вопросы. М.: Мир, 2002.

150. Фракталы в физике / Под ред. JI. Пьетронеро, Э. Тозатти. М.: Мир, 1988.

151. Хакен Г. Информация и самоорганизация. М.: Мир, 1991.

152. Хакен Г. Синергетика. М.: Мир, 1980.

153. Хакен Г. Тайны природы. Синергетика: учение о взаимодействии. -Москва-Ижевск: Институт компьютерных исследований, 2003.

154. Харари Ф. Теория графов. М.: Мир, 1973.

155. Химические приложения топологии и теории графов. Под ред. Кинга Р. М.: Мир, 1987.

156. ХоменюкВ.В. Элементы теории многокритериальной оптимизации. -М.: Наука, 1983.

157. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. — Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.

158. Штойер Р. Многокритериальная оптимизация: теория, вычисления и приложения. М.: Радио и связь, 1992.