Многокритериальная задача о раскраске на предфрактальных графах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Кононова, Наталия Владимировна

• Кононова, Наталия Владимировна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Кононова, Наталия Владимировна

Введение.

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

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

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

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

• I • >

1.4 Выводы.

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

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

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

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

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

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

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

2.6. Выводы.

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

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

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

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

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

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

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

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

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

3.9 Выводы.

Введение диссертации (часть автореферата) на тему «Многокритериальная задача о раскраске на предфрактальных графах»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 /+1 /

-1

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

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

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

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

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

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

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

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

Re [с]

А. п=1 п=2 Л

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Кононова, Наталия Владимировна

3.9 Выводы

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Кононова, Наталия Владимировна, 2008 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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