Содержание к диссертации
Введение
Глава 1. Многокритериальная задача раскраски предфрактального графа 15
1.1 Задача раскраски графов 15
1.2 Фрактальные и предфрактальные графы 24
1.3 Многокритериальная задача раскраски предфрактального графа ...32
1.4 Выводы 33
Глава 2. Особенности раскраски фрактальных и предфрактальных графов: ; свойства и характеристики 34
2.1 Бихроматические предфрактальные графы 34
2.2. Хроматическое число предфрактального графа, порожденного с сохранением смежности старых ребер 37
2.3. Об однозначнойраскраске предфрактальных графов 40
2.4. О критических подграфах предфрактального графа 44
2.5. О раскраске фрактальных графов 48
2.6. Раскраска плоских и планарных фрактальных (предфрактальных) графов 51
2.6. Выводы 55
Глава 3. Алгоритмы вершинной раскраски предфрактальных графов 57
3.1. Алгоритмы раскраски простых графов 57
3.2 Алгоритм Д раскраски предфрактального графа, смежность старых s ребер которого сохраняется, а затравка - полный граф 62
3.3 Алгоритм J32 раскраски предфрактального графа, смежность старых ребер которого сохраняется 67
3.4 Алгоритм /?з раскраски предфрактального графа, порожденного множеством затравок, смежность старых ребер которого сохраняется 72
3.5 Алгоритм ух раскраски предфрактального графа, старые ребра которого не пересекаются, а затравка - полный граф 78
3.6 Алгоритм у2 раскраски предфрактального графа, старые ребра которого не пересекаются 85
3.7 Алгоритм у3 раскраски предфрактального графа, порожденного множеством затравок, старые ребра которого не пересекаются 91
3.8 Сетевая модель оптимального монтажно-коммутационного пространства и раскраска её вершин 97
3.9 Выводы 111
Заключение 112
Литерапура
- Фрактальные и предфрактальные графы
- Многокритериальная задача раскраски предфрактального графа
- Хроматическое число предфрактального графа, порожденного с сохранением смежности старых ребер
- Алгоритм J32 раскраски предфрактального графа, смежность старых ребер которого сохраняется
Введение к работе
Моделирование [109, ПО, 130-132, 143, 158, 166] как способ познания окружающего мира, в современной науке существует недавно. Моделирование представляет собой объединение математических дисциплин (теория графов, исследование операций, математическое программирование, уравнения математической-физики и т.д.), на базе которых осуществляется решение целого ряда задач природы и общества. Естественно, формулировки задач являются отражением реальных процессов и явлений, которые приносят пользу или несут угрожающий характер для деятельности человека. Моделирование сложных процессов и структур вынуждает ученых объединять старые и создавать новые математические аппараты и инструменты.
Начало 70-х годов прошлого века было ознаменовано появлением новой научной парадигмы, называемой синергетикой [12, 23, 45, 50, 115, 122, 172-174] (от греч. synergeia - совместное действие, сотрудничество). Синергетика, основы, которой были заложены,Германом Хакеном и лауреатом Нобелевской премии Иваном Пригожиным, определяется как наука о коллективных статистических и динамических явлениях в закрытых и открытых многокомпонентных системах с «кооперативным» взаимодействием элементов систем. В физике, химии и биологии синергетика занимается структурными особенностями пространственно-временной самоорганизации [12, 23, 45, 50, 115, 122, 172-174] систем. Самоорганизация возникает в системах большой размерности и по сути представляет собой совместное существование взаиморегулируемых и взаимозависимых подсистем. Оказывается, в этом понимании между различными системами существует тесная связь, даже если они состоят из разнородных элементов с существенно отличными элементарными взаимодействиями.
Необходимость исследования открытых, нелинейных, далеких от равновесия систем во многих областях физики, техники, химии, экономики, экологии привела к развитию междисциплинарных подходов. Одним из наиболее успешных междисциплинарных подходов и является синергетика. В ос-
нове современной синергетики лежат три парадигмы, появившиеся друг за другом: парадигма диссипативных структур, парадигма динамического хаоса и парадигма сложности.
Во многих гидродинамических системах ключевое значение имеет наличие в них диссипативных процессов (вязкости, диффузии, теплопроводности). Они позволяют исследуемым системам "забыть" начальные данные и независимо от их "деталей" сформировать с течением времени одни и те же или похожие пространственно-временные структуры. Иными словами, немного (а иногда и сильно) изменив начальный профиль (начальные данные в соответствующей задаче математической физики), в конце концов мы получаем одно и то же стационарное распределение переменных в пространстве. Чтобы подчеркнуть это обстоятельство, такие структуры, с легкой руки И.Р. Пригожина, стали называть диссипативными структурами [23]. В основе большинства исследований научной школы И.Р. Пригожина лежали системы параболических уравнений типа реакция-диффузия
ut=I\uxx+f{u,v\
Vt=D2vxx+S{u,v\
0<хи(х,0) = ио(х), v(x,0) = v0(x), ux,vx x=0j/=0.
Если говорить о парадигме диссипативных структур как о подходе к анализу спонтанного возникновения упорядоченности в нелинейных средах, т.е. о самоорганизации, то следует сказать и о научной школе член-корреспондента РАН СП. Курдюмова. Научная школа СП. Курдюмова сформировалась в Институте прикладной математики им. М.В. Келдыша РАН, в МГУ им. М.В. Ломоносова, в Московском физико-техническом институте в 80-е годы прошлого столетия. Усилия участников этой научной школы были вложены в построение качественной теории нелинейного уравнения теплопроводности с объемным источником, так называемой модели тепловых структур [50]
7} = d\v(k(T) grad Т) + Q(T).
Качественная теория, отражающая в основном эффекты, понятые с помощью компьютерного моделирования, потребовала новых математических идей, существенно опирающихся на то, что мы имеем дело с одной переменной Г, а не с их набором. В отличие от стационарных диссипативных структур, которые изучались в брюссельской школе под руководством И.Р. Пригожина, в научной школе СП. Курдюмова исследовались нестационарные диссипативные структуры, развивающиеся в режиме с обострением. Под режимом с обострением понимают такие законы изменения параметров исследуемой системы, когда одна или несколько описывающих ее величин неограниченно возрастает за ограниченное время. В научной школе СП. Курдюмова было открыто явление локализации тепла, обнаружены и исследованы так называемые собственные функции нелинейной среды, описывающие, как правило, волны горения, сохраняющие в процессе эволюции свою форму. Они описываются автомодельными решениями исходного нелинейного уравнения теплопроводности, которое имеет вид Т = g(t)f(x I (p{f)), где функция g(t) задает закон роста амплитуды возникающей диссипативной структуры, cp{t) - закон изменения ее полуширины, а функция / - её форму [50].
В 1963 году американский метеоролог Эдвард Лоренц предложил простейшую модель, описывающую конвекцию воздуха (она играет важную роль в динамике атмосферы). Целью этой работы был ответ на вопрос: почему стремительное совершенствование компьютеров, математических моделей и вычислительных алгоритмов не привело к созданию методики получения достоверных среднесрочных (на 2-3 недели вперед) прогнозов погоды.
Эта модель описывается внешне очень простыми уравнениями [14]
х = —а{х + у) < у = — xz + гх - у, і = ху — bz
где переменная х характеризует поле скоростей, у и z — поля температур жидкости. Здесь г = R/Rc, где R — число Рэлея, a Rc — его критическое значение; а — число Прандтля; Ъ — постоянная, связанная с геометрией задачи. Компьютерный анализ системы Лоренца привел к принципиальному результату. Им был открыт динамический хаос, т.е. непериодическое движение в детерминированных системах (то есть в таких, где будущее однозначно определяется прошлым), имеющее конечный горизонт прогноза.
Рисунок 1 - Аттрактор Лоренца
Картина, полученная на компьютере (расчет проводился при г=28, сг=10, 6=8/3), убедила Э. Лоренца, что он открыл новое явление - динамический хаос. Этот клубок траекторий, называемый сейчас аттрактором Лоренца, описывает непериодическое движение с конечным горизонтом прогноза.
С точки зрения математики, можно считать, что любая динамическая система, что бы она ни моделировала, описывает движение точки в фазовом пространстве. Важнейшая характеристика этого пространства - его размерность, или, попросту говоря, количество ортогональных осей, которое необходимо задать для определения состояния системы. Если считать, что точка, двигаясь в фазовом пространстве, оставляет за собой след, то динамическому хаосу будет соответствовать клубок траекторий. Например, такой, как показан на рис. 1. Здесь размерность фазового пространства всего 3 (это пространство х, у, z). Замечательно, что такие удивительные объекты существу-
ют даже в трехмерном пространстве. Для установившихся колебаний, соответствующих динамическому хаосу, Д. Рюэль и Ф. Такенс в 1971 году предложили название - странный аттрактор.
Пророчество Анри Пуанкаре о том, что в будущем можно будет предсказывать новые физические явления, исходя из общей математической структуры описывающих эти явления уравнений, компьютерные эксперименты превратили в реальность.
Система Лоренца имеет конечный горизонт прогноза. Почему? Можно пояснить это следующим образом. Если мы вновь возьмем две близкие траектории, показанные на рис. 1, то они расходятся. Одна уходит от второй. Скорость расходимости определяется так называемым ляпуновским показателем, и от этой величины зависит интервал времени, на который может быть дан прогноз. Можно сказать, что для каждой системы есть свой горизонт прогноза.
В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и/или нетривиальных связей между ними. А с другой - речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны.
Хотя строгого и общего определения сложности не существует, опыт развития синергетики и изучения конкретных систем, интуитивно определяемых нами как сложные, позволяет высказать некоторые общие соображения о свойствах любой сложной системы на разных уровнях описания.
Системы с простой структурой, к примеру - иерархической, могут демонстрировать очень сложное нетривиальное поведение [123].
/+2 /+1 і
Рисунок 2 - Фрагмент иерархической системы
Каждый элемент /-го уровня состоит из трех элементов (/-1)-ого уровня. Элементы системы могут быть исправны или дефектны (показаны заливкой). Состояние каждого элемента определяется состоянием образующих его элементов предыдущего уровня, а также его собственной восприимчивостью к дефектам.
Многие системы обладают простой иерархической структурой, фрагмент которой изображен на рис. 2. Например, литосферу Земли можно представить как систему блоков, разделенных разломами. Каждый из этих блоков делится на более мелкие, те, в свою очередь, на еще более мелкие и т.д. Геофизики выделяют более 30 иерархических уровней в земной коре от тектонических плит протяженностью-в тысячи километров до зерен горных пород миллиметрового размера. Большие землетрясения обычно сопровождаются многочисленными повторными толчками — афтершоками, которые каскадом перераспределяют напряжение вниз по иерархии разломов. А подготовка землетрясения происходит посредством обратного каскада передачи напряжения, восходящего с нижних уровней иерархии к верхним.
Напрашивающимся примером иерархической системы, связанной с деятельностью человека, служит система административного или военного руководства. Успех в решении задач на некотором уровне управления определяется эффективностью функционирования нижележащих уровней.
Иерархической системой является и электорат. Он также делится на несколько групп со своими интересами. Каждая из них складывается из более мелких подгрупп и т.д. — вплоть до отдельного избирателя.
Мы можем наблюдать поведение иерархических систем только на верхних уровнях иерархии (землетрясения, исполнение распоряжений, результаты голосования). Однако причины событий лежат на нижних уровнях, и важно представлять, как происходит взаимодействие уровней.
Но, как говорилось ранее, сложное поведение системы может наблюдаться и при простых процессах, протекающих в ней. В такой ситуации сложность в системе обосновывается сложностью структуры системы. Именно такой сложности и посвящена настоящая диссертационная работа.
Термин "фрактал" (лат. fractus дроблёный) был введен в обращение французским математиком Бенуа Мандельбротом в 1975 году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, ценность подобных идей в науке была осознана лишь в 70-е годы прошлого столетия. Важную роль в широком распространении идей фрактальной геометрии сыграла книга Б. Мандельброта "Фрактальная геометрия природы" [124]. Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной (под размерностью понимается размерность Хаусдорфа-Безиковича, введенная в 1919 году Ф. Хаусдорфом и развитая впоследствии А.С. Безиковичем) [6, 15, 124, 127, 167, 169, 171, 178]. Основой новой геометрии является идея самоподобия [6, 15, 124, 127, 167, 169, 171, 178]. Она выражает тот факт, что иерархический принцип организации фрактальных структур не претерпевает значительных изменений при рассмотрении их с различным увеличением. В результате эти структуры на малых масштабах выглядят в среднем так же, как и на больших. Здесь следует провести разницу между геометрией Евклида, имеющей дело исключительно с гладкими кривыми, и бесконечно изрезанными самоподобными фрактальными кривыми. Элементы кривых у Евклида всегда самоподобны, но тривиальным образом: все кривые являются локально прямыми, а прямая всегда са-моподобна. Фрактальная же кривая в идеале, на любых, даже самых малень-
ких масштабах, не сводится к прямой и является в общем случае геометрически нерегулярной, хаотичной [6, 15, 124, 127, 167, 169, 171, 178].
Re [с]
Рисунок 3 - Множество Мандельброта
п=1
п=2
\
п=4
Фракталами являются, например, странные аттракторы (рис. 1), которые лежат в основе исследования динамических систем с хаотическим поведением. Вообще говоря, существует классификация фрактальных объектов [124]. Среди них можно выделить множество Мандельброта, изображенное на рис. 3, и кривую Коха - на
j-^Ч рис. 4. Первое обычно относят к алгеб-
раическим фракталам, второе — к гео-
Рисунок 4 - Кривая Коха метрическим.
Работы, связанные с исследование фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но не имеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги [178]. В настоящее время о перспективности и значимости исследований, связанных с фрактальными множествами, можно судить по
регулярно проводимым конференциям и периодическим изданиям, целиком посвященным соответствующей тематике. Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрактальных множеств [6, 15, 124, 127, 167, 169, 171, 178]. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабно-инвариантные) графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачивае-мости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких, как коммуникационные сети.
На протяжении более чем ста лет с момента появления первой публикации Эйлера, заложившей начала теории графов, оптимизационные теоретико-графовые задачи [2, 5, 7, 11, 14, 24, 29, 47, 106, 111, 114, 118, 126, 128, 135, 149-154, 159, 161, 163, 164, 168, 170, 175, 176] не рассматривались в многокритериальном аспекте [4, 13, 18, 20-22, 25, 42-44, 49, 84, 112, 116, 117, 134, 142-148, 162, 165, 177, 179]. В 80-х годах в школе профессора Емеличе-ва В.А. в Белорусском государственном университете были заложены основы многокритериальной оптимизации на графах [16, 17, 26-28, 30-41, 46, 96, 97, 102, 108, 138-141, 157, 160], что позволило решить ряд сложных практических задач. Интересные исследования по проблемам многокритериальной оптимизации на графах велись в Вычислительном Центре АН СССР [119-121, 125, 133] и Московском Государственном Университете М.И. Ломоносова [1]. Графы в этих задачах являлись моделями систем с фиксированной структурой. Но перед современной наукой стоят новые задачи, которые требуют совершенно новых методов и подходов для моделирования сложных систем. К таким системам относятся современные коммуникационные и информационные сети, структура которых претерпевает определенные изменения. Вместе с тем, не исчезает необходимость решения
классических теоретико-графовых и оптимизационных задач в системах с изменяющейся структурой связей между ее элементами.
Процесс изменения связей между элементами системы, изменения количества ее элементов и другие структурные преобразования в системе являются областью интересов структурной динамики [93, 94]. В общем случае можно говорить о различных изменениях структуры системы — о различных сценариях структурной динамики. Особо стоит выделить рост структуры, т.е. появление новых элементов и связей в системе. Такой сценарий присущ многим сетям связи, среди них — информационные, электроэнергетические, WWW (Internet), коммуникационные системы и т.д. В случае, когда структура системы "растет" одинаково и одновременно во всех доступных направлениях, принято говорить, что система имеет фрактальный рост. Фрактальный рост структуры системы моделируется фрактальным графом. Существенное распространение идеи структурной динамики и фрактального роста получилось благодаря»исследованиям [9, 85-92, 95, 98, 99-105, 156], проведенным в школе профессора Кочкарова A.M. При этом своего решения в системах с изменяющейся структурой потребовало значительное количество практических оптимизационных задач с многими критериями. Некоторые из них, такие как многокритериальная задача покрытия предфрактального графа простыми цепями, многокритериальная задача покрытия предфрактального графа звездами ранговых типов, многокритериальная задача о назначениях на предфрактальных графах, многокритериальная задача Эйлера на предфрак-тальных графах, удалось успешно решить [3, 8-10, 48, 68-83, 107, 136, 137, 155]. Одной из таких задач посвящена и настоящая диссертационная работа.
Целью диссертационной работы является исследование свойств и моделей сложных систем с многоэлементной изменяющейся структурой и решение многокритериальной задачи о раскраске на предфрактальных графах.
В соответствии с поставленной целью в диссертационном исследовании решались следующие задачи:
сформулировать многокритериальную задачу о раскраске на предфрак-тальных графах;
обосновать практическую интерпретацию предложенных критериев;
предложить алгоритмы, которые за полиномиальное время выделяют на предфрактальном графе оптимальное решение по различным критериям сформулированной задачи;
в случае, если предложенные алгоритмы выделяют неоптимальные решения, должны быть приведены оценки, гарантирующие отличие от оптимального решения на определенную величину;
исследовать изменения теоретико-графовых характеристик, связанных с раскраской при структурном росте, т.е. определить зависимость этих характеристик пред фрактальных графов от различных уровней их роста.
На защиту выносятся следующие положения, результаты и выводы:
установлена связь между хроматическим число фрактального (пред-фрактального) графа и хроматическим числом его затравки / затравок.
обоснована невозможность построения однозначно раскрашиваемого предфрактального графа.
показано, что фрактальный или предфрактальный граф, порожденный плоской 4-хроматической затравкой с сохранением смежности старых ребер, является планарным 4-хроматическим графом.
Фрактальные и предфрактальные графы
Определим термины и особенности фрактального графа. Термином затравка условимся называть какой-либо связный граф Н = {W, О). Для определения фрактального (предфрактального) графа [98] нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе G = (V, Е) у намеченной для замещения верши смежных ей ны v eV выделяется множество V = {Vj } с V, j = 1,2,..., вершин. Далее из графа G удаляется вершина v и все инцидентные ей ребра. Затем каждая,вершина v- eV, j = 1,2,..., V соединяется ребром с одной из вершин затравки Н = (W, Q). Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости.
Предфрактальный граф будем обозначать через GL ={VL,EL), где VL множество вершин графа, a EL - множество его ребер. Определим его ре куррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе 1 = 1,2,...,L \ графе G/ =() , /) каждую его вершину затравкой
Н = (W, Q). На этапе / = 1 предфрактальному графу соответствует затравка G] = Н. Об описанном процессе говорят, что предфрактальный граф GL ={VL,EL) порожден затравкой Н = {W,Q). Процесс порождения предфрактального графа GL, по существу, есть процесс построения последовательности предфрактальных графов Gl,G2,...,Gl,...,GL, называемый траекторией. Фрактальный граф G = (V,E), порожденный затравкой Н -{W,Q), определяется бесконечной траекторией.
Предфрактальный граф GL=(VL,EL) условимся называть (n,q,L) графом, если он порожден «-вершинной q-реберной связной затравкой Н = {W, Q), и (п, L) -графом, если затравка Н = {W, О) — регулярный граф. Использование операции ЗВЗ в процессе порождения предфрактального графа GL, для элементов G/ = (V[,E{), /є{1,2,...,L-1}, его траектории позволяет ввести отображение (p:V{ —» F/+1 или (piVj) = V!+i, а в общем виде ? ( /) = Г/+„ t = l,2,...,L-l. (1.10) В выражении (1.10) множество Vl+t - образ множества V{, а множество Vl — прообраз множества V!+t.
Для предфрактального графа GL ребра, появившиеся на /-ом, /є{1,2,...,L}, этапе порождения, будем называть ребрами ранга /. Новыми ребрами предфрактального графа GL назовем ребра ранга L, а все остальные ребра назовем - старыми.
Рассмотрим блоки предфрактального графа. Если из предфрактального графа GL, порожденного п-вершинной затравкой Н, последовательно удалить все старые ребра (ребра ранга /, / = 1,2,..., L -1), то исходный граф распадется на множество связных компонент {Ві/}, каждая из которых изоморфна [29] затравке Н. Множество компонент {В } будем называть бло ками первого ранга. Аналогично, при удалении из предфрактального графа GL всех старых ребер рангов / = 1,2,...,/,-2, получим множество блоков {/?" } второго ранга. Обобщая, скажем, что при удалении из предфрактального графа GL всех ребер рангов / = 1,2,...,L-r, получим множество {В {}, г є {1,2,...,/,- 1}, блоком г-го ранга, где / = 1,2,..., и г - порядковый номер блока. Блоки BjJ с GL первого ранга также будем называть подграф-затравками Н предфрактального графа GL .Очевидно, что всякий блок # = (U[ , М\/ ), г є {1,2,..., L -1} является предфрактальным графом Br = (Ur, Мг), порожденным затравкой Н.
Уточним для отображения (р в (1.10) ряд подробностей. Для любой вершины VEF/, j є {1,2,..., п } предфрактального графа G/ = (F/,/), І є {1,2,..., Z - 1}, из траектории графа GL, справедливо v (yj) = v?J,j. О-») ? (v,) = Bflj, где ,. = (t/«»j,Аґ« ,.)сй,да (= 1,2,..., -/. Аналогично, ) = , (1.12) р (В$) = в\$, г є{1,2 L- t),ie{1,2,...,и " }.
Два блока предфрактального графа назовем смежными, если существует ребро, вершины которого принадлежат различным блокам. Не требует доказательства тот факт, что блоки предфрактального графа смежны тогда и только тогда, когда смежны их прообразы из (1.11).
Утверждение 1.1 Всякий предфрактальный граф GL можно представить в виде множества подграф-затравок {В\/}, соединенных старыми ребрами разных рангов. А именно, старые ребра (Z,-l)-ro ранга объединяют множество подграф-затравок в множество блоков {Вк } второго ранга, их, в свою очередь, старые ребра (L - 2) -го ранга объединяют в множество блоков {В )} третьего ранга и т.д. Окончательно старые ребра первого ранга объединяют множество {/?[ } блоков (L -1) -го ранга в связный предфракталь-ный граф GL.
Многокритериальная задача раскраски предфрактального графа
Вершинная А:-раскраска графа - это присвоение его вершинам к различных цветов. Вершинная раскраска правильная, если никакие две смежные вершины в ней не получают одного цвета. Граф называется вершинно к-раскрашиваемым, если он имеет правильную вершинную к -раскраску.
Хроматическим числом (G) графа G называется минимальное число к, для которого G вершинно А:-раскрашиваемый. Граф G называется к-хроматическим, если %{G) = к.
Теорема 2.1 (теорема Кёнига) Граф G является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Теорема 2.2 Предфрактальный граф GL ={VL,EL), порожденный затравкой Н = (W, О), не G содержащей простых циклов нечетной длины, явля ется 2-хроматическим, если смежность его старых ребер одного ранга в процессе порождения не наруша ем ется. У (У J Доказательство. 1) Рассмотрим два произвольных I I графа G = {V ,E ) и G" = (V\E"), не содержащих Q простых циклов нечетной длины. Выбрав две верши _ , _ ны - v Є V и v" є V", проведем операцию склеивания
В результате получим граф G = (V,E [j Е"), склеенный из графов G и G" слиянием вершин v и v" в некоторую вершину v єУ. На рис. 2.1 изображено склеивание двух 4-вершинных циклов ( G и G" ).
Цикл С є G, содержащий две произвольные вершины v( є V и v2 є V, отличные от v є V, не является простым, поскольку содержит вершину V дважды. Т.е. цикл С Е G, содержащий две BepniHHbiVj и v2, принадлежащие различным подграфам G и G" графа G и отличные от вершины v, непременно является сложным. Поэтому все простые циклы графа G принадлежат целиком либо его подграфу G , либо подграфу G". А это значит, что все простые циклы графа G имеют четную длину, т.е. любой граф, полученный склеиванием графов, не имеющих циклов нечетной длины, также не имеет циклов нечетной длины (см. рис. 2.1).
2) Предфрактальный граф GL-(VL,EL), порожденный затравкой Н = (W, Q) с обязательным сохранением смежности старых ребер только одного ранга, можно получить склеиванием его подграф-затравок Z(GL) = {z P = #}, / = \JJ, s = l,wM (параграф 1.2 настоящей работы). Если же затравка Н = (W, Q) не содержит циклов нечетной длины, то согласно первой части доказательства, предфрактальный граф GL также не содержит циклов нечетной длины. А это в соответствии с теоремой 2.1 позволяет заключить, что предфрактальный граф GL является 2-хроматическим.
Предфрактальный граф GL={VL,EL), порожденный затравкой Н = (IV, Q), не содержащей простых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер в процессе порождения не нарушается.
Предфрактальный граф GL=(VL,EL), порожденный множеством затравок Н = {н,}={Нх,Н2,...,Н„...,Нт}, Т 2, не содержащих простых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер одного ранга в процессе порождения не нарушается.
Предфрактальный граф GL = (VL ,EL), порожденный множеством затравок Н = {#,} = {#,, Я2,..., Я,,..., Н,}, Т 2, не содержащих про стых циклов нечетной длины, является 2-хроматическим, если смежность его старых ребер в процессе порождения не нарушается.
На рис. 1.3 и 1.4 показаны предфрактальные графы, порожденные 2-хроматической затравкой-циклом длины 4 с сохранением смежности всех старых ребер и старых ребер только одного ранга соответственно. Сами предфрактальные графы, изображенные на этих рисунках, согласно сформулированным следствиям, также являются 2-хроматическими.
Очевидно, что всякий двудольный граф Н = (W ,W,Q) является 2 хроматическим. И, действительно, если все вершины W окрасить в один цвет, а вершины W" - в другой цвет, то граф Н будет правильно 2-раскрашенным. Примеры двудольных графов
Напомним, что цепь и звезда являются частными случаями двудольного графа. На рис. 2.2 представлены примеры таких графов: а) цепь, б) звезда. Причем звезда - пример полного двудольного графа, у которого одна из "долей" состоит из одной вершины.
Напомним также еще два важных факта. Во-первых, пред фрактальный граф, порожденный затракой-деревом (затравкой-цепью, затравкой-звездой), является деревом [98]. Во-вторых, любое неодноэлементное дерево является 2-хроматическим [5]. Следствие 2.2.4 Предфрактальный граф GL = (VL ,EL), порожденный затравкой Н = (W, Q) - деревом (звездой или цепью), является 2-хроматическим.
Хроматическое число предфрактального графа, порожденного с сохранением смежности старых ребер
Пусть G = (V,E) — помеченный граф. Каждая его (G)-раскраска порождает разбиение множества его вершин на z(G) одноцветных классов. Если %(G) = к и каждая к -раскраска графа G порождает одно и то же разбиение V ,то G называется однозначно к -раскрашиваемым, или просто однозначно раскрашиваемым [49]. Граф, представленный на рис. 2.3, однозначно раскрашиваемый. Но пятиугольник, например, не однозначно 3-раскрашиваем: возможно пять различных разбиений его вершин.
Лемма 2.1 Всякий 2-хроматический граф однозначно раскрашиваем. Доказательство. Всякий 2-хроматический граф является двудольным ], т.е. множество его вершин однозначно делится на множества, в которых вершины попарно несмежны. Лемма 2.2 Всякий предфрактальный 2-хроматический граф GL =(VL,EL) является однозначно раскрашиваемым. Лемма 2.3 Граф G = (V,E), полученный склеиванием однозначно раскрашиваемых графов G = {V\E ) и G" = {F",E"), таких, что (G") 2 и %(G") 2, является неоднозначно раскрашиваемым.
Доказательство. Графы G = (У , ) и G" = {V",E") в силу их одно значной окрашиваемости имеют однозначные разбиения множеств вершин на одноцветные классы - V = {{,{,...,!,...,V X(Q } И V" = {V{\V2,---,V[-,---,V rG } - соответственно. Произведем склейку графов G и G" в вершинах veK , и 캥 . Множество вершин графа G = (V,E) можно разбить на непересекающиеся подмножества Г є{Г, ..,К/,...,К КРме того и вершины каждого их этих подмножеств попарно не пересекаются, поскольку до склеивания графов являлись одноцветными классами вершин. Особое внимание стоит уделить смежности между вершинами этих подмножеств. Подмножества V{,V2,...,V; ,...,VLG ) eG, являвшиеся одноцветными классами однозначно раскрашиваемого графа G , непременно имеют смежные вершины, причем они имеются у любых двух подмножеств. Такая же ситуация и с подмножествами { ,У2,...,У",...,У"(0») є G. Таким образом, подмножества
У{,У2\...,Уі\...,У 0 уі,У{,,У2,---,Уі ,---,У (с )-і є& имеют хотя бы по одной смежной вершине с вершинами подмножества У1т ) U Vy(G") Но ни одно из подмножеств К, , 2,..., /,..., ).., є G не имеет смежных вершин ни с одним из подмножеств У{ ,У2,...,У{ ,...,Ух(с")-і е&- Это позволяет объединить любое из подмножеств У{,У2,...,У1,...,У Х(с )-\ G не более чем с одним из подмножеств V{,V2H,...,y",...,Vz(G")_\ = G, не нарушая попарной несмежности вершин объединенных подмножеств, т.е. получая одноцветные классы. В силу того, что объединение происходит произвольным образом, возможно получение различных одноцветных классов. А это говорит о том, что граф G = (V,E) не является однозначно раскрашиваемым.
В случае, когда %(G ) = 2 и %(G") = 2, граф G будет бихроматическим (параграф 2.1 и [5]), а значит, и однозначно раскрашиваемым (лемма 2.1).
Лемма 2.4 Граф G = (V,E), полученный склеиванием неоднозначно раскрашиваемых графов G = (У ,Е ) и G" = {V",E"), таких, что j(G ) 2 и Z(G") 2, является неоднозначно раскрашиваемым.
Доказательство. Графы G = (V,E ) и G" = (У",Е") в силу их неоднозначной окрашиваемости имеют различные разбиения множеств вершин на одноцветные классы. Рассмотрим одно из возможных разбиений на одноцветные классы для каждого из графов G и G" - У = {У{,У2,—,Уі ,—,Ух(р )} и V" - { ",F2",..., ...,F (G»4} - соответственно. Далее, проведя рассуждения аналогичные рассуждениям, проведенных в доказательстве леммы 2.3, получим, что при таких разбиениях вершин графов G и G" на одноцветные классы, граф G, полученный склеиванием этих графов, является неоднозначно раскрашиваемым. Рассмотрев любые другие разбиения на одноцветные классы графов G и G" и проведя с этими разбиения те же рассуждения, что с разбиениями V{,V{,...,V!,...,V %(JJ и V",V%,...,V",...y"x{G,y придем к заключению о неоднозначной окрашиваемости графа G при любых разбиениях графов G и G" на одноцветные классы.
Теорема 2.4 Однозначно А:-раскрашиваемых предфрактальных графов GL -{VL,EL),L 2, порожденных одной затравкой с сохранением смежности старых ребер, для к 2 не существует.
Доказательство состоит из двух частей. В первой части рассмотрен случай порождения предфрактального графа однозначно раскрашиваемой затравкой, а во второй - неоднозначно раскрашиваемой.
Алгоритм J32 раскраски предфрактального графа, смежность старых ребер которого сохраняется
Несколько слов о труднорешаемости задачи оптимальной раскраски. При К = %(L) = 2 задача разрешима за полиномиальное время. Но при всех фиксированных К 3, а также для К = 3 и плоских графов, степени вершин которых не превосходят 4, задача NP-полна. В общем случае задача может быть решена за полиномиальное время для графов, не имеющих вершин степени выше 3.
В таких задачах моделью является многокритериальная задача о раскраске на предфрактальных графах.
Большинство реальных задач составления расписания относятся к классу NP- полных. Это делает разработку алгоритма, способного решить их за допустимое время, действительно сложной задачей, даже если соответствующую предметную задачу можно поставить как однокритериальную. Ситуация существенно усугубляется тем, что большинство реальных задач составления расписаний многокритериальные.
Задачу составления расписания можно свести к задаче раскраски графа. Для этого строится граф, в котором каждая вершина представляет собой запланированное действие. В том случае, если между какими-то двумя вершинами возможны конфликты, то они соединяются ребром. Тогда задача составления расписания представляется как минимизация числа цветов, необходимых для раскраски графа. Каждый цвет соответствует одному периоду расписания. Учитывая NP-полноту задачи, для её решения необходимо моделировать действия составителя расписания с пустого расписания, когда все действия находятся в списке неучтенных. Далее алгоритм переходит от одного незаконченного расписания к другому, стремясь наилучшим образом расставить все действия, включенные в список. Процесс продолжается до тех пор, пока не будет сформировано полное расписание или выполнится фиксированное количество итераций.
В случае, когда задача большой размерности и структура меняется во времени, то задачу составления расписания необходимо моделировать с помощью раскраски на предфрактальных графах.
В третьей главе диссертационной работы предложены алгоритмы (Р\ Ръ и У\ Уъ) вершинной раскраски пред фрактального графа. Каждый из алгоритмов оптимизирует один или несколько критериев заданной в первой главе многокритериальной функции. Для многокритериальной задачи вершинной раскраски предфракталь-ного графа разработаны и исследованы следующие полиномиальные алгоритмы: алгоритм Д раскраски предфрактального графа, смежность старых ребер которого сохраняется, а затравка - полный граф; алгоритм /?2 раскраски предфрактального графа, смежность старых ребер которого сохраняется; алгоритм /?з раскраски предфрактального графа, порожденного множеством затравок, смежность старых ребер которого сохраняется; алгоритм ух раскраски предфрактального графа, старые ребра которого не пересекаются, а затравка - полный граф; алгоритм у2 раскраски предфрактального графа, старые ребра которого не пересекаются; алгоритм у3 раскраски предфрактального графа, порожденного множеством затравок, старые ребра которого не пересекаются.
В выводах диссертационной работы отметим результаты работы новых подходов, основные положения, подведем итоги работы, имеющие как теоретическую, так и практическую значимость:
1. Построена математическая модель сложной системы с изменяющейся структурой во времени и дана формулировка многокритериальной задачи о раскраске на вершинно взвешенных предфрактальных графах, а также обоснована практическая необходимость предложенной формулировки.
2. Очерчен круг задач, сводимых к задаче о раскраске на предфрактальных графах. Показано, что предфрактальные графы лежат в основе моделирования структуры оптимальной компоновки монтажно-коммутационного пространства, а в процессе порождения предфрактальных графов, затравкой является «конверт-граф».
3. Детально рассмотрены и четко определены фрактальные и предфрактальные графы, порождаемые при различных условиях смежности ("несмежности") их старых ребер.
4. В процессе исследования различных свойств и характеристик фрактальных и предфрактальных графов, связанных с их вершинной раскраской, установлена связь между хроматическим число фрактального (предфрактального) графа и хроматическим числом его затравки / затравок.
5. Обоснована невозможность построения однозначно раскрашиваемого предфрактального графа. Определены множества и мощности критических подграфов фрактальных и предфрактальных графов.
6. Показано, что фрактальный или предфрактальный граф, порожденный плоской 4-хроматической затравкой с сохранением смежности старых ребер, является планарным 4-хроматическим графом.
7. Предложенные полиномиальные алгоритмы вершинной раскраски предфрактального графа, оптимизируют один или несколько критериев сформулированной модельной многокритериальной задачи о раскраске.
