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

Введение.

Глава 1. ФРАКТАЛЬНЫЕ ГРАФЫ. ОПРЕДЕЛЕНИЯ, СВОЙСТВА И

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

1.1. Предфрактальный и фрактальный графы.

1.2. Фракталы в природе, геофизике и модели на предфрактальных графах.

1.3. Свойства предфрактального графа.

Глава 2. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ГРАФА С

ПОЛНОЙ ЗАТРАВКОЙ 2.1. Распознавание (я,£)-графа с полной затравкой, если старые ребра не пересекаются.

2.2 Распознавание (л,1)-графа с пересекающимися старыми ребрами.

2.3. Проблема распознавания (/г£)-графа в условиях отсутствия информации о затравке.

Глава 3. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ДЕРЕВА

3.1. Распознавание предфрактального дерева, если затравка звезда.

3.2. Распознавание канонического предфрактального дерева с затравкой "ребро".

Глава 4. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ГРАФА С РЕГУЛЯРНЫМИ ЗАТРАВКАМИ

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

4.2. Распознавание предфрактального (и,£)-графа с регулярной затравкой степени s.

4.3. Распознавание предфрактального (д!)-графа с регулярной затравкой степени s > —.

Глава 5. ФРАКТАЛЫ. ФРАКТАЛЬНЫЕ ГРАФЫ И ИХ РАЗМЕРНОСТЬ

5Л. Фракталы и фрактальная размерность.

5.2. Триадная кривая Кох.

5.3. Полный фрактальный (г,/,/г)-граф и алгоритм его построения.

5.4. Определение фрактальной размерности полного фрактального {r,l,h)~графа при г=1=3.

5.5. Определение фрактальной размерности полного фрактального г,/,/г)-графа при г=1=4.

5.6. Определение фрактальной размерности полного фрактального (г,/,/?)-графа при г-1=т.

5.7. Определение фрактальной размерности полного фрактального (г,/,/г)-графапри

5.8. Определение фрактальной размерности полного фрактального (г,/,/?)-графа при гф1 и произвольном коэффициенте сжатия.

Глава 6. МЕТРИЧЕСКИЕ И ТОПОЛОГИЧЕСКИЕ ХАРАКТЕРИСТИКИ ФРАКТАЛЬНОГО И ПРЕДФРАКТАЛЬНОГО ГРАФА

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

6.2. Реберная раскраска и хроматический индекс предфрактальных и фрактальных графов.

6.3. Вершинная раскраска и хроматическое число предфракального и фрактального графа.

6.4. Число внутренней устойчивости предфрактального графа.

6.5. Число внешней устойчивости предфрактального графа.

6.6. Остовные деревья фрактального и предфрактального графа.

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

Моделирование - это один из важнейших методов научного познания, с помощью которого создается модель объекта исследования. "Модель" означает математическое описание содержательной задачи [5,24,13,16,17,42]. Ключом к успешному решению исходной содержательной задачи является, прежде всего, адекватность математического описания содержательной сути задачи. Математическое моделирование состоит во введении абстрактных математических характеристик изучаемого процесса и записи строгих соотношений между этими характеристиками, которые являются "оформлением" интуитивных, почерпнутых из опыта, наблюдения, здравого смысла [39]. Математическая модель поэтому - схема, всегда огрубление реальности. Сущность математических методов изучения реальных процессов -выявление однозначно трактуемых соотношений между характеристиками процесса, которые позволяют выводить из них формальные следствия, свойства, предсказывать развитие процесса. Цена, которую за это приходится платить, - огрубление процесса, его схематизация. Появление фрактальных (предфрактальных) графов [27,91-93, 95-99,101,103] является логически закономерным следствием стремления возможно более адекватно моделировать реальные технические, экономические, социальные явления и объекты с помощью математического аппарата теории графов. При этом получение бесконечного фрактального графа из конечного предфрактального графа означает (в терминологии [24,45,47]) превращение феноменологической модели в асимптотическую модель.

В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, 5 фрактальный граф [91-93,95-99] - это в конечном счете один из способов выявления некоторых качеств моделируемой системы. Причем по отношению ко всей исследуемой системе речь здесь идет о таких качествах, которые не выводимы прямо из свойств элементов системы и локальных взаимодействий этих элементов.

Сформулированный выше тезис асимптотического анализа как математического инструмента науки о качественном лишь частично раскрывает суть проблемы математического моделирования. Представляется уместным привести суть размышлений Бенуа Мандельброта - одного из основателей фрактальной геометрии (1984) [59]. "Почему геометрию называют холодной и сухой? Одна из причин заключается в ее неспособности описать форму дерева или систему кровеносных сосудов, зигзаг молнии или броуновскую траекторию частицы вещества и т.п. Молния не распространяется по прямой, у броуновской траектории отсутствует хотя бы намек на какую-либо регулярность или закономерность. Столь желательная (при построении модели) детерминированность отсутствует у системы кровеносных сосудов. Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности. Для этого (природного) уровня число различных масштабов длин в структурах всегда бесконечно. Существование этих структур бросает нам вызов в виде трудной задачи изучения тех форм, которые Евклид отбросил как бесформенные - это задачи исследования морфологии аморфного (хаотичного). Математики, однако, пренебрегли этим вызовом и предпочли все больше и больше отдаляться от природы, изобретая теории, которые не соответствуют ничему из того, что можно увидеть или почувствовать".

Для того чтобы упомянутый выше вызов был принят, нужно было дождаться того времени, когда в 70-е годы зародилась, а в 80-е годы 6 сформировалась "nonlinear science" ("нелинейная наука", или динамический хаос) - современная научная парадигма, т.е. новые стандарты научных исследований. Последняя своим появлением означает нынешнюю революцию в рамках междисциплинарного подхода, который, по предложению немецкого физика-теоретика Германа Хакена, стали называть синергетикой [12,18,26,59,66]. Как показывают исследования в [31], при размерности системы три и выше, в ее поведении появляется хаотическая составляющая, которая образуется в результате как внешних хаотических воздействий, так и внутренних (тепловое колебательное движение, броуновское движение и т.д.). Порядок во временном изменении - это уравновешенность взаимодействия, приводящая к устойчивому равновесию, синхронность движений отдельных частей системы, влекущая за собой периодическое движение всей системы в целом. Хаос во временном изменении - это отсутствие регулярности, нерегулярность, непредсказуемость и случайность. Пространственное проявление порядка - это пространственная регулярность- и согласованность. Пространственный хаос - это отсутствие пространственной регулярности и рассогласованность. До недавнего времени считалось, что порядок возникает из окружающего бесформенного хаоса и этот порядок можно узнать только по предсказуемой (детерминированной) структуре [18]. В настоящее время эту точку зрения вытесняет другая концепция хаотических явлений: они возникают согласно регулярным законам и за ними стоит не бесформенный хаос, а скрытый порядок - фрактальные структуры. И путь к пониманию сложных систем, явлений состоит в построении иерархий упрощенных моделей [18,30,31]. Фактически можно теперь говорить о сформировавшемся междисциплинарном подходе - синергетике [12,18,25,26]. Отметим, что для подавляющего большинства задач 7 естествознания возникающие в русле этого направления модели представляют собой автономные системы обыкновенных дифференциальных уравнений, зависящих от параметров [50].

К настоящему времени можно констатировать, что в синергетике удалось установить существование универсальных принципов и форм поведения для самоорганизующихся процессов применительно ко всем уровням организации природных и общественных систем. Эти универсальные закономерности проявляются в общности математического описания множества разных объектов в физике, биологии, химии, общественных науках. Синергетика родилась как результат попытки увидеть новый, более высокий уровень единства природы за уже необозримым количеством уравнений, задач [59].

В рамках новой парадигмы появилось математическое понятие фрактала (термин "фрактал" происходит от английского слова РКАСТюпАЬ - дробный) [8,18,25,47,50,52]. Важнейшим свойством фрактальных множеств является инвариантность их внутренней структуры: какую бы малую часть фрактала мы ни взяли, его структура будет одной и той же. Иными словами, фрактальные объекты самоподобны, т.е. их вид не претерпевает существенных изменений при разглядывании их через микроскоп с любым увеличением [18,47,50].

Старейшим" примером фрактального множества является график

00 функции Вейерштрасса: со$(Ьпш), а< 1, Ь> 1, аЪ> 1. График п> 1

IV(х) инвариантен относительно некоторого преобразования координат (растяжения в Ь раз вдоль оси абсцисс и На вдоль оси ординат) и обладает сложной внутренней структурой. В меньшем масштабе он выглядит так же, как и в крупном (см. [18], стр.144), т.е. какую бы малую часть фрактала мы ни взяли, его структура будет одной и той же. Если фрактал строится 8 с помощью вероятностных алгоритмов, тогда свойство самоподобия проявляется в статистическом смысле. Однако в последнее время подмечено, что необозримо широкий класс моделируемых задач имеет принципиально дискретную природу [2,3,13,14,22,33,36,42,70-91]. В случае дискретных систем разбиение движений на регулярные и хаотические характеризует только их временное поведение. В случае распределенных систем речь может идти не только о временном, но и о пространственном порядке и хаосе, о периодичности и апериодичности, регулярности и нерегулярности не только временной, но и пространственной структуры, в силу чего для адекватного описания соответствующих математических моделей аппарат дифференциально-интегрального исчисления не подходит. Более того, в физике, технике, химии, социологии, экономике и других областях возникают задачи, которые адекватно моделируются средствами теории графов [16,17,21,29,37,42,43,48]. Граф - это структура, состоящая из вершин и ребер. Каждая вершина обозначает какой-либо отдельный объект или часть его. Ребро показывает связь между отдельными объектами. Эта связь может быть направленной и иметь некоторую "длину". Таким образом, математическая модель дискретной системы, являющаяся графом, сильно формализирует исходную задачу, т.е. в полученной модели мы оперируем лишь терминами "вершина" (узел) и "ребро" (связь).

Отметим, что в то же время рассматриваемым задачам, моделируемых на графах, присущи все остальные свойства фракталов: самоподобие, дробная фрактальная размерность, масштабная инвариантность, а также признаки динамического хаоса в траекториях моделируемого процесса [7,27,44,47]. В физике соответствующие теоретико-графовые конструкции получили название "фрактальные графы" [21,27,29,43,48]. Однако используемый Мелроузом и другими 9 авторами иерархический фрактальный граф обладает тем недостатком, что введен с узкой целью, а именно для отражения иерархии связи с учетом варьируемой разветвленности [53].

В целом ряде случаев идеализация самоподобия может означать слишком большое упрощение моделируемого объекта. Тем не менее, такого рода идеализация неизмеримо увеличивает адекватность отражения объектов, которым присуща хаотичность структуры его устройства или поведения. В частности, благодаря ей удается отразить широко распространенный иерархический принцип организации [26,66]. При этом становится разрешимым вопрос о том, при каких условиях и в каких динамических системах может из хаоса возникнуть порядок [8,18,52].

К настоящему времени можно говорить о сложившейся теории пространственно-временного хаоса [18,50]. Однако если исследуемая система состоит из большого числа взаимодействующих между собой частей и поведение системы существенно зависит от структуры связей между этими частями, то необходимо учитывать это взаимодействие при построении модели. Таким моделям (объектам) присущ особый вид хаоса, связанный с невозможностью (или сложностью) точного описания всех существующих связей в каждый момент времени. Такой хаос мы будем называть структурным.

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

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

Структурные характеристики графа относятся к так называемым "определяющим параметрам" [18,59] в области техники, например в математических моделях, связанных с автоматизацией проектирования электронной техники. Определяющие параметры математических моделей имеют, скорее, не структурную, а "числовую природу" и требуют соответствующих адекватных подходов при исследовании их математических моделей. К настоящему времени для такого рода задач утвердились идеология и соответствующая методология векторного, т.е. дискретного многокритериального программирования [13,14,29,33,34,36, 56,57,62-65].

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

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

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

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

11 языка и теории автоматов для классификации объектов. Такие подходы обычно называются синтаксическими или лингвистическими методами распознавания образов [46]. Настоящая работа относится к другому подходу, который складывается в рамках так называемой "нелинейной науки" ("nonlinear science") [26]. Представленными выше результатами осуществлено выделение и конструктивное обоснование полиномиально разрешимого [9] класса задач распознавания свойства предфрактальности графов, полученных в процессе моделирования специфических объектов дискретной природы.

Также заметим, что весьма многочисленный список экстремальных задач [33,35,36,42] на графах представляет собой класс уУР-полных задач в смысле распознавания и, соответственно, класс iVP-трудных задач, с точки зрения дискретной оптимизации. Здесь уместно отметить, что, например, известная задача нахождения (распознавания) гамильтонова цикла становится полиномиально разрешимой на канонических предфрактальных графах с полной затравкой Н - (W, Q) в случае, когда старые ребра не пересекаются. Аналогичные утверждения справедливы и для других задач из этого списка. Снижение трудоемкости экстремальных задач на предфрактальных графах обусловлено тем, что на этих графах для некоторых задач, наряду со свойством самоподобия, появляется свойство наследственности.

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

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

Целью работы является создание теории фрактальных графов. Исследование проблемы распознавания предфрактальных графов. Разработка алгоритмов распознавания предфрактальности графов. Обоснование полиномиально разрешимых классов задач на предфрактальных и фрактальных графах. Исследование инвариантов, топологических и метрических свойств фрактальных и предфрактальных графов. Вычисление фрактальной размерности фрактального графа. Исследование наследственных свойств предфрактальных и фрактальных графов. Исследование предфрактального графа для математической постановки задач физики, техники, экономики.

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

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

Для получения свойств рассматриваемой теоретико-графовой модели сначала нужно определить, является ли данный граф предфрактальным? Поэтому осуществлена разработка серии алгоритмов, позволяющих распознать класс графов, которые могут являться предфрактальными при условии, что предполагаемая "затравка" есть полный «-вершинный граф. Отдельного исследования потребовал случай, когда затравка есть полный 2-вершинный граф, который не распознается с помощью алгоритма распознавания предфрактала с произвольной полной и-вершинной затравкой, п> 3. Сформулированы и доказаны теоремы и леммы, обосновывающие эффективную работу этих алгоритмов.

13

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

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

14

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

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

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

1. Новая теория фрактальных графов.

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

3. Полиномиальные алгоритмы распознавания.

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

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

6. Выделение класса полиномиально разрешимых задач на предфрактальных графах из множества ЫР-пошых задач на графах.

Апробация работы. Основные результаты диссертации докладывались на Всесоюзной конференции "Проблемы теоретической кибернетики" (Иркутск, 1985), на Республиканском семинаре по дискретной оптимизации (Киев, 1985), на Всесоюзной конференции "Проблемы теоретической кибернетики" (Горький, 1988), на VI Международном конгрессе "Математические методы в строительстве"

15

Плцен-Чехословакия, 1991), на Международной конференции "Проектирование автоматизированных систем контроля и управления сложными объектами" (Харьков, 1992), на IX Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1995), на Международной конференции "Применение компьютерных технологий в гражданском строительстве" (Ротердам, 1995), на Международной конференции "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики" (Нальчик, 1996), на Всероссийском симпозиуме "Математическое моделирование эколого-экономических систем" (Кисловодск, 1997), на II научно-практической конференции Карачаево-Черкесского технологического института (Черкесск, 1997), на II Всероссийском симпозиуме "Математическое моделирование эколого-экономических систем" (Кисловодск, 1998), на Международном коллоквиуме математиков IKJVÎ97 (Веймар, 1997), на Международном конгрессе математиков 1СМ'98 (Берлин, 1998), а также на заседаниях научных семинаров CAO РАН, ТГРУ, СГТУ и КЧТИ.

По теме диссертации опубликовано 28 научных работ, в том числе одна монография.

Объем и структура работы. Диссертация состоит из введения, шести глав. Она содержит 208 страниц и 14 рисунков. Список литературы включает 106 наименований.

1. Аселеродов З.М., Донец Г.А. Представление и восстановление графов. Киев: Наук. Думка, 1991.

2. Бакурова A.B., Перепелица В.А. Вероятностный анализ сложности и устойчивости для векторной задачи коммивояжера. //Докл. АН Украины, Сер. А.-1993.-№ 11.-С.80-84.

3. Бакурова A.B., Емеличев В.А., Перепелица В.А. Об устойчивости многокритериальных задач на системах подмножеств. //Докл. АН Беларуси. -1995. -Т. 39, №2-С.33-35.

4. Барышев Ю.В. Иерархическая структура Метагалактики. Обзор проблем. Астрофиз. исслед. (Изв. САО).-1981.-Вып.14.-С.24-43.

5. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование.-М.:Радио и связь, 1981.

6. Вышковский Г.Л., Ганапольский Л.З., Долгов A.M. и др. Нелинейные нестационарные системы.-М. Машиностроение, 1986.

7. Вишек М.И. Фрактальная размерность множеств. //Соросовский образовательный журнал. -1998. -№1.-С. 122-127.

8. Гласс А., Мэки М. От часов к хаосу: Ритмы жизни. -М.: Мир, 1991.

9. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.-М. Мир, 1982.Ю.Дегтяренко В.Н. Оценка эффективности инвестиционных проектов. -М.: "Экспертное бюро М", 1997.

10. Де Янг К. Эволюционные вычисления: новейшие достижения и нерешенные проблемы //Обозрение прикладной и промышленной математики.-1996.-Т.3, вып.5.-С.597-609.

11. ЕвинИ.Л. Синергетика искусства. -М.: 1993.199

12. Емеличев В.А., Перепелица В.А., Козырев В.А. Обзор некоторых проблем дискретной многокритериальной оптимизации. // Труды сем. по дискретной математике и ее прилож. М.: МГУ,1989.-С.13-17.

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

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

15. Еленин Г.Г., Синько М.Г. Математическое моделирование явления на поверхности.-М.:3нание, 1988.

16. Иваницкий Г.Р. Ритмы развивающихся сложных систем.-М.:3нание, 1988.

17. Курдюмов С.П., Малинецкий P.P., Потапов А.Б. Нестационарные структуры, динамический хаос, клеточные автоматы. В кн. Новое в синергетике. Загадки мира неравновесных структур.-М.:Наука, 1996.-С.95-164 .

18. Костша H.I., Алексеев A.A., Василик О.Д. Фшансове прогнозування : Методы та модели -К.: Товариство "Знания", КОО, 1997.

19. Костевич А .С., Лапко A.A. Теория игр. Исследование операций,-Минск; "Высшая школа". 1982.

20. Луис Э., Гинеа Ф., Флорес Ф. Фрактальная природа трещин.-В сб. Фракталы в физике.-М.Мир, 1988.- С.244-248.

21. Лебедев В. С. Фрактальная структура Вселенной. //Астроном. циркуляр.-1988.-№1553.-С.З-4.

22. Луккин Ф. Кластеризация во Вселенной.В сб. Фракталы в физике.- М.: Мир, 1988. -С.446-451 .

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

24. Мун Ф. Хаотические колебания.-М.: 1990.200

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

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

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

28. Мулен Э. Кооперативное принятие решений: Аксиомы и модели.-М.: Мир, 1991.

29. Никитенко О.В. Нерегулярная динамика. Интегрированные системы функций Барнсли (Barnsley's IFS), фрактальное восполнение //Проблемы управления и информатики.-1996.-№6-С. 108-122 .

30. Неймарк Ю.И., Ланда П.С., Стахостическое и хаотическое колебания. М.:Наука, 1987.-С422.

31. Нитман И., Даккор Ж., Стенли X. Когда вязкие "пальцы" имеют фрактальную размерность?-В сб. Фракталы в физике.-М.:Мир, 1988.-С.266-281.

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

33. Перепелица В.А., Сергеева Л. Н. Исследование разрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач //Кибернетика и системный анализ.-1996.-№2.-С.71-77.

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

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

36. Петухов С. В. Геометрия живой природы и алгоритмы самоорганизации. -М.:3нание, 1988.

37. Пьетронеро Л., Купере Р. Стохостический подход к крупномасштабной кластеризации материи во Вселенной.-В сб. Фракталы в физике.-М.: МирД988.- С.455-562.

38. Павловский Ю.Н. Декомпозиция моделей управляемых систем.-М.: Знание, 1985.

39. Попов Е.П. Теория нелинейных систем автоматического регулирования и управления. Учебн. пособие.-М.:Наука, 1988.

40. Растригин Л. А. Случайный поиск в эволюционных вычислениях.// Обозрение прикладной и промышленной математики.-1996.-Т.З.вып.6.-С.688-705.

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

42. Солла С. Разрушение нагруженных фрактальных деревьев. В сб. Фракталы в физике.-М.Мир, 1988.-С.256-259.

43. Смирнов Б. М. Фрактальные кластеры //Успехи физических наук.-1986. -Т. 149, вып. 2.-С.177-213.

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

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

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

47. Хармут X. Теория секвентного анализа. Основы и применения.-М.Мир, 1980.

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

49. Шустер Г. Детерминированный хаос. Введение.-М. Мир, 1998.

50. ШкурбаВ. В. Задача трех станков.-М.:Наука, 1976. 52.Эткинс П. Порядок и беспорядок в природе.-М. Мир, 1987.

51. Girlich Е., Perepelitsa V.A. and Sergeeva L.N. Vector Investor Problem and its Fractal Properties, Otto-von-Guericke-Universitat, Magdeburg, Preprint №49, 1997, pp. 1-39.

52. Einasto Jaan, Superclusters of galaxies: Fractal properties //Astron., Cosmol. and Fundam. Phys.: Proc. 3rd ESO-CERN Symp., Bologna, May 16-20,1988. Dordrecht etc., 1989, pp.231-234.

53. Einasto Jaan, Einasto Maret, Gramann Mirt, Mon. Notic. Roy. Astron. Soc.1989. -238, № 1. -pp.155-177 .

54. Emelichev V.A. and Perepeliza V.A. Complexity of Vector Optimization Problems on Graphs // Optimization, 22 (1991) 6, pp.903-918.

55. Emelichev V.A. and Perepelitsa V.A. On cardinality of the set of alternatives in discrete many-criterion problems, Discrete Mathematics and Applications, Vol. 2, №5, pp.461-471.

56. Feitzinger J. V., Galinski T. The fractal dimension of star-forming sites in galaxies // Astron. and Astrophys, 1987, 179, № 1-2, pp.249-254 .

57. HakenH. Synergetics, Springer, 1997.

58. Kozina G.L., Perepelitsa V.A. Interval Spanning Trees Problem: Solvability and Computational Complexity //Interval Computations, 1994, № 1, pp.42-50

59. Krypin Anatoly A., Einasto Jaan, Einasto Maret, Saan Enn /Mon. Notic. Roy. Astron. Soc. -1989. -237, № 4 . -pp.929-938 .203

60. Perepelitsa V.A., Kozina G.L. Interval Discrete Models and Multiobjectivity Comlexity Estimates // Interval Computation, 1993, -№1, pp. 51-59.

61. Perepelitsa V.A., Sergeeva L.N., Girlich E. Ressearch of solvability of vector optimization problems by means of the linear convolution algorithm. -1994, Preprint №7, pp. 1-39, Magdeburg, Otto-von-Guericke-Universitat Magdeburg.

62. Prigogin I. From Being to Becoming. W.H. Freeman and Co., 1980.

63. Takens F. Detecting Strange Attrakctor in Turbulence, Dynamical System and Turbulence, Berlin, Springer, 1981. (Lect.Notes in math.;Vol.7.). p.336.

64. Vicsek Т., Szaley A. S. Fractal distribution of galaxies modeled by a cellular-automation-type stochastic process // Phys. Rev. Lett, 1987, 58, № 26, pp.2818-2821 .

65. Wen Z., Deng Z.-G., Liu Y.-Z., Xia X.-Y. The fractal dimension in the large-scale distribution of galaxies with different luminosities. 1989. 219, № 1-2, pp. 1-6.

66. Кочкаров A.M. Многокритериальная задача покрытия графа цепями заданной длины. В сб. Математические вопросы исследования операций.-Минск:НИИ ЭМП. 1982,- С.42-49.

67. Кочкаров A.M. Двукритериальная задача покрытия графа цепями. IX Межреспубликанская конференция молодых ученых204Совершенствование метода планирования и повышения эффективности общественного производства". Тез. докл.- Минск: 1982.-С.144.

68. Кочкаров A.M. Многокритериальная задача покрытия графа цепями. //"Вест.Белорус. ун-та", сер.1, физ. мат. и мех., Минск, 1982., Деп. в ВИНИТИ, 30.06.82г. №3387-82, С. 1-17.

69. Кочкаров A.M. Парето-оптимальные решения многокритериальной задачи покрытия графа цепями. Минск, 1983г., деп. в Бел. НИИНТИ 02.06.83г., № 645 Бе-Д 83,- С. 1-13.

70. Кочкаров A.M., Перепелица В.А. Алгоритмы с оценками для задачи покрытия графа цепями. Минск, 1983г., деп. в Бел. НИИНТИ, 02.06.83г., № 646 Бе-Д 83, С.1-13.

71. Кочкаров A.M., Мартынова С.А., Перепелица В.А. Экспериментальный анализ приближенных алгоритмов покрытия графа цепями. Минск, 1983г. деп. в Бел.НИИНТИ, 02.08.83, №752 Бе-Д 83.-С.1-11.

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

73. Кочкаров A.M. Многокритериальная задача покрытия графа цепями . Математические методы в исследовании операций. Тез. докл. Международной конференции НРБ, София, 1983.-С.42-43.

74. Кочкаров A.M., Перепелица В.А. Задача оптимизации севооборота в многокритериальной постановке . Ставрополь, 1984 г. Деп. в ВИНИТИ, №7765-84 Деп., С.1-31.

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

76. Кочкаров A.M., Шунгаров Х.Д. Вероятностный анализ одной многокритериальной задачи покрытия графа звездами. Республиканский семинар по дискретной оптимизации. Тез. докл. 1985.,-Киев,- С.72-74.

77. Кочкаров A.M., Перепелица В.А. Статистическая эффективность алгоритмов для полиматричных задач покрытия графа цепями. Республиканский семинар по дискретной оптимизации. Тез. докл. 1985.-Киев.-С.88-90.

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

79. Кочкаров A.M., Перепелица В.А. Вероятностный анализ одной многокритериальной задачи теории графов. Всесоюзная конференция "Проблемы теоретической кибернетики."- Иркутск: ИГУ, 1985. С.74-75.

80. Кочкаров A.M., Перепелица В.А. Оценки сложности многокритериальных транспортных задач. Республиканский семинар по дискретной оптимизации. Тез. докл. Киев ИК АН СССР, 1985. С.88-89.

81. Кочкаров A.M., Перепелица В.А., Шунгаров Х.Д. Исследование эффективности одного быстрого алгоритма решения двукритериальной206задачи покрытия графа звездами // Известия АН БССР, серия физ.-мат. наук. 1986.-№5. -С. 117-122.

82. Кочкаров A.M., Перепелица В.А. К оценкам сложности нахождения множеств альтернатив для многокритериальных задач об остовных деревьях. Всесоюзная конференция "Проблемы теоретической кибернетики". Тез. докл. Ч.1.-Горький: ГГУ, 1988,- С.178-179.

83. Кочкаров A.M., Перепелица В.А. О покрытии графа лесами. Труды сем. по дискретной математике и ее приложения,- М.: МГУ, 1989.-С.282-283.

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

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

86. Кочкаров A.M., Перепелица В.А. Остовные деревья на фрактальном графе. Всероссийский симпозиум "Математическое моделирование эколого-экономических систем". Тез. докл. Кисловодск: КИЭП, 1997.-С.67-69.207

87. Кочкаров A.M. Фрактальные графы в секвентном анализе . II Всероссийский Симпозиум "Математическое моделирование и вычислительный эксперимент в естественных, гуманитарных и технических науках". Тез. докл. Кисдоводск: КИЭП, 1998.-С.50-52.

88. Кочкаров A.M. Задача о кликах на фрактальных графах . Республиканская конференция преподавателей и аспирантов КЧТИ. Черкесск: КЧТИ, 1997.-С.51-55.

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

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

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

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

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

94. Kochkarov A.M., Perepelitsa V.A. About the algorithms with estimates for multiorite real problems on the graphs. Mathematical methods in engineerind.I, Proceeding of 6 th International Conference, Plzen-Czechoslovakia, 1991, pp.223-230.

95. Kochkarov A. M. , Perepelitsa V. A. , Sergeeva L. N. Algorithm for covering of graph by forest of minimum weight. Computing in Civil and Building Engineering, Pähl & Wemer (eds), 1995, Balkema/Rotterdam/ Brookfield, pp.711-714.208

96. Kochkarov A. M., Popova L.V., Zinchenko O.A. Multicriteria problems of regulation when planning building processes . Internationales Kolloquium itber Anwendungen det Informatik and Mathematik in Arcfitektur and Bauwesen, Weimar, 1997, p.67.

97. Kochkarov Ahmat, Perepelitsa Vitaly, Fractal Graphs and Their Properties. ICM 1998 Berlin, International Congress of Mathematicians, Abstracts of Short Communications and Posters, p.347 .

98. Kochkarov Ahmat, Perepelitsa Vitaly, Theoretical-graph models of large-scale clustering of matter in the Universe. Bull. Spes. Astroph. Obs., 1998, 45, pp. 130- 134.