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

• Узденов, Ахмат Абдуллахович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Узденов, Ахмат Абдуллахович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 МОДЕЛИ РАЗМЕЩЕНИЯ ЦЕНТРОВ НА ГРАФАХ

1.1 Задачи размещения центров и медиан на графах

1.2 Классическая постановка задачи размещения центров

в графах и сетях

1.3 Задача размещения /7-центра и алгоритм её решения

1.4 Выводы

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

2.1 Фрактальные и предфрактальные графы. Определение фрактального и предфрактального графов

2.2 Многокритериальная модель размещения р-центра

на предфрактальных графах

2.3 Математическая модель крупномасштабной кластеризации материи во Вселенной

2.4 Метрические характеристики предфрактальных графов, порождённых затравкой-звездой

2.5 Выводы

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

3.1 Алгоритм щ поиска внешнего центра предфрактального

графа

3.2 Алгоритм а2 поиска внутреннего центра предфрактального графа, смежность «старых» рёбер которого сохраняется

3.3 Алгоритм а3 поиска внешне-внутреннего центра предфрактального графа, смежность «старых» рёбер

которого сохраняется

3.4 Алгоритм а4 поиска центра предфрактального графа,

смежность «старых» рёбер которого сохраняется

3.5 Алгоритм р, поиска /?-центра (р = п1' ') предфрактального

графа, смежность «старых» рёбер которого сохраняется

»

3.6 Алгоритм р2 поиска р-центра (р = п ' ) предфрактального графа, смежность «старых» рёбер которого сохраняется

3.7 Алгоритм р поиска /7-центра предфрактального графа, смежность «старых» рёбер которого сохраняется

3.8 Описание программного комплекса и результаты расчётов

3.9 Выводы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В

ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗОВАННЫХ

МАТЕРИАЛОВ

ПРИЛОЖЕНИЕ. ПРОГРАММНЫЙ КОМПЛЕКС «НАХОЖДЕНИЕ

ЦЕНТРАЛЬНЫХ ВЕРШИН ФРАКТАЛЬНОГО ГРАФА».

ТЕКСТ ПРОГРАММ С КОММЕНТАРИЯМИ

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

ВВЕДЕНИЕ

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

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

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

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

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

В более общих и более сложных практических задачах появляется воз-

можность рассматривать и строить не один центр в одной вершине, а множество из/ьточек, которые и образуют «кратный центр» или «р-центр».

В классической теории графов перечень работ и список исследователей, которые решали задачу размещения центров, огромен. Достаточно сослаться на работы Н. Кристофидеса, C.J1. Хакими, Д. Дейкстра, С. Сингера, К. Бержа, A.A. Зыкова, Ф. Харари, Г. Фрэнка, И. Фриша, О. Ope, Р. Басакера, Т. Саати, Г.М. Адельсон-Вельского, Е.А. Диница, A.B. Карзанова, Р. Уилсо-на, J1. Форда, Д. Фалкерсона, В.А. Евстигнеева, Р.В. Флойда.

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

Благодаря исследованиям, проводимым в научной школе профессора A.M. Кочкарова в Северо-Кавказской государственной гуманитарно-технологической академии, фрактальные (предфрактальные) графы получили распространение как инструмент моделирования «сложных динамических систем». Это происходит из-за нарастающей потребности построения многокритериальных моделей и решения оптимизационных задач в сложных системах, обогащенных и отягощенных быстрым изменением во времени нестационарных переменных современных конъюнктур.

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

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

математики. Если раньше моделирование было исключительно прерогативой специалистов технических и инженерных направлений науки, то теперь оно как инструмент познания окружающего мира используется во многих отраслях современного знания [19, 29, 31].

Любая целенаправленная деятельность требует планирования и прогнозирования. Каждая из составляющих этой деятельности невозможна без понимания сути процесса в той области, где она осуществляется. Достичь удовлетворительного понимания можно с помощью адекватно построенной математической модели. На основе имеющейся математической модели возможно оптимизировать решение задачи, что позволяет делать прогнозы и планировать дальнейшие действия. Задачи автоматического управления, оптимального и адаптивного, автоматизации проектирования, эколого-экономического планирования, принятия решений, компромисса в условиях неполной информации, математического программирования и т.п. находятся в сфере деятельности специалистов по исследованию операций. Предметом их исследований становятся «сложные системы» [52, 74, 91].

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

¥(х) = (Fl(x),F2(x),...,Fi(x),...,Fn(x)),

Fj (х) —» extr(max/ min), i = l,n,

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

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

три последовательных этапа.

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

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

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

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

Одной из широко используемых и хорошо развитых областей дискретной математики является теория графов. Методы теории графов нашли приложение во многих областях современной науки: в технике, в экономике, в биологии и химии, в исследовании надёжности, стойкости и живучести систем, в моделировании динамических систем и в управлении ими и т.д. Нередко использование методов теории графов в перечисленных областях исходило из постановки оптимизационных задач. Напомним, что появление самих графов произошло при решении Л. Эйлером по сути оптимизационной задачи о кёнигсбергских мостах. Поиск решений оптимизационных задач на графах осуществляется специализированными алгоритмами. Время решения задачи алгоритмом оценивается его вычислительной трудоёмкостью или вычислительной сложностью [3, 13, 21, 30, 69].

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

существует константа с, такая, что \/(п)\ < с\0^(п))\ для всех значений

п > 0. Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называют алгоритм, у которого временная сложность равна 0{р{п)), где р(п) - некоторая полиномиальная функция. Алгоритмы, которые не поддаются подобной оценке, называются экспоненциальными или ЫР-полными. С ростом размерности задачи предпочтительность полиномиальных алгоритмов перед экспоненциальными вполне очевидна. Поэтому первые называются также эффективными, а вторые - неэффективными. Задача называется труднорешаемой, если для её решения не существует полиномиального алгоритма. Таким образом, обоснованный полиномиальный алгоритм решения графовой оптимизационной задачи является одним из наи-

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

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

Реализация цели диссертационного исследования потребовала решения следующих задач:

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

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

3 Построение и исследование математической модели размещения кратного центра или /7-центра на предфрактальном графе.

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

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

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

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

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

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

Научная новизна диссертационного исследования определяется:

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

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

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

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

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

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

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

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

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

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

Результаты программной реализации диссертационного исследования переданы и зарегистрированы в Реестре программ для ЭВМ (свидетельство № 2011618548 от 31 октября 2011 г.) для открытого и широкого использования и внедрения.

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

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

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

2 Математические модели размещения /?-центра удаётся строить не только на обыкновенных графах, но и на предфрактальных графах.

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

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

5 Обоснована практическая необходимость постановки многокритериальных задач математического моделирования сетей принципиально нового типа. Сформулирована многокритериальная задача размещения р-центра на взвешенных предфрактальных графах. Очерчен круг задач, сводимых к задаче о /?-центре на графах.

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

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

Апробация результатов исследования. Основные результаты работы докладывались и были одобрены на:

• У1-ой Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001);

• П-ой Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2001);

® 1У-ой Научной конференции «Региональная экономика, управление и право» (Черкесск, 2001);

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

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

• Международном Российско-Узбекском симпозиуме «Уравнения смешанного типа и родственные проблемы анализа и информатики» (Нальчик, 2003);

• ХУ1-ой Международной научной конференции «Математические ме-

тоды в технике и технологиях (ММТТ-16)» (Санкт-Петербург, 2003);

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

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

• Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2004);

• Всероссийской научно-практической конференции «Инвестиционная привлекательность туристических фирм и мест рекреации регионов» (Нижний Архыз, 2004);

• Ш-ей Международной конференции «Нелокальные краевые задачи и родственные проблемы математической проблемы математической биологии, информатики и физики» (Нальчик, 2006):

• 1-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2006);

® И-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2007);

• Региональной научно-практической конференции «Рациональные пути решения социально-экономических и научно-технических проблем региона» (Черкесск, 2008);

• Ш-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2008);

« У1-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и Ш-ей Молодёжной школы-семинара «Управление и обработка информации в технических системах» - «Управление 2011» (Таганрог, 2011);

® научных семинарах Филиала Южного федерального университета в г. Черкесске (Черкесск, 2002-2011).

Публикации. Основные результаты диссертационного исследования

изложены в 33 опубликованных научных работах автора общим объёмом 9.50 п.л., в том числе самого автора - 8.02 пл., в их числе 4 - в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК. Список публикаций содержится в библиографическом списке использованных материалов (с. 131-147 диссертации) и на с. 17-20 автореферата.

1 МОДЕЛИ РАЗМЕЩЕНИЯ ЦЕНТРОВ НА ГРАФАХ

1.1 Задачи размещения центров и медиан на графах

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

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

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

1.2 Классическая постановка задачи размещения центров

в графах и сетях

Для любой вершины v, графа G = (V,E) ЯдСО есть множество тех вершин vj графа G, которые достижимы из вершины vi с помощью путей с взвешенными длинами d(vt,vj), не превосходящими величины Л. Через

*i(vf) будет обозначаться множество тех вершин v ■ графа G, из которых вершина vi может быть достигнута с использованием путей, имеющих взвешенные длины d{vj,vi) < Л. Таким образом,

(vi) = ivj I d(Vj ,Vj)< Л, Vj е V),

Для каждой вершины vi графа G = (V,E) определим следующие числа:

s0(v,) = max[£/(v,,v.)]

v -еГ

st(vl) = max[d(vJ,vi)]. О-О

VjSV

sot (vi) = max[J (V/ ,Vj) + d (v., vf)].

Числа я0(уг), st(Vj) и называются соответственно числом внеш-

него разделения вершины, числом внутреннего разделения вершины и числом внешне-внутреннего разделения вершины vi.

Вершина v*, для которой

so (vo) = niin[ (v,-)], (1.2 .а)

vreV

называется внешним центром графа G, вершина v*, для которой

= (1.2.6)

г-ЕУ

называется внутренним центром графа С, а вершина V*,, для которой

(V,)], (1-2.б)

vie¡/

называется внешне-внутренним центром графа С.

У графа может быть несколько внешних и внутренних (внешне-внутренних) центров, которые образуют множества внешних и внутренних (внешне-внутренних) центров соответственно.

Число внешнего разделения вершины V*, являющейся внешним центром, называется внешним радиусом: р0 = ,у0(у*); число внутреннего разделения вершины V* внутреннего центра, называется внутренним радиусом: Л = (у*)' а числ0 внешне-внутреннего разделения вершины у*о1 внешне-

внутреннего центра, называется внешне-внутренним радиусом: р(Я = (у^).

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

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

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

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

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

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

Пример 1.1 Администрация округа решила построить новый пост пожарной охраны, который должен обслуживать шесть городов округа. Этот пост должен располагаться возле какой-либо из автомагистралей, но так, чтобы минимизировать расстояние до наиболее отдалённого от неё города. Если автомагистраль округа изображается ребром графа, то задача размещения пожарного поста становится задачей такого размещения точки на ребре графа, при котором минимизируется расстояние вдоль ребер (автомагистралей) от этой точки до наиболее удаленной вершины графа (города). Рассмотрим граф, представленный на рис. 1.1. Вес всех рёбер графа равен единице. Если в качестве точки размещения выбрать вершину 3, то наиболее отдаленной от вершины 3 является вершина 6. Расстояние от вершины 3 до вершины 6 равно 3 единицам.

Рисунок 1.1 - Карта связи автомагистралей между городами

Более удачным является выбор вершины 2, которая отдалена от любой вершины не более чем на 2 единицы. Еще более удачным является выбор в качестве точки размещения средней точки ребра (2, 5). Эта точка отдалена от

вершин 1, 3, 4, 6 на 1.5 единицы. Понятно, что вершина 2 соответствует центру графа, а средняя точка ребра (2, 5) - абсолютному центру.^

Пример 1.2 Предположим, что в том же округе должна быть размещена почта таким образом, чтобы минимизировалось суммарное расстояние от нее до каждого из городов округа. Размещение почты в средней точке ребра (2.5) дало бы суммарное расстояние, равное

1.5 + 0.5 + 1.5 + 1.5 + 0.5 + 1.5 =7 единицам, так как расстояние от средней точки ребра (2.5) до вершин 1, 2, 3, 4, 5, 6 соответственно равно 1.5; 0.5; 1.5; 1.5; 0.5; 1.5 единицы. Л

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

Алгоритм нахождения центров. Рассмотрим далее известный алгоритм нахождения центров на графе.

МЕТОД ВЗВЕШЕННЫХ РАССТОЯНИЙ (МВР) Вход: взвешенный граф С = (V, Е).

Выход: V* - центр графа (7.

Шаг 1 Построить матрицу кратчайших путей ) между любыми

двумя вершинами V, и у ■ с помощью процедуры Флойда.

Шаг 2 Для каждой вершины vi графа найти число разделения ¿(у,-). Шаг 3 Из всех вершин у/9 / = 1,2,..., п в качестве центра графа (7 вы-

брать вершину V* с наименьшим числом разделения: я(у*) = .

ПРОЦЕДУРА ФЛОЙДА

Вход: взвешенный граф С = (V, Е).

Выход: матрица кратчайших расстояний с/(у,-,у •). Л

На графе может существовать несколько центров или вершин с равными числами разделения.

Теорема 1.1 Вычислительная сложность алгоритма Флойда на гра-

о I .

фе О = (У,Е) равна О(п^), где п = \У\ [2].

Теорема 1.2 Вычислительная сложность алгоритма МБР на графе в = (Г,Е) равна 0(п3 +п2 +п), где п = \Г\ [69].

Соотношение (1.1) определяет число разделения для любой вершины у;- е V. Обобщим теперь это определение на случай «искусственных» точек, которые можно помещать на рёбрах.

е

V. о о в V ■

и

Рисунок 1.2 - Размещение искусственной точки и на ребре графа

Итак, если е - (у;-,у ■) (рис. 1.2) представляет ребро графа с весом (длиной) Су, то точка и, помещаемая на этом ребре, может быть определена посредством задания длины /(и,у •) участка (у¡,и), при этом должно выполняться равенство /(у,-, и) + 1{и, V ■) = с у.

Число разделения точки и, независимо от того, является ли она вершиной графа (7 или искусственной точкой ребра графа С, определяется следующим образом:

5(м) = тах[б/(и,у ■)], (1.3)

Точка и", для которой

4и*) = 1шп[«(м)], (1-4)

меК

называется абсолютным центром графа.

Число разделения абсолютного центра называется абсолютным радиусом г = я(и*).

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

Алгоритм нахождения абсолютных центров. Рассмотрим далее известные алгоритмы нахождения абсолютных центров на графе.

МЕТОД ХАКИМИ

Вход: взвешенный граф С? = (V, Е).

Выход: и* — абсолютный центр графа С.

Шаг 1 Для каждого ребра ек графа найти точки (или точку) ик на ек, которые имеют наименьшее число разделения.

Шаг 2 Из всех точек ик, к = \,2,...,т в качестве абсолютного центра

графа (7 выбрать точку с наименьшим числом разделения. Л

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

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

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

МОДИФИЦИРОВАННЫЙ МЕТОД ХАКИМИ

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

Всякому локальному центру, расположенному на ребре (vz-, v ■), соответствует его абсолютный локальный радиус г-, который не меньше, чем рц, где ру = max[v5 min {d(v5, vi), d(vs,, v ■)} ].

vseV

Py есть нижняя оценка абсолютного радиуса графа, если абсолютный центр лежит на ребре (v/5v •). Следовательно, величина Р = шах [рЛ явля-

(v,,vy)e£

ется обоснованной нижней оценкой абсолютного радиуса графа.

Допустим, что абсолютный центр расположен в середине ребра (v;-,v •).

Тогда абсолютный радиус равен Следовательно,

Н = min [рц н—с,] является обоснованной верхней оценкой абсолютного

(v,-,vy)e£ 2 '

радиуса графа. Таким образом, всякое ребро (у,- , у), для которого ■ > Н, может не рассматриваться при поиске абсолютного центра.

После уменьшения множества рёбер, которые будут участвовать в алгоритме, приступаем к шагам 1 и 2 первоначального метода Хакими. V

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

ИТЕРАЦИОННЫЙ МЕТОД

Пусть QÄ (у,-) - множество всех точек и, лежащих на рёбрах графа G, из которых вершина vi достижима со взвешенным расстоянием, не превосходящим Я. Таким образом, Öa(v/) = {и | ¿/(и,у;) < Я}.

Абсолютный радиус г, очевидно, является наименьшим значением Я, при котором из некоторой точки и графа G все вершины графа могут быть достигнуты с взвешенным расстоянием, меньшим или равным Я. Следовательно, г есть такое наименьшее значение Я, что

П[бя(гг)]-0я(^)П0я(у2)П...П0яК)^0. (1.5)

VjeV

Поэтому можно начать с произвольного небольшого значения Я, строить множества 6д(у,-) для всех z = 1,2,...,п и проверять, выполняется ли приведённое выше соотношение (1.5). Если оно не выполняется, то надо увеличить немного величину Я, заново построить множества и опять проверить, выполняется ли соотношение (1.5). Эту процедуру нужно повторять до тех пор, пока (1.5) не будет выполняться. Полученная таким образом величина Я принимается за абсолютный радиус г графа G. Более того, по-

скольку приращения величины Я малы, то пересечение П [бя(уг)] ПРИ за~

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

Если есть наикратчайшее расстояние между двумя произволь-

ными вершинами, то совершенно очевидно, что если Я меньше половины

взвешенного расстояния между V,- и у-, т. е. то

2

(У1) П (Уу) = 0 и полное пересечение множеств в (1.8) пусто.

Следовательно, итерационный процесс поиска абсолютного центра можно начать со значения Я, равного

Л0 = шах '.У

поскольку радиус г должен быть не меньше Я0. М

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

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

образуют кратный центр (р-центр).

Пусть V - подмножество, содержащее р вершин множества V вершин

графа 0 = (У,Е). Через будем обозначать наикратчайшее из рас-

стояний между вершинами множества V и вершиной V т. е.

d(\,Vj) = mm[d(yi,V:)].

Подобно тому, как определялось число разделения вершины, можно определить число разделения для множеств вершин:

=.тах[й?(у,у •)], (1.6)

где - число разделения множества V.

Множество V*, для которого

^у^ШШ^У)], (1.7)

V <=У

называется р-кратным центром (р-центром) графа (7.

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

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

Если предположить, что пожарные должны размещаться в вершинах

соответствующего графа О, то задача будет состоять в нахождении р-центров графа для р = 1,2,3,.- и т- Д- Д° тех пор, пока число разделения р-центра не станет меньше или равно заданного расстояния. Полученное (последнее) значение числа р будет наименьшим числом пожарных депо, а р-центр - их оптимальным размещением, удовлетворяющим предъявляемым требованиям. Л

Для поиска 1-центров графа легко может быть использован метод взвешенных расстояний (МВР). Однако находить таким же способом /?-центр можно лишь для небольших графов и для небольших значений величины р. При таком подходе надо построить всевозможные множества вершин V е V, содержащие р вершин, а затем, используя формулы (1.6) и (1.7), непосредственно найти множества V*, образующие р-центры.

Алгоритмы нахождения р-центра графа. Далее предложим пошаговое описание алгоритмов поиска /^-центров на графе.

Метод взвешенных расстояний при поиске /»-центра

Вход: взвешенный граф (7 = (V, Е).

Выход: V* -/7-центр графа

Шаг 1 Построить всевозможные множества вершин усК, содержащие ровно р вершин графа (7.

Шаг 2 Построить матрицу кратчайших путей с1(\,у ■) между множеством V и вершинами у • для всех V с V с помощью процедуры Флойда.

Шаг 3 Для каждого множества вершин V графа найти число разделения я(у).

Шаг 4 Из всех множеств V с К в качестве р-центра графа С выбрать множество V* с наименьшим числом разделения: =

усУ

ПРОЦЕДУРА ФЛОЙДА

Вход: взвешенный граф (? = (V, Е).

Выход: матрица кратчайших расстояний ¿/(уг-, V ■). М

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

Теорема 1.3 Вычислительная сложность алгоритма МБР (поиска р-

центра) на графе (7 = (V, Е) равна р-{п- р)'

гп\

,гдеп = \У\ [69].

\Р)

Общий случай задачи размещения нескольких пунктов обслуживания. Если ограничение, согласно которому точки /^-центра должны лежать в вершинах графа, снято и допускается размещение точек на рёбрах, то получающееся при этом множество из р точек называется абсолютным р-центром. Таким образом, абсолютный центр, состоящий из одной вершины, можно назвать абсолютным 1-центром.

Задача нахождения абсолютного /»-центра может быть сформулирована следующим образом:

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

Вторая задача б) очень близка к задаче а) и может быть решена тем же методом, что и задача а), суть её состоит в следующем:

б) Для заданного «критического» расстояния найти такое наименьшее число центров и такое их размещение, чтобы все вершины графа лежали в пределах этого критического расстояния.

Так формируется общая задача определения абсолютных /?-центров. Именно она наиболее часто встречается на практике. Однако решать её гораздо труднее, чем какой-либо из «упрощенных» вариантов а) или б). Метод Хакими, предназначенный для решения задачи с одним абсолютным центром, не может быть обобщён на случай абсолютных /?-центров. Для нахож-

дения таких центров Сингер предложил эвристический метод [12].

Далее будет рассмотрен итерационный алгоритм решения задачи об абсолютных /»-центрах графа. Из приведённых результатов вычислений видно, что этот алгоритм является быстро сходящимся. Метод обладает следующими двумя преимуществами:

® процесс можно закончить сразу же, как только достигнута необходимая «точность» в расположении центров;

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

Пусть и - произвольное множество каких-либо р точек на графе О. Число разделения я(и) множества и определяется так: л'(и) = тт[а?(и,у ■)],

где

d(u,vj) = тт[£/(мг-,V •)].

Абсолютный /»-центр графа О определяется как множество точек и*, для которого и* = тт[5,(и)].

и на С

Алгоритм нахождения абсолютных /»-центров. Рассмотрим по очереди каждую вершину у, и «углубимся» по всем возможным маршрутам, выходящим из неё, на расстояние Я, где Л - заданная константа, которую мы будем называть константой «проникновения».

Пусть ()л (у,) - множество всех точек и на графе (7, из которых вершина у,- достижима в пределах расстояния Л. Множества (у,-) определяются с помощью соотношения: Qл{vi)-{u\d(u,vi)< Л]. Эти множества

весьма легко можно построить, применяя алгоритм, подобный алгоритму Дейкстры [3].

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

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

/

Области, из которых можно в пределах Л достичь ровно t вершин

,..,,1; (для всех t = 1,2,..., п), определяются следующим выражением:

^"'Х ^ (1-8)

-{[ п &(\)]П[ П бя(V, )]}

1 ч ч

<7=1,...,? <5г=?+1,

где второй член исключает такие области, из которых достижимы вершины ,х^2 и ещё хотя бы одна из оставшихся вершин графа.

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

АЛГОРИТМ ПОСТРОЕНИЯ АБСОЛЮТНОГО /ЧДЕНТРА

Вход: взвешенный граф С = (V, Е).

Выход: и* - абсолютный/?-центр графа С.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Узденов, Ахмат Абдуллахович

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ

В ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ

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

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

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

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

4 Построена и исследована математическая модель задачи размещения кратного центра (в частности, /»-центра) на предфрактальном графе.

5 Исследованы свойства и найдены метрические характеристики предфрактальных графов, порождённых затравкой-звездой.

6 Построены алгоритмы нахождения оптимальных решений сформулированной задачи.

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Узденов, Ахмат Абдуллахович, 2011 год

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

1. Алескерое Ф.Т., Хабина Э.Л., ШварцД.А. Бинарные отношения, графы и коллективные решения. - М.: Издательский дом ГУ ВШЭ, 2006.

2. Асанов М. О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. - Ижевск: Научно-исследовательский центр «Регулярная и хаотическая динамика», 2001.

3. АхоА., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.

4. Барыилев Ю.В. Иерархическая структура метагалактики. Обзор проблем // Астрофизические исследования. Известия Специальной астрофизической обсерватории (CAO) РАН. -1981.-Т. 14.-С. 24-43.

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

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

7. Батчаев КЗ., Кочкаров A.M. Математическая модель задачи размещения центров технического обслуживания автомобильной компании // П-ая международная конференция «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики». Тезисы докладов. - Нальчик: Издательство НИИ МПиА КБНЦ РАН, 2001. -С. 14-16.

8. Батчаев КЗ., Кочкаров A.M. Об одной многокритериальной задаче покрытия минимального веса предфрактального графа звёздами ранговых типов // V-ый Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тезисы докладов. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2,002. -С. 7-9.

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

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

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

12. Божокин С.В., Паршин Д.А. Фракталы и мультифракталы. - Ижевск: Научно-исследовательский центр «Регулярная и хаотическая динамика», 2001.

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

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

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

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

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

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

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

20. Евстигнеев В.А., Касьянов В.Н. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.

21. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. - Новосибирск: Наука, 1998.

22. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. - Новосибирск: Наука, 1994.

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

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

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

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

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

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

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

30. ЗамбицкийД.К., ЛозовануД.Д. Алгоритмы решения оптимизационных задач на сетях. - Кишинев: Штиинца, 1983.

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

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

33. Казиев Р.Ш., Салпагаров С. И. Математическая модель информационного потока на предфрактальных графах // Материалы Российско-Узбекского симпозиума «Уравнения смешанного типа и родственные проблемы анализа и информатики». Тезисы докладов. - Нальчик: Издательство НИИ МПиА КБНЦ РАН, 2003. - С. 119-121.

34. Касты Дж. Большие системы. Связность, сложность и катастрофы. - М.: Мир, 1982.

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

36. Кононов Д. А., Кулъба В.В. и др. Синтез формализованных сценариев и структурная устойчивость сложных систем (синергетика и аттрактивное поведение). Препринт. - М.: Институт проблем управления имени В.А. Трапезникова РАН, 1998.

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

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

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

40. Коркмазова З.О., Никищенко С.П. Оценка числа эйлеровых циклов на предфрактальном (п, 1)-графе с затравкой - «полный двудольный подграф» // Материалы VIII-ой региональной научно-технической конфе-

ренции «Вузовская наука - Северо-Кавказскому региону». Том I. - Ставрополь: Северо-Кавказский государственный технический университет, 2004.-С. 11-12.

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

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

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

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

45. Кочкаров A.A. Плоские и планарные предфрактальные графы // V-ый Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тезисы докладов. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2002. - С. 35.

46. Кочкаров A.A. Стойкость, графы, синергетика// Новое в синергетике. Новая реальность, новые проблемы, новое поколение. Сборник статей. Часть 2 / Под редакций Г.Г. Малинецкого. - М: Радиотехника, 2006.

47. Кочкарое A.A. Число всевозможных предфрактальных графов // IV-ый Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тезисы докладов. Том 2. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2000. - С. 7374.

48. Кочкарое A.A., Кочкарое P.A. Исследование связности предфрактальных графов // IV-ый Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тезисы докладов. Том 2. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2000.-С. 74-75.

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

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

51. Кочкарое A.A., Кочкарое P.A. Топологические характеристики предфрактальных графов и предупреждение кризисов сложных систем // Труды X-ой Международной конференции «Проблемы управления безопасностью сложных систем». Часть 1. - М.: РГГУ - Издательский дом МПА-Прогресс, 2002. - С. 116-119.

52. Кочкарое A.A., Малинецкий Г.Г. Моделирование распространения внешних воздействий по структуре сложной системы // Математическое моделирование. - 2006. - Т. 18. - № 2. - С. 51-60.

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

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

55. Кочкаров A.A., Малинецкий Г.Г. Теория стойкости и структурное управление в сложных технических и социально-экономических системах // Известия Таганрогского государственного радиотехнического университета. Тематический выпуск «Перспективные системы и задачи управления». - Таганрог: ТРТУ, 2006. - № 3. - С. 100-107.

56. Кочкаров A.A., Салпагаров С.И. Число мостов предфрактального графа. // V-ый Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тезисы докладов. - Кисловодск: Издательский центр Кисловодского института экономики и права, 2002. - С. 3637.

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

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

59. Кочкаров A.M. Распознавание фрактальных графов. Алгоритмический подход. - Нижний Архыз: Специальная астрофизическая обсерватория (CAO) РАН, 1998.

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

61. Кочкаров A.M. Хроматическое число и хроматический индекс фрактальных графов // Республиканская конференция преподавателей и аспиран-

тов Карачаево-Черкесского государственного технологического института. Тезисы докладов. - Черкесск: КЧТИ, 1997. - С.56-57.

62. Кочкаров A.M., Кочкаров A.A., Никищенко С.П. Структурная динамика и исследование структурно-временных характеристик дискретных систем // Известия Таганрогского государственного радиотехнического университета. Тематический выпуск «Перспективные системы и задачи управления». - Таганрог: ТРТУ, 2006. - № 3. - С. 235-238.

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

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

65. Кочкаров A.M., Перепелица В.А. Число внутренней устойчивости пред-фрактального и фрактального графа. Сборник статей. - Нижний Архыз: Специальная астрофизическая обсерватория (CAO) РАН. - 1999.

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

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

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

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

70. Кулъба В.В., Кононов Д. А., Ковалевский С.С. и др. Сценарный анализ динамики поведения социально-экономических систем. Препринт. - М.: Институт проблем управления имени В.А. Трапезникова РАН, 2002.

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

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

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

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

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

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

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

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

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

80. Нечепуренко М.И., Попков В.К, Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск: Наука, 1990.

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

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

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

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

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

86. Павлов Д.А., Кочкаров A.A., Узденов A.A. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах // Препринт Специальной астрофизической обсерватории (CAO) РАН № 198. - Нижний Архыз: Издательство CAO РАН, 2004. - 15 с.

87. ПападимитриуX., СтайглицК. Комбинаторная оптимизация: Алгоритмы и сложность. - М.: Мир, 1985.

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

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

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

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

92. Петров A.A. Исследование операций и математическое моделирование //

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

93. Плесневич Г.С., Сапаров М.С. Алгоритмы в теории графов. - Ашхабад: Ылым, 1981.

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

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

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

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

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

99. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика. - М.: Мир, 1980.

100.Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. - М.: Наука, 1986.

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

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

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

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

105. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. - Киев: Наукова думка, 1988.

106. Сергиенко И.В., Перепелица В.А. К проблеме нахождения множеств аль-

тернатив в дискретных многокритериальных задачах // Кибернетика. -1987. -№ 5.-С. 85-93.

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

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

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

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

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

112. Узденов A.A. Задача выделения /»-центра с гарантированными оценками // Материалы VI-го Всероссийского симпозиума «Математическое моделирование и компьютерные технологии». - Кисловодск: Издательский центр Кисловодского института экономики и права, 2004. - С. 11.

113. Узденов A.A. Алгоритм определения абсолютных /»-центров на пред-фрактальных графах // - Черкесск: Карачаево-Черкесская государственная технологическая академия. Депонировано в. ВИНИТИ № 1975-В2003. - 2003. - С. 2-9.

114. Узденов A.A. Гарантированные оценки /»-медиан на предфрактальном графе с затравкой - «полный п -вершинный граф» // Материалы XVII-ой Международной научной конференции «Математические методы в технике и технологиях (ММТТ-17)». - Кострома: Издательство Костромского государственного технического университета, 2004. - Том 1. - С. 180181.

115. Узденов A.A. Гарантированные оценки /»-медиан на предфрактальном графе с затравкой - «полным и-вершинным графом», «ребром», «п-вершинной звездой» // Препринт Специальной астрофизической обсерватории (CAO) РАН № 202. - Нижний Архыз: Издательство CAO РАН, 2004. - 10 с.

116. Узденое A.A. Гарантированные оценки /-медиан на пред фрактальных графах // - Черкесск: Карачаево-Черкесская государственная технологическая академия. Депонировано в ВИНИТИ № 1976-В2003. - 2003. - С. 2-7

117. Узденое A.A. Математическая модель задач размещения на пред фрактальных и фрактальных графах // - Черкесск: Карачаево-Черкесская государственная технологическая академия. Депонировано в. ВИНИТИ № 767-В2002. - 2002. - С. 2-11.

118. Узденое A.A. Многокритериальная задача размещения на пред фрактальных и фрактальных графах // Сборник трудов IV-ой научно-практической конференции «Решение научно-технических и социально-экономических проблем современности». - Черкесск: Издательство Карачаево-Черкесского государственного технологического института, 2002. Часть 2. - С. 46.

119. Узденое A.A. Определение гравитационных центров L-ых уровней // Материалы VI-ой Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии». - Краснодар: Издательство Кубанского государственного аграрного университета, 2001. - С. 328.

120. Узденое A.A. Полиномиальный алгоритм решения двухкритериальной задачи о /-медианах // Материалы V-ro Всероссийского симпозиума «Математическое моделирование и компьютерные технологии». - Кисловодск: Издательский центр Кисловодского института экономики и права, 2002. - С. 39.

121. Узденое A.A. Полиномиальный алгоритм решения многокритериальной задачи о /»-медианах на предфрактальных графах // Материалы XVI-ой Международной научной конференции «Математические методы в технике и технологиях (ММТТ-16)». - СПб.: Издательство Санкт-Петербургского государственного технического института (технического

университета), 2003. - Том 1. - С. 187-190.

122. Узденое A.A. Задача выделения /-центра с гарантированными оценками на предфрактальном графе с затравкой - «двудольный граф» // Материалы Российской конференции «Дискретный анализ и исследование операций». - Новосибирск: Издательство Института математики имени С.Л.Соболева СО РАН, 2004. - С. 116.

123. Узденое A.A. Эффективный алгоритм построения /-центра предфрак-тального графа с затравкой регулярной степени // Материалы Региональной научно-практической конференции «Рациональные пути решения социально-экономических и научно-технических проблем региона». - Черкесск: Издательство Карачаево-Черкесской государственной технологической академии, 2008. Часть 1. - С. 44-46.

124. Узденое A.A. Алгоритм поиска внешнего центра предфрактального графа, смежность «старых» рёбер которого сохраняется // Доклады Адыгской (Черкесской) Международной академии наук. - 2010. - Том 12. - № 2.

125. Узденое A.A., Кочкаров P.A. Нахождение центральных вершин фрактального графа. Заявка № 2011616665 от 5 сентября 2011 г. Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. Зарегистрировано в Реестре программ для ЭВМ 31 октября 2011 г., свидетельство № 2011618548. - 9 с. 0.63 п.л., в т.ч. автора 0.5 п.л.

126. Узденое A.A., Кочкаров P.A. Алгоритм поиска внешне-внутреннего центра предфрактального графа с сохранением смежности «старых» рёбер // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление.-2010,-№ 3 (101). - С. 145-149.

127. Узденое A.A., Букка Е.С., Кочкаров P.A. Алгоритм поиска внешнего центра предфрактального графа // Известия Кабардино-Балкарского научного центра РАН. - 2010. - № 5 (37). - Часть II. - С. 31-36.

128. Узденов A.A., Кочкарое A.M. Задача о уьмедиане на пред фрактальных графах // Материалы Н-ой Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики». - Нальчик: Издательство НИИ ПМиА КБНЦ РАН, 2001.-С. 163-164.

129. Узденов A.A., Кочкарое A.M. Математическая модель прогнозирования свойств крупномасштабной кластеризации материи во Вселенной на предфрактальных графах // Труды IV-ой научной конференции «Региональная экономика, управление и право». - Черкесск: Издательство Карачаево-Черкесского государственного технологического института, 2001. - С. 25-27.

130. Узденов A.A., Кочкарое A.M. Эффективный алгоритм построения р-центров в иерархических системах // Известия Таганрогского государственного радиотехнического университета. Тематический выпуск трудов 1-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство ТРТУ, 2006. -№ 3. - С. 290-296.

131. Узденов A.A., Кочкарое P.A. Задача выделения /-центра с гарантированными оценками на предфрактальном графе с затравкой - «полный п-вершинный граф» // Известия Таганрогского государственного радиотехнического университета. Специальный выпуск № 8. - Таганрог: Издательство ТРТУ, 2004. - С. 305-306.

132. Узденов A.A., Кочкарое P.A. Об одной многокритериальной задаче выделения /»-центров на предфрактальном графе // Труды Ш-ей Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики». - Нальчик: Издательство НИИ ПМиА КБНЦ РАН, 2006. - С. 286-288.

133. Узденое A.A., Кочкаров P.A. Алгоритм выделения /-центров на пред-фрактальном графе // Вестник Северо-Кавказского государственного технического университета.- 2006. - № 5 (9). - С. 44-46.

134. Узденое A.A., Кочкаров P.A. Алгоритм поиска центра предфрактального графа, смежность «старых» рёбер которого сохраняется // Вестник Северо-Кавказского государственного технического университета. - 2011. -№ 1.

135. Узденое A.A., Кочкаров P.A., Урусова Г.З. Оценка сложности алгоритма выделения центра предфрактального графа, смежность «старых» рёбер которого сохраняется // Сборник материалов VI-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и Ш-ей Молодёжной школы-семинара «Управление и обработка информации в технических системах» - «Управление 2011». -Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2011. - С. 283-286.

136. Узденое A.A., Павлов ДА. Алгоритмы определения абсолютных р-центров на предфрактальных графах с затравкой - «полным п-вершинным графом» // Препринт Специальной астрофизической обсерватории (CAO) РАН № 201. - Нижний Архыз: Издательство CAO РАН, 2004. - 8 с.

137. Узденое A.A., Павлов Д.А. Разработка и исследование задачи распознавания предфрактального графа с затравкой - «простая цепь» // Материалы Н-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2007. - С. 191-193.

138. Узденое A.A., Павлов Д.А. Об одной многокритериальной задаче о р-медианах на предфрактальных графах // Электронный журнал «Исследовано в России», http://zhurnal.ape.relarn.ru/articles/2007/166.pdf, 2007. -

№ 10. - С. 1958-1961.

139. Узденов A.A., Салпагаров С.И. Задача об абсолютном /»-центре на пред-фрактальных графах // Материалы Всероссийской научно-практической конференции «Инвестиционная привлекательность туристических фирм и мест рекреации регионов». - Нижний Архыз: Издательство Ростовского государственного экономического университета «РИНХ», САО РАН, 2004. - С. 84-86.

140. Узденов A.A., Салпагарова Л.У. Гарантированные оценки /-медианы на предфрактальном графе с затравкой регулярной степени // Сборник материалов Ш-ей Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2008. - С. 247-248.

141. Узденов A.A., Салпагарова Л.У. Параллельный алгоритм поиска р-центра на предфрактальном графе // Сборник материалов Ш-ей Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2008. - С. 235236.

142. Узденов A.A., Элъканова Л. М. Двухпараметрическая шестикритериаль-ная задача о /»-центрах // Материалы Н-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2007. - С. 188-190.

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

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

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

146. Фракталы в физике / Под ред. Л. Пъетронеро, Э. Тозатти. - М„: Мир, 1988.

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

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

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

150. Чирков А.Ю., Шевченко В.Н., Золотых Н.Ю. О многокритериальной задаче целочисленного линейного программирования // Дискретный анализ и исследование операций. - Серия 2. - 2005. - Т. 12. - № 2. - С. 72-84.

151 .Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. - Ижевск: Научно-исследовательский центр «Регулярная и хаотическая динамика», 2001.

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

153. Ehrgott М., GandibleuxX. A survey and annotated bibliography of multiob-jective combinatorial optimization // OR Spectrum, 2000. - № 22. - P. 425460.

154.KigamiJ. Analysis on fractals / Volume 143 of Cambridge Tracts in Mathematics. - Cambridge: Cambridge University Press, 2001.

155.Kochkarov A., Perepelitsa V. Fractal Graphs and Their Properties // - Berlin: ICM 1998 - International Congress of Mathematicians, Abstracts of Short Communications and Posters, p. 347.

156. Krön B. Growth of self-similar graphs // Journal of Graph Theory. - 2004. -V. 45. - № 3. - P. 224-239.

157 .Krön В., Teufl E. Asymptotics of the transition probabilities of the simple ran-

dom walk on self-similar graphs // Transactions of American Mathematical Society. - 2004. - V. 356. - № 1. - P. 393-414.

158 .Riehl J. Hespanha J.P. Fractal graph optimization algorithms// Proceedings

of the 44-th Conference, on Decision and Control, 2005. - P. 2188-2,193.

159. Song C. HavlinS., Makse H.A. Self-similarity of Complex Networks// Nature. - 2005, - V. 433. - P. 392-395.

160. Watts D.J. Small Worlds. - Princeton: Princeton University Press, 1999.