Содержание к диссертации
Введение
ГЛАВА 1. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами 21
1.1. Эйлеровы графы и задача "китайского почтальона" 21
1.2. Фрактальные и предфрактальные графы 24
1.3. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами 29
1.4. Вывод 34
ГЛАВА 2. Алгоритмы с оценками построения покрытий циклами на предфрактальном графе 35
2.1. Алгоритм ах построения покрытия L-ранговыми циклами 35
2.2. Алгоритм аг выделения эйлерова цикла на предфрактальном графе, смежность старых ребер которого сохраняется 38
2.3. Алгоритм аг выделения /-смешанных циклов 47
2.4. Алгоритм а4 выделения эйлерова подграфа 52
2.4.1. Алгоритм aF выделения эйлерова подграфа на полном графе 58
2.4.2. Алгоритм aF выделения эйлерова подграфа на полном графе 62
2.5. Алгоритм а5 выделения эйлерова цикла на предфрактальном графе, смежность старых ребер одного ранга которого сохраняется 66
2.6. Алгоритм а6 выделения эйлерова подграфа на предфрактальном графе, смежность старых ребер которого сохраняется 74
2.7. Выводы 76
ГЛАВА 3. Алгоритмы порождения эйлеровых предфрактальных графов. некоторые характеристики неэйлеровых предфрактальных графов 79
3.1. Алгоритм Д порождения эйлерова предфрактального графа 79
3.2. Алгоритм Д порождения ориентированного эйлерова предфрактального графа 94
3.3. Выводы 101
Заключение 102
Литература
- Фрактальные и предфрактальные графы
- Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами
- Алгоритм аг выделения эйлерова цикла на предфрактальном графе, смежность старых ребер которого сохраняется
- Алгоритм Д порождения ориентированного эйлерова предфрактального графа
Введение к работе
Математическое моделирование и многокритериальная оптимизация
Моделирование [1] - незаменимый инструмент в поиске понимания сути исследуемых процессов и явлений. Математическая модель [1 -8], т.е. формальное отражение исследуемого явления или процесса, - является основой для всех дисциплин прикладной математики [5]. Если раньше моделирование было исключительной прерогативой специалистов технических и инженерных направлений науки, то теперь моделирование, как инструмент познания окружающего мира, используется во многих, если не во всех, отраслях современной науки.
Любая целенаправленная деятельность требует планирования, проектирования (конструирования) и прогнозирования. Каждая из составляющих не возможна без понимания сути процесса в той области, где осуществляется деятельность. Достичь понимания, как уже отмечалось, можно с помощью адекватно построенной математической модели. Это и есть главное обоснование необходимости построения математических моделей. На основе имеющейся математической модели возможна постановка оптимизационной задачи [10, 11], решение которой позволяет точно оценить сложившуюся ситуацию, а значит, сделать правильный прогноз и провести планирование дальнейших действий. Задачи оптимального и автоматического управления, автоматизации проектирования, эколого-экономического планирования, принятия решений, компромисса в условиях неполной информации, математического программирования и т.п. находятся в сфере деятельности специалистов по исследованию операций [12- 16]. Предметом исследования операций, как правило, являются сложные системы.
В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и (или) нетривиальных связей между ними. А с другой стороны, речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны. Поэтому сложные системы требуют "объемного" всестороннего анализа. В этом смысле методы исследования операций перемежаются с задачами системного анализа [8].
Основной целью задач исследования операций по оптимизации является оценивание различных вариантов решений и выбор среди них наиболее эффективных. В формулировке задач планирования и проектирования (конструирования) содержатся требования и критерии искомой (оптимальной) конструкции или искомого плана. Зачастую эти критерии и требования являются противоречащими друг другу. Что приводит к появлению многокритериальной постановки оптимизационной задачи. В общем случае она выглядит следующим образом: F(x) = {Fx{x),F2{xl...,Fi{x),...,Fn{x)), (1) Fj(х) -» extr{max/min), / = 1, w, где F(x) - векторно-целевая функция (ВЦФ) с критериями Fj(x), і = \,п, которые оптимизируются на множестве допустимых решений (МДР) ^ = (^}.
В исследовании всякой многокритериальной задачи можно выделить три последовательных этапа: построение множества допустимых решений. Оно всегда связанно со спецификой той области, в которой проводится оптимизация [17]. Нередко построение МДР нетривиальная задача. Существует ряд методов, в том числе и хорошо автоматизируемых, которые позволяют выделять МДР, т.е. формулировать полную постановку многокритериальной задачи, включающую, кроме МДР, и векторно-целевую функцию. выделение из множества допустимых решений оптимальных по Паре-то, так называемого паретовского мноэ/сества (ПМ) или множества эффективных решений. Решение Парето-оптимально, если значение любого из критериев можно улучшить лишь за счет ухудшения значений других критериев. Такие решения еще называют векторио-несравпимыми. Наименование указанного понятия связанно с именем итальянского ученого В. Парето (1848-1923), который одним из первых начал его использовать при математических исследованиях процесса рыночного обмена товаров [18]. В отечественной научной литературе наиболее полное и систематическое изложение проблем посвященных Парето-оптимальных решений можно найти в книгах [19,20]; - принятие окончательного решения или выбор. На этом этапе из ПМ необходимо выбрать решение, которое будет реализовано с учетом сущности задачи и особенностями области приложения. Выбор может быть осуществлен лицом принимающим решение (ЛПР), в соответствии с его личным опытом деятельности, или же автоматизировано с использованием методов и подходов теории принятия решений при многих критериях [21-37].
Каждый из этапов исследования многокритериальной задачи является отдельной самодостаточной задачей. Настоящую работу следует отнести к исследованиям, связанным со вторым этапом.
Дискретная многокритериальная оптимизация
Одной из широко используемых и хорошо развитых областей дискретной математики является теория графов [38-53]. Методы теории графов нашли свои приложения во многих областях современной прикладной науки: в технике [54 - 57], экономике [58 - 59], биологии и химии [60 - 63], в исследовании надежности, стойкости и живучести систем [64-71], моделировании динамических систем и управлении [72 - 79], и т.д. Нередко использование методов теории графов в перечисленных областях исходило из постановки оптимизационных задач. Напомним, что введение самих графов произошло при решении Л. Эйлером по сути оптимизационной задачи о кенигс-бергских мостах [80]. Поиск решений оптимизационных задач на графах осуществляется специализированными алгоритмами [40, 42,43,44, 81 - 90].
Качество поиска решения алгоритмом оценивается его трудоемкостью или, говоря иначе, вычислительной сложностью [83].
Вычислительная сложность - это общее число всех элементарных операций, произведенных алгоритмом за время его работы. Вообще говоря, вычислительная сложность - это функция f{n), которая ставит в соответствие размерности п задачи количество производимых алгоритмом элементарных операций. Будем считать, что /(«) есть 0(g(n)), если существует константа с, такая, что |/(и)| < c|(9(g(rc))| для всех значений п > О. Полиномиальным алгоритмом (или алгоритмом полиномиальной вычислительной сложности) называют алгоритм, у которого вычислительная сложность равна 0(р(п)), где р{п) - некоторая полиномиальная функция. Алгоритмы, которые не поддаются подобной оценке, называются экспоненциальными. С ростом размерности задачи предпочтительность полиномиальных алгоритмов [ перед экспоненциальными вполне очевидна. Поэтому первые называют эффективными, а вторые неэффективными. Задача называется труднорешае- „ мой, если для ее решения не существует полиномиального алгоритма. Таким образом, обоснованный полиномиальный алгоритм решения графовой опти-мизационной задачи является наиболее полезным результатом проводимого исследования.
Идеи многокритериальной оптимизации нашли свое продолжение и в задачах дискретной оптимизации [91 - 129]. Среди задач дискретной многокритериальной оптимизации можно выделить две группы. Первая группа -многокритериальные задачи целочисленного линейного программирования [111-119]. К этой группе относятся задача о назначениях, целочисленная транспортная задача, задача землепользования и т.д. Вторая группа - многокритериальные задачи на графах [92 - 110], и сетях [122 - 126]. В эту группу входит значительно более широкий класс задач по сравнению с первой группой. Рассмотрим более подробно группу многокритериальных задач на графах.
В формулировке многокритериальной задачи (I) на конкретном графе (орграфа) G = (V,E) [38-58], который, как правило, является моделью структуры означенной в задаче системы, считается, что ее допустимое решение х&Х представляет собой определенный подграф x = (Vx,Ex) графа (орграфа) G с множеством вершин VX<^V и множеством ребер (дуг)
Ех qE . Подграф х называется остовным, если 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 Всероссийских симпозиумов и т.д.
Объем и структура диссертационной работы. Диссертация состоит из введения, трех тематических глав, заключения, приложения и списка использованных источников.
Работа изложена на 121 странице, содержит 15 рисунков, 1 страницу приложения, 17 страниц списка использованных источников, содержащих 196 наименований, из них 19 - зарубежных авторов.
В первой главе предлагается обзор областей, в которых возникает необходимость решения задачи Эйлера. Определяется фрактальный (самоподобный или масштабно-инвариантный) граф. Формулируется модельная многокритериальная задача Эйлера на предфрактальных графах.
В основе определения фрактальных графов лежит операция замены вершины затравкой. Термином затравка (ЗВЗ) условимся называть какой-либо связный граф Н = (W,Q). Суть операции (ЗВЗ) заключается в следующем. В данном графе G = (V, Е) у намеченной для замещения вершины v є v /*/ г** выделяется множество V = {vj} с V, j = 1,2,..., V смежных ей вершин. Далее из графа g удаляется вершина v и все инцидентные ей ребра. Затем каждая вершина Vj є V, j = 1,2,..., V соединяется ребром с одной из вершин затравки Н. Вершины соединяются произвольно (случайным образом), или по определенному правилу, при необходимости.
Предфракталъный граф будем обозначать через GL =(VL,EL), где VL - множество вершин графа, a EL - множество его ребер. Определим его ре-куррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе / = 1,2,...,/,-1 графе G/ =(Vl,El) каждую его вершину затравкой Н. На этапе / = 1 предфрактальному графу соответствует затравка G\=H .Об описанном процессе говорят, что предфракталъный граф GL порожден затравкой Н. Процесс порождения предфрактального графа GL по существу есть процесс построения последовательности предфрактальных графов G\, G2,-., G{,..., GL, называемой траекторией. Фрактальный граф G = (V, Е), порожденный затравкой Н, определяется бесконечной траекторией.
Для предфрактального графа GL ребра, появившиеся на /-ом,
I е{\,2,...,Ц, этапе порождения, будем называть ребрами ранга I. Новыми ребрами предфрактального графа GL назовем ребра ранга L, а все остальные ребра назовем старыми.
При удалении из предфрактального графа GL всех ребер рангов / = 1,2,..., L - г получим множество {В^[]}, г є {1,2,..., L -1}, блоков г -го ран-га, где / = 1,2,..., п - порядковый номер блока. Термином подграф-затравка zy будем называть блок BJ^, s = \,n первого ранга предфрактального графа G/, l = \,L из траектории. Мощность множества Z(GL) = {zy }, l-\,L, s = \,n~ всех подграф-затравок из траектории графа nL -1 GL равна \Z(GL )| = . п — 1
Предфрактальный граф GL =(VL,EL) условимся называть {n,q,L)~ графом, если он порожден п -вершинной #-реберной связной затравкой H = (W,Q).
Будем говорить, что предфрактальный граф GL = (VL,EL) - взвешен, если каждому его ребру е^ є EL приписано действительное число м?(е^)є(в1~1а,в1~]Ь),где l = \,L -ранг ребра, а>0, и в < — .
Рассмотрим взвешенный предфрактальный граф GL=(VL,EL) порожденный затравкой Н = (W, Q), у которой мощность множества вершин \W| = п, а мощность множества ребер |g| = q.
Покрытием графа GL будем называть подграф x = (VL,Ex) = {Cm}, ExqEl, каждая компонента Ст, т = \,2,...,М, которого является эйлеровым графом. Компоненты Ст, т = 1,2,...,М в покрытии х не пересекаются.
Число Кт назовем типом компоненты Ст, если подграф Ст = (Vm,т)содержит Кт ребер. Другими словами Кт — длина (число ребер) цикла Ст. Цикл, ребра которого имеют одинаковый ранг /, будем называть / -ранговым циклом и обозначать С^.
Цикл предфрактального графа GL будем называть і-смешанным циклом и обозначим через С, если он состоит из ребер і различных рангов.
Предфрактальный граф GL, содержащий эйлеров цикл, будем называть эйлеровым предфрактальным графом.
Всевозможные покрытия {х} предфрактального графа GL образуют множество допустимых решений X = X(GL) = {х} (МДР).
Качество покрытия х на графе GL задается векторно-целевой функцией (ВЦФ): F(x) = (F^^ixlF.ixlF^xlF.ix)) (2) F, (х) = \х\ —> min, (3) где |л:| - число компонент в покрытии д:. F2(x)=YJ}Tj-^^n, (4) еєЕх \х\ где ^w(e) - общий (суммарный) вес покрытия х, a F2(x) - удельный вес ееЕх покрытия X. F3 (х) = max Кт -> min, (5) где Кт -типы компонент Ст, т = 1,2,...,М в покрытии. F4 (х) = deg Ст -> min, (6) для всех т = \,М, где maxdegv = degCOT - степень компоненты Ст в покры- veCm тии х. F5(x) = \Cm\-+mm, (7) для всех т = \,М, где \Ст\ - число вершин компоненты Ст в покрытии х.
Во второй главе описаны и обоснованы алгоритмы ах-а6 выделения эйлеровых подграфов предфрактального графа. Алгоритмы а{-а5 выделяют на предфрактальном графе покрытия, которые являются оптимальными по одному или нескольким критериям ВЦФ.
Алгоритм ах выделяет на предфрактальном графе покрытие, состоящее из Z-ранговых циклов.
ТЕОРЕМА 2.1. Алгоритм ах выделяет на взвешенном предфракталь ном (n,q,L)-графе GL=(VL,EL) покрытие Xj =(VL,EX ), оптимальное по третьему ^зС^і) критерию, оцениваемое по первому L і L L в ~
ТЕОРЕМА 2.2. Вычислительная сложность алгоритма а,, осуществляющего выделение на (п,q,L)-графе GL = (VL,EL), \VL\ = N = п , покрытия, состоящего из L-ранговых циклов, равна O(Nn). М
Алгоритм а2 выделяет на предфрактальном графе эйлеров цикл.
Теорема 2.3. Алгоритм а2 выделяет на взвешенном предфракталь ном (n,q,L)-графе GL=(VL,EL) покрытие х2 = (VL,EX), оптимальное по первому критерию Fx{x2), оцениваемое по второму an{n-\) {пв)1 -1 ^ F ,„ ч^ bn{n-\) {пв)1 -1 о ^--^0)^ ^-' третьему F3{x2) = L, чет- _, , . ^, Ln{n-\) _ , . вертому b4 {x2 ) < и пятому F5 {x2) = N критериям. Л
ТЕОРЕМА 2.4. Вычислительная сложность алгоритма а2, осуществляющего выделение на предфрактальном (n,q,L) -графе GL={VL,EL),
I Т О VL | = N = п эйлерова цикла равна 0{Nn). Л
Алгоритм а3 выделяет на предфрактальном графе покрытие, состоящее из / -смешанных циклов.
ТЕОРЕМА 2.5. Алгоритм а3 выделяет на взвешенном предфрактальном (n,q,L)-графе GL =(VL,EL) покрытие х3 ={VL,E ), оцениваемое по всем критериям: по первому Fx(х3) = п ~', по второму п{п -1) Л i_x м п(п -1) Л /_і л/_і, _ . ч . — 2Іп & a
2 i=L-i+\ 2 /=^-/+1 ш(и-1) v/ \ і ^ по четвертому Ь4{х3) < и пятому F5{х3) = п критериям, -ч
Алгоритм а4 выделяет на предфрактальном графе эйлеров подграф.
Теорема 2.6. Алгоритм а4 выделяет на взвешенном предфракталь ном (n,q,L)-графе GL = {VL,EL) покрытие х4 = {VL,E), оптимальное по первому критерию F{{x4), оцениваемое по второму ап{п-\) (иА)1-!^, ^Ъп{п-\) {пв)1 -1 _ , , . — -— < F2{х4) < — -— , третьему F3{x4) = L, чет-
2 пв-\ 2 пв-\ „ , . ^ Ln{n-\) _, , ч лт . вертому F4(х4) < и пятому F5(х4) = N критериям. *4
ТЕОРЕМА 2.7. Вычислительная сложность алгоритма а4> осуществляющего выделение на предфрактальном (n,q,L)-графе GL = {VL,EL),
I Ї О VL\ = N = п эйлеров подграф, равна 0(Nn ). М
Алгоритм а5, как и алгоритм а2, выделяет на предфрактальном графе эйлеров цикл. Но алгоритм а5, в отличии от алгоритма а2, осуществляет выделение эйлерова цикла только на тех предфрактальных графах, у которых сохраняется смежность старых ребер одного ранга.
Теорема 2.8. Алгоритм а5 выделяет на взвешенном предфракталь ном (n,g,L)-графе GL =(VL,EL) покрытие х5 =(VLiEx ), оптимальное по первому критерию Fl(x2), оцениваемое по второму ап{п-\) {пв)ь -1^р/ ^Ьп{п-\) (пв)1-\ ; W—T-F2(x2)^—; Б~Т"' тРетьемУ F3(X2) = L> чет~
2 пв-\ 2 пв-\ вертому F4 (х2 ) ^ и пятому F5 (х2) = N критериям. *4
ТЕОРЕМА 2.9. Вычислительная сложность алгоритма а5 осуществляющего выделение на предфрактальном (п,д,Ь)-графе GL =(VL,EL), VL\ = N = п эйлерова цикла, равна 0{Nn ). А
Алгоритм а6 выделяет на предфрактальном графе эйлеров подграф с заданным ограничением по времени t < Т. В качестве / может, например, использоваться число элементарных операций (выделение вершины, выделение ребра) в алгоритме. Алгоритм а6 позволяет выделять наименьший эйлеров подграф С = (VC,EC), Vc
ТЕОРЕМА 2.10. Алгоритм а6 выделяет наименьший эйлеров подграф С = (Гс,с), содержащий любые две заданные вершины u,veVL предфрактального (n,q,L)-графа GL =(VL,EL), Vc qVl, Ec qEl. A
Все предложенные алгоритмы являются эффективными, т.е. их вычислительная сложность оценивается полиномом от числа вершин исследуемого предфрактального графа.
Важно отметить, что алгоритмы а2 и а5, которые выделяют на пред-фрактальном графе эйлеров цикл, эффективнее аналогичного, широко известного алгоритма Флёри. Вычислительная сложность алгоритма Флёри равна 0{NA), где N - число вершин предфрактального (п, q, L) -графа GL, что в п раз больше вычислительной сложности алгоритмов а2 и сс5 ( теоремы 2.3. и 2.8.).
Третья глава посвящена алгоритмам порождения эйлеровых предфрак-тальных графов. В этой главе диссертационной работы рассматриваются так же некоторые характеристики неэйлеровых предфрактальных графов.
На практике нередко возникают задачи конструирования (проектирования) систем со сложной многоэлементной разветвленной структурой. Структура таких систем должна обладать заданными свойствами. В случае многокритериальной оптимизационной задачи проектирования, в качестве таких свойств, как правило, выступают оптимальные решения по одному или нескольким критериям ( форм. 2-7).
Алгоритм р{ гарантированно порождает эйлеров предфрактальный граф, смежность старых ребер которого сохраняется.
Теорема 3.1. Алгоритм Д порождает эйлеров предфрактальный граф GL = (VL,EL), затравка Н = (W,Q) которого также является эйлеровой. А
Следствие3.1. В траектории Gl,G2,...,GL предфрактального графа GL, порождаемого алгоритмом Д, все предфрактальные графы являются эйлеровыми. М
Алгоритм р2» как и алгоритм рх, гарантированно порождает эйлеров предфрактальный граф. Существенным отличием алгоритма (32 от алгоритма /?1 является то, что в результате работы алгоритма /?2 получается ориентированный эйлеров предфрактальный граф, порожденный ориентированной эйлеровой затравкой.
ТЕОРЕМА 3.2. Алгоритм /32 порождает ориентированный эйлеров предфракталъный граф GL =(VL,EL), затравка H = (W,Q) которого также является ориентированным эйлеровым графом. А
СЛЕДСТВИЕ3.2. В траектории Gi,G2,...iGL ориентированного пред-фрактального графа GL, порождаемого алгоритмом /32, все предфрак-тальные графы являются ориентированными эйлеровыми графами. А
На предфрактальных графах, полученных как результат работы алгоритмов Д и J32, можно гарантированно выделить покрытие используя алгоритмы а2 и а5, оптимальное по первому критерию ВЦФ задачи (2) - (7).
При решении модельной многокритериальной задачи (2)-(7) важно знать, во-первых, является ли предфрактальный граф, представляющий структуру моделируемой системы, эйлеровым, во-вторых, если же он неэй-леров, какова его мера "неэилеровости". В качестве такой меры в настоящей работе выступает число вершин нечетной степени.
Теорема 3.3. Число вершин нечетной степени предфрактального (n,q,L) -графа Gl~{^l^l)> порожденного эйлеровой затравкой Н = (W,Q), смежность старых ребер одного ранга которого не сохраняет- nL~2 (и-2) + 1 ся, не меньше 2q. Л
СЛЕДСТВИЕ3.3. Предфрактальный граф GL =(VL,EL), порожденный эйлеровой затравкой Н = (W,Q), смежность старых ребер одного ранга которого не сохраняется, не является эйлеровым. А
ТЕОРЕМА 3.4. Для предфрактального (n,q,L)-графа GL =(VLiEL), порожденного эйлеровой затравкой Н = (JV,Q), смежность старых ребер одного ранга которого не сохраняется, максимальная степень определяется неравенством maxdeg(GL) ТЕОРЕМА 3.5. Число вершин нечетной степени предфрактального (n,q,L) -графа GL=(VL,EL), порожденного неэйлеровой затравкой H = (JV,Q), смежность старых ребер которого сохраняется, не меньше Следствие 3.4. Предфракталъный граф GL = (VL, EL) порожденный неэйлеровой затравкой Н = (W,Q), смежность старых ребер которого сохраняется, не является эйлеровым. А Основные положения, выносимые на защиту Сложные развивающиеся структуры можно моделировать фрактальными (самоподобными) графами. Фрактальные графы имеют широкий круг приложений в физических и технических задачах. Многокритериальная задача Эйлера на предфрактальных графах. Эффективные (полиномиальные) алгоритмы поиска решений многокритериальной задачи Эйлера на предфрактальных графах. Для всех предложенных алгоритмов даны гарантированные оценки по критериям из многокритериальной задачи Эйлера, по которым оптимум не достигается. Для алгоритмов, осуществляющих поиск эйлерова цикла на предфрактальном графе, доказано их существенное превосходство по вычислительной сложности над стандартными методами. Переход от многокритериальной задачи Эйлера на предфрактальных графах к многокритериальной задаче конструирования (проектирования) многоэлементных структурно-сложных систем с заданными характеристиками. Высокоэффективные алгоритмы построения структурно-сложных систем с заданными характеристиками, соответствующим критериям многокритериальной задачи Эйлера. Необходимые и достаточные условия существования эйлерова цикла на предфрактальном графе. Введена мера "неэйлеровости" предфракталь- ного графа и получены оценки меры "неэйлеровости" для предфрактальных графов с различными условиями порождения. Апробация работы. Основные результаты работы докладывались на 2-й Международной конференции "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики" (Нальчик, 2001), на 5-м и 6-м Всероссийских симпозиумах "Математическое моделирование и компьютерные технологии" (Кисловодск, 2002, 2004), на Международном Российско-Узбекском симпозиуме "Уравнения смешанного типа и родственные проблемы анализа и информатики" (Нальчик, 2003), на 34-й научно-технической конференции профессорско-преподавательского состава, аспирантов и студентов Северо-Кавказского Государственного технического университета (Ставрополь, 2005), на 50-й научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников Таганрогского Государственного радиотехнического университета (Таганрог, 2004), на 8-й Региональной научно-технической конференции "Вузовская наука - Северо-Кавказскому региону" (Ставрополь, 2004), на 5-й научно-практической конференции "От фундаментальной науки - к решению прикладных задач современности" (Черкесск, 2005), на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской Государственной технологической академии (Черкесск, 2001-2005). Термином затравка условимся называть какой-либо связный граф Н = {JV,Q). Для определения фрактального (предфрактального) графа [1] нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе G = (V, Е) у намеченной для замещения вершины v eV выделяется множество V = {v.} с V, j = 1,2,..., V смежных ей вершин. Далее, из графа G удаляется вершина v и все инци V соединяется дентные ей ребра. Затем каждая вершина Vj-eV, j = 1,2,..., ребром с одной из вершин затравки Н = (JV,Q). Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости. Предфрактальный граф будем обозначать через GL =(VL,EL), где VL множество вершин графа, a EL - множество его ребер. Определим его ре куррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = 1,2,...,1,-1 графе G/= (У/, /) каждую его вершину затравкой Н = (W, Q). На этапе / = 1 предфрактальному графу соответствует затравка Gj =Н. Об описанном процессе говорят, что предфрактальный граф GL = (VL, EL) порожден затравкой Н = (W, Q). Процесс порождения предфрактального графа GL, по существу, есть процесс построения последовательности предфрактальных графов Gl,G2,...,Gi,...,GL, называемой траекторией. Фрактальный граф G = (V,E), порожденный затравкой Н = (W,Q), определяется бесконечной траекторией. Предфрактальный граф GL=(VL,EL) условимся называть (n,q,L) -графом, если он порожден и-вершинной #-реберной связной затравкой Н = (W, Q), и (n,L) -графом, если затравка Н = (W, Q) - регулярный граф. Использование операции ЗВЗ в процессе порождения предфрактального графа GL для элементов Gl ={Vl,El), /є{1,2,..., 1-1} и его траектории позволяет ввести отображение (р: Vj -» Vl+X или (p{Vl) = Vl+X, а в общем виде (Vi) = Vl+tt t = 1,2,...,1-/. (8) В выражении (8) множество Vl+t - образ множества Vt, а множество Vt - прообраз множества Vi+t. Для предфрактального графа GL, ребра, появившиеся на 1-м, /є{1,2,...,1} этапе порождения, будем называть ребрами ранга I. Новыми ребрами предфрактального графа GL назовем ребра ранга L, а все остальные ребра назовем - старыми. Если из предфрактального графа GL, порожденного «-вершинной затравкой Н, последовательно удалить все старые ребра (ребра ранга /, / = 1,2,..., L -1), то исходный граф распадется на множество связных компонент {В }, каждая из которых изоморфна [2] затравке Н. Множество компонент {В } будем называть блоками первого ранга. Аналогично, при удалении из предфрактального графа GL всех старых ребер рангов / = l,2,...,Z-2, получим множество блоков {В } второго ранга. Обобщая скажем, что при удалении из предфрактального графа GL всех ребер рангов / = l,2,...,L-r, получим множество {В[)}, г є {1,2,..., L -1}, блоком г-го ранга, где / = l,2,...,wL_r -порядковый номер блока. Блоки BjJ czGL первого ранга также будем называть подграф-затравками Н предфрактального графа GL .Очевидно, что всякий блок В і/ =(1/ \М ), Г Є {1,2,..., L-1}, является предфрактальным графом Br = (Ur, Мг ), порожденным затравкой Н. Два блока предфрактального графа назовем смежными, если существует ребро, вершины которого принадлежат различным блокам. Не требует доказательства тот факт, что блоки предфрактального графа смежны тогда и только тогда, когда смежны их прообразы (форм. 9). УТВЕРЖДЕНИЕ 1.1. Всякий предфрактальный граф GL можно представить в виде множества подграф-затравок {#[ }, соединенных старыми ребрами разных рангов. А именно, старые ребра (Z-l)-ro ранга объединяют множество подграф-затравок в множество блоков {B L } второго ранга, их в свою очередь, старые ребра (L - 2) -о ранга объединяют в множество блоков {В } третьего ранга и т.д. Окончательно, старые ребра первого ранга объединяют множество {/?[ } блоков (L-1)-о ранга в связный предфрактальный граф GL. -4 Пусть MnR = {G} - множество всевозможных предфрактальных графов G с «-вершинной затравкой, взвешенных числамиw(e) є {1,2,..., R}. Обозначим KRtn - класс задач F = {FX,F2,F3,FA,F5) покрытия циклами предфрактальных графов GeMnR. Пусть KRf =\J\jKR/J = (1,...,1) - ранг пред / п фрактального графа G/. Допустимое решение принято называть точкой в пространстве решений х. Для точек х еХ определено численное значение критерия Fk=F, т.е. можно говорить об определенных на X целевых функциях Fk(x),k = 1,5. Каждой точке х є X соотношения Fk = Fk(x),k = 1,5 ставят в соответствие некоторую точку в пространстве критериев F(X) = {F(x) = Fx (х), F2 (х), F2 (х), F4 (х), F5 (х)), хеХ}. Иными словами, эти соотношения определяют отображение F F(x) множества X в 2 мерное евклидово пространство. Множество F(x) носит название "множество достижимости (МД) или "множество предельных возможностей". Эффективными или оптимальными по Парето принято называть такие решения х є X, которые не улучшаемы по векторному критерию F = (Fl,...,Fm) в пределах множества всех допустимых решений многокритериальной задачи. По определению, эффективные решения, составляющие паретовское множество X, векторно несравнимы между собой в том смысле, что во всякой паре хх,х2 еХ нет доминируемого по F элемента. Эффективной или паретовской границей (П-границей) МД F(x) называем отображение паретовского множества в пространство критериев, т.е. подмножество точек F(x) = {F(x) = F,( ),...,Fm(x)),x є X}. В классической (1-критериальной) оптимизации задача считается решенной точно, если в X найдено хотя бы одно решение Л:0 , на котором значение критерия F = FX, достигает требуемого экстремума, например, минимума. При этом X может содержать сколь угодно мощное подмножество X оптимумов задачи F, однако вопрос о выделении из X всех представителей х є X не ставится. Аналогично, в многокритериальной оптимизации не ставится вопрос о выделении из X всего паретовского множества X. Говорят, что всякое полученное с помощью некоторого алгоритма а подмножество Ха с X является точным решением многокри териальной задачи, если F(Xa) = F(X), т.е. если образ выделенного ха совпадает с П-границей МД F(X). Нахождение точек П-границ F(X) относится к числу очень важных и в то же время очень трудных задач дискретной оптимизации. Трудоемкость выделения из X подмножестваХа, отвечающего определению точного решения задачиF = (F],F2,F3,F4,F5), по-видимому существенно превосходит трудоемкость решения так называемых переборных или универсальных задач, для которых известны лишь алгоритмы экспоненциальной трудоемкости. По указанной причине, одним из наиболее актуальных является вопрос о разработке такого приближенного алгоритма а, который для определенного класса исходных данных многокритериальной задачи гарантирует получение приемлемых приближенных решений Ха за счет существенного сокращения трудоемкости, Ха с X. При этом предполагается строгое математическое обоснование как границ выделенного класса исходных данных, так и оценок качества (точности) получаемых решений. Здесь речь идет об оценивании (в терминах пространства критериев F(X) точности аппроксимации паретовского множества X выделенным с помощью алгоритма подмножеством Ха cz X. Методология алгоритмов с оценками разрабатывалась применительно к классическим, т.е. однокритериальным задачам, которые являются частным случаем задач векторной оптимизации с множеством критериев F = {Fk},k 2. Отсюда, многие, казалось бы устоявшиеся определения и понятия в условиях многокритериальности "не работают", и, по этой причине нуждаются в построении новых, более общих моделей и формальных определений. При этом предполагаем, что всегда выполняется система строгих неравенств: ак О, где ак = minF x). Приведем некоторые замечания. Для каждого Fk GF выделим в X подмножество частных оптимумов Хк ={xk/Fk(xl) = mmFk(xk)} и рас смотрим пересечение X = f]Xk . Если оно непустое (X 0), то тогда по определению Х-Х и мощность множества точек П-границы F(X) = F(X)\. В этом случае решение задачи F = {Fx,F2,...,Fm)заключается в нахождении хотя бы одного элемента из множества X. Если X = 0, то F(X) 2 и, в случае выбора какой бы то ни было точки х0 є X в качестве окончательного решения задачи возникает противоречие или конфликтная ситуация: среди невыбранных точек найдется такая, которая по некоторому показателю качества Fk строго превосходит х0. Указанное противоречие порождает основную проблему многокритериальности, или в другой терминологии, проблему принятия решения. Рассмотрим взвешенный предфрактальный граф GL =(VL,EL), порожденный затравкой Н = (W, Q), \ = п, \Q\ = q, смежность старых ребер которого сохраняется. ТЕОРЕМА 2.4. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно 0. Доказательство этой теоремы можно найти в [38]. Смысл ее таков, что если в графе G все вершины четной степени, тогда можно выделить эйлеров цикл. ТЕОРЕМА2.5. Для того чтобы предфрактальный граф GL =(VL,EL), смежность старых ребер которого сохраняется, порожденный затравкой Н = (W,Q), содержал эйлеров цикл, достаточно существование эйлерова цикла на самой затравке. ДОКАЗАТЕЛЬСТВО. ДЛЯ ТОГО чтобы на предфрактальном графе существовал эйлеров цикл, необходимо и достаточно выполнение условия теоремы 3.4, то есть четности степеней всех его вершин. Рассмотрим процесс порождения предфрактального графа GL. Граф С?! представляет собой затравку Н = {W,Q), в которой все вершины имеют четную степень, по условию теоремы. На следующем шаге каждая вершина замещается затравкой Н = (W,Q), и получается граф G2. Смежность старых ребер сохраняется, это означает по сути, что затравка присоединяется к вершинам графа Gj одной из своих вершин. К общей вершине добавляются ребра затравки, а их четное число, тогда получаем, что к четному числу старых ребер добавляется четное число новых ребер. То есть, степень общих вершин графа G2 тоже четное число. Остальные "новые" вершины будут инцидентны только своим ребрам, то есть, степень вершин не изменится и останется четной. Получаем, что степень всех вершин графа G2 четное число. На следующем шаге заменяются все вершины G2 затравками H = (JV,Q) или по-другому, ко всем вершинам присоединяются затравки H = (W,Q) и получается граф G3. Также как и на предыдущем шаге, к общим вершинам прибавляется четное число ребер, поскольку вершины затравки имеют четные степени, а новые вершины остаются четными, так как к ним не присоединяются другие ребра. Таким образом, получаем, что степень всех вершин графа G3 также четное число. Продолжая процесс порождения предфрактального графа, на шаге L вершины графа GL_X замещаются затравками. Полученный предфрактальный граф GL также будет содержать в себе вершины только четной степени, в силу приведенных ранее рассуждений. Таким образом, если в предфрактальном графе GL=(VL,EL), смежность старых ребер сохраняется, а порождающая затравка содержит эйлеров цикл, тогда предфрактальный граф также содержит эйлеров цикл. Ч СЛЕДСТВИЕ 2.1. Предфрактальный граф GL =(VL,EL), порожденный множеством затравок Н = {#,} = \НХ,Н2,...,//,,...,НТ}, Т 2, смелсность старых ребер которого сохраняется, содержит эйлеров цикл, если эйлеровы циклы можно выделить на каждой его затравке Ht є Н, / = 1,2,...,71. -4 На рисунке 4 изображен эйлеров предфрактальный граф, порожденный множеством затравок Н = {Нх ,Н2,Н3], смежность старых ребер которого сохраняется. Предположим, что выполняется условие теоремы 3.4, и алгоритм а2 заведомо выделит эйлеров цикл на предфрактальном графе GL. Алгоритм а2 основан на алгоритме выделения эйлерова цикла, предложенном Флёри [21]. На вход алгоритма Флёри подается произвольный взвешенный граф, а на выходе получается эйлеров цикл. Далее алгоритм Флёри будет использоваться как процедура. Алгоритм а2 Опишем принцип работы алгоритма а2. Каждая подграф-затравка z;\ / = 1,/,, s = \, п рассматривается как отдельно взятый граф. Последовательно на каждой подграф-затравке z] вы деляются эйлеровы циклы Ст, т = \,.., . Поиск эйлерова цикла на от и-1 дельно взятой подграф-затравке осуществляется с помощью алгоритма Флёри, который используется в алгоритме а2 в качестве процедуры. Результатом работы алгоритма является эйлеров цикл предфрактального графа GL. АЛГОРИТМ а2 Вход: взвешенный предфрактальный граф GL =(VL,EL). Выход: эйлеров цикл С = (VL, Ес). ШАГ 1. Последовательно для каждой затравки z \ / = 1,/,, s = \,n -- л nL -\ _ .. найти эйлеров цикл Ст,т = 1,.., используя процедуру Флери. п-\ ШАГ 2. На выходе шага 1 получаем " эйлеровых циклов Ст для п-\ каждой затравки z) . Объединяя эйлеровы циклы Ст получим эйлеров цикл С = (VL,EC) предфрактального графа GL . ПРОЦЕДУРА ФЛЁРИ. ВХОД: взвешенный граф G = (V, Е). Выход: эйлеров цикл С = {V,EC). ТЕОРЕМА2.6. Алгоритм а2 выделяет эйлеров цикл С = (VL,ЕС) на предфракталъном графе GL=(VL,EL), порожденном затравкой H = (W,Q),\W\ = n,\Q\ = q. ДОКАЗАТЕЛЬСТВО. Алгоритм а2 на предфрактальном графе GL выделя ет множество эйлеровых циклов {Cf = (УР,Е (/))}, / = l,L, s = \,nl х. В качестве порождающей затравки выберем ориентированную связную затравку Н = (W, Q), Ж = п, \Q\ = q и предположим, что она содержит эйлеров цикл Нм =(W,QM). ТЕОРЕМА 3.6. Связный ориентированный граф G является эйлеровым тогда и только тогда, когда для каждой вершины число входящих дуг равно числу исходящих. Доказательство данной теоремы можно найти в [Фляйшнер]. Смысл ее таков, что если в орграфе G для каждой входящей в вершину дуги найдется исходящая, тогда можно выделить эйлеров цикл. Число дуг, входящих в вершину v, обозначается /deg(v) и называется полустепенью захода, а число дуг исходящих из вершины v: odeg(v) полустепеныо исхода. ТЕОРЕМА 3.7. Для того чтобы предфракталъный граф GL ={VL,EL), смежность старых ребер которого сохраняется, порожденный ориентированной затравкой Н = (W, Q), содержал эйлеров цикл, достаточно существование эйлерова цикла на самой затравке. ДОКАЗАТЕЛЬСТВО. ДЛЯ ТОГО, чтобы на предфрактальном орграфе GL существовал эйлеров цикл, необходимо и достаточно выполнение условия теоремы 3.6, то есть /deg(v) = odeg(v), для любой вершины veVL. Рассмотрим процесс порождения предфрактального орграфа GL. Граф Gl представляет собой ориентированную затравку Н = (W,Q), в которой для всех вершин VGGJ верно /deg(v) = odeg(v), по условию теоремы. На следующем шаге каждая вершина замещается затравкой H = (W,Q), и получается граф G2. Смежность старых ребер сохраняется, это означает по сути, что затравка присоединяется к вершинам графа Gx одной из своих вершин. Поскольку у каждой вершины затравки H = (W,Q) полустепень захода равняется полустепени исхода, к общей вершине Gj добавляется равное число как входящих, так и исходящих дуг. А на самом графе Gl все вершины также имеют равные полустепени захода и исхода. Тогда получается, что при добавлении равного числа входящих и исходящих дуг, полустепени захода и исхода равны для каждой общей вершины. "Новые" вершины затравок будут инцидентны только своим ребрам, то есть их полустепени вершин не изменятся. Получаем, что полустепень захода равняется полустепени исхода /deg(v) = odeg(v) для каждой вершины v графа G2, то есть G2 - эйлеров предфрактальный орграф. На следующем шаге заменяются все вершины G2 затравками H = (W,Q) или по-другому, ко всем вершинам присоединяются затравки H = (JV,Q) и получается граф G2. Также как и на предыдущем шаге, к общим вершинам прибавляется равное число входящих и исходящих дуг, поскольку для вершин w затравки Н = (W,Q) верно /deg(w) = odeg(w). А новые вершины сохраняют свои полустепени, так как к ним не присоединяются другие дуги. Таким образом, полустепень захода равняется полустепени исхода /deg(v) = odeg(v) для каждой вершины v графа G3, то есть G3 - эйлеров предфрактальный орграф. Продолжая процесс порождения предфрактального графа, на шаге L вершины графа GLA замещаются затравками. Полученный предфрактальный граф GL также будет содержать в себе вершины с равными полустепенями /deg(v) = odeg(v) ,veVLB силу приведенных ранее рассуждений. Таким образом, если в предфрактальном графе GL=(VL,EL) смежность старых ребер сохраняется, а порождающая затравка является эйлеровым орграфом, предфрактальный орграф также является эйлеровым или по-другому содержит в себе ориентированный эйлеров цикл. Ч СЛЕДСТВИЕ 3.5. Предфрактальный орграф GL=(VL,EL), порожденный множеством затравок Н = {#,} = [Нх, Н2,.-, Ht,..., НТ}, Т 2, смежность старых ребер которого сохраняется, является эйлеровым, если каждая его затравка Ht єН, t = 1,2,...,Т является эйлеровым орграфом. -4 Алгоритм /?2 Опишем принцип работы алгоритма /?2 порождения предфрактального эйлерова орграфа GL = (VL,EL). Процесс порождения предфрактального орграфа GL, есть процесс построения последовательности предфрактальных графов Gl,G2,...,G[,...,GL, называемой траекторией. Граф Gl в траектории представляет собой затравку H = (W,Q). Для построения следующих в траектории графов воспользуемся операцией замены вершины затравкой (ЗВЗ). Для построения графа G2 каждую вершину G1 заместим затравкой Н = (W, Q) таким образом, чтобы смежность старых ребер не нарушалась, что будет представлять собой простое присоединение затравки к каждой из вершин графа Gx. Далее, для получения графа G3 также заменим каждую вершину G2 затравкой, не нарушая при этом смежности старых ребер. Основным правилом для построения графов G3,G4,...,GL будет сохранение смежности старых ребер. На последнем шаге заменяем каждую вершину графа GLA затравкой H = (W,Q) и получаем предфрактальный граф GL={VL,EL).Фрактальные и предфрактальные графы
Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами
Алгоритм аг выделения эйлерова цикла на предфрактальном графе, смежность старых ребер которого сохраняется
Алгоритм Д порождения ориентированного эйлерова предфрактального графа
Похожие диссертации на Многокритериальная задача Эйлера на предфрактальных графах
