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

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

РГБ ОД

/ иг ?т

Зинченко Ольга Алексеевна

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

ДЕРЕВЬЯХ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Черкесск - 2000

л

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

Научный руководитель: доктор физико-математических

наук, профессор ПЕРЕПЕЛИЦА В.А.

Официальные оппоненты: доктор физико-математических

наук, профессор СЕМЕНЧИН Е.А.

кандидат физико-математических наук, доцент САВРУКОВА М.Н.

Ведущая организация: Институт информатики и проблем

регионального управления КБНЦ РАН г. Нальчик

Защита состоится «.29» 2000 г. в -// часов на

заседании диссертационного совета К 063.52.12 в Ростовском государственном университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, корп. 2 ЮГИНФО РГУ, к. 406.

С диссертацией можно ознакомиться в научной библиотеке РГУ по адресу: ул. Пушкинская, 148.

Автореферат разослан «25/» х/^УС_ 2000 г.

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

Совета К 063.52.12,

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

Старший научный сотрудник "* /Муратова Г.В./

/7062. 3 с Ы #

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

эффективного алгоритма.

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

программирования.

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

сельскохозяйственного водоснабжения, используя

теоретико-графовые модели и алгоритмы решения задачи об остовных деревьях в многокритериальной постановке. Дана оценка вычислительной сложности рассамтриваемой задачи. Рассмотрены 2-критериальные задачи об остовных деревьях, у ВЦФ которых первый критерий представляет собой весовой критерий вида М1ЫБим и М1ШАХ, а второй критерий является топологическим; построен

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

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

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

Практическая_ценность. При разработке

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 1996г.); на

Международном коллоквиуме по применению математики в архитектуре и строительстве (Веймар, 1997г.); на Международном конгрессе математиков (Берлин, 1998г.); на научных конференциях «Гагаринские чтения» (Москва, 1997г., 2000г.); на Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 1996, 1997, 1998, 2000гг.); на научно-практических конференциях КЧГТИ (Черкесск, 1995, 1997гг.) и научных семинарах кафедры прикладной математики и информатики КЧГТИ, г. Черкесск.

Публикации■ По теме диссертации опубликовано 15 работ.

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

СОДЕРЖАНИЕ РАБОТЫ

Во_введении обоснована актуальность темы

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

В главе 1 дано содержательное описание задачи проектирования оросительных систем (ЗОС) и представлена ее теоретико-графовая модель.

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

варианта ЗОС в полной мере можно отразить не одним, а целым рядом показателей или критериев, которые являются принципиально разнородными.

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

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

В §1.2 дана общая постановка векторной задачи об

остовных деревьях. Задан У1 -вершинный N-взвешенный граф т.е. граф Ст — (У,Е)1 в котором каждому ребру е&Е приписаны веса и\,(е)> 0, у = 1,2,....¿V . Множество допустимых решений (МДР) X = {х} состоит из остовных деревьев х = (V,ЕХ), Ех с Е. На МДР^ определена векторная целевая функция (ВЦФ):

= (1) состоящая из критериев вида М1ЫЭим ^(дг)=2>Лв)->1шп, у = (2)

ге£,

или из критериев вида М1ЫМАХ

Fy{x) = шах wv(e) -> min, v = JV, + 1,..., N . (3)

ee£x

При N>2 ВЦФ (1) - (3) определяет на МДРХ паретовское множество (ПМ) X с X . Искомым решением данной векторной задачи является так называемое полное

множество альтернатив (ПМА) ЛГ°„ Подмножество Х° с X называется ПМА, если его мощность l-V0; минимальна и при этом выполняется равенство F(Xa) = F(X), где

F(X') = {F(X) = (/?(*), F2(x), ..., FN(x)):x еГ} VI'cI

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

деревьях, у ВЦФ которых первый критерий -» min

представляет собой весовой критерий вида (2) или (3) , а второй критерий является топологическим: радиус и диаметр остовного дерева, которые условимся обозначать

соответственно через р{х) и число висячих вершин,

т.е. мощность | ^О) |, где Vx(x) = {v е V; öegxv = \] множество вершин степени 1; степень дерева W(x:) = шах degr v _ Т.о. получаем двукритериальную

задачу с ВЦФ

F(*) = (^(*),F2(*)), (4)

у которой Ff(x) представляет собой минимизируемый метрический критерий

Fx(х) е | Xw„(e), max wv(e)\, {5)

[es Е, ееЬ' J

а второй критерий является топологическим, т.е. .

F2(x) e -> max, PT(;t)-*min, ¡^(х)!->• minj. (6)

В §1.3 дана оценка вычислительной сложности задачи об остовных деревьях с ВЦФ (4)-(6), приведены оценки мощности ПМА. Приведены доказательства следующих теорем.

Теорема 1.1 Для всякой индивидуальной 2-

критериальной задачи об остовных деревьях с ВЦФ (4)-(б)

на П-вершинном графе для мощности ПМА Х° справедлива верхняя оценка

\Х°\йп-2, (7)

которая является достижимой.

Принято говорить, что задача с данной ВЦФ обладает свойством полноты, если для всякого ее МДР X можно указать такие значения параметров ее критериев (2)-(3),

при которых выполняются равенства Х°=X =X . Для рассматриваемой задачи об остовных деревьях устанавливаются достаточные условия, при которых имеет место свойство полноты. На основании этого получено

Утверждение 1.1. Если ВЦФ векторной задачи об остовных деревьях содержит пару критериев весового вида (2), то эта задача является труднорешаемой, более точно, вычислительная сложность нахождения ее ПМА

ограничена снизу величиной п" 2 .

Далее исследуется вычислительная сложность 2-критериальной задачи с ВЦФ (4)-(6).

Теорема 1.2 Проблема нахождения ПМА для каждой из 2-критериальных задач с ВЦФ (4)-(6) является NP-трудной проблемой.

Пусть M(n,R) = {G} - множество всех П- вершинных 1-взвешенных графов G = (V,Е) t у каждого из которых ребрам е&Е приписаны веса и> (е) Пусть

(р — <р (и) - медленно растущая функция, Jj^ <Р (") = °° , например ф (я) = In In In П .

п

Теорема 1.3 Если 7~j , то для почти

In п+ In In п + <р

каждого графа GeM(n,R) ПМА 2-критериальной задачи об остовных деревьях с ВЦФ (4)-(6) является

! Y0 - 1

одноэлементным, т.е. его мощность \л — 1 .

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

Сначала рассмотрены однокритериальные

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

дерева графа G . Приведены доказательства следующих лемм.

Лемма 2.1. Задача об остовном дереве с

максимизируемой ЦФ степени дерева

WО) -> тах, (2.1)

полиномиально разрешима.

Лемма 2.2. Задача об остовном дереве с ЦФ

р(х) -> min (2.2)

полиномиально разрешима.

Далее рассматривается 2-критериальная задача с

ВЦФ

F(x)=(F,(x),F2(x)), (2.4)

в которой первый критерий

F,(x) e-j w(x) = y\w(e) min, maxw(e)-> minf , (2.5)

l J

а второй критерий является топологическим F2(x) e{w(x) max, p(jc)-»min}. (2.6)

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

Пусть X - множество допустимых решений рассматриваемой задачи, X' - собственное подмножество множества X .

Лемма 2.4. Если X СX и парето-оптимальное для множества X решение то X1 является парето-

оптимальным решением и для подмножества X' .

Лемма 2.5. Справедливы два утверждения. 1) Решение

хк 6X(GS) является парето-оптимальным для

X(G,), X(Gs)c:X множества. 2) В множестве X(G,) элемент

представляет собой оптимум по критерию F2(x), т.е.

Из лемм 2.4 и 2.5 вытекает справедливость двух утверждений.

Следствие 1. Решение является парето-

оптимальным в множестве Xs/ т.е.

Лемма 2.6. Пусть для . нахождения ПМА двукритериальной задачи об остовных деревьях используется алгоритм ог°. Тогда для всякого графа GeMnl выполняется включение F(X°)c: F(X(cc0)).

Теорема 2.1. В случае рациональных весов ребер графа проблема нахождения ПМА двукритериальной задачи об остовных деревьях с ВЦФ (2.4)-(2.6) разрешима с

полиномиальной вычислительной сложностью т<0(пь).

В главе 3 рассматриваются регулярные деревья, т.е. такие деревья, в которых невисячие вершины имеют одинаковую степень. Дано индуктивное определение предфрактального и фрактального графа в связи с тем, что к этому классу относятся регулярные деревья. Приведено определение фрактального и предфрактального графов. Пусть й =(У,Е) - граф (конечный или

бесконечный) , где V - множество вершин графа, а Е -множество его ребер. Термином «затравка» будем называть связный И- вершинный граф Н = (}У,0), вершины которого в случае необходимости могут быть окрашены.

В качестве образующего (порождающего) правила введена и определена операция «замещение вершины

затравкой» (ЗВЗ). Операция ЗВЗ (замещения вершины е V затравкой Я = (И^,0) преобразует данный граф С — (У,Е) в граф, состоящий из множества вершин и

множества ребер

Определен поэтапный процесс построения

фрактального графа (ФГ), порождаемого одной и той же

затравкой Н. На этапе 5 = 1 в заданной затравке Н = (}¥,0) нумеруем вершины и ребра, если необходимо, то взвешиваем их и раскрашиваем. Полученный граф обозначим через

и назовем предфрактальным графом

(ПФГ) 1-го поколения; ребра е Е Е^ называем ребрами 1-

го поколения. ПФГ ¡-то поколения обозначим через .

Он получается в результате применения операции ЗВЗ к

ПФГ (/-1)-го поколения, т.е. к .

ПФГ С(/) называется (п,-графом, если у его П-вершинной затравки Н = (№,0) множество б состоит из

<7-|б|-~~—~ ребер. Более общим термином «(и,/)-граф»

называем всякий порожденный И-вершинной затравкой ПФГ ^-го поколения.

Показаны условия, при выполнении которых ПФГ представляет Р-адическое дерево, т.е. дерево, у которого всякая невисячая вершина v имеет степень degv = Р +1.

Процесс построения {п,Ь) - графа или более общего ПФГ является рекуррентным (рекурсивным) и означает, по существу, построение последовательности предфрактальных графов, которую будем называть траекторией: С<0=(Г(05£(0); / = 1,2,...,

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

Теорема 3.2 Всякий («, £)-граф С=(У,Е),

порожденный затравкой-ребром ( п — 2) является деревом,

у которого диаметр сЦ(Э)>2Ь—\1 где - диаметр

графа О .

Теорема 3.3 Для всякого предфрактального графа С? ранга Ь , порожденного затравкой-ребром, справедлива следующая оценка величины диаметра :

¿/(£7) < — 1, , которая является достижимой.

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

Указаны также верхние и нижние оценки для степени. Степень графа = (У,Е) обозначим через

5(0); 5(6) = тахс^у .

С

Утверждение 3.5. Для всякого (и,¿)-графа С, порожденного затравкой Н, справедливы оценки минимальной степени 50(Я) < 50(С?) < £80(Н) , причем верхняя и нижняя оценки достижимы.

В главе 4 рассмотрены задачи, возникающие при моделировании экономико-экологических систем сетевого типа, которые чаще всего формулируются в виде

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

связный граф (г = (У,Е) и некоторое число к >2 . Допустимым решением является всякое остовное дерево х = (И,Ех), ЕхсЕ, степень которого удовлетворяет ограничению degx = tn¡Dídegxv < к; Х-{х) - множество всех "допустимых решений. На МДР X определяется векторная

целевая функция F(_x) = ^Fl(_x),f'2(^),...,Fl/(_x)), состоящая из критериев вида MINSUM: F, (*) = Xwv(e) min' v = где

чйЕх

wv(e) - стоимость {или затраты) v-ro ресурса, расходуемого на создание объекта, представленного в модели ребром е .

В условиях многокритериальное™ (при N>:2)

классическое понятие оптимального решения, вообще говоря, отсутствует. Лицо, принимающее решение (ЛПР), осуществляет выбор наиболее целесообразного варианта

из паретовского множества X , определяемого в МДР X векторно-целевой функцией F(x~). Если при этом выборе считаются равносильными или эквивалентными всякая пара

X ,Х € X , удовлетворяющая равенству F{x') = F(*") , то в качестве искомого (математического) решения N-критериальной задачи является полное множество альтернатив.

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

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

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

(■? . Процедура построения этой цепи по существу представляет собой алгоритм линейной свертки, работающей по известному принципу «иди в ближайший». На заключительной стадии работы алгоритма непокрытые цепью вершины присоединяются к построенной цепи с учетом вышеуказанного ограничения на степени вершин. На этой стадии алгоритм также работает по принципу «иди в ближайший».

При выполнении определенных достаточных условий

алгоритм А является статистически эффективным, т.е. он почти всегда находит ПМА с полиномиальной

трудоемкостью. Строгому описанию указанных достаточных условий предпошлем обозначения: J(n, Я, АО = {о}

множество всех VI -вершинных графов С = (К. £), у

которых каждому ребру е £ Е приписаны N весов Ч(е) е {1,2,...,./?}; еп < (1п1пгс)4 - убывающая от п последовательность.' Тогда, в случае ограничения на степень с!е§.х<А:, к> 3, при выполнении неравенства

Я"

-—- для почти всех графов

2(к -\)(1 + £п)\п п

алгоритм А находит одноточечное ПМА X0 (мощность ¡Я'"| = 1) И- критериальных задач об остовных деревьях

ограниченной степени с трудоемкостью с(Л)£ О

( 2 Л п

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

алгоритма А — Ак для случаев, когда он находит остовное' дерево X степени degx < к .

4(1 + £п)1пи

Теорема 4.1. Если ° — ^ , то алгоритм А3

почти всегда выделяет остовное дерево степени 3 на П-вершинном вероятностном графе С„, ребра которого появляются с вероятностью Рис весом 1, т.е.

п—>оо

Теорема 4.3. -Если г 2.-———- то алгоритм

(к — 2)п

Ак почти всегда выделяет на вероятностном графе С?„ остовное дерево X с ограничением на степень его

вершин degХ<к, т.е. } = 1 .

„ (к-2)п

Теорема 4.4. Если Л ь ———-—— то для почти

2(А:-1)(1 + £„)1пи

всех графов из алгоритм А* находит на графе

N

С~{У,Е) с весами = одноточечное ПМА для N-

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

Следствие 4.1. Теоремой 4.4 выделен класс многокритериальных задач об остовных деревьях ограниченной степени, относительно которого принято говорить, что для него существует статистически эффективный алгоритм. Иными словами, при выполнении

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

В заключении сформулированы основные результаты работы, выносимые на защиту:

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

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

3. Выделен класс полиномиально разрешимых 2-критериальных задач об остовных деревьях, в которых один из критериев является топологическим. Доказана "полиномиальная разрешимость однокритериальных задач с критериями максимизируемой степени и минимизируемого радиуса.

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

5. Регулярное остовное дерево представлено как предфрактальное (фрактальное) дерево, проведены

исследования топологических характеристик

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

6. Даны оценки топологических характеристик остовного регулярного дерева предфрактального графа.

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

Основные результаты■ диссертации опубликованы в следующих работах:

1.3инченко O.A., Перепелица В.А., Узденова Ф.М. Формирование множества критериев эффективности для поддержки принятия решений при банковских инвестициях. В сб. тезисов докладов 1-ой научно-практической конф. Карачаево-Черкесского технол. института, Ч. 3. - К-ЧТИ: Черкесск, 1995. - с. 42-44

2.3инченко O.A., Перепелица В.А., Узденова Ф.М. .0 прямых методах поддержки принятия решений в условиях многокритериальности. «Математическое моделирование и компьютерные технологии». Материалы I междун. научн. симпозиума «Экономика и право - стратегии 3000», т. 4. Кисловодск: КИЭП, 1996. - с. 62-66

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

-математики и физики». - Нальчик: Ин-т ПМА РАН, 1996. -•с. 39-40

4.Зинченко O.A. Векторная задача " о регулярных остовных деревьях. Информ. бюллетень ассоциации матем. программирования №7. - Екатеринбург: УрО РАН, 1997. -с. 103-104

5.Зинченко O.A., Канищева C.B. Новые инварианты при моделировании сетевых объектов регулярными деревьями. «Математическое моделирование эколого-экономических систем». Материалы Всеросс. научн. симпозиума «Математическое моделирование и компьютерные

технологии», т.1. - Кисловодск: КИЭП, 1997. - с. 51-53

6.Зинченко O.A., Канищева C.B. Оценка для регулярных деревьев. Тез. докл. научн. конф. «XXIII Гагаринские чтения». - М.: МАТИ РГТУ, 1997. - с. 27-28

7.Zinchenko O.A., Kochkarov A.M., Popova E.V. Multicriteria problems of regulation when planning building processes. Abstracts of IKM (Internationales Kolloquium itber Anwendungen det Informatik and Mathematik in Arcfitektur and Bauwesen). - Weimar: Bauhaus University, 1997. - p. 67

8.Зинченко O.A., Винцер O.B. Экстремальные задачи об остовных деревьях с топологическими критериями. Тез. докл. II научн. конф. КЧТИ. - Черкесск: КЧТИ, 1997. -с. 33-37

9.Зинченко O.A., Борлаков Х.Ш., Урусова П.А. Экономико-математические методы и модели. - Черкесск: КЧТИ, 1997.

10. Зинченко O.A. Оценки сложности и вероятностный анализ векторной задачи об остовных деревьях. «Матем.

моделирование, и вычислит. эксперимент в естестр., гуманитарных и техн. науках». Тезисы докл. II Всеросс. научн. симпозиума «Матем. моделирование и компьютерные технологии», т.2. - Кисловодск: КИЭП,. 1998. - с.35-37

11. Зинченко O.A., Шурыгина C.B. К.алгоритмической проблеме нахождения регулярных деревьев. «Математика и ее прикладные аспекты». Тезисы докл. XXXVIII регион, конф. молодых ученых и студентов - Нальчик: КВГУ, 1998.

- с. 27-28

12. Zinchenko O.A. The extreme graphs problems. Abstracts of Short Communications and Poster Sessions International Congress of Mathematicians. - Berlin, 1998. - p. 356

13. Зинченко O.A. Об. NP-трудном классе векторных задач на графах. Черкесск, 1999. Деп. в ВИНИТИ, № 3103В 99, с. 1-28

14. Зинченко O.A. Декомпозиционный статистически эффективный алгоритм для векторной задачи об остовных деревьях ограниченной степени. «Матем. моделир. и выч. эксперимент в естеств., гуманитарных и техн. науках». Сб. научн. трудов IV Всеросс. симпозиума «Матем. моделир. и компьютерные технологии», т. 2, ч.1 Кисловодск: КИЭП, 2000. - с. 54-55

15. Зинченко O.A., Шапошникова О.И., Шурыгина C.B. Сравнительный анализ эффективности приближенных алгоритмов для задачи об остовных деревьях. Тез. докл. научн.. конф. «Гагаринские чтения 2000», М. : МАТИ, 2000.

- с.15-16

ВВЕДЕНИЕ.

Глава 1. ТЕОРЕТИКО-ГРАФОВАЯ МОДЕЛЬ ПРОЕКТИРОВАНИЯ

ОРОСИТЕЛЬНЫХ СЕТЕЙ И ОЦЕНКИ ЕЕ СЛОЖНОСТИ.

1.1. Содержательное описание задачи и соответствующая теоретико-графовая модель.

1.2. Общая постановка векторной задачи об остовных деревьях.

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

1.3. Оценка вычислительной сложности задачи об остовных деревьях.

1.3.1. Оценка мощности ПМА X для задач об остовных деревьях.

1.3.2. МР-трудная проблема нахождения ПМА для векторных задач об остовных деревьях.

Глава 2. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЙ КЛАСС ЗАДАЧ ОБ

ОСТОВНЫХ ДЕРЕВЬЯХ.

2.1. Полиномиальная разрешимость однокритериальных задач с топологическими критериями.

2.2. Полиномиальная разрешимость 2-критериальных задач, в которых один из критериев является топологическим.

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

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

3.2. Операция замещения вершин затравкой (ЗВЗ).

3.3. Порождение Р -адического дерева.

3.4. Фрактальное дерево.

3.4.1. Регулярное дерево.

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

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

3.6. Алгоритм замещения висячей вершины затравкой.

3.6.1. Индивидуальная задача выделения остовного дерева степени / < 4.

Глава 4. ДЕКОМПОЗИЦИОННЫЙ СТАТИСТИЧЕСКИ ЭФФЕКТИВНЫЙ АЛГОРИТМ.

4.1. Формулировка проблемы.

4.2. Описание алгоритма

4.3. Обоснование статистической эффективности алгоритма.

4.3.1. Выделение минимального связного остовного дерева со степенями вершин не более 3.

4.3.2. Выделение остовного дерева с ограничением на степени вершин.

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

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

Использование математического аппарата теории графов при расчете физических систем с сосредоточенными параметрами обязано принципу суперпозиции, реализованному и развитому в работах Киргофа (1847 г.), Максвелла (1892 г.), Крона (1957 г.) [60]. Этот принцип позволил эффективно декомпозировать (разбивать) систему и тем самым значительно уменьшать трудоемкость проводимых расчетов.

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

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

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

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

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

Химики различают, как известно, много видов молекул, например, звездообразные, гребнеобразные, сетчатые и т.д. [61].

Линейная гребнеобразная звездообразная

Рис. 1 деревообразная

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

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

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

Рис.2

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

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

На самом деле молекулы полимеров имеют сложное разветвленное строение и, как правило, мало напоминают дерево.

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

Рис.3

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

Алгоритм кодирования Фано имеет очень простую графическую иллюстрацию [2]. Граф для кода Фано строится следующим образом (рис.4) . Из нижней (корневой) вершины графа исходят два ребра, одно из которых помечено символом 0, другое -символом 1. Эти два ребра соответствуют разбиению множества сообщений на две вероятностные группы, одной из которых сопоставляется символом 0, а другой - символ 1. Ребра, исходящие из вершин следующего «этажа», соответствуют разбиению получившихся групп снова на равновероятные группы и т.д. Построение графа заканчивается, когда множество сообщений будет разбито на одноэлементные подмножества. Каждая концевая вершина графа, т.е. вершина, из которой уже не исходят ребра, соответствует некоторому кодовому слову. Чтобы указать это слово, надо пройти путь от корневой вершины до соответствующей концевой, выписывая в порядке следования по этому пути символы проходимых ребер.

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

Кодовое дерево может быть построено для кода с произвольным основанием б. Каждое его ребро помечается одним из б символов алфавита и из каждой вершины такого дерева исходит самое большее с! различных ребер [2].

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

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

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

Рис. 4 систему (ЭИС) отрасли, предприятия и т.д., которые называются объектами управления [64]. Экономическая информационная система создается для решения ее с помощью задачи управления объектом. Чем сложнее объект управления, тем сложнее его информационная система, поскольку для такого объекта необходимо ставить и решать более сложные задачи управления.

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

ПС21 пс:

ПС41 ф* ф ПС42 ф ПС34 ф ПС13 ф ПС25

II уровень

III уровень

IV уровень

I уровень

Рис. 5 Система и подсистемы

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

Задача о нахождении покрывающего дерева минимального веса имеет очевидную экономическую интерпретацию: п-городов нужно соединить сетью шоссейных дорог. Для каждой пары городов П и Г] (1< I < ] < п) известна стоимость р. (П , Г]) строительства соединяющих дорог требуется построить самую дешевую сеть дорог, не содержащую циклов, и такую, чтобы из любого города П можно было бы проехать в любой другой город Г].

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

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

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

Для хотя бы частичного разрешения проблемы вычислительной сложности предлагается использовать математический аппарат предфрактальных графов. Таким образом, в настоящей работе уделено внимание относительно малоизвестному математическому объекту, называемому термином «фрактальные графы». Появление фрактальных предфрактальных) графов является логически закономерным следствием стремления возможно более адекватно моделировать реальные геофизические, экономические, социальные явления и объекты с помощью математического аппарата теории графов. Предлагается использовать фрактальный граф и предфрактальный граф в том определении, которое впервые было сформулировано В.А. Перепелицей [29-33, 80, 81]

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

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

Научная новизна. Исследованы задачи об остовных деревьях в многокритериальной постановке, возникающие при проектировании оросительных систем и систем магистральных водопроводов для сельскохозяйственного водоснабжения и дана оценка их вычислительной сложности. Рассмотрены 2-критериальные задачи об остовных деревьях, у ВЦФ которых первый критерий представляет собой весовой критерий вида и М1ЫМАХ, а второй критерий является топологическим; построен статистически эффективный алгоритм, использующий принцип декомпозиции. Предлагается использовать в определении допустимого решения понятие предфрактального дерева. Получены верхние и нижние оценки радиуса и диаметра предфрактальных графов; формулы вычисления максимальной степени остовного предфрактального дерева на предфрактальном и фрактальном графе.

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

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

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

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

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

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

В 1.2 дана общая постановка векторной задачи об остовных деревьях. Задан п -вершинный N -взвешенный граф т.е. граф G = (VtE)t в котором каждому ребру е^Е приписаны веса wv(e)> О, v- l,2,.N. Множество допустимых решений (МДР) X - {х} состоит из остовных деревьев [11, 55] х = (V,EX\ Ех с Е. На МДРX определена векторная целевая функция (ВЦФ): F(x) = (F^x), F2(x)9 Fn(x)), (1) состоящая из критериев вида MfNSUM К(х)= v= 1,2, .,Nt, N,<N (2) ee£r или из критериев вида MINMAX ivOO = max wv(e) -» min, v = Nl +1,N (3) eeEx

При N >2 ВЦФ (1) - (3) определяет на МДРХ паретовское множество (ПМ) X с X [10]. Искомым решением данной векторной задачи является так называемое полное множество альтернатив

ПМА) Х°. Подмножество Х°с1 называется ПМА, если его мощность Х°\ минимальна и при этом выполняется равенство

Fix*) = F(X), где

F{T) = {F{X) = (FJx), F2(x), .,Fn(x)): кГ}УГс!

В этой главе представлены задачи об остовных деревьях с топологическими критериями. Рассматривается класс таких 2-критериальных задач об остовных деревьях, у ВЦФ которых первый критерий ^(л) mîn представляет собой весовой критерий вида (2) или (3), а второй критерий является топологическим: радиус и диаметр остовного дерева, которые условимся обозначать соответственно через р(х) и d(x) ; число висячих вершин, т.е. мощность I vx(x) |г где Ц(х) = {v е V; deg^v = l} - множество вершин степени 1; степень дерева W{x) = max degx v т.о. получаем двукритериальную задачу с ВЦФ

F(x) = (Ц(х% F2(x)X (4) у которой Fj(x) представляет собой минимизируемый метрический критерий

Y,wv(e\ maxwy(e) , /5ч ееЕг е х V а второй критерий является топологическим, т.е.

F2(x) е Jö?(.x)—» max, W(x)—> min, V^{x) minj. (6)

В 1.3 дана оценка вычислительной сложности задачи об остовных деревьях с ВЦФ (4)-(6), приведены оценки мощности ПМА. Приведены доказательства следующих теорем.

Теорема 1.1. Для всякой индивидуальной 2критериальной задачи об остовных деревьях с ВЦФ (4)-(6) на пвершинном графе для мощности ПМА справедлива верхняя оценка

Х°\ < и - 2, (7) которая является достижимой.

Принято говорить, что задача с данной ВЦФ обладает свойством полноты, если для всякого ее МДР X можно указать такие значения параметров ее критериев (2)-(3), при которых выполняются равенства х° = х = х. Для рассматриваемой задачи об остовных деревьях устанавливаются достаточные условия, при которых имеет место свойство полноты. На основании этого получено

Утверждение 1.1. Если ВЦФ векторной задачи об остовных деревьях содержит пару критериев весового вида (2), то эта задача является труднорешаемой, более точно, вычислительная сложность нахождения ее ПМА ограничена снизу величиной пп~2.

Далее исследуется вычислительная сложность 2-критериальной задачи с ВЦФ (4)-(6).

Теорема 1.2. Проблема нахождения ПМА для каждой из 2-критериальных задач с ВЦФ (4)-(6) является NP-трудной проблемой. Пусть M(rt,R) = {G} - множество всех «-вершинных 1взвешенных графов G = (V,E)t у каждого из которых ребрам ееЕ приписаны веса w(e)e{\,2Пусть q> = q>{ri) -медленно растущая функция, lim (р{п) = оо j например п—>СО ср (п) - In In In п. п

Теорема 1.3. Если R ^ п + \п\пп + (р > т0 Для почти каждого графа GeM(n,R) ПМА 2-критериальной задачи об остовных деревьях с ВЦФ (4)-(6) является одноэлементным, т.е. его мощность XQ\ = 1.

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

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

Лемма 2.1. Задача об остовном дереве с максимизируемой ЦФ степени дерева

W(x)^> шах, (2.1) полиномиально разрешима.

Лемма 2.2. Задача об остовном дереве с ЦФ р(х) -» min (2.2) полиномиально разрешима.

Рассматривается 2-критериальная задача с ВЦФ F(x) = (Fl(x),F2(x)), (2.4) в которой первый критерий а второй критерий является топологическим

F2(x) <={fF(x) -» max, р(х) -» min} . (2.6)

Для графа GeMnl введем обозначения: r = r(G) = {&,.,ps,.,pL} множество упорядоченных по убыванию значений весов wfe) ребер е еЕ; Es - множество всех ребер е еЕ, имеющих вес w2(e) = ps-Gr = (V,E{r))~ остовный подграф графа G, L состоящий из ребер, имеющих второй вес < рГУ т.е. E(r) = [}es .

8— Г

Считаем, что остовные деревья х е х подграфы вида Gr данного графа G существуют для индексов г < L, где li}<L.

Рассматривая двукритериальную задачу об остовных деревьях на данном графе G еМпа и его подграфа Gs, s=i,2t.il0t используем обозначения: Xs- множество всех таких решений этой задачи на Gsl которые оптимальны по критерию F2(x); Xs паретовское подмножество множества Х3. Для этой задачи на всяком графе С с непустым множеством остовных деревьев X справедлива лемма 2.3.

Лемма 2.3. Для каждого непустого хя, s < ц} мощность

Показано, что проблема нахождения ПМА для двукритериальной задачи об остовных деревьях с ВЦФ (2.4)-(2.6) разрешима с полиномиальной сложностью.

Пусть X - множество допустимых решений рассматриваемой задачи, X* - собственное подмножество множества X.

Лемма 2.4. Если ГсХ и парето-оптимальное для множества X решение ге(Гп1), то ^ является парето-оптимальным решением и для подмножества X'.

Лемма 2.5. Справедливы два утверждения. 1) Решение х1 является парето-оптимальным для Х(в5), Х(^) с I множества. 2) В множестве х(Оя) элемент представляет собой оптимум по критерию (л), т.е. х ® е X 4.

Из лемм 4 и 5 вытекает справедливость двух утверждений.

Следствие 2.1 Решение является парето-оптимальным в множестве х1 ехя.

Лемма 2.6. Пусть для нахождения ПМА двукритериальной задачи об остовных деревьях используется алгоритм а0. Тогда для всякого графа О еМнЛ выполняется включение с .

Теорема 2.1. В случае рациональных весов ребер графа проблема нахождения ПМА двукритериальной задачи об остовных деревьях с ВЦФ (7)-(9) разрешима с полиномиальной вычислительной сложностью т < 0(п5).

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

Приведено определение фрактального и предфрактального графов. Пусть 0 = (у,Е) - граф (конечный или бесконечный), где

V - множество вершин графа, а Е - множество его ребер. Термином «затравка» будем называть связный п - вершинный граф Н = О), вершины которого в случае необходимости могут быть окрашены.

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

Операция ЗВЗ (замещения вершины е V затравкой Н = (Ж,(?)) преобразует данный граф £ = (У,Е) в граф, состоящий из множества вершин и множества ребер

Определен поэтапный процесс построения фрактального графа (ФГ)> порождаемого одной и той же затравкой Н. На этапе ^ = 1 в заданной затравке # = (Ж,0 нумеруем вершины и ребра, если необходимо, то взвешиваем их и раскрашиваем. Полученный граф обозначим через С(1) = (¥{Г\Е{1}) и назовем предфрактальным графом (ПФГ) 1-го поколения; ребра е е Е(Г) называем ребрами 1-го поколения.

Пусть выполнены этапы в = 1,2,.,/ и получен ПФГ 1-го поколения С(/) = (У(1\Е(1}). На этапе 5 = /'+1 к каждой вершине V е К(0 применяется операция ЗВЗ, в результате чего получается ПФГ с(Му =(Уа+1у,Е(Му) (/ +1) -го поколения. Все новые» ребра в , составляющие подмножество (Е(М) - Е(1}) называются ребрами (/ + 1)-го поколения. При выполнении бесконечного (счетного) числа этапов (/ -»получаем фрактальный граф. Можно сказать, что фрактальный граф содержит ребра любого поколения /, / = 1,2,.

ПФГ С{1) называется (п,-графом, если у его п -вершинной затравки н = (Ж,д) множество д состоит из

Т1 — д=\0\<—-— ребер. Более общим термином «(п, /)-граф» называем всякий порожденный п -вершинной затравкой ПФГ 1-го поколения. Если необходимо подчеркнуть характер порождающей затравки Я, то используем термины: «(и,/) - граф с полной затравкой» (Я- полный граф), «(»,/) - граф с однородной затравкой» ( Я - однородный граф) и т.д

Показаны условия, при выполнении которых ПФГ Сг представляет Р -адическое дерево, т.е. дерево, у которого всякая невисячая вершина V имеет степень = Р +

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

0</> = / = (3.2) где индексом / занумерованы этапы построения ПФГ. Приведены доказательства следующих теорем:

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

Теорема 3.2. Всякий (щ £)-граф 0 = {УуЕ), порожденный затравкой-ребром (п = 2) является деревом, у которого диаметр 21 -1, где <}({}) - диаметр графа £.

Теорема 3.3. Для всякого предфрактального графа О ранга

Ь, порожденного затравкой-ребром, справедлива следующая оценка величины диаметра ^(С); ¿{О) < 2х -1, > которая является достижимой.

Рассмотрим случай, когда в траектории (3.2) при порождении предфрактального дерева первоначальные веса ребер затравок умножаются на коэффициент подобия, равный $ < 1.

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

Пусть фрактальное дерево порождается ^ -вершинными затравками t = l7Т и ^ = К. При этом коэффициент подобия определяется числом Я. Тогда справедлива I

Теорема 3.4. Если значение Я < —, то всякое прекдфрактальное или фрактальное дерево, порождаемое К затравками-звездами имеет ограниченный сверху вес.

Указаны также верхняя и нижние оценки для степени.

Утверждение 3.5. Для всякого (п, Ь) -графа С, порожденного затравкой Н, справедливы оценки минимальной степени

5r0(Я)<»Sf0(G)<Z5,0(Я), причем верхняя и нижняя оценки достижимы.

В главе 4. Рассмотрены задачи, возникающие при моделировании экономико-экологических систем сетевого типа, которые чаще всего формулируются в виде экстремальных задач на взвешенных графах. Одна из возможных математических постановок такой задачи формулируется следующим образом. Задан П -вершинный связный граф О = (У,Е) и некоторое число 2. Допустимым решением является всякое остовное дерево х = (У,Ех), ЕХ^Е1 степень которого удовлетворяет ограничению degx = maxdegху<с1\ Х = {х} - множество всех допустимых уеУ решений (МДР). На МДР X определяется векторная целевая функция (ВЦФ) /7(Х) = (х), Ь\ (х),., (х))( состоящая из критериев вида М^виМ: К(х) = XX (¿0 у = 1М, где щ(е) ееЕх

- стоимость (или затраты) у-го ресурса, расходуемого на создание объекта, представленного в модели ребром е.

В условиях многокритериальное™ (при N >2) классическое понятие оптимального решения, вообще говоря, отсутствует. Лицо, принимающее решение (ЛПР), осуществляет выбор наиболее целесообразного варианта из паретовского множества X [10], определяемого в МДР X векторно-целевой функцией Е(х). Если при этом выборе считаются равносильными или эквивалентными всякая пара хт,х" е X т удовлетворяющая равенству

Е{х) = Е{х"), то в качестве искомого (математического) решения

N -критериальной задачи является полное множество альтернатив (ПМА) [10].

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

При выполнении определенных достаточных условий алгоритм А является статистически эффективным, т.е. он почти всегда находит ПМА с полиномиальной трудоемкостью. Строгому описанию указанных достаточных условий предпошлем обозначения: У (л, я, ЛО = {с} - множество всех #-вершинных графов О = (У,Е), у которых каждому ребру е е Е приписаны N весов >1/,(е) е {1,2,.,/?}; еп < (1п1пя)-1 - убывающая от п последовательность. Тогда, в случае ограничения на степень йщх<с}, с1>3, при выполнении неравенства

R N ^ ———--— для почти всех графов G g J(n, R, N)

2{d - l)(l + sп)ш n алгоритм А находит одноточечное ПМА Xo (мощность jx°| = i) N -критериальных задач об остовных деревьях ограниченной степени с трудоемкостью о-(А) < о f 2 \ П v й j

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

А - Аа для случаев, когда он находит остовное дерево X степени degx< Й? .

4(1 + £„)\пп

Теорема 4.1. Если " - ~ , то алгоритм А3 почти всегда выделяет остовное дерево степени 3 на п -вершинном вероятностном графе г ребра которого появляются с вероятностью Р и с весом 1, т.е. Нт/^А"3}= 1. 2(с1-\)(\ + еп)Ъиг Ай Теорема 4.3. Если г>--' Т0 алгоРи™ ^ почти всегда выделяет на вероятностном графе Оп остовное дерево X с ограничением на степень его вершин degx<<i) т.е. ИтР{Кк}=1. ы - 2)п

Теорема 4.4. Если « ^ , 1Ч„-г.—, то для почти всех

2(й-1)(1 + ^)1пя графов из алгоритм А* находит на графе С = {У,Е) с N весами = одноточечное ПМА для N -критериальной задачи об остовных деревьях ограниченной степени.

28

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Регулярное остовное дерево представлено как предфрактальное (фрактальное) дерево, проведены исследования топологических характеристик предфрактальных деревьев. Описана схема построения предфрактального (фрактального) дерева.

113

6. Даны оценки топологических характеристик остовного регулярного дерева предфрактального графа.

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

1. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск: Наука, 1990.

2. Андреев В.Н. Иоффе А.Я. Эти замечательные цепи. -М: Знание, 1987 с. 150-156.

3. Аршинов М.Н., Садовский Л.Е. Коды и математика. -М: Наука, 1983-с. 21-23.

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

5. Аттаев А.Х. Задача оптимальной трассировки трубопроводной сети. В сб. науч. трудов САПР и АСПР в мелиорации. Нальчик, КБГУ, 1983.

6. Богданов A.A. Всеобщая организационная наука или тектология. -М.: 1913-1929. Т. 1-3.

7. Брейтон Р.К., Хетчел Г.Д., Санджовани-Витентелли А. Обзор методов оптимального проектирования интегральных схем. ЛГИ ИЗР. 1981.- Т. 69, № 10,- С. 180 - 215.

8. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. - Вып. 31. - с.35-42.

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

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

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

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

13. Зинченко O.A. Векторная задача о регулярных остовных деревьях. Информ. бюллетень ассоциации матем. программирования №7. Екатеринбург: УрО РАН, 1997. - с. 103-104.

14. Зинченко O.A., Канищева C.B. Оценка для регулярных деревьев. Тез. докл. научн. конф. «XXIH Гагаринские чтения». М.: МАТИ РГТУ, 1997. - с. 27-28.

15. Зинченко O.A., Винцер O.B. Экстремальные задачи об остовных деревьях с топологическими критериями. Тез. докл. If научн. конф. КЧТИ. Черкесск: КЧТИ, 1997. - с. 33-37 .

16. Зинченко O.A., Борлаков Х.Ш., Урусова П.А. Экономико-математические методы и модели. Черкесск: КЧТИ, 1997.

17. Зинченко O.A., Шурыгина C.B. К алгоритмической проблеме нахождения регулярных деревьев. «Математика и ее прикладные аспекты». Тезисы докл. XXXVIII регион, конф. молодых ученых и студентов Нальчик: КБГУ, 1998. - с. 27-28.

18. Зинченко O.A. Об NP-трудном классе векторных задач на графах. Черкесск, 1999. Деп. в ВИНИТИ, № 3103-В 99, с. 1-28.

19. Зинченко O.A., Шапошникова О.И., Шурыгина C.B. Сравнительный анализ эффективности приближенных алгоритмов для задачи об остовных деревьях. Тез. докл. научн. конф. «Гагаринские чтения 2000». М.: МАТИ, 2000. с. 15-16 .

20. Казиев В.M. О задаче комплектования графиков гидромодулей. В сб. науч. трудов САПР и АСПР в мелиорации. Нальчик: КБГУ, 1983.

21. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер // Успехи математических наук. 1985. - Т.40, №1 (241). - С. 107-173.

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

23. Кочкаров A.M., Перепелица В.А. Метрические характеристики фрактального и пред фрактального графа. // РАЕ CAO.-1999.-C.8-14.

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

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

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

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

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

29. Кудаев Б.Ч., Нахушева М.М. 2-оптимальное решение задачи синтеза сетей методом динамической декомпозиции / Доклады АМАН, 1999, т.4, №1, с. 15-20.

30. Кудаев В.Ч., Луценко Е.В., Алдошин В.И., Об одном подходе к автоматизированному проектированию оросительных насосных станций. В кн.: САПР и АСПР в мелиорации. Сборник научных трудов (межведомственный). Нальчик, 1983.

31. Кудаев В.Ч., Каров Х.М., Луценко Е.В., Хахо И.Х. Об одной задаче проектирования гидромелиоративной системы. В кн.: Перспективные методы планирования и анализа экспериментов. Тезисы докладов II Всесоюзной конференции, ч. II.-М., 1985.

32. Кудаев В.Ч., Аттаев А.Х., Байрактаров Б.Р. Задача трассировки оросительной сети. В кн.: Перспективные методы планирования и анализа экспериментов. Тезисы докладов III Всесоюзной конференции, ч. 2, М., 1988, - с. 121-123.

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

34. Ларичев О.И. Наука и искусство принятия решения. М.: Наука, 1979. - с. 200.

35. Липатов Е.П. Теория графов и ее применения. М: Знание, 1986 - с. 16-18.

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

37. Луценко Е.В. Задачи оптимального проектирования ЗОС. В сб. науч. трудов САПР и АСПР в мелиорации. Нальчик, КБГУ, 1983.

38. Магрупов Т.М. Графы, сети, алгоритмы и их приложения. Ташкент: Фан УССР, 1990. - с. 66-75.

39. Мальцев А.И. Алгоритмы и рекурсивные функции. -М.: Наука, 1965.-е. 298.

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

41. Моисеев H.H. Алгоритмы развития. М.: Наука, 1987.-е. 304.

42. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983.

43. Нахушева М.М. Метод динамической декомпозиции решения задач синтеза сетей и его приложения: Автореферат дис. .к.ф-м. н., Нальчик , 2000.

44. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. М.: Высшая школа, 1980.

45. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1983.

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

47. Перепелица В.А., Кочкаров A.M., Тамбиева Д.А. Теория графов и элементы комбинаторики. М.: Высшая школа, 1996.

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

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

50. Перепелица В.А. Асимптотический подход к решению некоторых экстремальных задач на графах // Проблемы кибернетики. 1973. - Вып. 26. - с.291-314.

51. Прикладные задачи теории графов. М: МЭИ, 1981. -вып. 556. - с. 17-20.

52. Применение теории графов связей в технике. М.: Мир, 1974.

53. Применение теории графов в химии. Новосибирск: Наука, 1988.

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

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

56. Полгородник Н.П. Применение математической логики и теории графов в обработке экономической информации. Киев, 1972 - с. 107.

57. Пригожин И.Р. Время, структура и флюктуации // Успехи физических наук. 1980. - т. 131, вып. 2. - с. 185-197.

58. САПР-СКГВХ (первая очередь). Автоматизированные технологические линии проектирования, разработанные в НИИ ПММ КБГУ, г. Нальчик, 1982.

59. САПР-СКГВХ (вторая очередь). Подсистемы, разрабатываемые в НИИ ПММ КБГУ, г. Нальчик, -1985.

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

61. Селютин В.А. Машинное конструирование электронных устройств. -М.: Сов. Радио, 1977.

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

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

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

65. Сотсков Ю.Н., Струсквич В.А., Танаев B.C. Математические модели и методы календарного планирования. Минск: Университетское, 1994. - с. 232.

66. Taxa X. Введение в исследования операций. В 2-х книгах. М.: Мир, 1985. - Кн. 1 - 438с., кн. 2-е. 496.7 б. Федер Е. Фракталы. М.: Мир, 1991. 7 7. Хармут X. Теория секвентного анализа. Основы и применения. - М.: Мир, 1980. - с. 576.

67. Шустер Г. Детерминированный хаос. Введение. -М.: Мир, 1988.-е. 240.

68. Design automation of digital systems, Vof. 1. Theory and techniques, Ed. by M.A. Breuer, Prentice-Half, Inc., Englewood Cliffs, New Jersey, 1972.

69. Русс, перев. Теория и методы автоматизации проектирования вычислительных систем. Под. ред. М. Брейера.-М.: мир, 1977.)

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

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

72. Kruskal J.B. On the shortest Spanning Subtree of a Graph and the traveling salesman problem // Proc. Amer. Math Soc. -1956.-Vol. 7.-p. 48-50.

73. Perepelitsa V.A., Sergienko I.V. Concerning the Problem to Find Sets of Alternatives in Discrete Multicriterial Problems / Kibernetika. -1987. № 5, p. 85-93.

74. Perepelitsa V.A., Pinchuk V.P., Sergeeva L.N., Pozdnjakova A.J. Fractal Graphs and their Properties. IKM'97, Digital Proceedings, Bauhaus Universität Weimar, 1997 (Word-Wide Web:http://www.uni-weimar.de/~ikm/index.html).

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

76. Zinchenko O.A., Kochkarov A.M., Popova E.V. Multicriteria problems of regulation when planning building processes. Abstracts of IKM (Internationales Kolloquium itber