Многокритериальная задача о назначениях на предфрактальных графах

• Автор: Салпагаров, Сосланбек Исмаилович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Черкесск
• Количество страниц: 106 с.

Содержание
ВВЕДЕНИЕ.

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

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

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

предфрактальном графе

2. СВОЙСТВА ПРЕДФРАКТАЛЬНОГО ГРАФА, ПОРОЖДЕННОГО ДВУДОЛЬНОЙ ЗАТРАВКОЙ.

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

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

предфрактальном графе

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

2.4. Радиус и диаметр предфрактального графа
3. АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ РЕШЕНИЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ НА ПРЕДФРАКТАЛЬНОМ ГРАФЕ.
3.1. Параллельные алгоритмы на графах.
3.2. Параллельный алгоритм а, выделения совершенного паросочетания минимального веса
3.3. параллельный алгоритм а2 выделения остовного дерева минимального веса
3.4. Параллельный алгоритм а3 выделения остовного леса,
состоящего из пы компонент
4. ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРЕДФРАКТАЛЫЮГО ГРАФА, ПОРОЖДЕННОГО ДВУДОЛЬНОЙ ЗАТРАВКОЙ.
4.1. Параллельный алгоритм у распознавания предфрактального графа, порожденного затравкой ребром
4.2. Параллельный алгоритм уг распознавания предфрактального графа, порожденного затравкойзвездой.
4.3. Параллельный алгоритм уз распознавания предфрактального графа, порожденного затравкой циклом четной длины
ЛИТЕРАТУРА


Рассмотренные в работе математические модели, методы многокритериальной оптимизации, алгоритмы построения покрытий с оценками и алгоритмы распознавания на предфрактальных графах, расширяют и дополняют существующие разработки в данной области, что подтверждает теоретическую значимость работы. Практическая ценность. Практическая ценность результатов работы определяется возможностью их применения при создании систем принятия решений. Построена математическая предфракталыю-графовая модель реализации научно-исследовательских проектов. Все исследованные модели и задачи, в случае реализации, способны повысить эффективность рассматриваемой системы. Тема исследований связана с некоторыми курсами лекций, читаемыми на факультете прикладной математики Карачаево-Черкесской государственной технологической академии. Полученные в работе результаты используются в учебном процессе. В первой главе описывается многокритериальная задача о назначениях (ЗН) на предфрактальных графах [1,2-5]. Наравне с этим строится математическая модель реализации крупного научно-исследовательского проекта. Термином затравка условимся называть какой-либо связный граф Я = (Ж,0. Для определения фрактального (предфракталъного) графа нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе О = (У, Е) у намеченной для замещения вершины V еУ выделяется множество V = {Vj}cV, у = 1,2,. Далее из графа С7 удаляется вершина V и все инци-дентные ей ребра. Затем каждая вершина Vj еУ, у = 1,2,. У, соединяется ребром с одной из вершин затравки Я -(IV,О). Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости. Предфрактальный граф будем обозначать через 0 = (Уь гДе ~ множество вершин графа, а Е1 - множество его ребер. Определим, его поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = 1,2,. I -1 графе С/ = (У/, Е1) каждую его вершину затравкой Я = (IV, 0. На этапе / = 1 предфракталыюму графу соответствует затравка 6^ = Я. Об описанном процессе говорят, что предфрактальный граф =(У1^Е[у) порожден затравкой Я = (1^,0. Процесс порождения предфрактального графа , по существу, есть процесс построения последовательности предфрактальных графов называемый траекторией. К,Я), порожденный затравкой Я = (7Г,0, определяется бесконечной траекторией. Предфрактальный граф 0 = (У1,ЕЬ) условимся называть (п^,Ь)-графом, если он порожден п -вершинной #-реберной связной затравкой Я = (IV,О), и (п,Ь)-графом, если затравка Я = (}У,0) - регулярный граф. Для предфрактального графа <5^, ребра, появившиеся на /-ом, / є {1,2этапе порождения, будем называть ребрами ранга І. Новыми ребрами предфрактального графа Є/, назовем ребра ранга Ь, а все остальные ребра назовем — старыми. Ь), где / = 1,? Обобщением описанного процесса порождения предфрактального графа является такой случай, когда вместо единственной затравки Н используется множество затравок Н = {#,} = {#,, Н2НТ}, Т > 2. Суть этого обобщения состоит в том, что при переходе от графа (? Н( є Н, которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры. ЗН в теоретико-графовой (классической) постановке сводится к поиску на двудольном графе паросочетаний, удовлетворяющих требованиям некоторых критериев. С появлением понятия фрактального (предфрактального) графа многие задачи математического программирования исследуемые аппаратом теории графов, ЗН в том числе, потребовали серьезной доработки, а нередко и совершенно новых методов для решения этих задач с постановкой на предфрактальных графах. В нашем случае, для ЗН, основная причина необходимости ее постановки на предфрактальных графах заключается в усложнении схемы всевозможных связей между заказчиками и исполнителями. Продемонстрировать это можно на примере крупного научно-исследовательского проекта. Любой крупный научно-исследовательский проект делится на части, и предлагается для реализации научно-исследовательским институтам (НИИ) и научно-производственным объединениям (НПО).