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

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

Коркмазова Зарема Осмяновна

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

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

Автореферат

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

Ставрополь, 2006

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

Научный руководитель:

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

профессор

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

Официальные оппоненты:

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

профессор

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

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

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

Н: ац Виктория Игоревна

ля:

Таганрогский государственный радиотехнический университет

Защита состоится «22» сентября 2006 г в 16 часов на заседании

диссертационного совета ДМ 212.245.09 при Северо-Кавказском

государственном техническом университете по адресу: 355029, г. Ставрополь, пр. Кулакова, 2, ауд. Г-529.

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

Автореферат разослан «___»_ 2006 г.

/ —_мс-

Ученый секретарь диссертационного совета ///'<5-

кандидат физико-математических наук, доцент ___I/ О.С.Мезенцева

1. Общая характеристика работы

Актуальность темы. Современные исследования сложных систем, таких как, информационные, электроэнергетические, WJVW (Internet), коммуникационные показывают, что они по истечении времени претерпевают определенные изменения, вызываемые различными внешними обстоятельствами. Структуру системы произвольной природы (социальной, социально-экономической, технической, химико-биологической и т.п.) можно представить в виде графа. Граф - это абстрактный объект. Как правило, вершины графа соответствуют элементам системы, а ребра - связям между ними. Изменения, происходящие в структуре сложной системы, могут быть описаны простейшими теоретико-графовыми операциями: стягивание ребра, удаление (добавление) ребра, удаление (добавление) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными. Для второго случая разумно использовать понятие структурной динамики — изменение структуры системы с течением времени. Несомненно, для описании структурной динамики лучше всего подходит аппарат теории графов.

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

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

Фрактальный граф - сложный абстрактный объект, совмещающий в себе свойства, характеристики и достоинства фракталов и "обычных" графов.

Понятие фрактал, введенное Бенуа Мандельбротом, объединило объекты, обладающие особым свойством — свойством самоподобия (self-

similarity) или масштабной инвариантности. Работы, связанные с исследованием фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но не имеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги "Фракталы в физике". В настоящее время о перспективности и значимости исследований, связанных с фрактальными множествами, можно судить по регулярно проводимым конференциям и периодическим изданиям (журнал "Chaos, Solitons & Fractals"), Целиком посвященных соответствующей тематике и множеству книг (учебников и| монографий). Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрактальных множеств. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабно-инвариантные) графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети.

Активное изучение фрактальных графов и областей их приложения ведется в научной шкрле профессора A.M. Кочкарова. Исследования ведутся по трем направлениям: распознавание фрактальных графов, свойства и характеристики фрактальных графов, задачи многокритериальной оптимизации в системах с масштабно-инвариантной структурой. Надо отметить, что масштабная инвариантность структур моделируемых систем является следствием структурной динамики в этих системах.

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

Цели работы

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

2. Исследование возможности перехода от многокритериальной задачи Эйлера на предфрактальных графах к многокритериальной задаче конструирования (проектирования) многоэлементных структурно-сложных систем с заданными характеристиками.

3. Определение условий существования эйлерова цикла на предфрактальных ¡графах. Выявление особых свойств и характеристик предфрактальных эйлеровых графов.

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

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

Научная новизна. В диссертационной работе получили дальнейшее развитие теория и методы решения задач оптимального обхода взаимосвязанных объектов в системах со сложной структурой.! Впервые сформулирована и решена модельная многокритериальная задача Эйлера на предфрактальных графах. Рассмотрена и дополняющая Задача к многокритериальной задаче Эйлера на предфрактальных графах| — задача конструирования (проектирования) структурно-сложных систем с заданными характеристиками. Для прямой и дополняющей модельных задач Эйлера на предфрактальных графах поиск решений осуществляется эффективными алгоритмами. !

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

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

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

Апробация работы. Основные результаты работы докладывались на 2-й Международной конференции "Нелокальные краевые задачи й родственные проблемы математической биологии, информатики и физики" (Нальчик, 2001), на 5-м и 6-м Всероссийских симпозиумах "Математическое моделирование и компьютерные технологии") (Кисловодск, 2002 и 2004), на Международном Российско-Узбекском симпозиуме "Уравнения смешанного типа и родственные проблемы анализа и информатики" (Нальчик, 2003), на 34-й научно-технической конференции профессорско-преподавательского состава, аспирантов и студентов Северо-Кавказского Государственного технического университета (Ставрополь, 2005), на 50-й научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников Таганрогского Государственного радиотехнического университета (Таганрог, 2004), на 8-й Региональной научно-технической конференции "Вузовская наука - Северо-Кавказскому региону" (Ставрополь, 2004), на 5-й научно-практической конференции "От фундаментальной науки - к решению прикладных задач современности" (Черкесск, 2005), на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской Государственной технологической академии (Черкесск, 2001-2005).

Основные положения, выносимые на защиту

1. Сложные развивающиеся структуры можно моделировать фрактальными (самоподобными) графами. Фрактальные графы имеют широкий круг приложений в физических и технических задачах. Многокритериальная задача Эйлера на предфрактальных графах.

2. Эффективные (полиномиальные) алгоритмы поиска решений многокритериальной задачи Эйлера на предфрактальных графах. Для всех предложенных алгоритмов даны гарантированные оценки по критериям из

б

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

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

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

Публикации. По результатам выполненной работы имеется 17 публикаций, в том числе 2 статьи в журналах из списка ВАК РФ, 3 статьи, депонированные в ВИНИТИ, 2 препринта, тезисы докладов в материалах 4 международных конференций, тезисы докладов в материалах 2 Всероссийских симпозиумов.

Структура диссертации. Диссертация состоит из введения и трех глав, изложенных на 121 странице, содержит 15 рисунков и библиографию из 196 наименований.

2. Содержание работы

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

Дается краткое изложение содержания диссертации. '

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

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

7

либо связный граф Н = (№",(2) ■ Суть операции (ЗВЗ) заключается в следующем. В данном графе О = (V, Е) у намеченной для замещения вершины Гег выделяется множество V = {р"у} с V, } = 1,2,...,|г/| смежных ей вершин. Далее из графа с удаляется вершина у и все инцидентные ей ребра. Затем каждая вершина Уу еК, ] = 1,2,...,|н| соединяется ребром с одной из

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

Предфрактальный граф будем обозначать через где

- множество вершин графа, а Еь - множество его ребер. Определим его рекуррентно, поэтапно, заменяя каждый раз 5 построенном на предыдущем этапе / = 1,2,..., £ -1 графе б, = (К/,£;) каждую его вершину затравкой Н. На этапе / = 1 предфрактальному графу соот»етствует затравка С1=Н. Об описанном процессе говорят, что предфрактальный граф ' порожден затравкой Н. Процесс порождения предфрактального графа Оь по существу есть процесс построения последовательности предфрактальных графов называемой траекторией. Фрактальный граф

0 = (У,Е), порожденный затравкой Н, определяется бесконечной траекторией.

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

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

ребрами предфрактального графа назовем ребра ранга Ь, а все остальные ребра назовем старыми.

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

/ = 1,2.....Ь-г получим множество [В\г]}, г е {1,2,..., £ - 1}, блоков г-го

ранга, где / = 1,2,...,и£_г - порядковый номер блока. Термином подграф-затравка г^ будем называть блок В^, ,у = 1 ,п'~1 первого ранга предфрактального графа С/, / = 1,1 из траектории. Мощность множества

2(С?£) = }, / = 1,£, 5 = 1,й/_| всех подграф-затравок из траектории графа равна ЩО^-

п1-1 и -1 '

На рисунке 1 изображена траектория предфрактального графа С3 = (У3,Е3), порожденного затравкой Н = (IV, Q) - полным 4-вершинным графом (рисунок 1А). Самыми "жирными" линиями нарисованы ребра подграф-затравки г®. Линиями средней "жирности" нарисованы ребра подграф-затравок г^, г32^ и г^К И наконец, тонкими линиями

(рисунок 1В) нарисованы новые ребра предфрактального графа С3, которые образуют подграф-затравки , я = 1,16. '

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

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

если каждому его ребру е^ б Еь приписано действительное число

и>(ес0) е (в'^а.&^Ь), где I = -ранг ребра, а > О, и в <-.

Ь

Рассмотрим взвешенный предфрактальный граф = (У1,Е1) порожденный затравкой Н = (IV, 0, у которой мощность множества вершин \1¥\ = л, а мощность множества ребер |2| = 9 ■

Покрытием графа С?£ будем называть подграф х = (У1,ЕХ) = {С„,}, Ех с Е/ , каждая компонента Ст, т = 1,2,...,М которого является эйлеровым графом. Компоненты Ст, т = 1,2,...,М в покрытии х не пересекаются.

Число Кт назовем типом компоненты Ст, если подграф Ст = (Ут,Ет)содержит Кт ребер. Другими словами Кт - длина (число ребер) цикла Ст.Цикл, ребра которого имеют одинаковый ранг /, будем называть I-

ранговым циклом и обозначать .

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

циклом и обозначим через С1, если он состоит из ребер / различных рангов.

(а )0,=Я

£<3

(6)G2

(в) G

Рисунок 1- Траектория предфрактального графа G3 = {V3,E3)

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

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

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

Fx (x) = |jt| —> min, (2)

где Ы - число компонент в покрытии л:.

iiW- S^rr-nnin. (3)

где 2vKe) _ общий (суммарный) вес покрытия х, а F2(x) - удельный вес

ееЕх

покрытия X.

F3 (х) = шах Кт —» min,, (4)

теЛ/

где Кт — типы компонент Ст, т — 1,2,..., М в покрытии.

F4(*) = degCm ->min, (5)

для всех т = \,М, где maxdegv = degCm - степень компоненты С„, в

veCm

покрытии X.

F5(x) = jCml->mm, (6)

для всех т = \,М, где \Ст \ - число вершин компоненты Ст в покрытии х.

Во второйгглаве описаны и обоснованы алгоритмы а{-а6 выделения эйлеровых подграфов предфрактального графа. Алгоритмы а{-а5 выделяют на предфрактальном графе покрытия, которые являются оптимальными по одному или нескольким критериям ВЦФ задачи (1)-(6).

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

Теорема 2.1. Алгоритм at выделяет на взвешенном предфрактальном (n,q,L) -графе GL = (К,, EL) покрытие x^=(yL,EKl), оптимальное по третьему _ F3 (л,) критерию, оцениваемое по первому

6L~l —— <■ Fl (jc j) 5 6L~X второму F2(x{) четвертому F4 (*[) <п и

пятому F5(x{) = n критериям.

Теорема 2.2. Вычислительная сложность алгоритма at, осуществляющего выделение на (п,ц,Ь)-графе GL = (VL,EL), \VL\\=N = nL, покрытия, состоящего из L-ранговых циклов, равна O(Nn). i

Алгоритм а2 выделяет на предфрактальном графе эйлеров цикл.

Теорема 2.3. Алгоритм аг выделяет . на взвешенном предфрактальном (п,</,I.)-графе покрытие х2 = {У/_,ЕХ1),

оптимальное по первому критерию оцениваемое по второму

аф-1) ' ч^Ьи(и-1) (пв)1-1 _, , ,

2 «0-1 2 И0-1 ' тРетьемУ =

четвертому Р4{х2) ^ —~ и пятому (л2) - .ЛГ критериям.

Теорема 2.4. Вычислительная сложность алгоритма а2, осуществляющего выделение на предфрактальном (п,д,1,)-графе С7£ = (УЬ,ЕС), |К£| = N = и1" эйлерова цикла равна 0(Шг).

Алгоритм а3 выделяет на предфрактальном графе покрытие, состоящее из »-смешанных циклов.

теорема 2.5. Алгоритм аъ выделяет на взвешенном предфрактальном (п,д,Ь)-графе = (К^,Е; ) покрытие хг = ).

оцениваемое по всем критериям: по первому /*!(х3) = «о второму

2 /=¿-/+1 2 /=/.-<+1-

по четвертому ^4(х3) < ^ и пятому (х3) = и' критериям. ■

Алгоритм а4 выделяет на предфрактальном графе эйлеров подграф. Теорема 2.6. Алгоритм а4 выделяет на взвешенном предфрактальном I,)-графе С; = покрытие х4 = (УЬ,ЕХ^),

оптимальное по первому критерию (_г4), оцениваемое по второму

о д 1 ^)~ \ • д . . третьему Е3(х4) = 1,

2 пв-1 2 пв — 1

четвертому Е4 (х4 ) < —^—— и пятому (х4 ) = N критериям.

Теорема 2.7. Вычислительная сложность алгоритма а4, осуществляющего выделение на предфрактальном (п,д,£)-графе =(К£,£7 ), \Уь\ = N = п1 эйлеров подграф, равна 0(Ып2).

12

Алгоритм а}, как и алгоритм а2, выделяет на предфрактальном графе эйлеров цикл. Но алгоритм а5, в отличие от алгоритма аг, осуществляет выделение эйлерова цикла только на тех предфрактальных графах, у которых сохраняется смежность старых ребер одного ранга.

Теорема 2.8. Алгорипш а5 выделяет на взвешенном предфрактальном (п,ц,Ь)-графе = (УЬ,ЕЬ) покрытие х5 —{У[.,ЕХ ), оптимальное по первому критерию (х2), оцениваемое по второму ап{п-1) (пв)1-, ^Цп-1) (пв)1-\

2 пв-\ г{-Хг) 2 пв-1 ' тРетьемУ =

четвертому (х2 ) - ~~~—~ и пятому (д:2 ) = N критериям.

Теорема 2.9. Вычислительная сложность алгоритма а3, осуществляющего выделение на предфрактальном (п,д,Ь)-графе = (), |К£| = N = пь эйлерова цикла, равна 0(АТп2).

Алгоритм а6 вьщеляет на предфрактальном графе эйлеров подграф с заданным ограничением по времени / < Г. В качестве / может, например, использоваться число элементарных операций (выделение вершины, выделение ребра) в алгоритме. Алгоритм а6 позволяет выделять наименьший эйлеров подграф С = (УС,ЕС), ГссКд, ЕС^Е1, содержащий любые две заданные вершины и.уе^ предфрактального графа

Теорема 2.10. Алгоритм а6 выделяет наименьший эйлеров подграф С = (Ус,Ес), содержащий любые две заданные вершины и, V е предфрактального (п,ц,Ь)-графа ={У1,Е1), Ус с , Ес с^Е^.

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

I

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

равна 0(Ы2), где N - число вершин предфрактального (п,<7, £)-графа , что в п 1~г раз больше вычислительной сложности алгоритмов а2 и а5 (теоремы 2.4 и 2.9).

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

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

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

Теорема 3.1. Алгоритм рх порождает эйлеров предфрактальный граф = затравка II = (IV, £)) которого также является

эйлеровой.

Следствие 3.1., В траектории 0х,0г,...,01 предфрактального графа порождаемого алгоритмом рх, все предфрактальные графы являются эйлеровыми.

Алгоритм /?2, как и алгоритм /?,, гарантированно порождает эйлеров предфрактальный граф. Существенным отличием алгоритма рг от алгоритма /?! является то, что в результате работы алгоритма /?2 получается ориентированный эйлеров предфрактальный граф, порожденный ориентированной эйлеровой затравкой.

Теорема 3.2. Алгоритм /?2 порождает ориентированный эйлеров предфрактальный граф = (УЬ,Е,), затравка Н = (IV,(2) которого также является ориентированным эйлеровым графом.

Следствие 3.2. В траектории 01,02,...,011 ориентированного предфрактального графа Сг£, порождаемого алгоритмом р2, все предфракталъные графы являются ориентированными эйлеровыми графами.

На предфрактальных графах, полученных как результат работы алгоритмов рх и р2, можно Гарантированно выделить покрытие, используя алгоритмы а2 и а5, оптимальное по первому критерию ВЦФ задачи (1)-(6).

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

Теорема 3.3. Число вершин нечетной степени предфрактального («,</, Ь)-графа = (у1,Е1), порожденного эйлеровой затравкой

II = (IV, 2), смежность старых ребер одного ранга которого не

и£-2(и-2) + 1 „

сохраняется, не меньше-1----2д.

п-1

Следствие 3.3. Предфрактальный граф Сг^ = порожденный

эйлеровой затравкой II = (}У,0), смежность старых ребер одного ранга которого не сохраняется, не является эйлеровым.

Теорема 3.4. Для предфрактального (п,д,Ь)-графа порожденного эйлеровой затравкой Н = (IV,О), смежность старых ребер одного ранга которого не сохраняется, максимальная степень определяется неравенством шах ) < и + £ - 2.

Теорема 3.5. Число вершин нечетной степени предфрактального (п,д,Ь)-графа С1 = (У1,Е1), порожденного неэйлеровой з|ятравкой Н = (IV, О), смежность старых ребер которого сохраняется, не меньше

Следствие 3.4. Предфрактальный граф Сг£ = (У1,Е1), порожденный неэйлеровой затравкой Н = (1У,0), смежность старых ребер которого сохраняется, не является эйлеровым.

Основные результаты, полученные в диссертации

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

:'' $ Л...-

многокритериальная задача Эйлера на предфрактальЯых графах.

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

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

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

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

1. Коркмазова З.О., КочкаровА.А. Алгоритм порождения ориентированного эйлерова предфрактального графа // Вестник Северо-

Кавказского государственного технического университета. - Ставрополь, СевКавГТУ, 2006, №3 (7) - С. 55-61.

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

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

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

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

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

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

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

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

Ю.Коркмазова З.О., Салпагаров С.И. Параллельный алгоритм решения задачи Эйлера на предфрактальных графах// Материалы Российско-Узбекского симпозиума "Уравнения смешанного типа и родственные проблемы анализа и информатики". Тез. докл. - Нальчик: НИИ ПМиА КБНЦ РАН, 2003.-С. 124-126.

11 .Коркмазова 3.0., Тлябичева М.А. Р-адические деревья на предфрактальных графах// Материалы Российско-Узбекского симпозиума "Уравнения смешанного типа и родственные проблемы анализа и информатики". Тез. докл. - Нальчик: НИИ ПМиА КБНЦ РАН, 2003. -С.154-155.

\2.Коркмазова З.О., Узденов A.A. /¿-медиана предфрактального графа с затравкой лес // Материалы Российско-Узбекского симпозиума "Уравнения смешанного типа и родственные проблемы! анализа и информатики". Тез. докл. - Нальчик: НИИ ПМиА КБНЦ РАН, 2003. - С. 157-158.

13.Коркмазова 3.0., Кочкаров A.M. Полиномиально разрешимый класс многокритериальных задач покрытия предфрактальных и фрактальных графов эйлеровыми циклами (цепями) // VI Всероссийский Симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2004. - С. 13-15.

\ А.Коркмазова 3.0. Алгоритм выделения максимального эйлерового предфрактального подграфа // V научно-практическая конференция "От фундаментальной науки - к решению прикладных задач современности". Тез. докл. - Черкесск: Карачаево-Черкесская Гос. Технолог. Ак., 2004. - С. 89.

15.Коркмазова З.О., Никищенко С.П. Двухпараметрическая трехкритериальная задача Эйлера на предфрактальных графах с полной двудольной затравкой // Материалы VIII региональной научно-технической конференции "Вузовская наука - Северо-Кавказскому региону". Том I. -Ставрополь: СевКавГТУ, 2004. - С. 11.

\6 .Коркмазова 3.0., Никищенко С.П. Оценка числа эйлеровых циклов на предфрактальном (и, £)-графе с затравкой полный двудольный подграф// Материалы VIII региональной научно-технической конференции "Вузовская

наука — Северо-Кавказскому региону". Том I. - Ставрополь: СевКавГТУ, 2004.-С. 11-12.

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

Подписано в печать 11.07.2006г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1,16 Заказ 00853. Тираж 100 экз.

Отпечатано с готового оригинал-макета на множительно-полиграфическом участке КЧГТА 369000, г. Черкесск, ул. Ставропольская, 36

Г ВВЕДЕНИЕ.

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

1.1. Эйлеровы графы и задача "китайского почтальона".

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

1.3. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами.

1.4. Вывод.

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

2.1. Алгоритм ах построения покрытия L-ранговыми циклами.

2.2. Алгоритм аг выделения эйлерова цикла на предфрактальном графе, смежность старых ребер которого сохраняется.

2.3. Алгоритм аъ выделения /-смешанных циклов.

2.4. Алгоритм а4 выделения эйлерова подграфа.

2.4.1. Алгоритм (Хр выделения эйлерова подграфа на полном графе.

2.4.2. Алгоритм aF выделения эйлерова подграфа на полном графе.

2.5. Алгоритм а5 выделения эйлерова цикла на предфрактальном графе, смежность старых ребер одного ранга которого сохраняется.

2.6. Алгоритм а6 выделения эйлерова подграфа на предфрактальном графе, смежность старых ребер которого сохраняется.

2.7. Выводы.

ГЛАВА 3. АЛГОРИТМЫ ПОРОЖДЕНИЯ ЭЙЛЕРОВЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ. НЕКОТОРЫЕ ХАРАКТЕРИСТИКИ

НЕЭЙЛЕРОВЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ.

3.1. Алгоритм Д порождения эйлерова предфрактального графа.

3.2. Алгоритм Д, порождения ориентированного эйлерова предфрактального графа.

3.3. Выводы.

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

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

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

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

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

F(*) = (1)

Fj (х) extr{max/ min), / = 1, п, где F(x) - векторно-целевая функция (ВЦФ) с критериями Fj(x), i = \,n, которые оптимизируются на множестве допустимых решений (МДР) X = {х].

В исследовании всякой многокритериальной задачи можно выделить три последовательных этапа:

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

- выделение из множества допустимых решений оптимальных по Паре-то, так называемого паретовского множества (ПМ) или множества эффективных решений. Решение Парето-оптимально, если значение любого из критериев можно улучшить лишь за счет ухудшения значений других критериев. Такие решения еще называют векторно-несравнимыми. Наименование указанного понятия связанно с именем итальянского ученого В. Парето (1848-1923), который одним из первых начал его использовать при математических исследованиях процесса рыночного обмена товаров [18]. В отечественной научной литературе наиболее полное и систематическое изложение проблем посвященных Парето-оптимальных решений можно найти в книгах [19,20];

- принятие окончательного решения или выбор. На этом этапе из ПМ необходимо выбрать решение, которое будет реализовано с учетом сущности задачи и особенностями области приложения. Выбор может быть осуществлен лицом принимающим решение (ЛПР), в соответствии с его личным опытом деятельности, или же автоматизировано с использованием методов и подходов теории принятия решений при многих критериях [21-37].

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

Дискретная многокритериальная оптимизация

Одной из широко используемых и хорошо развитых областей дискретной математики является теория графов [38-53]. Методы теории графов нашли свои приложения во многих областях современной прикладной науки: в технике [54 - 57], экономике [58 - 59], биологии и химии [60 - 63], в исследовании надежности, стойкости и живучести систем [64-71], моделировании динамических систем и управлении [72 - 79], и т.д. Нередко использование методов теории графов в перечисленных областях исходило из постановки оптимизационных задач. Напомним, что введение самих графов произошло при решении J1. Эйлером по сути оптимизационной задачи о кенигс-бергских мостах [80]. Поиск решений оптимизационных задач на графах осуществляется специализированными алгоритмами [40, 42,43,44, 81 - 90].

Качество поиска решения алгоритмом оценивается его трудоемкостью или, говоря иначе, вычислительной слоэ/сностью [83].

Вычислительная слоэюностъ - это общее число всех элементарных операций, произведенных алгоритмом за время его работы. Вообще говоря, вычислительная сложность - это функция /(п), которая ставит в соответствие размерности п задачи количество производимых алгоритмом элементарных операций. Будем считать, что /(«) есть 0(g(n)), если существует константа с, такая, что |/(и)| < c\0{g(n))\ для всех значений п> 0. Полиномиальным алгоритмом (или алгоритмом полиномиальной вычислительной сложности) называют алгоритм, у которого вычислительная сложность равна 0(р(п)), где р{п) - некоторая полиномиальная функция. Алгоритмы, которые не поддаются подобной оценке, называются экспоненциальными. С ростом размерности задачи предпочтительность полиномиальных алгоритмов перед экспоненциальными вполне очевидна. Поэтому первые называют эффективными, а вторые неэффективными. Задача называется труднорешае-мой, если для ее решения не существует полиномиального алгоритма. Таким образом, обоснованный полиномиальный алгоритм решения графовой оптимизационной задачи является наиболее полезным результатом проводимого исследования.

Идеи многокритериальной оптимизации нашли свое продолжение и в задачах дискретной оптимизации [91 - 129]. Среди задач дискретной многокритериальной оптимизации можно выделить две группы. Первая группа -многокритериальные задачи целочисленного линейного программирования [111-119]. К этой группе относятся задача о назначениях, целочисленная транспортная задача, задача землепользования и т.д. Вторая группа - многокритериальные задачи на графах [92 - 110], и сетях [122 - 126]. В эту группу входит значительно более широкий класс задач по сравнению с первой группой. Рассмотрим более подробно группу многокритериальных задач на графах.

В формулировке многокритериальной задачи (I) на конкретном графе (орграфа) G = (V,E) [38-58], который, как правило, является моделью структуры означенной в задаче системы, считается, что ее допустимое решение х&Х представляет собой определенный подграф х = (VX,EX) графа (орграфа) G с множеством вершин F^cF и множеством ребер (дуг) Ех q Е. Подграф х называется остовным, если Vx = V. Часто остовный подграф называю покрытием. Определенное специальным образом допустимое решение хеХ является отличительной особенностью многокритериальных задач на графах. Вид подграфа x = (Vx,Ex) определяет множество многокритериальных задач на графах, среди которых можно выделить основные:

- задача о совершенных паросочетаниях;

- задача об остовных деревьях;

- задача о путях (цепях) между парой вершин;

- задача о покрытии графа цепями;

- задача о покрытии графа звездами.

В качестве критериев F/ (х), / = 1, п, в таких задачах используются степень подграфа [38-58] л;, его диаметр [38-58], количество компонент связности [38 — 58] и общий (суммарный) вес, если граф G взвешен [38 - 58].

Структурная динамика, фрактальные графы и многокритериальная оптимизация

Современные исследования сложных систем, таких, как информационные, электроэнергетические, WWW (Internet), коммуникационные системы показывают, что структуры этих систем по истечении времени претерпевают определенные изменения, вызываемые различными внешними обстоятельствами [130-134]. Структуру системы произвольной природы (социальной, социально-экономической, технической, химико-биологической и т.п.) можно представить в виде графа. Граф — это абстрактный объект, как правило, вершины графа соответствуют элементам системы, а ребра - связям между элементами этой системы. Изменения, происходящие в структуре сложной системы, могут быть описаны простейшими теоретико-графовыми операциями: стягивание ребра, удаление (добавление) ребра, удаление (добавление) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными. Для второго случая разумно ввести понятие структурной динамики — изменение структуры системы с течением времени. Несомненно, для описания структурной динамики лучше всего подходит аппарат теории графов.

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

В настоящей работе рассматривается одно из возможных правил, задающих структурную динамику сложных систем. Формальными представлениями изменения структуры систем по этому правилу являются масштабно-инвариантные или самоподобные графы (self-similar graphs) большой размерности, называемые фрактальными (предфрактальными).

Фрактальный граф - сложный абстрактный объект, совмещающий в себе свойства, характеристики и достоинства фракталов и "обычных" графов.

Понятие фрактал, введенное Бенуа Мандельбротом [135], объединило объекты, обладающие особым свойством - свойством самоподобия (self-similarity) или масштабной инвариантности. Работы, связанные с исследованием фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но неимеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги [136]. В настоящее время о перспективности и значимости исследований, связанных с фрактальными множествами, можно судить по регулярно проводимым конференциям и периодическим изданиям (журнал "Chaos, Solitons & Fractals"), целиком посвященных соответствующей тематике и множеству книг (учебников и монографий) [135-141]. Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрактальных множеств [142- 154]. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабно-инвариантные) графы большой размерности, т.е. с большим числом вершин. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем [153], таких как коммуникационные сети.

Активное изучение фрактальных графов и областей их приложения ведется в научной школе профессора A.M. Кочкарова. Исследования ведутся по трем направлениям: распознавание фрактальных графов [128, 155], их свойства и характеристики [156- 170], задачи многокритериальной оптимизации в системах с масштабно-инвариантной структурой [171-196]. Надо отметить, что масштабная инвариантность структур моделируемых систем является следствием структурной динамики в этих системах.

Краткое содержание и структура диссертационной работы

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

Публикации. По результатам выполненной работы имеется 17 публикация, в том числе 2 статьи в журналах из списка ВАК РФ, 3 статьи, депонированные в ВИНИТИ, 2 препринта, тезисы докладов в материалах 4 международных конференций, тезисы докладов в материалах 2 Всероссийских симпозиумов и т.д.

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

З.З.Выводы

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

Рассмотрены различные случаи порождения предфрактального графа и подсчитаны некоторые характеристики:

-предфрактальный граф порожден эйлеровой затравкой, у которого старые ребра одного ранга не пересекаются (число вершин нечетной степени й nL~2(n-l) + \ больше или равно ------2 q, максимальная степень п-1 max deg((j£ )<n + L-2);

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

3. Рассмотрены различные случаи порождения предфрактального графа и подсчитаны некоторые характеристики:

1) предфрактальный граф порожден эйлеровой затравкой, у которого старые ребра одного ранга не пересекаются (число вершин нечетной степени max deg(GL) < п + L - 2);

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

• 2 q, максимальная степень вершин нечетной степени больше или равно

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

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

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

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

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

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

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

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

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

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

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

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

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

14. ТахаХ. Введение в исследование операций. М.: Диалект, 2005.

15. Венцелъ Е.С. Введение в исследование операций. М.: Сов. радио, 1964.16