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

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

САЛПАГАРОВ Сослан-бек Исмаилович

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

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

Автореферат

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

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

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

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

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

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

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

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

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

Сербина Людмила Ивановна

Лепский Александр Евгеньевич

Ведущая организация: Кубанский государственный университет

Защита состоится «24» декабря 2005 г. в 12-00 часов па заседании диссертационного совета ДМ 212.259.09 при Северо-Кавказском государственном техническом университете по адресу: 355029 г. Ставрополь, пр. Кулакова, 2, ауд. Г-402.

С диссертацией можно ознакомиться в библиотеке

Автореферат разослан «20» ноября 2005 г.

Ученый секретарь диссертационного совета,

к.ф.-м.наук, доцент Мезенцева О.С.

ллэч

з

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

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

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

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

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

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

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

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

Ю<, !

ллькля

л

Ь г I ьКА

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

Пели работы.

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

2. Исследование свойств класса предфрактальных граф, возникающих в многокритериальной задаче о назначениях.

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

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

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

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

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

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

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

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

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

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

Публикации. По результатам выполненной работы имеется 17 публикаций (см. список публикаций).

Структура диссертации. Диссертация состоит из введения и четырех глав изложенных на 106 страницах, содержит 5 рисунков и библиографии из 114 наименовании.

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

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

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

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

Термином затравка условимся называть какой-либо связный граф Н = (\У,12). Для определения фрактального (предфрактальиого) графа нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе й = (V, Е) у намеченной для замещения вершины V е V выделяется множество V = (уу} с V , ] = 1,2,..., |у|, смежных ей вершин. Далее из графа в удаляется вершина V и все инцидентные ей ребра. Затем каждая вершина VjSV, _/' = 1,2,...,|1Й|, соединяется ребром с одной из вершин затравки Н = (IV, О). Вершины со-

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

Предфрактальный граф будем обозначать через = (У1,Е1), где - множество вершин графа, г Е1 - множество его ребер. Определим его , поэтапно, заменяя каждый раз в построенном на предыдущем этапе I = 1,2,..., Ь-1 графе С, = (У,, Е1) каждую его вершину затравкой Я = (IV, О). На этапе I = 1 предфрактальному графу соответствует затравка . Об описанном процессе говорят, что предфрактальный граф = пороэюден затравкой Н = (И7,0). Процесс порождения

предфрактального графа по существу, есть процесс построения последовательности предфрактальных графов ,02,—,С1,...,С1, называемой траекторией. .Фрактальный граф С = (У,Е), порожденный затравкой Я = (}¥, О), определяется бесконечной траекторией.

Предфрактальный граф (?£ = , Еь) условимся называть графом, если он порожден л-вершинной д -реберной связной затравкой Н = (№, О), и (п, Ь) -графом, если затравка Я = 0У, (У) - регулярный граф.

Для предфрактального графа Сь, ребра, появившиеся на /-ом, /е {1,2,..., Ц, этапе порождения, будем называть ребрами ранга I. Новыми ребрами предфрактального графа Оь назовем ребра ранга Ь, а все остальные ребра назовем - старыми.

На рис. 1.1 изображена траектория предфрактального графа = (У3, £3), порожденного затравкой Я = 0^,2) - полным 4-вершинным графом (см. рис. 1.1 А).

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

м'(е(")е (в'-1а,0'~1Ь), где 1 = ЪЬ -рангребра, а>0, и 9<

Ъ

Обобщением описанного процесса порождения предфрактального графа является такой случай, когда вместо единственной затравки Н используется множество затравок Н = {#,}={#,,#2,...,#,,...,#г}, Т>2. Суть этого обобщения состоит в том, что при переходе от графа к графу С/ каждая вершина замещается некоторой затравкой Я, е Н, которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры.

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

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

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

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

ЗН потребует решения и на других уровнях: проблема выбора встанет на уровне отделов и сотрудников институтов.

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

Первый — каков граф G. представляющий схему всевозможных взаимодействий между учреждения, заказчиками и исполнителями? Очевидно структура этой схемы сложнее, чем "обычный" двудольный граф. Каждое учреждение, начиная с высшего уровня, решая поставленную перед ним задачу (т.е. выполняя заказ) устанавливает связи между исполнителями и заказчиками более низкого уровня. А поскольку между указанными учреждениями-исполнителями и учреждениями-заказчиками более низкого уровня схема взаимодействий есть двудольный граф, это верно для любых уровней учреждений, то граф G, отражающий общую схему возможных взаимодействий, обладает свойством самоподобия. Поэтому общая схема возможных взаимодействий между учреждения различных уровней, принимающих участие в научно-исследовательском проекте -есть предфракталъный граф, порожденный двудольной затравкой.

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

Рассмотрим взвешенный предфракталышй граф GL - (VL, EL) порожденный двудольной затравкой Н = (W',W",Q), у которой \W\ = \W\~nl2,\Q\ = q.

Покрытием графа GL будем называть подграф х = (VL,EX) = [Dk}, Ех с El , каждая компонента Dk, к = 1,2,..., К, которого является деревом. Очевидно, что покрытие х = (V¡ ,EX) является остовным лесом графа GL.

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

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

F(x) = (F} (х), F2 (л), F3 (Х), Fa (Л)) (1)

F|W= Í>(e)->min, (2)

ее £,

где ^уу(е) - общий (суммарный) вес покрытия х;

F2(x) = |;t|—»min,

где - число компонент в покрытии х. F3 (х) = deg Dk —»min,

(4)

для всех к -I, К, где тах<1еду = с^.Е>£ - степень компоненты йк в

для всех к = 1, К, где \Ок\ - число вершин компоненты Эк в покрытии X •

Все критерии (см. (2)-(5)) векторно-целевой функхщи (1) имеют, конкретную содержательную интерпретацию.

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

Число компонент в покрытии х соответствует числу частей, на которые разделен основной проект. Чем менее раздроблен основной проект при его реализации, тем эффективнее процесс объединения и обобщения результатов на завершающем этапе выполнения этого проекта. Поэтому второй критерий (3) ВЦФ (1) направлен на уменьшение числа компонент в покрытии.

Некоторые учреждения при распределении работ (частей основного проекта) могут одновременно сотрудничать с несколькими предприятиями. В покрытии х степени вершин компонент Вк будут указывать на число учреждений сотрудничающих с учреждением, соответствующему данной вершине. Учреждения в таком широком сотрудничестве выступает и в качестве заказчиков, и в качестве исполнителя заказа. Как известно, чрезмерная загрузка предприятия, преобладающая над его производственными возможностями, сильно ухудшает качество предлагаемых услуги и производимых изделий. Критерий (4) ВЦФ (1) стремиться уменьшить максимальную среди степеней вершин каждой компоненты Т>к покрытия х, что обосновывается целесообразностью уменьшения количества сотрудничающих учреждений.

под-

покрытии х.

F4(*) = |Z)A|->iriin,

(5)

Вершины, соответствующие учреждениям и предприятиям имеющим тесные взаимоотношение, образуют компоненты йк покрытия х. Увеличение количества взаимосвязанных учреждений и предприятий работающих над одним заказом (частью основного проекта) понижает эффективность выполняемой работы. Число вершин (или ребер, на дереве число вершин отличается от числа ребер ровно на единицу) входящих в компоненты покрытия х уменьшаются до возможного минимума критерием (5) ВЦФ (I), что позволяет предполагать достижения эффективного сотрудничества между учреждениями, соответствующие вершины которых на предфрактальном графе объединены в компоненты Бк покрытия х.

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

Граф й - (У, Е) называется к -дольным, если множество его вершин

V • можно разделить на к непересекающихся подмножеств

V = } таких, что концы всякогб ребра <?е Е одновременно не принадлежат ни одному из этих подмножеств.

Теорема 2.1. Предфракталъный граф = {УС,Е1), порожденный

двудольной затравкой Н={У/'№,0), = |1У| = л/2-; является 21 -дольным графом.

Следствие 2.1.1. Предфракталъный граф Оь = (У1,Е1), порожденный множеством двудольных затравок Н = {#,} = {#|,#2,...,Яг}(

Т>2, является 21 -дольным графом.

Примечание 2.1. Доказательство теоремы 2.1 несет конструктивный характер, и поэтому дает алгоритм выделение всех 21 "долей" предфрактального графа порожденного двудольной затравкой.

На рис. 2.1 изображен предфрактальиый граф =(У3,Е3), порожденный полной двудольной 3-вершинной затравкой Н = (У/',№",()), 1^1 = 2, |1У"| = 2, смежность старых ребер которого в траектории не нарушается. Пунктирной линией очерчены вершины, образующие доли на графах (73 и Н.

Совершенное паросочетание графа б - это паросочетание, покрывающее все вершины графа С.

Теорема 2.2. Предфракталъный граф Оь = (Уь,Е1), порожденный двудольной затравкой Н = (№',№",(2), \\¥'\-\\¥"\ = п12, имеет совершенное паросочетание, если совершенное паросочетание можно выделить на его затравке Н = (\У\У",О).

Следствие 2.2.1. Предфракталъный граф вц = (У, ,ЕЦ), порожденный множеством двудольных затравок Н = {Н1}={Н1,Н2,—,ННТ),

Т>2, имеет совершенное паросочетание, если совершенное паросочета-ниеможно выделить на каждой его затравке Н, е Н, I = 1,2,...,Г.

Размер произвольного наибольшего паросочетания в графе С назы-

И'"

Н=(№,0)

03=(У3,£3)

ребра первого ранга ребра второго ранга ребра третьего ранга

Рис. 2.1

вается числом паросочетания (или реберное число независимости) графа й и обозначается и(С).

ТЕОРЕМА 2.3. Если на предфрактальном графе ={У1,Е1), порожденного двудольной затравкой Н = (№',№",О), ¡1У1 - ¡1^1 = п/2, существует паросочетание, то для его числа паросочетания справедли-

I-1 ¿-I

во двустороннее неравенство (И(Н))" < У (С,,) < (п/2)" .

Следствие 2.3.1. Для числа паросочетания предфрактального графа = (Уь,Е1), порожденного множеством двудопьных затравок Н = {#,}={//[,Я2,...,ЯГ,...,Нг), Т> 2, при условии, что на предфрак-тальном графе существует паросочетание, справедливо двустороннее

неравенство (у(Ят1П))"''' < У(С£).< \ где Ят,„ -затравка из

Н с наименьшим по числу ребер совершенным паросочетанием среди всех затравок Н,, а |Утах| - наибольшее число вершин среди затравок Н,.

Пусть Я = (IV,О) есть «-вершинный связный граф. Длина кратчайшей цепи, соединяющей пару вершин и, V е IV, называется расстоянием между вершинами и и V и обозначается через р(и,у). Заметим, что введенное таким образом расстояние удовлетворяет известным аксиомам Евклидовой метрики.

Для фиксированной вершины ие И7 величина е(и) = тахр(и,\>) на-

уеИ'

зывается эксцентриситетом вершины и е И7.

Максимальный среди вссх эксцентриситетов вершин графа Н =(№,£>) называется диаметром графа Н и обозначается через е?(#), т.е. с1{Н) = шах е(и).

не IV

Если пара вершин соединяется кратчайшей цепью длины

р{и,г) = (1{Н), то эта цепь называется диаметральной.

Радиус графа Н обозначается через г{Н) и вычисляется по формуле г{Н) = тш £"(/<).

неН'

Вершина и называется периферийной, если е(и) = <1(Н). Утверждение 2.1. Радиус и диаметр полного двудольного графа Н = равны, с1{Н) = г(Н) -2. Причем кратчайшая цепь соеди-

няющая две вершины из одного и того же подмножества вершин (XV' или V/*) является диаметральной (его длина равна двум), т.е. все вершины графа И - периферийные. <

Теоргмл 2.4. Для предфрактального графа = (У^Е^), порожденного полной двудольной затравкой Н = (И7',И'",£)), ¡IV= (IV"] = п!2,

смежность старых ребер которого в траектории не нарушается, диаметр определяется равенством = 41,-2.

ТЕОРЕМА 2.5. Для предфракталъного графа Оь = {У1,Е1), порожденного полной двудольной затравкой Н (У), = = л/2, смежность.старых ребер которого в траектории не нарушается, радиус определяется равенством г{Сгц) = 2Ь.

В третьей главе описаны и обоснованы три параллельных алгоритма аи а2 и аг построения некоторых решений многокритериальной задачи (1)-(5) 0 назначениях. Параллельный алгоритм от, - выделение совершен' кого паросочетания минимального веса (СПМВ), параллельный алгоритм - выделение остовного дерева минимального веса (ОДМВ) и парал-' лельн'ый алгоритм а3 - выделение остовного леса.

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

Рассмотрим взвешенный предфрактальный граф С1 = (У1,Е1) порожденный двудольной затравкой Я = (№',]¥",()), |И7/| = = ;г/2, , |<2] = «. и к процессоров р1,р2,...,рк.

АЛГОРИТМ «1

Теорема 3.1. Алгоритм ах выделяет совершенное паросочетание М - (К, Ем) минимального веса на предфрактальном (п, Ь) -графе Сь ~.(У1,Е1), порожденном двудольной затравкой Н = (У/',У/",(У),

= |И'"| = /г/2, = ц, если

Теорема 3.2. Вычислительная сложность параллельного алгоритма а, построения СПМВ на предфрактальном (п, Ь) -графе = {У1,Е1),

порожденного двудольной затравкой Н = (Ш',\У",(2), где = N = п1,

равна 0(Ып2).

Примечание 3.1. В классической теоретико-графовой постановке построение СПМВ на графах осуществляется алгоритмом Эдмондса, который используется в качестве процедуры в алгоритме аВычислительная сложность параллельного алгоритма о.х меньше вычислительной сложности алгоритма Эдмондса, в /V2 раз на предфрактальном («,£)-графе С[_=(У1,Е1).

Теорема 3.3. Временная слоэюность параллельного алгоритма а1, где имеется к процессоров pl,p2,...,pk, к = nL~l, равна 0(п3).

Примечание 3.2. Временная сложность параллельного алгоритма

ах меньше временной сложности алгоритма Эдмондса, в N2 • nL~2 раз.

Теорема 3.4. Временная сложность параллельного алгоритма (Хх, где используется г процессоров pl,p2,...,pr, 1 <г<к, к = nL~l равна

Примечание 3.3. Временная сложность параллельного алгоритма щ, где используется г процессоров р\,р2.....РГ, \<r<k, k = nL~l меньше временной сложности алгоритма Эдмондса, в rNn L~2 раз.

Теорема 3.5. Алгоритм сл выделяет покрытие xt = (VL, ЕХ{) на предфрактальном (n,L)-графе GL=(VL,EL), порожденным двудольной затравкой Н = {W',W",Q), оптимальное по третьему F3 (х,) и четвертому F4 (xt) критерию, и оцениваемое по первому

9L-i с< Fi(Xi) < QL~I и шорому)

АЛГОРИТМ а2

теорема 3.6. Параллельный алгоритм а2 выделяет ОДМВ Т = (VL, Ет) на предфрактальном (n,L) -графе GL={VL,EL), порожденный двудольной затравкой Н = (W',W",Q), Щ = \W"\ = п/2, \Q\ = q.

Теорема 3.7. Вычислительная сложность параллельного алгоритма а2, выделяющего ОДМВ Т = (VL, Ет) на предфрактальном (n,L) -графе Gl={Vl,El), порожденного двудольной затравкой Н = (W',W",Q), где \V,\ = N = nL,равна 0(Nn2).

Примечание 3.4. В классической теоретико-графовой постановке построение ОДМВ на графах осуществляется алгоритмом Прима, который используется в качестве процедуры в алгоритме а2. Сравнив вычислительную сложность алгоритма Прима с вычислительной сложностью параллельного алгоритма (Х2 на предфрактальном графе Gi, получим:

0(N2) < 0(Nn2). Вычислительная сложность алгоритма а2 меньше вычислительной сложности алгоритма Прима в и1'2 раз.

Теорема 3.8. Временная сложность параллельного алгоритма а2,

п1 -1

где имеется к процессоров р],р2,—,рк, к =-,равна 0(п2).

п-1

Примечание 3.5. Временная сложность параллельного алгоритма а2 меньше временной сложности алгоритма Прима, в раз.

Теорема 3.9. Временная сложность параллельного алгоритма а2,

где используется г процессоров р1,р2,...,рг, 1 <г<к, к=--- равна

п-1

Примечание 3.6. Временная сложность параллельного алгоритма

а2 где используется г процессоров р1,р2,...,р , 1<г<к, к= —--

п-1

меньше временной сложности алгоритма Прима, в гп!'~2 раз.

Теорема 3.10. Алгоритм а2 выделяет покрытие х2 - (У^, ЕХг) на

предфрактальном (п,Ь) -графе = (Уь ,ЕЬ), порожденным двудольной затравкой Н = (\У',\У",(2), оптимальное по второму критерию Гг (х2) и,

оцениваемое по первому ^(х2) ^ —третьему Р3(х2)<~-

и четвертому Рл(х2) = п1.

АЛГОРИТМ а3

Теорема 3.11. Параллельный алгоритм аг выделяет остовный лес Т* =(У1гЕТ*) на предфрактальном (п,Е)-графе — (У1,Е1), порожденный двудольной затравкой Н = (№'№",£>), \У/\ = |1У"| = п/2, |<2| = <7-

теорема 3.12. Вычислительная сложность параллельного алгоритма <23, выделяющего остовный лес = (УЬ,ЕТ„) на предфрактальном (п,Ь)-графе порожденного двудольной затравкой'

Н = где = И = п1, равна О(Ш).

Теорема 3.13. Временная сложность параллельного алгоритма а3, гдегшеется к процессоров р1,р2,...,рк, к - п1~х, равна 0(п2).

Теорема 3.14. Временная сложность параллельного алгоритма а2, где используется г процессоров р],р2,...,рг, 1<г<к, к = п1А равна

Теорема 3.15. Алгоритм а3 выделяет покрытие х3 = на

предфрактальном (п,Ь)-графе С1=(У1,Е1), порожденным двудольной затравкой Н = ,(}), оцениваемое по первому критерию

Г1 (х3)<(п~ 1 )(пв) , второму ^(.*3) = п1м, третьему (х3) < ^ и

четвертому Р4(х3) = п.

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

Различают два типа распознавания: явное и неявное.

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

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

Напомним, что цепь, звезда и цикл четной длины являются частными случаями двудольного графа. На рис. 4.1 представлены примеры таких графов: а) цепь, б) цикл, в) звезда. Причем звезда пример полного двудольного графа, у которого хотя бы одна из "долей" состоит из одной вершины (см. рис. 4.1 (б')).

Рис. 4.1. Примеры двудольных графов: а) цепь, б) цикл, в) звезда

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

АЛГОРИТМ у,

Цель применения алгоритма у1 к данному (2,1)-дереву £> = (V, Е) состоит в том, чтобы преобразовать £> в (2,1,-1)-дерево Д. Применительно к £> работа у1 состоит из К этапов, пронумерованных индексом к~1,2,...,К; К<Ь-1. В свою очередь, всякий этап (кроме последнего) состоит из подэтапов, пронумерованных индексами тск = 1,2,..., тк, где величина тк есть число висячих или квазивисячих цепей в дереве, которое представлено на вход алгоритма у1 к началу реализации этапа к.

Назначим каждому подэтапу щ =1,2.....тк, тк < , этапа к процессор р„к с соответствующим порядковым номером. Процессоры выполняют предписываемую им алгоритмом работу одновременно.

Теорема 4.1. Верхняя оценка вычислительной сложности алгоритма У\ распознавания графа Б = (У,Е) равна т(у1) < = 0(|У|1о§|У|).

Теорема 4.3. Алгоритм У\ для распознавания предфракталыюго (2,Ь) -дерева = , Еь) использует не более чем 21'1 процессоров.

Теорема 4.4. Временная сложность алгоритм уу распознавания предфрактального (2, Ь) -дерева = {УЬ,Е1), смеэюность старых ребер которого не нарушается, равна 0(Ь).

Следствие 4.4.1. Временная сложность алгоритм у2 распознавания предфрактального (2, Ь) -дерева не больше 0{Ь).

АЛГОРИТМ у2

Алгоритм у2 распознает предфрактальное (л, Ь) -дерево й, порожденное /г-вершинной связной звездой, т.е. Н состоит из одного элемента -звезды, |Н| = 1.

Алгоритм у2 состоит из Ь —1 этапов. Если данный граф й пред-фрактальный, то на очередном этапе г в текущем графе Ог+1 выделяются все затравки, состоящие из ребер ранга г +1, после чего каждая из этих затравок стягивается в вершину. И полученный в результате текущий граф Сг представляется на вход этапа г +1.

Каждой вершине V е Уг+1 дерева = (Уг+1, Ег+1), такой

чтос1е£у = л-1 или V = п-2, на текущем этапе алгоритма у2 назначаем процессор ру. Все процессоры {}, V е Уг+1 одновременно выполняют работу предписанную им алгоритмом у2 на этапе г.

Теорема 4.6. Верхняя оценка вычислительной сложности трудоемкости алгоритма у2 т(у2)< О(тЬ), где т = \Е\ - количество ребер рассматриваемого графа П = (У,Е).

Теорема 4.7. Проблема распознавания свойства предфрактально-сти данного графа С полиномиально разрешима алгоритмом у2 при выполнении следующих условий: граф й является (п,Ь) -деревом, порожденным п-вершинными затравками-звездами, п> 4.

Теорема 4.8. Алгоритм у2 для распознавания предфрактального II-

адического (п,Е)-дерева = (У1,Е[) использует не более чем {п-1)'~1 процессоров.

Теорема 4.9. Временная сложность алгоритма у2 распознавания предфрактального Л-одического (п,Ц -дерева равна 0(п1).

АЛГОРИТМ у3

Алгоритм у3, применяемый к (л.Е)-графу с циклической затравкой четной длины, состоит из Ь этапов, пронумерованных индексом /=1,2,...,/,.

Этап /6 {1,2,...,/.}состоит из 2м подэтапов. На каждом из этих подэ-тапов выделяется очередная затравка, после чего ее ребра окрашиваются.

Каждому подэтапу £0 этапа Ze{l,2,...,Z,} назначается процессор р^

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

Теорема 4.11. Всякий предфрактальный (п,Ь)-граф G=(V,E) с циклической затравкой четной длины распознается алгоритмом Уз с полиномиальной трудоемкостью 0(|£|£).

Теорема 4.12. Алгоритм у3 для распознавания предфрактального графа GL = (VL,EL) использует не более чем 2L~l процессоров.

Теорема 4.13. Временная сложность алгоритма у3 распознавания предфрактального (п, L) -графа GL = (Vr,EL) равна О (¡iL).

Ш.. Основные результаты диссертации

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

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

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

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

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

1. Кочкаров A.A., Салпагаров С.И., Кочкаров P.A. О количественных оценках топологических характеристик предфрактальных графов // Известия ТРТУ. Специальный выпуск. - Таганрог, 2004. - №8. -С. 298-301.

2. Павлов Д.А., Салпагаров С.И. Многокритериальная задача выделения маршрутов на предфрактальном графе // Известия ТРТУ. Специальный выпуск. - Таганрог, 2004. - № 8. - С. 303-304.

3. Казиев Р.Ш., Салпагаров С.И. Математическая модель информационного потока на предфрактальных графах// Материалы Российское Узбекского симпозиума "Уравнения смешанного типа и родственные

проблемы анализа и информатики". Тез. докл. - Нальчик: НИИ МПиА КБНЦ РАН, 2003. - С. 119-121.

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

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

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

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

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

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

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

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

12.Салпагаров С.И., Кочкаров A.M. Распознавание предфрактального графа, порожденного двудольной затравкой с равномощными долями// Материалы XXXIV научно-технической конференции по результатам работы профессорско-преподавательского состава, аспирантов и студентов за 2004 год. Ставрополь: СевКавГТУ, 2005. - С.

[З.Павлов Д.А., Салпагаров С.И. Оценка покрытия предфрактального графа кратчайшими простыми цепями // VI Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2004. - С. 15-17.

14.Тлябичева М.А., Салпагаров С.И. О полиномиальной разрешимости задач покрытия предфрактальных графов р-адическими деревьями// VI

Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2004. - С. 17-19.

\5.Салпагаров С.И. Параллельный алгоритм Соллина поиска остовного дерева // Успехи современного естествознания. 2003. - № 9. - С. 66-67.

16.Салпагаров С.И. Топологические и метрические свойства предфрак-тального графа, порожденной двудольной затравкой. Черкесск, К41ТА, 2004, Деп. в ВИНИТИ, № 1871-В2004. - 18 с.

П.Салпагаров С.И. Многокритериальная задача покрытия предфракталь-ного графа лесом. Черкесск, КЧГТА, 2004, Деп. в ВИНИТИ, № 1870-В2004. - 14 с.

САДПАГАРОВ Сослан-бек Исмаилович

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

АВТОРЕФЕРАТ

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

Опечатано с готового оригинал-макета на множительно-полиграфическом

участке КЧ1 ТА 369000, г. Черкесск, ул. Ставропольская, 36

JTtr?

s-

РНБ Русский фонд

2007-4 11194

• введение.

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

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

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

2. свойства предфрактального графа, порожденного двудольной затравкой.

2.1. О многодольности предфрактального графа.

2.2. Условие существования совершенного паросочетания на пред фрактальном графе.

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

2.4. Радиус и диаметр предфрактального графа.

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

• 3.1. Параллельные алгоритмы на графах.

3.2. Параллельный алгоритм а, выделения совершенного паросочетания минимального веса.

3.3. параллельный алгоритм аг выделения остовного дерева минимального веса.

3.4. Параллельный алгоритм аз выделения остовного леса, состоящего из пы компонент.

4. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРЕДФРАКТАЛЬНОГО ГРАФА, ПОРОЖДЕННОГО ДВУДОЛЬНОЙ ЗАТРАВКОЙ.

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

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

В первой главе описывается многокритериальная задача о назначениях (ЗН) на предфракталъных графах [1,2-5]. Наравне с этим строится математическая модель реализации крупного научно-исследовательского проекта.

Термином затравка условимся называть какой-либо связный граф Я = (Ж, 0. Для определения фрактального (предфракталъного) графа нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе (7 = (V, Е) у намеченной для замещения вершины уеК выделяется множество К = {уЛсК, у = 1,2,., V смежных ей вершин. Далее из графа О удаляется вершина V и все инцидентные ей ребра. Затем каждая вершина ^ еК, j = 1,2,., V , соединяется ребром с одной из вершин затравки Я = (Ж,0. Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости.

Предфрактальный граф будем обозначать через = (УЬ,ЕЬ), где Уь -множество вершин графа, а Еь - множество его ребер. Определим, его поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = 1,2,., Ь -1 графе 01 = (У/, Е1) каждую его вершину затравкой Я = (IV, 0. На этапе / = 1 предфрактальному графу соответствует затравка = Я. Об описанном процессе говорят, что предфрактальный граф = (У1,Е^ порожден затравкой Я = (IV, 0. Процесс порождения предфрактального графа , по существу, есть процесс построения последовательности предфрак-тальных графов называемый траекторией. Фрактальный граф О = (У, Е), порожденный затравкой Я = (IV, 0, определяется бесконечной траекторией.

Предфрактальный граф С1=(УЬ,Е1) условимся называть (и, графом, если он порожден «-вершинной д-реберной связной затравкой Я = (Ж, 0, и (п, Ь) -графом, если затравка Я = (РУ, 0 - регулярный граф.

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

I е {1,2,., этапе порождения, будем называть ребрами ранга I. Новыми ребрами предфрактального графа Оь назовем ребра ранга Ь, а все остальные ребра назовем - старыми.

Будем говорить, что предфрактальиый граф = , ) - взвешен, если каждому его ребру е^ е Еь приписано действительное число м?(е{1)) е (в1'1 а, в1АЬ), где / = - ранг ребра, а > 0, и в < -. Ь

Обобщением описанного процесса порождения предфрактального графа является такой случай, когда вместо единственной затравки Н используется множество затравок н = {Н(} = [Н{,Н2Н(,.,НТ}, Т>2. Суть этого обобщения состоит в том, что при переходе от графа к графу С/ каждая вершина замещается некоторой затравкой Н{ е Н, которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры.

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

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

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

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

ЗН потребует решения и на других уровнях: проблема выбора встанет на уровне отделов и сотрудников институтов.

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

Первый - каков граф (7, представляющий схему всевозможных взаимодействий между учреждениями, заказчиками и исполнителями? Очевидно структура этой схемы сложнее, чем "обычный" двудольный граф. Каждое учреждение, начиная с высшего уровня, решая поставленную перед ним задачу (т.е. выполняя заказ) устанавливает связи между исполнителями и заказчиками более низкого уровня. А поскольку между указанными учреждениями-исполнителями и учреждениями-заказчиками более низкого уровня схема взаимодействий есть двудольный граф, это верно для любых уровней учреждений, то граф Сг, отражающий общую схему возможных взаимодействий, обладает свойством самоподобия. Поэтому общая схема возможных взаимодействий между учреждениями различных уровней, принимающих участие в реализации научно-исследовательского проекта - есть предфрак-тальный граф, порожденный двудольной затравкой.

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

Рассмотрим взвешенный пред фрактальный граф Gh =(VL,EL) порожденный двудольной затравкой Н = (W',W",Q), у которой \W'\ = \W"\ = rill, е|=?

Покрытием графа GL будем называть подграф х = (VL, Ех) = {Dk }, Exc:El, каждая компонента Dk, к = 1,2,., К, которого является деревом. Очевидно, что покрытие х = (VL, Ех ) является остовным лесом графа GL.

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

Качество покрытия х на графе GL задается векторно-целевой функцией (ВЦФ) [6-18]: х) = (F, (х), F2 (х), F3 (Х), F4 (Х)) (1.4)

F\(x)= !>(<?)-> min, (1>5) ееЕх где Yjw(e) ~ общий (суммарный) вес покрытия х; ееЕх х) = л: -> шт,

1.6) где \х\ - число компонент в покрытии х. з (л:) = deg Вк -> тт,

1.7) для всех к = \,К, где maxdegv = degZ)¿ - степень компоненты йк в для всех к = 1,К, где \Ик| - число вершин компоненты Ик в покрытии

Все критерии (см. (1.5)-(1.8)) векторно-целевой функции (1.4) имеют конкретную содержательную интерпретацию.

Веса, приписанные ребрам предфрактального графа , призваны отражать "неэффективность" сотрудничества между учреждениями, которым соответствуют вершины - концы ребер. Наладить плодотворное сотрудничество между крупными предприятиями, ввиду их сильной конкуренции, труднее чем между более мелкими, поэтому вес ребер с ростом их рангов уменьшается. При такой интерпретации весов, приписанных ребрам предфрактального графа, целесообразно искать покрытие с наименьшим весом. Именно, это и сформулировано в первом критерии (1.5) ВЦФ (1.4).

Число компонента \х\ в покрытии л; соответствует числу частей, на которые разделен основной проект. Чем менее раздроблен основной проект при его реализации, тем эффективнее процесс объединения и обобщения результатов на завершающем этапе выполнения этого проекта. Поэтому второй критерий (1.6) ВЦФ (1.4) направлен на уменьшение числа компонента в покрытии.

Некоторые учреждения при распределении работ (частей основного проекта) могут одновременно сотрудничать с несколькими предприятиями. В покрытии х степени вершин компоненты Бк будут указывать на число учгейк покрытии я;. = ¿1-> ГШП ,

1.8) реждений сотрудничающих с учреждением, соответствующему данной вершине. Учреждение в таком широком сотрудничестве выступает, как и качестве заказчиков, так и в качестве исполнителей заказов. Как известно, чрезмерная загрузка предприятия, преобладающая над его производственными возможностями, сильно ухудшает качество предлагаемых услуг и производимых изделий. Критерий (1.7) ВЦФ (1.4) стремиться уменьшить максимальную среди степеней вершин каждой компоненты йк покрытия х, что обосновывается целесообразностью уменьшения количества сотрудничающих учреждений.

Вершины, соответствующие учреждениям и предприятиям имеющим тесные взаимоотношение, образуют компоненты Ик покрытия х. Увеличение количества взаимосвязанных учреждений и предприятий работающих над одним заказом (частью основного проекта) понижает эффективность выполняемой работы. Число вершин или ребер, на дереве (число вершин отличается от числа ребер ровно на единицу), входящих в компоненты Вк покрытия х уменьшаются до возможного минимума критерием (1.8) ВЦФ (1.4), что позволяет предполагать достижения эффективного сотрудничества между учреждениями, соответствующие вершины которых на предфрактальном графе объединены в компоненты Ик покрытия х.

Вторая глава посвящена свойствам и характеристикам предфракталь-ного графа [19-20], порожденного двудольной затравкой.

Граф £ = (У,Е) называется к -дольным, если множество его вершин V можно разделить на к непересекающихся подмножеств V = {V1 ,У2,.,Ук} таких, что концы всякого ребра ееЕ одновременно не принадлежат ни одному из этих подмножеств. теорема 2.1. Предфрактальный граф = (УЬ,ЕЬ), порожденный двудольной затравкой Н = О), = = и/2, является дольным графом.

Следствие 2.1.1. Предфракталъный граф Оь = (УЬ,ЕЬ), порожденный множеством двудольных затравок Н = {Н()= {Н1,Н2,.,Н(,.,НТ},

Т> 2, является 21 -дольным графом.

Примечание 2.1. Доказательство теоремы 2.1 несет конструктивный характер, и поэтому дает алгоритм выделение всех 21 "долей" пред-фрактального графа , порожденного двудольной затравкой.

Совершенное паросочетание графа (7 - это паросочетание, покрывающее все вершины графа Сг.

ТЕОРЕМА 2.2. Предфракталъный граф 01={у1,Еь), порожденный двудольной затравкой Н = (IV',¡¥",<2), = \ = п!2, имеет совершенное паросочетание, если совершенное паросочетание можно выделить на его затравке И = 0. следствие 2.2.1. Предфракталъный граф =(УЬ,Е1), порожденный множеством двудольных затравок Н = {Н(}= {Нх,Н2,—,Нп.,НТ), Т> 2, имеет совершенное паросочетание, если совершенное паросочетание можно выделить на каждой его затравке Н( е. Н, / = 1,2,.,Г.

Размер произвольного наибольшего паросочетания в графе (7 называется числом паросочетания (или реберное число независимости) графа О и обозначается.

Теорема 2.3. Если на предфрактальном графе Оь = (У1,Е1), порожденном двудольной затравкой Н = (]¥',)¥",О), = = л/2, существует паросочетание, то для его числа паросочетания о(Оь) справедливо двустороннее неравенство (и(Н))п < < (п/ 2)" . следствие 2.3.1. Для числа паросочетания предфракталъного графа 01 = (VI, Еь), порожденного множеством двудольных затравок Т>2, при условии, что на предфрактальном графе существует паросочетание, справедливо двустороннее неравенство (и(Нт[п ))" < о{01) < шах^—)п , где #т{п - затравка из н с наименьшим по числу ребер совершенным паросочетанием среди всех затравок Н,, а |Гтах| - наибольшее число вершин среди затравок Н(.

Пусть Н = (1¥,0 есть и-вершинный связный граф. Длина кратчайшей цепи, соединяющей пару вершин и,уе.1¥, называется расстоянием между вершинами и и V и обозначается через р(и,у). Заметим, что введенное таким образом расстояние удовлетворяет известным аксиомам Евклидовой метрики.

Для фиксированной вершины меЖ величина е(и) = шахр(м,у) называется эксцентриситетом вершины и е Ж.

Максимальный среди всех эксцентриситетов вершин графа Н = (IV, О) называется диаметром графа Н и обозначается через с1(Н), т.е. с/(#) = тах£(м). неЖ

Если пара вершин и,уе1¥ соединяется кратчайшей цепью длины р(и, у) = <Л(Н), то эта цепь называется диаметральной.

Радиус графа Н обозначается через г(Н) и вычисляется по формуле г(Н) = ттф). иеЖ

Вершина и называется периферийной, если е(и) = с1(Н).

УТВЕРЖДЕНИЕ 2.1. Радиус и диаметр полного двудольного графа Н = (Ж',]¥",0) равны, с!(Н) = г(Н) = 2. Причем кратчайшая цепь, соединяющая две вершины из одного и того же подмножества вершин (Ш' или IV") является диаметральной (его длина равна двум), т.е. все вершины графа Н — периферийные. А

ТЕОРЕМА 2.4. Для предфрактального графа = (У[^,Е1), порожденного полной двудольной затравкой Н ,]¥",0), = = и/2, смежность старых ребер которого в траектории не нарушается, диаметр определяется равенством с1(<Э1) = 4Ь — 2.

ТЕОРЕМА 2.5. Для предфракталъного графа = порожденного полной двудольной затравкой Я = = /7/2, см годность старых ребер которого в траектории не нарушается, радиус определяется равенством г{Ст1) = 2Ь.

В третьей главе описаны и обоснованы три параллельных алгоритма ах, а2 и аъ построения некоторых решений многокритериальной задачи

1)-(5) о назначениях [21-29]. Параллельный алгоритм ах - выделение совершенного паросочетания минимального веса (СГТМВ), параллельный алгоритм а2 - выделение остовного дерева минимального веса (ОДМВ) и параллельный алгоритм а3 - выделение остовного леса.

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

Рассмотрим взвешенный пред фрактальный граф (?£ = (У1,Е1) порожденный двудольной затравкой Я = \}¥'\ = = п!2, |б| = <7, и к процессоров рх, р2Рк .

АЛГОРИТМ ах

Теорема 3.1. Алгоритм выделяет совершенное паросочетание М = {у ,ЕМ) минимального веса на предфрактальном {п,Ь) -графе Оь=(У1,Е1), порожденном двудольной затравкой Н = (№',№",<2),

У'\ = = п/2,\()\ = д, если

ТЕОРЕМА 3.2. Вычислительная сложность параллельного алгоритма а1 построения СПМВ на предфрактальном {п,Ь)-графе = (У1,ЕЬ), порожденном двудольной затравкой Н О), где = Лг = и£, равна

0{Ип2).

Примечание 3.1. В классической теоретико-графовой постановке построение СПМВ на графах осуществляется алгоритмом Эдмондса, который используется в качестве процедуры в алгоритме Вычислительная сложность параллельного алгоритма а^ меньше вычислительной сложноу сти алгоритма Эдмондса, в N раз на предфрактальном (п, Ь) -графе ТЕОРЕМА 3.3. Временная сложность параллельного алгоритма где г1 -2 имеется к процессоров Р\,Р2>—>Рк> к = п ,равна 0(п ).

Примечание 3.2. Временная сложность параллельного алгоритма ах

1 / —1 меньше временной сложности алгоритма Эдмондса, в N • п раз.

Теорема 3.4. Временная сложность параллельного алгоритма а.\, где используется г процессоров р1,р2,.,рг, 1 <г<к, к = п1~1 равна о{- • ТУ • и2 .

• ^ У

Примечание 3.3. Временная сложность параллельного алгоритма ах, где используется г процессоров р1,р2,.,рг, 1 <г<к, к = п1'1 меньше временной сложности алгоритма Эдмондса, в гИп раз.

ТЕОРЕМА 3.5. Алгоритм а1 выделяет покрытие л^ =(У1,ЕХ1) на предфрактальном (п,Ь)-графе Оь = (У1,ЕЬ), пороэюденном двудольной затравкой Н = оптимальном по третьему /^(х!) и четвертому /^С*!)

Ь г I ап ^ . ч 1 оп критерию, и оцениваемом по первому в -<гх{хх)<и - и второ

2 2 му, Г2(х1)<^~.

АЛГОРИТМ а2

Теорема 3.6. Параллельный алгоритм а2 выделяет ОДМВ

Т - (Vl,Et) на предфракталъном (n,L)-графе GL = (VL,EL), порожденном двудольной затравкой И = (W',W\Q), \W'\ = \W"\ = п!2, \Q\ = q.

Теорема 3.7. Вычислительная сложность параллельного алгоритма а2, выделяющего ОДМВ Т = (VL,ET) на предфракталъном (n,L)-графе

Gl=(Vl,El), порожденном двудольной затравкой Н = {W',W,Q), где \VL\ = N = nL, равна 0(Nn2).

Примечание 3.4. В классической теоретико-графовой постановке построение ОДМВ на графах осуществляется алгоритмом Прима, который используется в качестве процедуры в алгоритме а2. Сравнив вычислительную сложность алгоритма Прима с вычислительной сложностью параллельного алгоритма а2 на предфракталъном графе GL, получим:

0(N ) < 0(Nn ). Вычислительная сложность алгоритма а2 меньше вычислительной сложности алгоритма Прима в nL~2 раз.

ТЕОРЕМА 3.8. Временная сложность параллельного алгоритма а2, где у I ~ 1 /->/ 2\ имеется к процессоров р\,р2,—,рк> к =-, равна и(п ). п-1

Примечание 3.5. Временная сложность параллельного алгоритма а2 г 2 меньше временной сложности алгоритма Прима, в Nn раз.

ТЕОРЕМА 3.9. Временная сложность параллельного алгоритма а2, где

7 nL~\ используется г процессоров p{,p2,.,pr, 1 <г<к, к =- равна п-1 o{--N-n2 . r j

Примечание 3.6. Временная сложность параллельного алгоритма а2 где используется г процессоров р1,р2,.,рг, 1 <г<к, к = —-- меньше п-1 временной сложности алгоритма Прима, в гп1~2 раз.

Теорема3.10. Алгоритм а2 выделяет покрытие х2 = (УЬ,ЕХ2) на предфрактальном (п, Ь) -графе Сь = (Уь ,ЕЬ), порожденном двудольной затравкой Н = (№\1¥",0), оптимальном по второму критерию Е2(х2) и, оцениваемом по первому Т7;(х2)<{п-\)Ъ^П^-третьему Р3(х2) <— и пв~ 1 2 четвертому /?4(х2) = п1.

АЛГОРИТМ аъ

Теорема 3.11. Параллельный алгоритм а3 выделяет остовный лес Т* ={У1,ЕТ*) на предфрактальном (п,Ь)-графе С1=(У1,Е1), порожденном двудольной затравкой Н = {\V\W\Q), = \Ш"\ = п!2, |б| = $. теорема 3.12. Вычислительная сложность параллельного алгоритма а3> выделяющего остовный лес Т* = (УЬ,ЕТ.) на предфрактальном (п,Ь)~ графе С1=(У1,Е1), порожденном двудольной затравкой Н = (№',\У,0), где ^ = # = п1, равна 0(Ш).

Теорема 3.13. Временная сложность параллельного алгоритма а3,

Т —1 О где имеется к процессоров р1,р2,---,рк> к = п , равна 0(п ).

Теорема 3.14. Временная сложность параллельного алгоритма а2, где используется г процессоров р1,р2,.,рг, \<г<к, к = п1~1 равна О

I }

N-п \г ;

Теорема3.15. Алгоритм а3 выделяет покрытие х3={У1,ЕХг) на предфрактальном {п,Ь)-графе = {УЬ,ЕЬ), порожденном двудольной затравкой Н = (}¥',IV",О), оцениваемом по первому критерию ^(хз) < (п-\)(пд)1~1, второму Г2{хъ) = п1~х, третьему Ръ{хъ)<— и четвертому (х3) = п.

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

Различают два типа распознавания: явное и неявное.

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

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

В дискретной многокритериальной оптимизации, несмотря на ее значительные достижения в области прикладной математики, использование параллельных алгоритмов является редкостью даже среди алгоритмов построения решений. Отчасти этот пробел восполняется в третьей главе настоящей диссертации. Появление же параллельных алгоритмов распознавания, описанных в четвертой главе, связано с исследованием предфрактальных графов. Самоподобие [30-33], - основное свойство предфрактальных графов, дает возможность распараллеливания алгоритмов распознавания.

АЛГОРИТМ п

Цель применения алгоритма у\ к данному (2,Ь)-дереву = состоит в том, чтобы преобразовать В в (2,Ь-\)-дерево Применительно к £> работа у\ состоит из К этапов, пронумерованных индексом к=\,2,.,К-, К<Ь-1. В свою очередь, всякий этап (кроме последнего) состоит из подэ-тапов, пронумерованных индексами жк=\,2,.,тк, где величина тк есть число висячих или квазивисячих цепей в дереве, которое представлено на вход алгоритма у1 к началу реализации этапа к.

Назначим каждому подэтапу лк =1,2 ,.,тк, тк < \У\, этапа к процессор рЛк с соответствующим порядковым номером. Процессоры выполняют предписываемую им алгоритмом работу одновременно. теорема 4.1. Верхняя оценка вычислительной сложности алгоритма У\ распознавания графа И = (У,Е) равна т{у\) ^ = .

Теорема 4.3. Алгоритм у1 для распознавания предфрактального (2,Ь) -дерева = (У1,ЕЬ) использует не более чем 21~1 процессоров.

Теорема 4.4. Временная сложность алгоритма у1 распознавания предфрактального (2, Ь) -дерева Бь =(У1,Е1), смежность старых ребер которого не нарушается, равна О(Ь).

Следствие 4.4.1. Временная сложность алгоритма у1 распознавания предфрактального (2, Ь) -дерева не больше О(Ь).

АЛГОРИТМ у2

Алгоритм у2 распознает предфрактальное (п,Ь) -дерево С, порожденное и-вершинной связной звездой, т.е. Н состоит из одного элемента - звезды, |н| = 1.

Алгоритм у2 состоит из Ь - 1 этапов. Если данный граф <7 предфрак-тальный, то на очередном этапе г в текущем графе выделяются все затравки, состоящие из ребер ранга г + 1, после чего каждая из этих затравок стягивается в вершину, и полученный в результате текущий граф Ог представляется на вход этапа г + 1.

Каждой вершине уеУг+1 дерева (7г+1 =(Уг+\, Ег+Х), такой чтос^у = и-1 или с^у = и-2, на текущем этапе алгоритма у2 назначаем процессор ру. Все процессоры {ру}, v6Fr+1 одновременно выполняют работу предписанную им алгоритмом у2 на этапе г.

Теорема 4.6. Верхняя оценка вычислительной сложности трудоемкости алгоритма у2 т(у2) <0(тЬ), где т = \Е\ — количество ребер рассматриваемого графа £> = (V, Е).

ТЕОРЕМА 4.7. Проблема распознавания свойства предфрактальности данного графа (7 полиномиально разрешима алгоритмом у2 при выполнении следующих условий: граф С является (п,Ь)-деревом, порожденным п-вершинными затравками-звездами, п > 4.

ТЕОРЕМА 4.8. Алгоритм у2 для распознавания предфрактального Яадического {п,Ь)-дерева ВЬ=(У1,ЕЬ) использует не более чем (п-\)1~1 процессоров.

Теорема 4.9. Временная сложность алгоритма у2 распознавания предфрактального Я-адического (п, Ь) -дерева равна 0{пЬ).

АЛГОРИТМ 73

Алгоритм 73, применяемый к (я,£)-графу с циклической затравкой четной длины, состоит из Ь этапов, пронумерованных индексом /=1,2,.,/,.

Этап / е {1,2,.,£}состоит из 2м подэтапов. На каждом из этих подэта-пов выделяется очередная затравка, после чего ее ребра окрашиваются.

Каждому подэтапу к0 этапа / е {1,2,.,/,} назначается процессор рко с соответствующим порядковым номером. Процессоры выполняют предписываемую им алгоритмом работу одновременно.

ТЕОРЕМА 4.11. Всякий предфракталъный (п,Ь)-граф С=(У,Е) с циклической затравкой четной длины распознается алгоритмом уъ с полиномиальной трудоемкостью 0(\Е\Ь).

Теорема 4.12. Алгоритм /3 для распознавания предфрактального графа Оь = использует не более чем 21~х процессоров.

Теорема 4.13. Временная сложность алгоритма у3 распознавания предфрактального {п, Ь) -графа Оь = , Еь ) равна 0{пЬ).

Основные результаты диссертации заключаются в следующем:

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

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

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

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

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

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

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

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

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

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

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

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

9. Вагнер Г. Основы исследования операций. М.: Мир, 1972.

10. Современное состояние теории исследования операций// Под. ред. Моисеева H.H. -М.: Наука, 1979.

11. Кофман А., Фор Р. Займемся исследованием операций. М.: Мир, 1966.

12. Перепелица В.А. К задаче о назначениях// Управляемые системы. Новосибирск: Ин-т матем. СО АН СССР, 1969. - Вып. 2. - С. 45 - 48.

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

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

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

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

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

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

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

20. Кочкаров A.M. Алгоритмические вопросы теории фрактальных графов// Диссертация на соискание ученой степени д.ф.-м.н. Черкесск: КЧТИ, 1998.

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

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

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

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

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

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

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

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

29. Божокин C.B., Паршин Д.А. Фракталы и мультифракталы. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.

30. Венцель Е.С. Исследование операций. Задачи, принципы, методология. -М.: Высш. шк., 2001.

31. Прейсон Дж.К.мл., Делл К. Американский менеджмент на пороге XXI века. М.: Экономика, 1991.

32. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении. М.: Дело, 2002.

33. Экономика предприятия (фирмы)// Под ред. Волкова О.И., Девяткина О.В. ML: ИНФРА-М, 2002.

34. Экономическая теория. Учебник// Под ред. Николаевой И.П. М.: Проспект, 1998.

35. Математика и кибернетик в экономике. Словарь-справочник. М.: Экономика, 1975.

36. Кобринский Н.Е., Майминас Е.З., Смирнов АД. Введение в экономическую кибернетику. М.: Экономика, 1975.

37. Сорос Дж. Алхимия финансов.-М.: ИНФРА, 1996.-416с.

38. Aharoni R. Konig's duality theorem for infinite bipartite graphs// J. London Math. Soc., 29,1984.

39. Hall Ph. On representatives of subsets// J. London Math. Soc., 10, 1935. P. 26 -30.

40. Haimos P.R., Vaughn H.E. The marriage problem// Amer. J. Math. 72, 1950.-P. 214-215.

41. Frobenius G. Uber zerlegbare Determinanten// Konig. Preuss. Akad. Wiss. XVIII, 1917.-S. IIA-211.

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

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

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

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

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

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

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

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

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

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

52. Kochkaro A., Perepelitsa V. Fractal Graphs and Their Properties// ICM 1998 Berlin, International Congress of Mathematicians, Abstracts of Short Communications and Posters.- P.347.

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

54. Уильяме K.JI. Многомерный подход к синтаксическому распознаванию образов. В кн. Кибернетический сборник. Новая серия, вып. 16. М.: Мир, 1979.-С.82-112.

55. Малинецкий Г.Г., Попов А.Б. Нелинейность . Новые проблемы, новые возможности. В кн. Новое в синергетике. Загадки мира неравновесных структур. М.: Наука, 1996. - С.95-164.

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

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

58. Горбунова Е.О. Формально-кинетическая модель бесструктурного мелкозернистого параллелизма // Сибирский журнал вычислительной математики. 1999. Т. 2. № 3. С. 239-256.

59. Бандман O.JI. Мелкозернистый параллелизм в вычислительной математике // Программирование. 2001. №4. С. 5-20.

60. Бочаров Н.В. Технологии и техника параллельного программирования // Программирование. 2003. №1. С. 5-23.

61. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.

62. Кузюрин Н.Н. Параллельный алгоритм для задачи о балансировке множеств. // Дискретная математика. 1991. Т.З. В.4. С. 153-158.

63. Bader D.A., Illendula А.К., Moret В.М.Е., Weisse-BernsteinN.R. Using PRAM algorithms on a uniform-memory-access shared-memory architecture. WAE 2001. LNCS 2141. 2001. P. 129-144.

64. Agbaria A., Ben-Asher Y, Newman I. Communication-processor tradeoffs in a limited resources PRAM. Algorithmica. 2002. № 34. P. 276-297.

65. МакконеллДж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002.

66. Metaxas P. Parallel Algorithms for Graph Problems. PhD dissertation, Dartmouth College, 1991.

67. Han K, Pan V. Y, ReifJ.H. Efficient parallel algorithms for computing all pair shortest paths in directed graphs. Algorithmica. 1997. № 17. P. 399-415.

68. King V., Poon Ch.K., Ramachandra V., Sinha S. An optimal EREW PRAM algorithm for minimum spanning tree verification. Information Processing Letters. 1997. №62. P. 153-159.

69. Sajith G., Saxena S. Optimal parallel algorithm for Brook's colouring bounded degree graphs in logarithmic time on EREW PRAM. Discrete Applied Mathimatics. 1996. № 64. P. 249-265.

70. Johnson D.B., Metaxas P. Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree. Algorithmica. 1996. № 16. P.633-648.

71. ChenZ.-Z., HeX. Parallel algorithms for maximal acyclic sets. Algorithmica. 1997. №19. P. 354-368.

72. Непомнящая А.Ш. Представление алгоритма Эдмондса для нахождения оптимального ветвления графа на ассоциативном параллельном процессоре // Программирование. 2001. №4. С. 43-52.

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

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

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

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

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

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

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

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

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

82. Павлов Д.А. Многокритериальная задача покрытия предфрактальных графов простыми цепями: Автореф. дис. . канд. физ.-математ. наук. Черкесск: Кар.-Чер. Гос. Технолог. Ак., 2004.

83. Батчаев. КЗ. Многокритериальная задача покрытия предфрактальных графов звездами ранговых типов: Автореф. дис. . канд. физ.-математ. наук. Черкесск: Кар.-Чер. Гос. Технолог. Ак., 2004.

84. Салпагарова A.A. Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах: Автореф. дис. . канд. физ.-математ. наук. Черкесск: Кар.-Чер. Гос. Технолог. Ин., 1998.

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

86. Кочкаров A.M. Эффективность алгоритмов решения экстремальных задач на графах с векторными и дробно-линейными критериями. Дис. . канд. физ.-математ. наук. Минск: БГУ, 1983.

87. Перепелица В.А. Вопросы Разработки и исследования алгоритмов нахождения множеств альтернатив для одного класса дискретных задач Дис. . док. физ.-математ. наук. Запорожье: Запорож. ГУ, 1988.

88. Павлов Д. А., Кочкаров A.A. Об одной многокритериальной задаче покрытия минимального веса предфрактального графа пересекающимися цепями. Препринт № 200. Нижний Архыз: Спец. астрофиз. обсерватория РАН, 2004.

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

90. Марголина А. Фрактальная размерность периметра роста. В сб. Фракталы в физике. М.:Мир, 1988. - С.507-512.

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

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

93. Салпагаров С.И. Параллельный алгоритм Соллина поиска остовного дерева// Успехи современного естествознания. 2003. № 9. - С. 66-67.

94. Салпагаров С.И. Топологические и метрические свойства предфрак-тального графа, порожденной двудольной затравкой// Рукопись Деп. в ВИНИТИ, № 1871-В2004. С.1 - 18.

95. Салпагаров С.И. Многокритериальная задача покрытия предфрактального графа лесом// Рукопись Деп. в ВИНИТИ, № 1870-В2004. С. 1-14.