Содержание к диссертации
Введение
1. Многокритериальная задача покрытия предфрактального графа лесом 24
1.1. Фрактальные и предфрактальные графы 24
1.2. Многокритериальная постановка задачи о назначениях на предфрактальном графе 29
2. Свойства предфрактального графа, порожденного двудольной затравкой 35
2.1. О многодольности предфрактального графа 35
2.2. Условие существования совершенного паросочетания на предфрактальном графе 38
2.3. О числе паросочетания предфрактального графа 40
2.4. Радиус и диаметр предфрактального графа 42
3. Алгоритмы с оценками для решений задачи о назначениях на предфрактальном графе 49
3.1. Параллельные алгоритмы на графах 49
3.2. Параллельный алгоритм а, выделения совершенного паросочетания минимального веса 53
3.3. параллельный алгоритм 0 выделения остовного дерева минимального веса 58
3.4. Параллельный алгоритм аз выделения остовного леса,
состоящего из nL 1 компонент 64
4. Параллельные алгоритмы распознавания предфрактального графа, порожденного двудольной затравкой 69
4.1. Параллельный алгоритм у і распознавания предфрактального графа, порожденного затравкой -ребром 71
4.2. Параллельный алгоритм у2 распознавания предфрактального графа, порожденного затравкой-звездой 79
4.3. Параллельный алгоритм уз распознавания предфрактального графа, порожденного затравкой - циклом четной длины 85
Литература
- Многокритериальная постановка задачи о назначениях на предфрактальном графе
- Условие существования совершенного паросочетания на предфрактальном графе
- Параллельный алгоритм а, выделения совершенного паросочетания минимального веса
- Параллельный алгоритм у2 распознавания предфрактального графа, порожденного затравкой-звездой
Введение к работе
Достижения современной науки за последние десятилетия в области вычислительной техники позволили по-новому взглянуть на задачи дискретной математики и математического моделирования.
Нередко в математическом моделировании возникает необходимость проведения численного анализа или вычислительного эксперимента. Размерность задачи может потребовать больших ресурсов вычислительной техники, имея при этом ограничения по сроку получения результатов. Выходом из этой сложной ситуации могут послужить многопроцессорные системы {многопроцессорная среда, вычислительные кластеры).
Серьезным препятствием повсеместного внедрения многопроцессорных систем в различных областях науки, является разновидность их архитектур. Для достижения оптимального результата при использовании многопроцессорных вычислительных систем требуются специализированные языки параллельного программирования, а как следствие, и параллельные алгоритмы, реализуемые в выбранной многопроцессорной среде, имеющимся параллельным языком программирования.
Проблема создания параллельных алгоритмов особенно остро стоит в дискретной математике в целом, и теории графов в частности, как в областях математики, являющихся теоретической базой для информатики. Важно, чтобы создаваемые параллельные алгоритмы имели возможность реализации в различных многопроцессорных системах с различными параллельными языками программирования.
Уже отмечалось, что важным практическим приложением многопроцессорных систем является их возможность решения задач большой размерности. Но не редко, исследуемые задачи, объекты, данные и системы претерпевают определенные изменения. Эти изменения (случайные и/или строгие
по определенным правилам) в структуре данных должны учитываться при написании алгоритмов.
В основе многих дискретных математических моделей лежат графы, и более сложные объекты, фрактальные {предфрактальные) графы [1]. Фрактальные (предфрактальные) графы являются симбиозом графа, в его классическом понимании, и фрактала. Фрактальные (предфрактальные) графы отражают сложные структуры "растущие" с течением времени. Фрактальные (предфрактальные) графы описывают общую картину связей в многоэлементных системах, а поэтому часто имеют большую размерность.
В настоящей диссертационной работе на примере многокритериальной задачи о назначениях на предфрактальных графах продемонстрирована связь и переход от математической модели (реализации крупного научно-исследовательского проекта) сложной системы, с растущей по некоторому правилу структуре, к исследованию многокритериальной задачи, сформулированной при построении модели, и параллельным алгоритмам построения решений задачи и параллельным алгоритмам распознавания структуры самой системы.
Цель работы
Построение и исследование математической модели реализации крупного научно-исследовательского проекта, с последующим сведением ее к многокритериальной задаче о назначениях на предфрактальных графах.
Исследование свойств класса предфрактальных графов, возникающих в многокритериальной задаче о назначениях.
Построение параллельных алгоритмов нахождения решений исследуемой задачи. Построение параллельных алгоритмов распознавания структуры моделируемой системы. Обоснование реализации алгоритмов в многопроцессорных средах с различной архитектурой.
Методы исследования. Все исследования, проведенные в настоящей работе, используют методы и подходы дискретной математики, и теории графов, в частности. Аппарат теории графов наилучшим образом подходит
для формального представления задач связанных с изменением и преобразованием дискретных объектов, какими являются структуры систем. Кроме того используются методы когнитивного моделирования, связанные с анализом динамики нелинейных систем, развивающихся на предфрактальных графах. Используются методы нелинейной динамики, имитационного моделирования и теории фракталов.
Научная новизна. Исследование классической задачи о назначениях в многокритериальной постановке на предфрактальных графах.
Улучшения временной трудоемкости известных алгоритмов для нахождения решения классической задачи о назначениях на предфрактальных графах и построение новых параллельных алгоритмов.
Создание параллельных алгоритмов распознавания предфрактальных графов с возможностью их реализации в различных многопроцессорных средах.
Теоретическая значимость работы. Рассмотренные в работе математические модели, методы многокритериальной оптимизации, алгоритмы построения покрытий с оценками и алгоритмы распознавания на предфрактальных графах, расширяют и дополняют существующие разработки в данной области, что подтверждает теоретическую значимость работы.
Практическая ценность. Практическая ценность результатов работы определяется возможностью их применения при создании систем принятия решений. Построена математическая пред фрактально-графовая модель реализации научно-исследовательских проектов. Все исследованные модели и задачи, в случае реализации, способны повысить эффективность рассматриваемой системы.
Тема исследований связана с некоторыми курсами лекций, читаемыми на факультете прикладной математики Карачаево-Черкесской государственной технологической академии. Полученные в работе результаты используются в учебном процессе.
В первой главе описывается многокритериальная задача о назначениях (ЗН) на предфрактальных графах [1,2-5]. Наравне с этим строится математическая модель реализации крупного научно-исследовательского проекта.
Термином затравка условимся называть какой-либо связный граф Н = (W, Q). Для определения фрактального (предфракталъного) графа нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем. В данном графе G = (V, Е) у намеченной для замещения вершины veK выделяется множество V = {vj}czV, у = 1,2,..., V\,
смежных ей вершин. Далее из графа G удаляется вершина v и все инцидентные ей ребра. Затем каждая вершина v.- є V, j = 1,2,..., V , соединяется
ребром с одной из вершин затравки Н = (W,Q). Вершины соединяются произвольно (случайным образом) или по определенному правилу, при необходимости.
Предфрактальный граф будем обозначать через GL = (VL,EL), где VL -
множество вершин графа, a EL - множество его ребер. Определим, его поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = 1,2,..., L -1 графе G/ = (F/, Е1) каждую его вершину затравкой Н = (W, Q).
На этапе / = 1 предфрактальному графу соответствует затравка G{ = Н. Об описанном процессе говорят, что предфрактальный граф GL =(VL,EL) порожден затравкой Н = (W, Q). Процесс порождения предфрактального графа GL, по существу, есть процесс построения последовательности предфрактальных графов Gl,G2,...,Gl,...,GL, называемый траекторией. Фрактальный граф G = (V, Е), порожденный затравкой Н = (W, Q), определяется бесконечной траекторией.
Предфрактальный граф GL =(VL,EL) условимся называть (n,q,L)-графом, если он порожден «-вершинной g-реберной связной затравкой Н = (W, Q), и (п, L) -графом, если затравка Н = (W, Q) - регулярный граф.
8 Для предфрактального графа GL, ребра, появившиеся на /-ом, /g{1,2,...,L}, этапе порождения, будем называть ребрами ранга I. Новыми ребрами предфрактального графа GL назовем ребра ранга L, а все остальные ребра назовем - старыми.
Будем говорить, что предфрактальный граф GL =(VL,EL) -взвешен,
если каждому его ребру е^ є EL приписано действительное число
w(e(l)) є (в1~]а, в1АЬ), где / = \JL - ранг ребра, а> О, и в < -.
Обобщением описанного процесса порождения предфрактального графа GL является такой случай, когда вместо единственной затравки Н используется множество затравок Н = {Н(} = {Н{,Н2,—,Ht,...,НТ}, Г > 2. Суть этого обобщения состоит в том, что при переходе от графа Gt_x к графу G/ каждая вершина замещается некоторой затравкой Ht є Н, которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры.
ЗН в теоретико-графовой (классической) постановке сводится к поиску на двудольном графе паросочетаний, удовлетворяющих требованиям некоторых критериев. С появлением понятия фрактального (предфрактального) графа многие задачи математического программирования исследуемые аппаратом теории графов, ЗН в том числе, потребовали серьезной доработки, а нередко и совершенно новых методов для решения этих задач с постановкой на предфрактальных графах.
В нашем случае, для ЗН, основная причина необходимости ее постановки на предфрактальных графах заключается в усложнении схемы всевозможных связей между заказчиками и исполнителями. Продемонстрировать это можно на примере крупного научно-исследовательского проекта.
Любой крупный научно-исследовательский проект делится на части, и предлагается для реализации научно-исследовательским институтам (НИИ) и научно-производственным объединениям (НПО). Часто эти учреждения не в
состоянии справиться с поставленными задачами в одиночку, и поэтому выбирают среди всевозможных учреждений аналогичного профиля наиболее полезные с точки зрения сотрудничества. Выбор учреждений для сотрудничества - есть решение классической задачи о назначениях, т.е. выделение па-росочетании на двудольном графе, отражающем всевозможные связи между учреждениями этого, высшего уровня.
Каждое из учреждений высшего уровня делит свою часть проекта и распределяет по ведомственным или проектным институтам, т.е. учреждениям более низкого по масштабам выполняемой работы уровня. Всем этим учреждениям приходится искать удовлетворяющие поставленным требованиям учреждения для сотрудничества уже из своего уровня, т.е. снова решать ЗН.
ЗН потребует решения и на других уровнях: проблема выбора встанет на уровне отделов и сотрудников институтов.
Предложенное описание фактической реализации крупного научно-исследовательского проекта путем разделения его на более мелкие проекты (заказы) поднимает два важных вопроса.
Первый - каков граф G, представляющий схему всевозможных взаимодействий между учреждениями, заказчиками и исполнителями? Очевидно структура этой схемы сложнее, чем "обычный" двудольный граф. Каждое учреждение, начиная с высшего уровня, решая поставленную перед ним задачу (т.е. выполняя заказ) устанавливает связи между исполнителями и заказчиками более низкого уровня. А поскольку между указанными учреждениями-исполнителями и учреждениями-заказчиками более низкого уровня схема взаимодействий есть двудольный граф, это верно для любых уровней учреждений, то граф G, отражающий общую схему возможных взаимодействий, обладает свойством самоподобия. Поэтому общая схема возможных взаимодействий между учреждениями различных уровней, принимающих участие в реализации научно-исследовательского проекта - есть предфрак-тальный граф, порожденный двудольной затравкой.
Второй - какой суграф, удовлетворяющий условиям ЗН, является решением ЗН на предфрактальном графе? Ошибочно предполагать, что решением, как и в классической постановке, являются только лишь паросочета-ния. На предфрактальном графе ребра, отвечающие за связи между учреждениями высоких уровней, могут пересекаться с ребрами, отвечающими за связи между учреждениями более низких уровней. Наличие таких пересечений среди ребер различных рангов в покрытии (суграфе) предфрактального графа не противоречит основным требованиям ЗН в силу того, что отдельно взятое учреждение, относительно учреждений своего уровня может выступать как заказчик, в то время как относительно учреждений другого уровня может выступать в качестве исполнителя. Таким образом, искомым решением ЗН на предфрактальном графе является остовный лес. Напомним, что остовный лес - это несвязный суграф, каждая компонента которого дерево. Важно, что па-росочетания также удовлетворяют определению остовного леса.
Рассмотрим взвешенный пред фрактальный граф GL =(VL,EL) порожденный двудольной затравкой Н = (W',W,Q), у которой \W\ = \W"\ = п/2,
|е|=«-
Покрытием графа GL будем называть подграф x = (VL,Ex) = {Dk}, ExqzEL, каждая компонента Dk, к = 1,2,...,К, которого является деревом. Очевидно, что покрытие х = (VL, Ех ) является остовным лесом графа GL.
Всевозможные покрытия {х} предфрактального графа GL образуют множество допустимых решений X = X(GL) = {х} (МДР).
Качество покрытия х на графе GL задается векторно-целевой функцией (ВЦФ) [6-18]:
F(x) = (F, (*), F2 (*), ^з (х), ^4 (*)) (1.4)
Fl(x)= >( min, (1.5)
eeEx
где Y,w(e) ~ общий (суммарный) вес покрытия х;
ееЕх
F2(jc) = |x|->min, (1.6)
где \х\ - число компонент в покрытии х.
F3 (х) = deg Dk -» min, (1.7)
для всех к = \,К, где maxdegv = degZ) - степень компоненты Dk в
veDk
покрытии я;.
F4(x) = \Dk\->mm, (1.8)
для всех к = \,К, где \Dk\ - число вершин компоненты Dk в покрытии
X.
Все критерии (см. (1.5)-(1.8)) векторно-целевой функции (1.4) имеют конкретную содержательную интерпретацию.
Веса, приписанные ребрам предфрактального графа GL, призваны отражать "неэффективность" сотрудничества между учреждениями, которым соответствуют вершины - концы ребер. Наладить плодотворное сотрудничество между крупными предприятиями, ввиду их сильной конкуренции, труднее чем между более мелкими, поэтому вес ребер с ростом их рангов уменьшается. При такой интерпретации весов, приписанных ребрам предфрактального графа, целесообразно искать покрытие с наименьшим весом. Именно, это и сформулировано в первом критерии (1.5) ВЦФ (1.4).
Число компонента \х\ в покрытии л: соответствует числу частей, на которые разделен основной проект. Чем менее раздроблен основной проект при его реализации, тем эффективнее процесс объединения и обобщения результатов на завершающем этапе выполнения этого проекта. Поэтому второй критерий (1.6) ВЦФ (1.4) направлен на уменьшение числа компонента в покрытии.
Некоторые учреждения при распределении работ (частей основного проекта) могут одновременно сотрудничать с несколькими предприятиями. В покрытии д; степени вершин компоненты Dk будут указывать на число уч-
реждений сотрудничающих с учреждением, соответствующему данной вершине. Учреждение в таком широком сотрудничестве выступает, как и качестве заказчиков, так и в качестве исполнителей заказов. Как известно, чрезмерная загрузка предприятия, преобладающая над его производственными возможностями, сильно ухудшает качество предлагаемых услуг и производимых изделий. Критерий (1.7) ВЦФ (1.4) стремиться уменьшить максимальную среди степеней вершин каждой компоненты Dk покрытия *, что обосновывается целесообразностью уменьшения количества сотрудничающих учреждений.
Вершины, соответствующие учреждениям и предприятиям имеющим тесные взаимоотношение, образуют компоненты Dk покрытия х. Увеличение количества взаимосвязанных учреждений и предприятий работающих над одним заказом (частью основного проекта) понижает эффективность выполняемой работы. Число вершин или ребер, на дереве (число вершин отличается от числа ребер ровно на единицу), входящих в компоненты Dk покрытия х уменьшаются до возможного минимума критерием (1.8) ВЦФ (1.4), что позволяет предполагать достижения эффективного сотрудничества между учреждениями, соответствующие вершины которых на предфрактальном графе GL объединены в компоненты Dk покрытия х.
Вторая глава посвящена свойствам и характеристикам предфракталь-ного графа [19-20], порожденного двудольной затравкой.
Граф G = (V,E) называется к -дольным, если множество его вершин V
можно разделить на к непересекающихся подмножеств V = {V ,V2,...,V }
таких, что концы всякого ребра ееЕ одновременно не принадлежат ни одному из этих подмножеств.
ТЕОРЕМА 2.1. Предфракталъный граф GL=(VL,EL), пороэюденный
двудольной затравкой Н = (W',W,Q), \W\ = \W"\ = n/2, является 2 -дольным графом.
13 Следствие 2.1.1. Предфракталъный граф GL=(VL,EL), порожденный множеством двудольных затравок H = {Ht}={Hi,H2,...,Ht,...,HT},
Т>2, является 2 -дольным графом.
Примечание 2.1. Доказательство теоремы 2.1 несет конструктивный характер, и поэтому дает алгоритм выделение всех 2 "долей" пред-фрактального графа GL, порожденного двудольной затравкой.
Совершенное паросочетание графа G - это паросочетание, покрывающее все вершины графа G.
Теорема 2.2. Предфракталъный граф GL=(VL,EL), порожденный
двудольной затравкой Н = (W',W,Q), tyV'\ = ^V"\ = nl2, имеет совершенное
паросочетание, если совершенное паросочетание можно выделить на его затравке И = (W',W\Q).
СЛЕДСТВИЕ 2.2.1. Предфракталъный граф GL=(VL,EL), порожденный множеством двудольных затравок Н = \Ht)= {Нх,Н2,—,Нп...уНТ), Т>2, имеет совершенное паросочетание, если совершенное паросочетание можно выделить на каждой его затравке Ht є Н, / = 1,2,...,Г.
Размер произвольного наибольшего паросочетания в графе G называется числом паросочетания (или реберное число независимости) графа G и обозначается.
Теорема 2.3. Если на предфракталыюм графе GL =(VL,EL),
порожденном двудольной затравкой Н = (W',W",Q), \W\ = \W"\ = n/2, существует паросочетание, то для его числа паросочетания v{GL)
справедливо двустороннее неравенство (и(Н))п < v{GL)< (п/2)п .
СЛЕДСТВИЕ 2.3.1. Для числа паросочетания предфрактального графа GL=(VL,EL), порожденного множеством двудольных затравок R = {H(}={Hl,H2,—,Ht,...,HT}, Т>2, при условии, что на предфракталь-ном графе существует паросочетание, справедливо двустороннее неравен-
ство (u(Hmin))" < v{GL) < ( m—)" , где Hmin — затравка из Н с наи-
меньшим по числу ребер совершенным паросочетанием среди всех затравок Ht, а \Vmax\ - наибольшее число вершин среди затравок Ht.
Пусть Н = (W,Q) есть и-вершинный связный граф. Длина кратчайшей цепи, соединяющей пару вершин u,veW, называется расстоянием между вершинами и и v и обозначается через p(u,v). Заметим, что введенное таким образом расстояние удовлетворяет известным аксиомам Евклидовой метрики.
Для фиксированной вершины ueW величина є(и) = maxp(u,v)
v&fV
называется эксцентриситетом вершины и &W.
Максимальный среди всех эксцентриситетов вершин графа Н = (W, Q)
называется диаметром графа Н и обозначается через d(H), т.е.
d(H) = max є(и).
uefV
Если пара вершин u,vgW соединяется кратчайшей цепью длины р(и, v) = d(H), то эта цепь называется диаметральной.
Радиус графа Н обозначается через г{Н) и вычисляется по формуле r{H) = min є{и).
Вершина и называется периферийной, если є(и) = d(H).
УТВЕРЖДЕНИЕ 2.1. Радиус и диаметр полного двудольного графа Н = (W,W",Q) равны, d(H) = r(H) = 2. Причем кратчайшая цепь, соединяющая две вершины из одного и того же подмножества вершин (W или W") является диаметральной (его длина равна двум), т.е. все вершины графа Н — периферийные. А
Теорема2.4. Для предфрактального графа GL =(VL,EL), порожденного полной двудольной затравкой Н =(W',W,Q), 1^1 = 1^1 = ^/2, смеж-
ностъ старых ребер которого в траектории не нарушается, диаметр определяется равенством d{GL ) = 4L — 2.
ТЕОРЕМА 2.5. Для предфрактального графа GL = (VL,EL), порожденного полной двудольной затравкой Н = {W',W",Q), ^V'\ = ^V"\ = nl2, смежность старых ребер которого в траектории не нарушается, радиус определяется равенством r(GL ) = 2L.
В третьей главе описаны и обоснованы три параллельных алгоритма ах, а2 и аъ построения некоторых решений многокритериальной задачи
(1)-(5) о назначениях [21-29]. Параллельный алгоритм ах - выделение совершенного паросочетания минимального веса (СПМВ), параллельный алгоритм а2 - выделение остовного дерева минимального веса (ОДМВ) и параллельный алгоритм а3 - выделение остовного леса.
Трудоемкость параллельных алгоритмов оценивается по двум критериям. Под временной сложностью алгоритма будем понимать число простых операций, произведенных за время работы алгоритма одним из процессоров. Вычислительная сложность представляет общее число всех операций произведенных алгоритмом за время его работы.
Рассмотрим взвешенный пред фрактальный граф GL =(VL,EL) порожденный двудольной затравкой Н = {W',W,Q), tyV'\ = \W\ = nl2, |?| = <7, и k процессоров P\,P2i—>Pk-
АЛГОРИТМ ax
Теорема 3.1. Алгоритм ax выделяет совершенное паросочетание М = (V, Ем) минимального веса на предфрактальном (п, L) -графе GL=(yL,EL), порожденном двудольной затравкой Н = (W,W,Q),
\W'\ = \W"\ = nl2,\Q\ = q, если в <-.
ТЕОРЕМА 3.2. Вычислительная сложность параллельного алгоритма ах построения .СПМВ на предфрактальном (n,L)-графе GL ={VL,EL), по-
рожденном двудольной затравкой Н = (Wf,W,Q), где \VL\ = N = п , равна
0(Nn2).
Примечание 3.1. В классической теоретико-графовой постановке построение СПМВ на графах осуществляется алгоритмом Эдмондса, который используется в качестве процедуры в алгоритме ах. Вычислительная
сложность параллельного алгоритма 0L\ меньше вычислительной сложно-
сти алгоритма Эдмондса, в N раз на предфрактальном (n,L)-графе GL=(VL,EL).
ТЕОРЕМА 3.3. Временная сложность параллельного алгоритма ait где
1 — 1 ^
имеется к процессоров Р\,Р2>—>Рк> к = п .равна 0(п ).
Примечание 3.2. Временная сложность параллельного алгоритма ах
меньше временной сложности алгоритма Эдмондса, в N -п раз.
Теорема 3.4. Временная сложность параллельного алгоритма а^, где
1 ~>
используется г процессоров р1,р2,...,рг, \<г<к, к = п~ равна
О ' \r J
Примечание 3.3. Временная сложность параллельного алгоритма ах, где используется г процессоров р1,р2,...,рг, \<г<к, к = nL~l меньше ере-
*/ Ї —9
менной сложности алгоритма Эдмондса, в rNn раз.
ТЕОРЕМА 3.5. Алгоритм ах выделяет покрытие х{ =(VL,EX ) на предфрактальном (n,L)-графе GL =(VL,EL), пороэюденном двудольной затравкой Н = {W,W\Q), оптимальном по третьему F3(xl) и четвертому F4(xi)
„л_і an ^ _,, ч . _/_] on
критерию, и оцениваемом по первому в
му, F2(xl)<—.
АЛГОРИТМ а2
Теорема 3.6. Параллельный алгоритм а2 выделяет ОДМВ
Т = (VL,ET) на предфрактальном (n,L)-графе GL =(VL,EL), порожденном
двудольной затравкой Н = (W',W",Q), \W\ = \W'\ = и/2, \Q\ = q.
Теорема 3.7. Вычислительная сложность параллельного алгоритма а2, выделяющего ОДМВ Т = (VL,ET) на предфрактальном (n,L)-графе
GL={VL,EL), порожденном двудольной затравкой Н = {W',W,Q), где \VL| = N = nL,равна 0(Nn2).
Примечание 3.4. В классической теоретико-графовой постановке построение ОДМВ на графах осуществляется алгоритмом Прима, который используется в качестве процедуры в алгоритме а2. Сравнив вычислительную сложность алгоритма Прима с вычислительной сложностью параллельного алгоритма а2 на предфрактальном графе GL, получим:
0(N ) < 0(Nn ). Вычислительная сложность алгоритма а2 меньше вычислительной сложности алгоритма Прима в п раз.
ТЕОРЕМА 3.8. Временная сложность параллельного алгоритма а2, где
имеется к процессоров P\,p2,:.,Pk, к = ,равна и{п ).
п-\
Примечание 3.5. Временная сложность параллельного алгоритма а2
меньше временной сложности алгоритма Прима, в Nn раз.
ТЕОРЕМА 3.9. Временная сложность параллельного алгоритма а2, где
, ^/ 7 nL-\
используется г процессоров Pi,p2,...,pr, \<г<к, к = равна
п-\
o{X-N.n2\
18 Примечание 3.6. Временная сложность параллельного алгоритма а2
где используется г процессоров pi,p2,...,pr, 1<г<к, к = меньше
п-\
Т —*?
временной сложности алгоритма Прима, в т раз.
Теорема3.10. Алгоритм а2 выделяет покрытие х2 =(VL,EX ) на
предфракталъном (п, L) -графе GL = (VL ,EL), порожденном двудольной затравкой Н = (W\W",Q), оптимальном по второму критерию F2(x2) и, оце-
ниваемом по первому Fl(x2) <(и-1)о-— , третьему F3(x2)<— и
пв~\ 2
четвертому F4(x2) = n .
АЛГОРИТМ аъ
Теорема 3.11. Параллельный алгоритм а3 выделяет остовный лес
Т* ={VL,E .) на предфракталъном (n,L)-графе GL =(VL,EL), порожденном двудольной затравкой Н = (W',W",Q), \W\ = \W\ = nil, \Q\ = q.
ТЕОРЕМА 3.12. Вычислительная сложность параллельного алгоритма а3, выделяющего остовный лес Т* =(VL,E .) на предфракталъном (п,Ь)-
графе GL=(VL,EL), порожденном двудольной затравкой Н = (W,W,Q), где \VL\ = N = п1,равна 0{Nri).
Теорема 3.13. Временная сложность параллельного алгоритма а3,
где имеется к процессоров P\,P2->—>Pk> k = n , равна 0(п ).
Теорема 3.14. Временная сложность параллельного алгоритма а2,
где используется г процессоров pl,p2,...,pr, \
-N -п
\г )
Теорема3.15. Алгоритм а3 выделяет покрытие x3={VL,Ex) на предфракталъном (n,L)-графе GL ={VL,EL), пороэюденном двудольной за-
19 травкой Н = {W',W,Q), оцениваемом по первому критерию
Fl(x3)<(n-l)(n6)L~1, второму F2(x3) = nL~l, третьему F3(x3)< — и чет-вертому F4(x3) = n.
В четвертой главе описаны и обоснованы параллельные алгоритмы распознавания предфрактального графа, порожденного двудольной затравкой.
Различают два типа распознавания: явное и неявное.
Под неявным распознаванием подразумевают утверждение о том, что данный граф является фрактальным и базируется на некоторой п -вершинной затравке. Явное распознавание, сверх того, предполагает идентификацию рангов всех ребер заданного графа и его траекторию.
Все алгоритмы распознавания, представленные в настоящей главе, являются алгоритмами явного распознавания. Предлагается три параллельных алгоритма распознавания предфрактальных графов, порожденных двудольными затравками. Параллельный алгоритм ух - распознавание предфрактального графа, порожденного затравкой-ребром. Параллельный алгоритм у2
- распознавание предфрактального графа, порожденного затравкой-звездой. Параллельный алгоритм у3 - распознавание предфрактального графа, порожденного затравкой-циклом четной длины.
В дискретной многокритериальной оптимизации, несмотря на ее значительные достижения в области прикладной математики, использование параллельных алгоритмов является редкостью даже среди алгоритмов построения решений. Отчасти этот пробел восполняется в третьей главе настоящей диссертации. Появление же параллельных алгоритмов распознавания, описанных в четвертой главе, связано с исследованием предфрактальных графов. Самоподобие [30-33], - основное свойство предфрактальных графов, дает возможность распараллеливания алгоритмов распознавания.
20 АЛГОРИТМ у\ Цель применения алгоритма ух к данному (2, L) -дереву D = (V,E) состоит в том, чтобы преобразовать D в (2,L-Y)-дерево Д. Применительно к D работа ух состоит из К этапов, пронумерованных индексом к=\,2,...,К; K
Назначим каждому подэтапу пк =1,2,...,тк, тк < \v\, этапа к процессор рК с соответствующим порядковым номером. Процессоры выполняют предписываемую им алгоритмом работу одновременно.
Теорема 4.1. Верхняя оценка вычислительной сложности алгоритма ух распознавания графа D = (V,E) равна t{y{) < Oty\b) = 0(|F|log|^|).
Теорема 4.3. Алгоритм у і для распознавания предфрактального (2,L)-
дерева DL = (VL, EL ) использует не более чем 2 ~ процессоров.
Теорема 4.4. Временная сложность алгоритма ух распознавания предфрактального (2, L) -дерева DL =(VL,EL), смежность старых ребер которого не нарушается, равна O(L).
Следствие 4.4.1. Временная сложность алгоритма ух распознавания предфрактального (2, L) -дерева не больше O(L).
АЛГОРИТМ у2 Алгоритм у2 распознает предфрактальное (n,L) -дерево G, порожденное w-вершинной связной звездой, т.е. Н состоит из одного элемента - звезды, ІНІ = 1.
Алгоритм у2 состоит из L - 1 этапов. Если данный граф G предфрак-тальный, то на очередном этапе г в текущем графе Gr+l выделяются все затравки, состоящие из ребер ранга г + 1, после чего каждая из этих затравок стягивается в вершину, и полученный в результате текущий граф Gr представляется на вход этапа г + 1.
Каждой вершине veVr+l дерева Gr+] =(Vr+l,Er+l), такой
4Todegv = 72-l или degv = n-2, на текущем этапе алгоритма у2 назначаем процессор ру. Все процессоры {pv}, veVr+i одновременно выполняют работу предписанную им алгоритмом у2 на этапе г.
Теорема 4.6. Верхняя оценка вычислительной сложности трудоемкости алгоритма у2 т(у2) ^ 0(mL), где т = \Е\ — количество ребер рассматриваемого графа D = (V, Е).
ТЕОРЕМА 4.7. Проблема распознавания свойства предфракталъности данного графа G полиномиально разрешима алгоритмом у2 при выполнении
следующих условий: граф G является (п,Ь)-деревом, порожденным п-
вершиннымизатравками-звездами, п>4.
ТЕОРЕМА 4.8. Алгоритм у2 для распознавания предфрактального R-
адического (п, L) -дерева DL = (VL, EL) использует не более чем (п -1) процессоров.
Теорема 4.9. Временная сложность алгоритма у2 распознавания предфрактального R-адического {п, L) -дерева равна 0{nL).
АЛГОРИТМ /з
Алгоритм у3, применяемый к (я,)-графу с циклической затравкой четной длины, состоит из L этапов, пронумерованных индексом /=1,2,...,/,.
Этап / є {1,2,...,L}coctoht из 2 ~ подэтапов. На каждом из этих подэта-пов выделяется очередная затравка, после чего ее ребра окрашиваются.
Каждому подэтапу к0 этапа /є{і,2,...,/,} назначается процессор рк с
соответствующим порядковым номером. Процессоры выполняют предписываемую им алгоритмом работу одновременно.
Теорема 4.11. Всякий предфрактальный (п,Ь)-граф G=(V,E) с циклической затравкой четной длины распознается алгоритмом у3 с полиномиальной трудоемкостью 0(|is|Z,).
Теорема 4.12. Алгоритм у3 для распознавания предфракталъного
графа GL = (VL,EL) использует не более чем 2 ~ процессоров.
ТЕОРЕМА 4.13. Временная сложность алгоритма у3 распознавания предфракталъного (п, L) -графа GL = (VL, EL ) равна 0{nL).
Основные результаты диссертации заключаются в следующем:
- сформулирована и исследована многокритериальная задача о назначениях на предфрактальных графах. Продемонстрирована значимость задачи о назначениях на предфрактальных графах на примере реализации крупного научно-исследовательского проекта;
исследованы метрические и топологические свойства предфрактального графа, порожденного одной или множеством двудольных затравок. Определено условие существования совершенного паросочетания на предфрактальном графе, порожденном двудольной затравкой. Даны оценки для числа паросочетания, диаметра и радиуса предфрактального графа, П(^1и^однвнш10<дя5адалюбиспаБряйлса|щ параллельных алгоритма для построения решений задачи о назначениях на предфрактальных графах. Алгоритмы строят решения, оптимальные по одним, и, оцениваемые по другим критериям, сформулированной многокритериальной задачи о назначениях;
- впервые описаны и обоснованы три параллельных алгоритма распознавания предфрактального графа, порожденного двудольной затравкой.
Апробация работы. Основные результаты работы докладывались на 5-ом и 6-ом Всероссийских симпозиумах "Математическое моделирование и компьютерные технологии" (Кисловодск, 2002 и 2004), Международном Российско-Узбекском симпозиуме "Уравнения смешанного типа и родственные проблемы анализа и информатики" (Нальчик, 2003), 34-ой научно-технической конференции профессорско-преподавательского состава, аспирантов и студентов Северо-Кавказского Государственного технического университета (Ставрополь, 2004), 50-ой научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников Таганрогского Государственного радиотехнического университета (Таганрог, 2004), научных семинарах профессорско-преподавательского состава Карачаево-Черкесской Государственной технологической академии (Черкесск, 2001-2005)
По результатам выполненной работы имеется 17 публикаций. Диссертация состоит из введения и четырех глав изложенных на 106 страницах, содержит 5 рисунков и библиографию из 114 наименовании.
Многокритериальная постановка задачи о назначениях на предфрактальном графе
Формально, если в задаче о назначениях (ЗН) каждому из п заказчиков и т исполнителей поставить в соответствие вершины графа, а ребрами обозначить возможности исполнения работ предложенных заказчиками, то полученный двудольный [2,3] граф G = (V ,V",E) является схемой, отражающей всевозможные связи между заказчиками и исполнителями. На графе G множества вершин V, \V\ = n, и V, \V\ = m, соответствуют заказчикам и исполнителям. Множество ребер Е соответствует связям между исполнителями и заказчиками. Смысл связей заключается в возможности реализацией исполнителями работ предложенных заказчиками. Каждому ребру из Е приписываются веса, которые призваны качественно демонстрировать экономическую целесообразность выполняемых работ предложенных конкретным заказчиком конкретному исполнителю.
В фиксированный момент времени в работе должен быть задействован каждый исполнитель, причем он может принимать участие в выполнение только одного заказа. Каждый заказчик так же может следить за реализацией единственного заказа.
План выполнения работ предложенных заказчиками исполнителям в терминах теории графов будет соответствовать паросочетанию [2-5], выделенном на двудольном графе G. Напомним, что паросочетание [5] - это несвязный суграф, каждая компонента которого представляет собой ребро.
Необходимость построения экономически обоснованного плана вынуждает обратится в сферу дискретной многокритериальной оптимизации [6-8].
Таким образом, ЗН в теоретико-графовой (классической) постановке сводится к поиску на двудольном графе паросочетаний, удовлетворяющих требованиям некоторых критериев. ЗН в классической постановке как в од-нокритериальном [9-13], так и в многокритериальном [14-18] случае тщательно исследована.
С появлением понятия фрактального (предфрактального) графа [1,19,20] многие задачи математического программирования исследуемые аппаратом теории графов [21,22], ЗН в том числе, потребовали серьезной доработки, а нередко и совершенно новых методов для решения этих задач с постановкой на пред фрактальных графах [23-29].
В нашем случае, для ЗН, основная причина необходимости ее постановки на предфрактальных графах заключается в усложнении схемы всевозможных связей между заказчиками и исполнителями. Продемонстрировать это можно на примере крупного научно-исследовательского проекта.
Любой крупный научно-исследовательский проект делится на части, и предлагается для реализации научно-исследовательским институтам (НИИ) и научно-производственным объединениям (НПО). Часто эти учреждения не в состоянии справится с поставленными задачами в одиночку, и поэтому выбирают среди всевозможных учреждений аналогичного профиля наиболее полезные с точки зрения сотрудничества. Выбор учреждений для сотрудничества - есть решение классической задачи о назначениях, т.е. выделение паросочетании на двудольном графе, отражающем всевозможные связи между учреждениями этого, высшего уровня.
Каждое из учреждений высшего уровня делит свою часть проекта и распределяет по ведомственным или проектным институтам, т.е. учреждениям более низкого по масштабам выполняемой работе уровня. Всем этим учреждениям приходится искать удовлетворяющие поставленным требованиям учреждения для сотрудничества уже из своего уровня, т.е. снова решать ЗН. ЗН потребует решения и на других уровнях: проблема выбора встанет на уровне отделов и сотрудников институтов.
Предложенное описание фактической реализации крупного научно-исследовательского проекта путем разделения его на более мелкие проекты (заказы) поднимает два важных вопроса.
Первый - каков граф G, представляющий схему всевозможных взаимодействий между учреждениями, заказчиками и исполнителями?
Очевидно структура этой схемы сложнее, чем "обычный" двудольный граф. Каждое учреждение, начиная с высшего уровня, решая поставленную перед ним задачу (т.е. выполняя заказ) устанавливает связи между исполнителями и заказчиками более низкого уровня. А поскольку между указанными учреждениями-исполнителями и учреждениями-заказчиками более низкого уровня схема взаимодействий есть двудольный граф, это верно для любых уровней учреждений, то граф G, отражающий общую схему возможных взаимодействий, обладает свойством самоподобия [1,19,20,30-33]. Поэтому общая схема возможных взаимодействий между учреждениями различных уровней, принимающих участие в реализации научно-исследовательского проекта - есть предфрактальный граф, порожденный двудольной затравкой.
Второй - какой суграф, удовлетворяющий условиям ЗН, является решением ЗН на предфрактальном графе? Ошибочно предполагать, что решением, как и в классической постановке, являются только лишь паросочета-ния. На предфрактальном графе ребра, отвечающие за связи между учреждениями высоких уровней, могут пересекаться с ребрами, отвечающими за связи между учреждениями более низких уровней. Наличие таких пересечений среди ребер различных рангов в покрытии (суграфе) предфрактального графа не противоречит основным требованиям ЗН в силу того, что отдельно взятое учреждение, относительно учреждений своего уровня может выступать как заказчик, в то время как относительно учреждений другого уровня может выступать в качестве исполнителя.
Условие существования совершенного паросочетания на предфрактальном графе
Совершенное паросочетание [5] графа G — это паросочетание, покрывающее все вершины графа G.
По проблеме существования паросочетаний (совершенных паросочета-ний) на двудольных графах выполнена масса работ, и предложено множество условий их существований [42-45]. Используя эти условия для двудольной затравки, сформулируем условие существование совершенного паросочетания на предфрактальном графе.
ТЕОРЕМА 2.2. Предфрактальный граф GL=(VL,EL), порожденный двудольной затравкой Н = (W ,W,Q), \W\=\W"\ = n/2, имеет совершенное паросочетание, если совершенное паросочетание можно выделить на его затравке H = (W ,W,Q).
ДОКАЗАТЕЛЬСТВО. Рассмотрим предфрактальный граф GL=(VL,EL), порожденный двудольной затравкой Н = (W ,Wn,Q), и множество подграф-затравок z\ , s = \,nL , ранга L. Согласно определения предфрактального графа (см. параграф 1.1) каждая из п х подграф-затравок L-ro ранга совпа дает с самой затравкой Н = zf , предфрактального графа GL. Очевидно также, что для образование подграф-затравок L-ro ранга используются все вершины (т.е. полностью множество VL) предфрактального графа GL.
Это представляется возможным благодаря предположению существования совершенного паросочетания на двудольной затравке Н предфрак-тального графа GL. Поскольку выделенный на предфрактальном графе GL суграф M = (VL,EM) = {M5(i) = (VS(L),E{SL))}, s = \,nL l, состоит из компонент, каждая из которых является ребром, то суграф М - есть совершенное паросочетание. Л
СЛЕДСТВИЕ 2.2.1. Предфрактальный граф GL = (VL,EL), порожденный множеством двудольных затравок H = {Ht}={Hl,H2,—,Ht,...,HT}, Т 2, имеет совершенное паросочетание, если совершенное паросочетание можно выделить на каждой его затравке Н( є Н, / = 1,2,...,71. А
На рис. 2.2 изображен предфрактальный граф G3 =(V3,E3), порожденный полной двудольной 4-вершинной затравкой Н = {W ,W\Q), \W\ = 2, IW "І = 2. На графах G3 и Н, серыми линия выделены ребра, образующие совершенное паросочетание.
В работах [46-60], посвященных топологическим и метрическим свойствам предфрактальных графов не уделено внимание числу паросочетания графа [5,7].
Размер произвольного наибольшего паросочетания в графе G называется числом паросочетания (или реберное число независимости [5]) графа G и обозначается v{G). ТЕОРЕМА 2.3. Если на предфрактальном графе GL = (VL,EL), порожденном двудольной затравкой Н = (JV ,W",Q), W = W = п12, существует паросочетание, то для его числа паросочетания v(GL) справедливо двусто L \ 1-І роннее неравенство (v(H)) u(GL ) {п12) ДОКАЗАТЕЛЬСТВО. Рассмотрим предфрактальный граф GL=(VL,EL), порожденный двудольной затравкой Н = (W,W,Q), и множество его под граф-затравок z}L\ s = \,nL l, ранга L. Первое. Согласно утверждению 1.1. (см. также доказательство теоремы 2.2.) множество наибольших паросочетаний {М = (V}L\E )}, s = \,nL l, выделенных на подграф-затравках zy исследуемого предфрактального графа GL, образуют некоторое паросочетание М = (VL, Ем). В самом деле подграф М c:GL, предфрактального графа состоит из компонент, каждая из которых является ребром из EL.
Очевидно, что число паросочетания v(GL) предфрактального графа GL не будет меньше числа ребер в его паросочетаний М = (VL,EM), состоящего из наибольших паросочетаний по М) с: z\L подграф-затравок L -го ранга,т.е. {и{Н))п v(GL). Второе. Среди множества всех «-вершинных двудольных графов G = {V ,V\E) наибольшим паросочетанием обладает полный, причем ]у \ = К" = «. У такого графа G = (V ,V,E) число паросочетания равно u(G) = я/2, т.е. каждая пара вершин входит в наибольшее паросочетание по одному разу. Вообще говоря, для полного двудольного графа наибольшее паросочетание также является совершенным [5].
Рассмотрим предфрактальный граф GL=(VL,EL), порожденный полной двудольной затравкой Н = (W,W",Q). Используя доказательство теорема 2.2. предфрактальном графе GL можно построить совершенное паросочетание М = (VL, E j). Оно будем состоять из совершенных паросочетаний {М =(V L\E )} подграф-затравок z L\ s = \,nL l, ранга L. Число же самих подграф-затравок L-ro ранга, напомним, равно nL .
Параллельный алгоритм а, выделения совершенного паросочетания минимального веса
Рассмотрим взвешенный пред фрактальный граф GL =(VL,EL) порожденный двудольной затравкой Н = (W ,W\Q), W = F" = «/2, ? = 7, и к процессоров р1,р2,...,ріс,гдє к = п .
Предположим, что выполняется условие существования совершенного паросочетания на предфрактальном графе, в соответствие с теоремой 2.2. Таким образом, в начале работы алгоритма ах будем предполагать, что на двудольной затравке Н = (W ,W",Q) существует совершенное паросочетание.
Алгоритм ах основан на алгоритме выделения совершенного паросочетания минимального веса (СПМВ), предложенный Эдмондсом [13,84,86,87]. На вход алгоритма Эдмондса подается произвольный взвешенный граф, а на выходе получается СПМВ. Далее алгоритм Эдмондса будет использоваться как процедура Эдмондса.
Опишем принцип работы алгоритма ах.
Количество процессоров равно количеству всех затравок L-oro ранга, то есть к = п . Тогда каждый из процессоров ps назначим одной из затравок z) \ s = \,п .
Каждая подграф-затравка z\ \ s = \,nL рассматривается как отдельно взятый граф, все к процессоров Р\,р2 — Рк параллельно независимо друг от друга находят СПМВ Ms каждый на назначенной ему затравке z .
Поиск СПМВ на отдельно взятой подграф-затравке осуществляется с помощью алгоритма Эдмондса, который используется в алгоритме ах в качестве процедуры. Осуществив поиск СПМВ на подграф-затравках, получим СПМВ всего предфрактального графа GL. После чего алгоритм ах заканчивает свою работу. Вход: взвешенный предфрактальный граф GL = (VL,EL). Выход: совершенное паросочетание минимального веса ML. ШАГ 1. Параллельно и независимо друг от друга к процессоров Р\,Р2 -- Рк Для каждой затравки z L\ s = \,nL l находят СПМВ Ms используя процедуру Эдмондса. ШАГ2. На выходе шага 1 получаем s = \,nL ] совершенных паросоче-таний минимального веса Ms, для каждой затравки z . Объединяя эти совершенные паросочетания Ms получим совершенное паросочетание минимального веса ML предфрактального графа GL. ПРОЦЕДУРА ЭДМОНДСА. ВХОД: взвешенный граф G = (V, Е). ВЫХОД: СПМВ M = (V,EM).
ТЕОРЕМА 3.1. Алгоритм а{ выделяет совершенное паросочетание М = (V,EM) минимального веса на предфрактальном (п,Ь)-графе GL =(VL,EL), порожденном двудольной затравкой Н = {W ,W",Q), \W \ = \W"\ = n/2,\Q\ = q,ewue ДОКАЗАТЕЛЬСТВО. На первом шаге к процессоров находят СПМВ на подграф-затравках, используя процедуру Эдмондса.
На последнем шаге L построения предфрактального графа GL все вершины замещаются затравкой Н = (W,Q), тогда каждая вершина L-oro ранга принадлежит какой-либо подграф-затравке z} . Найдя совершенное паросочетание на затравке z) , покроются все вершины принадлежащие этой затравке.
Таким образом отбросим все ребра ранга l = \,L-\, и будем работать только с подграф-затравками L-oro ранга z;L\ s = \,nL х.
Выделим на подграф-затравке L-oro ранга z\ совершенное паросочетание минимального веса Мх. В результате паросочетание Мх покрыло п вершин. Далее выделим на второй затравке L-oro ранга z\ совершенное паросочетание минимального веса М2- Паросочетание М2 покрыло еще п вершин. Это покрытие никак не повлияло на Ml, так как затравки z\ HZJ являются отдельными, не связанными между собой подграфами.
Тогда, после выделения совершенного паросочетания М L.x на последней затравке z(L_,, будет покрыто п -п = п вершин. Получим, что покрыто все множество вершин GL = (VL ,EL): \VL = nL.
На затравках zy выделялись совершенные паросочетания Ms, s = \,nL , то есть вершины пред фрактального графа покрывались паросоче-танием. Таким образом, полученное покрытие является совершенным паро-сочетанием МL предфрактального графа GL. А поскольку предфрактальный граф взвешен с помощью коэффициента в — , вес ребра L -го ранга меньше Ъ веса любого из ребер предыдущих рангов. Таким образом поиск совершенных паросочетаний минимального веса производился на ребрах самых минимальных весов, следовательно совершенное паросочетание ML выделенное на предфрактальном графе GL будет минимального веса.
Параллельный алгоритм у2 распознавания предфрактального графа, порожденного затравкой-звездой
Результатом работы многих процессов являются структуры, отражающиеся диадическими деревьями [101,102]. Естественным обобщением этого понятия является Я-адическое дерево [101,102]. Термином "Я-адическое дерево" называем всякое дерево, у которого каждая невисячая вершина имеет степени г + 1, г 2. С учетом практиче ских приложений будем различать Л-адическое дерево и корневое R-адическое дерево.
Следуя общему определению, фрактальным (предфрактальным) деревом [101] называем такой связный фрактальный (предфрактальный) граф, который не содержит циклов. Фрактальное (предфрактальное) дерево порождается тогда и только тогда, когда множество затравок Н = {//} представляет собой лес.
С учетом отмеченного выше можно сказать, что диадическое дерево порождается единственной затравкой, которая представляет собой 3-вершинную звезду. Аналогично Л-адическое дерево порождается затравкой, которая представляет собой (г + 1)-вершинную звезду.
Сохраняя для обозначения дерева символ G, можем представлять траекторию порождения предфрактального дерева в тех же обозначениях, что и последовательность Gx,G2,—,Gr,...,GL. Алгоритм получения этой траектории в случае порождения предфрактального Я-адического дерева можно описать следующим образом.
Переход от текущего дерева Gr =(Vr,Er) к текущему дереву Gr+1 всякий раз подчиняется трем общим правилам:
1) если вершина v eVr не является висячей, то она не замещается затравкой;
2) замещаемая затравкой вершина v є Vr выбирается только из подмножества висячих вершин, а само висячее ребро становится инцидентным центру звезды;
3) если какая-либо висячая вершина v є Vr оказалась незамещенной затравкой, то она называется "замороженной" и по отношению к ней операция ЗВЗ не применяется ни на каком из следующих этапов r + l,r + 2,...,L. С учетом этих правил, процесс порождения Я-адического дерева будет определен полностью, если отметим, что в траектории Gl,G2,...,Gr,...,GL ее начальный элемент Gj представляет собой (г +1) -вершинную звезду.
Заметим: определенное выше і?-адическое дерево не является каноническим [57] пред фрактальным деревом. Однако в реальности существуют процессы, адекватная математическая модель которых базируется на каноническом предфрактальном дереве. В качестве примера такого процесса можно рассмотреть описанную [102] модель блуждающей бабочки. Содержательно эта модель строится на квадратной решетке и отражает задачу о распространении инфекции от первоначального зараженного узла.
На наш взгляд, в точечной модели [102] более информативной является графовая модель, в силу того что процесс порождения фрактального дерева несет в себе достаточно существенную информацию о динамике моделируемого процесса, более того, весьма информативными могут оказаться значения параметров, относящихся к теории графов: диаметра, степени порожденного дерева, количества висячих вершин и др.
Естественным обобщением Я-адического дерева является предфрак-тальное дерево, которое порождается в точном соответствии с описанными правилами 1) - 3) с тем лишь отличием, что "незамороженная" висячая вершина замещается альтернативно некоторой звездой из заданного множества звезд Н = {н}. Полученное таким образом дерево условимся называть термином "Н-дерево".
