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

Павлов Дмитрий Алексеевич

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

05.13.17 - Теоретические основы информатики

Автореферат

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

Таганрог - 2004

ч

Работа выполнена в Карачаево-Черкесской государственной технологической академии на кафедре Математики.

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

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

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

профессор Боташев Хасан Ибрагимович

кандидат физико-математических наук,

доцент Шунгаров Хамид Джашауович

Ведущая организация: Северо-Кавказский государственный технический университет

Защита состоится «11» ноября 2004 г в 14-20 часов на заседании диссертационного совета ДР 212.259.09 при Таганрогском государственном радиотехническом университете по адресу: 347928 г.Таганрог, пер.Некрасовский, 44, ауд. Д-406.

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

Автореферат разослан «_£_» октября 2004 г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Л.К. Бабенко

2005-4

3

/ е.50&в

12600

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

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

В качестве средства моделирования динамического хаоса в диссертации предлагается использовать фрактальный граф и предфрактальный граф в том определении, которое впервые было предложено В.А. Перепелицей и A.M. Кочкаровым.

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

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

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

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

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

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

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

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

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

вании;

графов;

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

Работа выполнена в соответствии с пунктами 2.2 - «Разработка и анализ моделей информационных процессов и структур», 3.3 - «Разработка и исследование моделей данных и новых принципов их проектирования», 7.1 -«Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил», 10.3 - «Разработка основ ... теории графов», 14 - «Разработка теоретических основ создания программных систем для новых информационных технологий» паспорта специальности 05.13.17 - «Теоретические основы информатики».

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

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

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

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

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

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

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

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

Апробация работы. Научные и практические результаты, полученные в диссертации, опубликованы в 12 печатных работах и докладывались на: IV Научно-практической конференции «Решение научно-технических и соци-

ально-экономических проблем современности» (г.Черкесск, 2002); XVI Международной научной конференции «Математические методы в технике и технологиях» (г.Санкт-Петербург, 2003); XVII Международной научной конференции «Математические методы в технике и технологиях» (г.Кострома, 2004); VI Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (г.Кисловодск, 2004); Научных семинарах профессорско-преподавательского состава КЧГТА (г.Черкесск, 2001-2004).

Структура диссертации. Диссертация состоит из введения, трех тематических глав, заключения, приложения и списка использованных источников. Работа изложена на 112 страницах, из них 2 страницы рисунков, 1 страница приложения, 11 страниц списка использованных источников, содержащего 104 наименований.

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

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

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

Введем понятие предфрактального графа. Пусть Н = 0 - п-вершинный связный граф с множеством вершин IV, = п и множеством ребер |<2| = <7- Условимся называть его «затравкой». В качестве обобщения известной операции «расщепления вершины графа», определим операцию «замещения вершины затравкой» (ЗВЗ). Для произвольного графа б = (У,Е) ее суть состоит в замещении вершины уе V графа п -вершинной затравкой Н = (Ж, О). При этом каждое ребро (у, у') е Е, у' е V, инцидентное вершине у, удаляется и заменяется на (и,у') € Е, где и е IV- вершина затравки, выбираемая либо произвольно, либо по определенному закону. Определим по-I этапный процесс выполнения операции ЗВЗ. На этапе / = 1 в данной затравке

Н = (№,£)) нумеруем вершины и ребра - получаем граф, обозначаемый через С, = (И,,£,), т.е. С, =(У,,Е,) = Н = (№,(?). Пусть выполнены этапы / = 1,2,...,I и по завершении этапа £ получен граф (?£=(*£,2^) из =(*£_!,£¿-1) заменой каждой его вершины затравкой Н-(IV,0. Полученный граф будем называть предфрактальным (и, Ь) -графом, где \Щ = п. Процесс порождения предфрактального графа Сь, по существу, есть процесс построения последовательности предфрактальных графов называемой траекторией.

Для предфрактального графа ребра, появившиеся на /-ом,

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

Если из предфрактального графа с1, порожденного и-вершинной затравкой Н, последовательно удалить все старые ребра (ребра ранга I, I =1,2, , Л -1), то исходный граф распадется на множество связных компонент Я)1', 5 = 1,я'-1 , изоморфных затравке Н и которые назовем термином

подграф-затравка г'^. Последовательное выделение подграф-затравок г^ на графах (7,, 02 из траектории предфрактального графа Оь разбивает

множество ребер Е1 на непересекающиеся подмножества подграф-затравок

2(Сс) = *}, где / = 1,1, - ранг подграф-затравки, а у = 1, п'~х - ее порядковый номер.

Будем говорить, что предфрактальный граф = , Е1_) - взвешен, если каждому его ребру е</) е Еь приписано действительное число

и<е(") е [в'-'а-^'-'Ь], где / = Ц. - ранг ребра, а > 0, и в < -.

Ь

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

Рассмотрим взвешенный предфрактальный граф С1 = (Ус, Е,) порожденный затравкой Я = ((V, 0, у которой = п, |б| = ц.

Под цепью предфрактального графа б^ понимаем простую цепь С, а количество вершин в ней называем длиной цепи и обозначаем 1еп{С). Простую цепь, ребра которой имеют одинаковый ранг /, будем называть /ранговой цепью и обозначать С(,).

Покрытием вида К, графа С^ будем называть подграф у = (Уь,Еу),

Еу с Е1, состоящий из множества простых цепей, где каждая вершина инцидентна ребрам только одной цепи из у. Всевозможные покрытия {у} предфрактального графа С£ образуют множество допустимых решений У = У(С1) = ^}(МДР).

Качество покрытия у на графе GL определяется векторно-целевой функцией (ВЦФ):

Hy) = (Fl(y),F2(y),Fi{y)) (1)

min, (2)

Сеу ееС

£ Л М6) - вес покрытия у;

СеуееС

F2(y) = \y\^mm, (3)

где |_у| - мощность покрытия или количество цепей покрытия у;

^00 = Л-»min, (4)

где - г| количество типов цепей, составляющих покрытие у.

Покрытием вида К2 графа GL будем называть подграф х = {VL ,ЕХ), ExciEl, состоящий из множества таких простых цепей {CuC2>...,Ck,...,CK}, что между двумя произвольными вершинами из покрытия также существует простая цепь. Множество всех покрытий х обозначим через X. Очевидно, что покрытие x = (VL,Ex) является связным подграфом графа Gl и образуется простыми цепями пересекающимися либо по вершинам либо по ребрам. Поэтому кратчайшую цепь, имея ввиду цепь с наименьшим суммарным весом ее ребер, из графа будем называть максимальной (максимальной по включению), если она не является собственной подцепью какой-либо другой кратчайшей цепи. Вообще говоря, наличие в покрытии К2 немаксимальных цепей не противоречит определению покрытия.

Простую цепь предфрактального графа GL будем называть /'смешанной цепью и обозначим через С', если она состоит из ребер i различных рангов.

На множестве покрытий хе X графа GL = (VL,EL) определена век-торно-целевая функция (ВЦФ):

F(x) = (F, (х), F2 (х), F3 (Х), F4 (Х), Fs (Х)) (5)

min, (6)

ееЕх

где - общий (суммарный) вес покрытия х;

ееЕх

F2 (дг) = mia »4Q) -» т3* > (7)

км, К

где Ск - максимальна цепь, к = 1,К, из покрытия хе {Cl,C2,...,Ck,...,CK}, a w(Ck) - ее длина (суммарный вес ребер цепи).

F3(jt) = N(x) -> min, (8)

где N(x) - число всех максимальных цепей в покрытии х;

F4 (х) = I —> min, (9)

для всякой смешенной цепи С' из покрытия х.

Fs (*) = | Р.х (". v) - PcL (и. v)| -> min, (10)

где для любых вершин u,veVL графа pt(u,v) - расстояние в покрытии х, а Pql (u,v) - расстояние на графе GL;

Напомним, что pClL(u,v) - длина кратчайшей цепи {m,v}, а потому Рс (и, v) - минимальна по сравнению с длинами цепей соединяющих вершины w,v е VL фафа Gl на {х}.

Всевозможные покрытия {*} предфрактального графа GL образуют множество допустимых решений X = X(GL) = {х} (МДР) для ВЦФ (5) - (10)

Решением многокритериальных задач с ВЦФ ((1)-(4)) и ((5)-(10)) является паретовске множество.

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

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

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

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

Все критерии (2)-(4) ВЦФ ((1)-(4)) имеют конкретную содержательную интерпретацию. Критерий (2) характеризует надежность связи сети. Критерий (3) направлен на сокращение времени обработки информации в корпора-

тивной сети с распределенной вычислительной системой. При равномерном распределении задачи между элементами сети, все будут задействованы в решении задачи одинаково, что позволит не перегружать отдельные ЭВМ, именно на это направлен критерий (4).

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

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

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

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

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

На практике очень важно, чтобы длина маршрутов движения пассажирского транспорта между ее конечными остановками была наименьшей. Для достижения этого при проектировании пассажирской транспортной системы привлечен критерий (7). К тому же, важно что бы каждый маршрут обхватывал как можно больше вершин на своем пути. Оптимальным для целевой функции /^(х) является такое покрытие хе{Сх,С2.....Ск,...,Ск), все

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

Чем меньше маршрутов движения транспорта в пассажирской транспортной системе, тем меньше потребуется сделать пересадок, чтобы добраться до необходимого узла системы и тем меньше потребуется единиц транспорта для самой системы. Критерий (8), ввиду того, что всем различным цепям покрытия х = (У1,Ех) соответствуют маршруты движения пассажирского транспорта, стремиться уменьшит общее число всевозможных маршрутов движения транспорта.

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

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

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

Для многокритериальной задачи покрытия предфрактального графа простыми непересекающимися цепями вида К,, с ВЦФ ((1)-(4)), построены полиномиальные алгоритмы с оценками.

Алгоритм ах строит покрытия I -ранговыми цепями длины один. Основная идея алгоритма заключается в том, что каждая подграф-затравка г^,

£ = I,«1"1 рассматривается как отдельно взятый граф. Последовательно на каждой из и1'1 подграф-затравке находятся ее совершенные паросочетания М3. Поиск совершенного паросочетания на отдельно взятой подграф-затравке осуществляется с помощью алгоритма Эдмондса.

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

достаточно существование совершенного паросочетания Нм = ) на самой затравке Н = (№,()).

Теорема 1 гласит о том, что если удастся найти совершенное паросоче-тание на порождающей затравке Н - (^,0), тогда обязательно найдется совершенное паросочетание М = {V ,ЕМ) и на самом предфракталыюм фафе С = (V, Е). Таким образом, предположим, что выполняется условие теоремы 1, и алгоритм а, заведомо выделит совершенное паросочетание минимального веса.

теорема 2. Вычислительная сложность алгоритма ах, покрытия цепями длины один (ребро) минимального веса на предфрактальном (п,Ь)-графе С1 = (У1,Е1), порожденного затравкой Н = где ¡И7] = и,

= N ^ п1, равна 0(Ы п2).

Теорема3. Алгоритм ах выделяет покрытие у1=(У,Еу) на предфрактальном (п, ¿) -графе = (У1, Е1), порожденном п -вершинной затравкой Н = (№,()), оптимальное по первому /*) (_у,) и третьему (у,)

п1

. критерию, и оцениваемое по второму, (у,) < —.

Алгоритм аг выделяет покрытие цепями длины два (два ребра) на взвешенном предфрактальном (и, I)-графе С1=(У1,Е1) порожденном затравкой Н = (IV, у которой = п, |0[ = ^, где п кратно трем.

Основная идея алгоритма заключается в том, что каждая подграф-затравка г^, 5 = 1 ,п1~{ рассматривается как отдельно взятый граф. Последовательно на каждой из п1~1 подграф-затравке производится поиск покрытий простыми цепями длины два М5. Поиск покрытия на отдельно взятой подграф-затравке осуществляется с помощью процедуры Выделения покрытия цепями длины два, в основе которой лежит алгоритм Эдмондса. Осуществив поиск покрытий простыми цепями длины два на подграф-затравках, мы получим покрытие у2=(У,Еуг) простыми цепями длины два ребра

предфрактального графа С1, после чего алгоритм а2 заканчивает свою работу.

Опишем кратко процедуру Выделения покрытия цепями длины два для целостного понимания алгоритма а2 ■ На взвешенном графе С = (У, Е) производится поиск совершенного паросочетания минимального веса А/, используя алгоритм Эдмондса. Далее среди элементов совершенного паросочетания минимального веса Мх, выделяется элемент т; еМ{, у'еУ с максимальным весом. Далее, рассматривая у концевых вершин выбранного элемента т] инцидентные ребра графа б, выбираем и выделяем те из них, ко-

торые имеют минимальный вес. Выделенные ребра уже соединяют два элемента покрытия m¡,mJeMl,ieI и образует в отдельности друг от друга

цепи с3. Далее, рассматриваем в отдельности каждую из этих цепей и выбираем среди них ту, которая имеет минимальный вес. У выбранной минимальной цепи с" сравниваем и выбираем из двух ребер принадлежащих покрытию Мх то, которое имеет минимальный вес, а ребро покрытия M¡ с максимальным весом исключаем из цепи Cj, запоминая и окрашивая конечную вершину исключенного ребра, принадлежащего Mi. В результате этой операции мы выделили цепь длины два. Далее описанная операция применяется многократно, пока не будет покрыт весь граф G цепями длины два.

Теорема 4. Если существует покрытие, то алгоритм а2 выделяет покрытие у2 = (V, £) цепями длины два (два ребра) на предфрактальном (n,L)-графе GL=(VL,EL), порожденного п-вершинной затравкой Н = (W,Q), где п кратно трем.

ТЕОРЕМА 5. Вычислительная сложность алгоритма а2 покрытия цепями длины два (дваребра) на предфрактальном (n,L)-графе GL = (yi,EL), порожденного затравкой Н = (fV,Q), где = и, |F¿¡ = N = nL, равна 0{N-2n2).

Теорема 6. Алгоритм а2 выделяет покрытие уг - (У,Еу2) на предфрактальном (n,L)-графе GL=(VL,EL), порожденном п-вершинной затравкой Н = (W,Q), оптимальное по третьему Fi (у2) критерию, и оцени-

2nL _ nL

всюмое по первому критерию, F¡ (у2) < ——6L xb и по второму, F2 (у2) < —,

если в<

Ъ

Алгоритм аъ строит покрытие уъ = (V ,Еу^) простыми цепями длины

три (три ребра). Как и для алгоритма а2, каждую подграф-затравку z(sL\

s = 1 ,nL~x будем рассматривать как отдельно взятый фаф. Последовательно на каждой из п1~] подграф-затравок производится поиск покрытий простыми цепями длины три ребра. Поиск покрытия на отдельно взятой подграф-затравке осуществляется с помощью процедуры Выделения покрытия цепями длины три в, основе которой лежит алгоритм Эдмондса.

Предложим краткое описание процедуры Выделения покрытия цепями длины три для целостного понимания алгоритма. На взвешенном графе G = (V,E) производится поиск совершенного паросочетания минимального веса М,. Запоминаем далее первоначальную структуру графа. Затем каждый

элемент покрытия mJ е А/, стягиваем в вершину. К полученному в результате операции стягивания покрытых ребер новом графе применяется снова алгоритм ах покрытия предфрактального графа цепями длины один. В результате чего имеем покрытие М2, которое также выделяем. Далее, восстанавливается первоначальная структура графа G = (V, Е), на котором уже будут выделены покрытия М1 и М2 Объединение множеств ребер входящих в Мх и М2 (Mt <оМ2), будут образовывать цепь длины три.

Теорема 7. Вычислительная сложность алгоритма а3, выделения покрытия цепями длины три (три ребра) на предфрактальном {п, L) -графе Gl=(Vl,El), порожденного затравкой H = (W,Q), где \1У\ = п, \VL\ = N = nL, равна 0(N-2n2).

Теорема 8. Алгоритм а} выделяет покрытие у3 = (V ,Еу}) цепями длины три (триребра) на предфрактальном (n,L)-графе GL = (VLyEL), порожденном п -вершинной затравкой Н = (fV,Q), оптимальное по третьему

3 п1

Рз(Уз) критерию, и оцениваемое по первому критерию, Ft(у,) <—-в1~уЬ и

4

по второму, F2 (у3 ) = —, если в < —.

4 Ь

Для многокритериальной задачи покрытия (вида К2) предфракгальных графов простыми пересекающимися цепями с ВЦФ ((5)-(10)) разработаны и обоснованы два полиномиальных алгоритма Д и /?2 •

Алгоритм рх строит на графе GL остовное дерево Т = (VL,ET) минимального веса (ОДМВ). Суть работы алгоритма заключается в следующем. Каждая подграф-затравка = 5 = 1 ,им, из множества Z(GL) рассматривается как отдельно взятый граф. Последовательно на каждый из п1 -1

- подграф-затравках независимо друг от друга находится ее ОДМВ

п -1

(0). Поиск ОДМВ отдельно взятой подграф-затравки осущест-1

вляется алгоритмом Прима.

Теорема 9. Вычислительная сложность алгоритма Д, выделяющего ОДМВ Т = (VL,ET) на предфрактальном (и,L)-графе GL = (VL,EL), порожденного затравкой Н = (IV,Q), где \W\ = и, \VL\ - N - nL, равна 0(Nn2).

Теорема 10. Алгоритм Д выделяет ОДМВ Т = (VL, Ет) на предфрактальном (n,L) -графе GL=(VL,EL), порожденном затравкой H=(W,Q),ede \W\ = n, \VL\ = N = nL.

Теорема И. Алгоритм выделяет покрытие хх=Т = (У/ ,ЕТ) на предфрактальном (п,Ц) -графе (7/ = {У1,Е1), порожденном п -вершинной затравкой Н = (№,()), оптимальное по первому критерию /^(х,) = щщ Е,(х), и оцениваемое по двум следующим, е[1;и''_1(и -1)],

хеХ

и -2].

В завершении главы 2 предложен алгоритм /?2, выделяющий на предфрактальном графе покрытие х2=.! -(УL,EJ) = {CuC2,...,Ck,...,Cк}e X, у которого все цепи Ск ={ук,ик} - простые, к-\,К.

В основе алгоритма р2 лежит алгоритм выделения наибольших максимальных цепей (алгоритм ВНМЦ) на произвольном графе. Алгоритм р2, используя алгоритм ВНМЦ в качестве процедуры, на каждой подграф-затравке множества 2(С£)ег^,/ = 1,£, $ = предфрактального графа выделяет подграф ^ - (У<'\Е ,п) = {С„С2,...,Ск.....СК } такой все

цепи Ск = {«, у} являются максимальными, среди всех цепей между вершинами и, у е К/" подграф-затравки г^ и наибольшими. Множество покрытий

= 1,1, ^ = 1,ям , выделенное на подграф-затравках предфрактального графа С,, образует покрытие хг = 7 = (У1, £у).

Теорема 12. Вычислительная сложность алгоритма ¡32, выделяющего покрытие J = {УЬ,ЕЦ) па предфрактальном (п,Ь)-графе й/ -порожденном затравкой # = (й^,0, где\Щ = п, \У/_\= N = п1 равна 0(Ш4).

Теорема 13. Алгоритм /?2 выделяет покрытие х2 = J = (УL,EJ) = {Сг,С2.....Ск,...,Ск) е X, где Ск - кратчайшие цепи одного ранга, на предфрактальном {п,Ь)-графе = (У1,Е!у), порожденном затравкой Н = 0, = и, = 9, оцениваемое по первому критерию:

па/Ь-1 па/Ь-1

ТЕОРЕМА 14. Алгоритм р2 выделяет связный остовный подграф 3 = {У1,Е^ = {С1,С2,..,,Ск,...,Ск), где Ск - кратчайшие цепи, на предфрактальном (п,Е)-графе б, = (У1,Е1), с затравкой # = (Ж,0, \lV\-n, |б|= Я • смежность старых ребер которого не нарушается.

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

Обоснованием алгоритмов служит теорема

Теорема 15. Всякое фрактальное +1, I) -дерево 0=(У,Е') ранга £ > 2 обладает следующими свойствами:

а) никакая новая затравка не пересекается;

б) всякое висячее ребро является новым;

в) степень и диаметр имеют соответственно верхние и нижние оценки

которые являются достижимыми.

Если рассмотрим вопрос о вычислительной сложности алгоритма уг, то видно, что данное предфрактальное дерево сводится к построению последовательности 0,,£>2,...,£)л . Очевидно, что для вычислительной сложности справедлива следующая верхняя оценка: т(у2) ^ 0(1 УIL) = 0(| V \ log | V |). Основные результаты работы заключаются в следующем, впервые поставлена и исследована многокритериальная задача покрытия предфрактального графа простыми непересекающимися цепями; впервые поставлена и исследована многокритериальная задача покрытия предфрактального графа простыми пересекающимися цепями; - построены и исследованы модели корпоративной сети с распределенной вычислительной системой и крупномасштабной транспортной системы, сводимых к многокритериальной задачи покрытия предфрактальных графов соответственно непересекающимися и пересекающимися простыми

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

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

1. Павлов Д А. Двухкритериальная задача покрытия предфрактального графа цепями длины г (т = 1,2,3)// Сб. трудов IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности». Черкесск, 2002. -С.31-33.

2. Павлов Д.А. Полиномиальный алгоритм покрытия предфрактального графа простыми цепями// Сб. трудов IV научно-практической конференции «Решение научно-технических и социально-экономических проблем современности». Черкесск, 2002. -С.33-35.

3. Павлов Д А. Нахождение диаметральной простой цепи на фрактальном и предфрактапьном графах// Сб. трудов XVI Международ, науч. конф. «Математические методы в технике и технологиях». Санкт-Петербург: СПГТИ, 2003. -С. 186-187.

цепями;

16

»19 4 38

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

5. Павлов ДА. Оценка покрытия предфрактального графа кратчайшими простыми цепями// VI Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭП, 2004.-С. 15-17.

6. Павлов ДА Многокритериальная задача покрытия предфрактального графа цепями типа г (г = 1,2,3). Черкесск, КЧГТИ, 2003, Деп. в ВИНИТИ, №670-В2003. - С. 1 -17.

7. Павлов ДА Многокритериальная задача покрытия фрактальных и предфрактальных графов простыми цепями. Черкесск, КЧГТА, 2004, Деп. в ВИНИТИ, №1248-В2004. - С. 1-12.

8. Павлов Д.А., Узденов A.A. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой полный л-вершинный граф. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-9.

9. Павлов Д.А., Кочкаров A.A. Алгоритмы решения многокритериальной задачи покрытия предфрактальных графов пересекающимися простыми цепями. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-27.

10.Павлов ДА., Саппагаров С.И. Многокритериальная задача выделения маршрутов на предфракгальном графе// Известия ТРТУ. - Таганрог: ТРТУ, 2004.

11.Павлов ДА., Кочкаров A.A. Об одной многокритериальной задачи покрытия минимального веса предфрактального графа простыми пересекающимися цепями. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-13.

12.Павлов ДА., Кочкаров P.A., Узденов A.A. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах. Препринт. РАН CAO. Нижний Архыз. 2004.-C.I-16.

В работах, опубликованных в соавторстве, лично Павлову Д.А. принадлежат следующие результаты: в [8] предложены алгоритмы определения абсолютных р-центров; в [9] построена математическая модель транспортной системы в больших масштабах; в [10] разработаны и описаны алгоритмы построения покрытий и вычислены оценки их трудоемкости; в [11] разработана и описана процедура выделения наибольших максимальных цепей на предфрактальных графах; в [12] сформулирована многокритериальная постановка задачи выделения маршрутов на предфракгальном rnarhe и пячпяЯлтаня пК. щая идея методов ее решения.

Типография ТРТУ, ГСП 17А, Таганрог, ул. Энгел РНБ РуССКИЙ ф0НД

2005-4

12600

ВВЕДЕНИЕ.

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

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

1.2. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К^.

1.3. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями (покрытие вида К2).

Выводы.

ГЛАВА 2. АЛГОРИТМЫ С ОЦЕНКАМИ ПОСТРОЕНИЯ ПОКРЫТИЙ ПРОСТЫМИ ЦЕПЯМИ НА ПРЕДФРАКТАЛЬНОМ ГРАФЕ.

2.1. Разработка и исследование полиномиальных алгоритмов построения покрытия К,.

2.1.1. Алгоритмы а} построения покрытия ¿-ранговыми цепями длины один.

2.1.2. Алгоритмы а2 построения покрытия ¿-ранговыми цепями длины два.

2.1.3. Алгоритмы а3 построения покрытия ¿-ранговыми цепями длины три.

2.2. Разработка и исследование полиномиальных алгоритмов построения покрытия К2.

2.2.1. Алгоритм /?! построения остовного дерева минимального веса.

2.2.2. Алгоритм /?2 выделения наибольших максимальных цепей.

Выводы.

ГЛАВА 3. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ДЕРЕВА С ЗАТРАВКОЙ ПРОСТАЯ ЦЕПЬ.

3.1. Алгоритм распознавания предфрактального графа с затравкой цепь длины один (ребро).

3.2. Алгоритм распознавания предфрактального графа с затравкой простая цепь длины g (g ребер).

Выводы.

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

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

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

Задача покрытия п -вершинного графа / -вершинными цепями в одно-критериальной постановке решена в [2] для частного случая, когда граф покрывается двухвершинными цепями. К настоящему времени для построения такого покрытия известен алгоритм с трудоемкостью порядка пъ элементарных операций [3]. В работе [4] предложены эвристические алгоритмы решения однокритериальных задач покрытия графов, в случае, когда на длины цепей наложены ограничения сверху. Предлагаемый в работе [5] алгоритм трудоемкости 0(п~) решает частный случай с гарантированным относительным уклонением, не превосходящем —. Что касается эффективно разрешимых классов задач покрытия графов гамильтоновыми цепями, то наиболее полно эти результаты представлены в [6]. Задача покрытия кратчайшими пересекающимися цепями достаточно подробно исследована в [7], где рассматривается оценка числа цепей в зависимости от типов графов. Но эта задача не исследовалась в оптимизационной постановке, и не имеет конкретного алгоритма построения покрытия для любого графа. В общем случае однокрите-риальная постановка задачи покрытия графа цепями содержит, как частные случаи, NP-трудные задачи [8]: покрытие графа А:-вершинными цепями, в частности, задача нахождения на графе гамильтоновой цепи минимального веса [8]. К последней задаче примыкает задача о гамильтоновых циклах и тесно связанная с ней задача коммивояжера [9-16].

Причем в целом, исследования по задачам покрытия графа носят фрагментарный характер и касаются в основном случая однокритериальных постановок. Покрытие графов цепями в многокритериальной постановке достаточно глубоко исследовались Кочкаровым A.M., Перепелиной В.А. и др. в работах [17-29]. В этих работах рассматривается проблема многокритериальное™ и предлагается вероятностный анализ алгоритмов [30,31], позволяющих доказывать теоремы о поведении алгоритмов в среднем и асимптотическом поведении.

Однако многие из этих задач моделируемых на графах, состоят из большого числа элементов, причем им присущи свойства фракталов: самоподобие, дробная фрактальная размерность, масштабная инвариантность, а также признаки динамического хаоса в траекториях моделируемого процесса [32-35]. Как только задачи становятся большой размерности, они становятся трудно решаемыми в смысле вычислений, поэтому для моделирования таких задач классические методы теории графов оказываются неэффективными.

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

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

Также заметим, что весьма многочисленный список экстремальных задач [36-40] на графах представляет собой класс /^/"-трудных задач с точки зрения дискретной оптимизации. Здесь уместно отметить, что, например, известная задача нахождения (распознавания) гамильтонова цикла становится полиномиально разрешимой на канонических предфрактальных графах с полной затравкой Я = (Ж,0 в случае, когда старые ребра не пересекаются. Аналогичные утверждения справедливы и для других задач из этого списка. Снижение трудоемкости экстремальных задач на предфрактальных графах обусловлено тем, что на этих графах для некоторых задач, наряду со свойством самоподобия, появляется свойство наследственности.

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

Предпосылкой возникновения фрактальных и предфрактальных графов, явилось понятие «фрактала». Оно было введено в обращение французским математиком Бенуа Мандельбротом в 1975 году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, в физике ценность подобных идей была осознана лишь в 70-е годы нашего столетия. Важную роль в широком распространении идей фрактальной геометрии сыграла замечательная книга Б.Мандельброта «Фрактальная геометрия природы» [41]. Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной (под размерностью понимается размерность Хаус-дорфа - Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая впоследствии A.C. Безиковичем) [32,42-44]. Основой новой геометрии является идея самоподобия [33,41,42]. Она выражает тот факт, что иерархический принцип организации фрактальных структур не претерпевает значительных изменений при рассмотрении их с различным увеличением. В результате эти структуры на малых масштабах выглядят в среднем так же, как и на больших. Здесь следует провести разницу между геометрией Евклида, имеющей дело исключительно с гладкими кривыми, и бесконечно изрезанными самоподобными фрактальными кривыми. Элементы кривых у Евклида всегда са-моподобны, но тривиальным образом: все кривые являются локально прямыми, а прямая всегда самоподобна. Фрактальная же кривая, в идеале, на любых, даже самых маленьких масштабах не сводится к прямой и является в общем случае геометрически нерегулярной, хаотичной [45-47].

Дальнейшее изучение фракталов осуществлялось в рамках нового междисциплинарного подхода - синергетики [45,48-50], где одной из центральных задач являлось моделирование объектов и явлений, которым присущ хаос, т.е. непредсказуемость протекающих в них процессов, отсутствие пространственной регулярности, случайность, рассогласованность поведения составляющих элементов и т.п. С развитием этого направления удалось выявить регулярные законы и закономерности возникновения, казалось бы, на первый взгляд, хаотичных систем, условие протекания непредсказуемых (или, по крайней мере, очень сложных) процессов и явлений, показать фрактальные структуры, лежащие в их основе. Более того, при дальнейшем изучении оказалось, что моделирование многих фрактальных объектов физики, химии, биологии и других дисциплин сводится к составлению автономных систем обыкновенных дифференциальных уравнений, зависящих от параметров [47].

При исследовании дискретных объектов [17-31,36-40,51-54], в основе которых лежит пространственно-временной хаос, аппарат дифференциально-интегрального исчисления не подходит [45-47]. Подобные объекты моделируются средствами теории графов [10-16,55-60]. При этом, получаемые модели обладают всеми свойствами фракталов: дробной размерностью, самоподобием, масштабной инвариантностью, что создало предпосылки возникновения фрактальных графов.

Впервые понятие «фрактальный граф» было введено в работе [33] Мелроузом. Однако используемый Мелроузом и другими авторами иерархический фрактальный граф обладает тем недостатком, что введен с узкой целью, а именно для отражения иерархии связи с учетом варьируемой разветв-ленности [61]. Дальнейшее развитие теория предфрактальных и фрактальных графов получила в работах Кочкарова A.M. и Перепелицы В.А. [43,44,62-72]. В [62,66,67-71] приведены некоторые результаты исследования свойств фрактальных графов. Некоторые модели на предфрактальных графах построены в [44,64,67,72]. Построению остовных деревьев на фрактальных графах посвящена работа [63]. Результаты исследований задачи о кликах фрактального графа предложены в [65].

Появление фрактальных (предфрактальных) графов является логически закономерным следствием стремления возможно более адекватно моделировать реальные технические, экономические, социальные явления и объекты с помощью математического аппарата теории графов. При этом получение бесконечного фрактального графа из конечного предфрактального графа означает (в терминологии [34,35]) превращение феноменологической модели в асимптотическую. В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, фрактальный граф [44,62-72] - это в конечном счете один из способов выявления некоторых качеств моделируемой системы. Поэтому для решения конкретных задач математики, физики, экономики, биологии, строительства, планирования и т.д. используются предфрактальные графы, ранг которых может выступать характеристикой степени приближения строящихся моделей к реальным объектам исследования. При этом, чем выше ранг графа, тем более точные результаты получаются при решении задач. Учитывая, что решение многих задач экономики, техники, строительства, планирования и т.п. тесно связано с необходимостью моделирования очень сложных и изменчивых во времени структур, состоящих из большого числа элементов, применение классических методов теории графов не всегда представляется возможным в силу своей неэффективности. Применение же теории предфрактальных и фрактальных графов помогает решать задачи, там, где бессильны традиционные подходы.

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

В настоящее время исследования фрактальных и предфрактальных графов ведется в 3-х направлениях:

1. распознавание фрактальных графов;

2. вычисление размерности фрактальных графов;

3. оптимизационные задачи на фрактальных графах.

В направлении 1 исследования получили свою разработку в работах Кочкарова A.M. Представленными в [44] результатами осуществлено выделение и конструктивное обоснование полиномиально разрешимого [8] класса задач распознавания свойства предфрактальности графов, полученных в процессе моделирования специфических объектов дискретной природы.

В работах [43,44] вычислены размерности Хаусдорфа- Безиковича для некоторых типов фрактальных графов.

В направлении 3 исследования проводятся Кочкаровым A.M. и его учениками.

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

В диссертации задача покрытия предфрактальных графов простыми цепями рассматривается в многокритериальной постановке [38-40,73-77]. Что позволяет оценить покрытие не одним, а несколькими критериями, которые в силу своей разнородности невозможно адекватно представить в виде одной интегральной целевой функции.

При формулировке многокритериальной задачи оптимизации, как и в классических постановках однокритериальной оптимизации, с помощью системы ограничений или другим способом задается множество X = {jc} допустимых решений (альтернатив, вариантов, планов и т.п.), на котором определены целевые функции Fk (х), к = \,т .

При решении многокритериальной задачи требуется по возможности отыскать такое iel, на котором некоторая часть целевых функций достигала бы минимума, а оставшаяся часть - максимума. Так как критерий Fk (х) —» max всегда можно заменить на - Fk(x) —» min , то в дальнейшем условимся считать, что в многокритериальной задачи оптимизации все целевые функции минимизируются:

Fj(x) -» min , F2(x) min , ., Fm(x) —» min ,{m> 2). Многокритериальная задача оказывается разрешимой в вышеуказант ном смысле, если будет не пустым пересечение [>\Хк , где Xк - множество к= 1 всех решений х е X, на каждом из которых значение функции Fk(x) достигает минимума.

Проблема многокритериальной оптимизации возникает тогда, когда т

Хк - 0. В этом случае, какое бы фиксированное х() е X мы ни взяли в ка

А-1 честве искомого решения задачи, найдется другое решение х, е X, на котором значение хотя бы одной целевой функции Fk(xx) меньше, чем Fk{x()). Таким образом, предложить универсальное правило (алгоритм) выбора одного «наилучшего» решения не представляется возможны. Поэтому вопрос определения так называемого векторного оптимума относится к компетенции лица, принимающего решения (ЛПР).

В этих условиях решить многокритериальную задачу - значит найти не одно решение, а множество так называемых Парето-оптимальных решений. Элемент х0 е X называется Парето-оптимальным решением (по критериям

Fl(x), ., Р]п(х)), если он удовлетворяет следующему условию: не существует такого элемента у е X, чтобы среди неравенств

Ь\{у)<Рк{х),к = \^п было хотя бы одно строгое.

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

У(Х()) = Г(Х),гд.е

Ь\Х) = №(х),Р2(х),.,Рт(х)) \ х е X} будем называть полным решением.

В отечественной и зарубежной литературе [38-40,76,77] можно найти описание различных подходов к решению многокритериальной задачи оптимизации. Зачастую в этих публикациях рассматриваются одновременно две проблемы, которые мы разделяем: нахождение Парето-оптимальных решений и выбор из них наиболее целесообразного решения, называемого векторным оптимумом.

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

I. Свертка [38,54,73]. При этом подходе искомым векторным оптимумом объявляется такое решение, на котором достигает минимума единственная функция - свертка исходных целевых функций. Чаще всего она определяется в виде суммы: т к=\ где Fk(x)~ нормированное значение функции Fk(x), hk- коэффициент относи сительной важности к-ой целевой функции, hk > 0, ^h.k = 1. к=1

Нормирование функций Fk (х), необходимо для приведения их к одному измерению, осуществляется, например, согласно правилам:

Fk" {х) = -L Fk {х) или Fk" {х) = -th^L t ak Ak - ak где Ak = max Fk (x), ak = min Fk (x). xeX xeX m

Иногда свертку определяют в виде произведения Р{х) = ]~J Fk (x). Так=1 кая форма свертки наиболее приемлема для постановок типа задач надежности, в которых функции Fk(x) означают вероятность отказов или вероятность безотказной работы.

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

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

2) Существуют такие наборы целевых функций F{(x), ., Fm{x), что свертка не достигает минимума ни при каких значениях х е X . Это означает, что некоторые интересные для ЛПР решения в принципе нельзя найти с помощью свертки.

Этих недостатков удается в некоторой степени избежать, если вместо линейной свертки 3(х) использовать функцию следующего вида: 1 т к=1 где s > 1.

II. Нахождение лексико-графического [38,78] оптимума.

При этом подходе необходимым условием получения приемлемого решения многокритериальной задачи является ранжирование (линейное упорядочивание) критериев Fk(x), к = \,т, по важности. Для ранжирования по важности критериев наиболее изученным является случай, когда искомое решение является лексико-графическим Парето-оптимальным решением [38,78]. Поиск лексико-графического Парето-оптимального решения осуществляется по правилу: добивайся улучшения по более важному критерию за счет любых потерь по всем остальным менее важным критериям. Это правило, в частности, означает, что для любой пары упорядоченных критериев Fk(x) и F/(x) один из них в «бесконечное число раз» важнее другого.

III. Введение метрики в пространстве целевых функций [38].

Естественно, что в случае, когда все минимумы min Fk(x) = ак , к = \,т достигаются при одном и том же значении х0, многокритериальная задача решена однозначно. В общем случае этого, конечно же, ожидать нельзя, и тогда напрашивается такое определение векторного оптимума х0, для которого вектор F0 (х0) = (/*j ), F2 (х0 ),., Fm (x0 )) наименее удален от вектора a = (al,a2,.iam).

Иными словами, в пространстве целевых функций Fk(x), к-\,т, определяют точку а, которую называют точкой «абсолютного минимума». При этом подразумевают, что расстояние от абсолютного минимума до всякой точки F(x) g Rm берется с учетом относительной важности целевых функций (х). Таким образом, получается функция, являющаяся улучшенным вариантом свертки

Очевидно, что при этом подходе все числа ак должны быть положительными.

Заметим, что оптимуму, на котором достигается минимум функции / (х), в значительно меньшей степени присущи перечисленные выше недостатки свертки [38].

IV. Численные методы построения Парето-оптимальных решений [79].

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

Следует отметить, что наибольшие успехи в решении многокритериальных задач (в смысле нахождения Паретовского множества) достигнуты для классов многокритериальных задач линейного программирования. При этом построение Паретовского множества осуществляется путем прямого обобщения симплекс-метода линейного программирования на многокритериальный случай. Указание на многочисленные публикации по этой теме в иностранных источниках можно найти в [77].

Область дискретной векторной оптимизации еще мала изучена. Основанный на методе построения последовательности планов подход к решению дискретных многокритериальных задач изложен в книге [80], алгоритмы, использующие идеи «просеивания» решений, предложены в [81,82]. Методы решения многокритериальных задач с булевыми переменными излагаются в работах [73,83-86]. Отметим также работу [87], посвященную многокритериальной задачи теории расписаний, и работу [88], в которой исследуется полиматричная задача коммивояжера.

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

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

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

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

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

- проблема вычисления фрактальной размерности произвольного фрактального графа;

- проблема компактного задания предфрактального и фрактального графа;

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

В настоящей работе решается ряд обозначенных выше проблем.

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

Основными задачами исследования, определяемыми поставленной целью, являются:

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

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

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

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

Методы исследования основываются на использовании математического аппарата:

- теории графов;

- теории предфрактальных и фрактальных графов;

- комбинаторики;

- многокритериальной оптимизации.

Перейдем к изложению содержания диссертации.

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

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

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

Вторая глава посвящена построению алгоритмов с оценками покрытия простыми цепями двух типов, а именно непересекающимися и пересекающимися простыми цепями. Для покрытия простыми непересекающимися цепями - типа рассматриваются и обосновываются алгоритмы построения покрытия Ь - ранговыми цепями длины один (одно ребро), Ь - ранговыми цепями длины два (два ребра) и Ь - ранговыми цепями длины три (три ребра). Все приведенные алгоритмы являются полиномиальными и основаны на алгоритме выделения совершенного паросочетания минимального веса, предложенного Эдмонсом [10,11], который представлен в алгоритмах в виде процедуры. Причем каждый из рассмотренных алгоритмов строит парето-оптимальное решение многокритериальной задачи, а также даются и обосновываются оценки значений критериев для построенных решений.

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

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

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

- впервые поставлена и исследована многокритериальная задача покрытия предфрактального графа простыми непересекающимися цепями; впервые поставлена и исследована многокритериальная задача покрытия предфрактального графа простыми пересекающимися цепями;

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

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

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

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

По теме диссертационной работы опубликовано 12 печатных работ.

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

- IV Научно-практической конференции «Решение научно-технических и социально-экономических проблем современности» (г.Черкесск, 2002);

- XVI Международной научной конференции «Математические методы в технике и технологиях» (г.Санкт-Петербург, 2003);

- XVII Международной научной конференции «Математические методы в технике и технологиях» (г.Кострома, 2004);

- VI Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (г.Кисловодск, 2004);

- Научных семинарах профессорско-преподавательского состава КЧГТА (г.Черкесск, 2001-2004).

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

Выводы

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

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

ЗАКЛЮЧЕНИЕ

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

При этом получены следующие новые научные результаты:

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

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

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

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

1. Мелихов А.H., Берштейя J1.С. Курейчик В.М. Применение графов для проектирования дискретных устройств. - М.: Наука, 1974.

2. Geojfrion A. Solving bicriterion mathematical programs. Oper. Res., 1967, V. 15, №1, p.39-54.

3. Карзапов A.B. Экономные реализации алгоритмов Эдмонса нахождения паросочетания максимальной мощности и максимального веса / Исследования по дискретной оптимизации. -М.: Наука, 1976, С.306-327.

4. Лихолат H.A. Об одной задаче оптимального покрытия графа / Исследование операций и АСУ. Киев: Вища школа, 1978, вып.II, С.117-121.

5. Сердюков А.И. К задаче о покрытии //Управляемые системы. -Новосибирск, 1975, Вып. 14. С.24-32.

6. Емеличев В.А., Супруненко Д.А., Танаев B.C. О работах белорусских математиков в области дискретной математики // Изв. АН СССР. Техническая кибернетика, №6, 1982, С.25-46.

7. Юшмалов C.B. Маршруты в графах и связанные с ними множества вершин: Дисс. канд. физ.-мат.наук: 01.01.09/ Моск. гос. ун-т. М. 1982, С.102.

8. Еэри М., Джюнсон Д. Вычислительные машины и труднорешаемые задачи.-М.:Мир, 1982.

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

10. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.11 .Берж К. Теория графов и ее применения. М.: Иностр. лит., 1962.

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

12. ХЪ.Оре О. Теория графов. М.: Наука. Гл. ред. физ.-мат. лит., 1980.

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

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

15. Харари Ф. Теория графов.-М.Мир, 1973.17 .Кочкаров A.M. Многокритериальная задача покрытия графа цепями заданной длины. В сб. Математические вопросы исследования операций.-Минск:НИИ ЭМП. 1982,- С.42-49.

16. Кочкаров A.M. Двукритериальная задача покрытия графа цепями. IX Межреспубликанская конференция молодых ученых "Совершенствование метода планирования и повышения эффективности общественного производства". Тез. докл.- Минск: 1982.-С.144.

17. Кочкаров A.M. Многокритериальная задача покрытия графа цепями. //"Вест.Белорус, ун-та", сер.1, физ. мат. и мех., Минск, 1982., Деп. в ВИНИТИ, 30.06.82г. №3387-82, С.1-17.

18. Кочкаров A.M., Мартынова С.А., Перепелица В.А. Экспериментальный анализ приближенных алгоритмов покрытия графа цепями. Минск, 1983г. деп. в Бел.НИИНТИ, 02.08.83, №752 Бе-Д 83.-С. 1-11.

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

20. Кочкаров A.M. Многокритериальная задача покрытия графа цепями. Математические методы в исследовании операций. Тез. докл. Международной конференции НРБ, София, 1983.-С.42-43.

21. Кочкаров A.M., Перепелица В.А. Статистическая эффективность алгоритмов для полиматричных задач покрытия графа цепями. Республиканский семинар по дискретной оптимизации. Тез. докл. 1985.-Киев.-С.88-90.

22. ЗЗ.Мелроуз Дж. Иерархические фрактальные графы и блуждания на них . В сб. Фракталы в физике М.: Мир, 1988.-С.519-523.

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

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

25. Емеличев В.А., Перепелица В.А., Козырев В.А. Обзор некоторых проблем дискретной многокритериальной оптимизации. // Труды сем. по дискретной математике и ее прилож. -М.: МГУ,1989.-С.13-17.

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

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

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

29. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. -Киев: Наук, думка, 1988.41 .Манделъброт Б. Фрактальная геометрия природы. М.: ИКИ, 2002.

30. А2.Божокип C.B., Паршин Д.А. Фракталы и мультифракталы. Ижевск: НИЦ «РХД», 2001.

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

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

33. Курдюмов С.П., Малинецкий P.P., Потапов А.Б. Нестационарные структуры, динамический хаос, клеточные автоматы. В кн. Новое в синергетике. Загадки мира неравновесных структур.-М.:Наука, 1996 -С.95-164 .

34. Малинецкий Г.Г., Попов А.Б. Нелинейность. Новые проблемы, новые возможности. В кн. Новое в синергетике. Загадки мира неравновесных структур.-М.:Наука, 1996.-С.95-164.

35. AI .Шустер Г. Детерминированный хаос. Введение.-М.:Мир, 1998.

36. Гласс А., Мэки М. От часов к хаосу: Ритмы жизни. -М.: Мир, 1991.

37. Евин ИЛ. Синергетика искусства. -М.: 1993.

38. Haken И. Synergetics, Springer, 1997.51 .Кочкаров A.M., Перепелица В.А. Оценки сложности многокритериальных транспортных задач. Республиканский семинар по дискретной оптимизации. Тез. докл. Киев, ИК АН СССР, 1985. С.88-89.

39. Кочкаров A.M., Перепелица В.А. К оценкам сложности нахождения множеств альтернатив для многокритериальных задач об остовных деревьях. Всесоюзная конференция "Проблемы теоретической кибернетики". Тез. докл. 4.1-Горький: ГГУ, 1988,- С. 178-179.

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

41. Ope О. Графы и их применение. М.: Мир, 1965.51 .Зыков A.A. Основы теории графов. М.: Наука. Гл. ред. физ.-мат. лит., 1987.

42. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука. Гл. ред. физ.-мат. лит., 1985.

43. Tamm У. Теория графов. М.: Мир, 1988.

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

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

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

47. А.Ковалев М.М. Дискретная оптимизация. Минск: Изд-во БГУ, 1977.

48. Костевич А .С, Лапко А.А. Теория игр. Исследование операций.-Минск; "Высшая школа". 1982.

49. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач. //Дискретная математика.-1994, вып.1.-С.З-33.77 .Подия овский В. В., Ногин В. Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982.

50. Вентцелъ Е.С. Исследование операций: задачи, принципы, методология. -М.: Наука, 1980.

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

52. Ю.Михалевич B.C. Последовательные алгоритмы оптимизации и их применение.// I, II Кибернетика, 1965, №1, С. 45-56, №2, С.85-89.

53. Комлик В.И., Курелинков В.И., Ромашкина Н.В. Об одном алгоритме построения множества неулучшаемых планов.// Авоматизир. системы план, расчетов в республ. плановых органах, 1977, вып.9, С.18-21.

54. Buckley Т. Atoll decompositions of graphs "The Graphs Theory", 1982, 6, № 3, p.362-390.8Ь.Dinkelbach W. On nonlinear fractional programming. Manag. Sc. 3, 1967.

55. Козакова М.Ф. Нахождение оптимумов Парето в полиметрической задаче коммивояжера. В кн.: Математические методы решения экономических задач. -М.: Наука, 1974, №5, с.55-61.

56. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации.// Проблемы кибернетики, -1975. вып. 31, С.35-42.

57. Павлов Д.А., Кочкаров P.A., Узденов A.A. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах. Препринт. РАН CAO. Нижний Архыз. 2004 -С. 1 -16.

58. Павлов ДА. Многокритериальная задача покрытия фрактальных и предфрактальных графов простыми цепями. Черкесск, КЧГТА, 2004, Деп. в ВИНИТИ, №1248-В2004. С. 1-12.

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

60. Павлов ДА. Двухкритериальная задача покрытия предфрактального графа цепями длины г (т = 1,2,3)// Сб. трудов IV научно-практическойконференции «Решение научно-технических и социальноэкономических проблем современности». Черкесск, 2002. -С.31-33.

61. Павлов Д.А., Кочкаров А.А. Алгоритмы решения многокритериальной задачи покрытия предфрактальных графов пересекающимися простыми цепями. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-27.

62. Павлов Д.А. Оценка покрытия предфрактального графа кратчайшими простыми цепями// VI Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭП, 2004. С. 15-17.

63. Павлов Д.А., Салпагаров С.И. Многокритериальная задача выделения маршрутов на предфрактальном графе// Известия ТРТУ. Таганрог: ТРТУ, 2004,

64. Павлов Д.А. Нахождение диаметральной простой цепи на фрактальном и предфрактальном графах// Сб. трудов XVI Международ, науч. конф. «Математические методы в технике и технологиях». Санкт-Петербург: СПГТИ, 2003. -С. 186-187.

65. Павлов Д.А., Узденов А.А. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой полный «-вершинный граф. Препринт. РАН CAO. Нижний Архыз. 2004.-С.1-9.

66. Кочкаров A.M. Алгоритмические вопросы теории фрактальных графов: Дисс. док.физ.-мат. наук: 05.13.16. Черкесск: КЧТИ, 1998.

67. Смирнов Б. М. Фрактальные кластеры //Успехи физических наук,-1986. -Т.149, вып. 2.-С. 177-213.