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

НИИ Прикладной математики и автоматизации Кабардино-Балкарского научного

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

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

звездами ранговых типов [3,4], с заранее определенными значениями критериев.

Оговоримся, что недостающие понятия теории графов и предфрактальных графов можно найти в [1,2,3].

Пусть задан предфрактальный (п^)-граф GL = (VL, EL), порожденный связной затравкой H=(W,Q) [2].

Под звездой K1 s понимают полный двудольный граф, одна доля которого состоит из

единственной вершины (центра звезды) [1], а другая - из s вершин, называемых висячими. Иными словами, звезда - это совокупность ребер, инцидентных одной вершине. Число s назовем типом звезды. Для предфрактального (п^)-графа GL = (VL, EL) ранговым типом sl

будем называть тип s звезды K1 s, все ребра которой имеют одинаковый ранг

l, (/ = 1,2,...,L). При этом звезду будем обозначать K1ls, и назовем звездой рангового типа.

Очевидно, что для любой звезды K1ls ранговый тип sl может меняться на отрезке [1, m],

где m = maxdeg u .

,-7.77

Остовный подграф x = (VL, ELx) не содержащий изолированных вершин, назовем допустимым покрытием предфрактального (п^)-графа GL =(VL, EL) звездами ранговых

типов, если каждая его связная компонента представляет собой звезду K1 s рангового типа.

Множество всевозможных допустимых покрытий x графа GL =(VL, EL) звездами ранговых типов K1l s обозначим через X = {x} . На X определим критерии:

с наперед заданными ограничениями

Батчаев И.З. (butch w@rambler.ru)

центра РАН

(1.2)

(1.3)

(1.4)

В общем виде задача покрытия графа звездами формулируется так: для заданного взвешенного предфрактального (и^)-графа GL =(VL, EL), порожденного связной n-

вершинной затравкой H=(W,Q), необходимо отыскать такое покрытие x из множества допустимых покрытий X, что значение каждого из критериев (по возможности) F (x) -- min, (i = 1,2,3), x e X [3,4].

Ясно, что наиболее предпочтительным решением данной задачи с критериями (1.2-1.4) является точное решение, то есть покрытие, для которого значение всех трех критериев минимально.

В данной работе рассматривается следующая задача: пусть заданы числа a1, a2, a3, где

a1, a2 - натуральные числа, a3 является положительным рациональным числом.

Необходимо построить предфрактальный граф GL = (VL, EL) (если это возможно), для которого существует точное решение x со следующими значениями критериев:

F1 (x) = a1,F2(x) = a2,F3(x) = a3.

Для решения поставленной задачи предлагается

Алгоритм а.

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

критерия a2 . Далее подбирается ранг предфрактального графа и необходимое количество звезд, состоящих из старых ребер, так, чтобы число звезд покрытия x равнялось a1. После этого строится предфрактальный граф и его ребрам приписываются такие числа, чтобы вес покрытия x оказался равным a3 .

Для простоты будем строить граф GL = (VL, EL), старые ребра которого не пересекаются. При этом граф порожден затравкой H=(W,Q), состоящей из совокупности звезд K11,K12,...,K1 a2, центры которых последовательно соединены ребрами, то есть

затравка состоит из висячих вершин и центров звезд (узловых вершин). Здесь \W\ = n, Q = n -1 (затравка является деревом). Коэффициент пропорциональности к,

влияющий на изменение веса ребер, для определенности возьмем равным к = 2.

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

nL-2q + nL-3q +... + nq + q = EL J, причем в данном случае затравка является деревом, поэтому имеет место q = QI = n -1 и, следовательно, количество старых ребер равно

EL J = nL 2q + nL 3q +... + nq + q = (n- 1)(nL 2 + nL 3 +... + n +1)= (n- 1)П-1 = nL 1 -1, но

тогда \VL\ = nL > 2(nL-1-1)= 2EL\. По лемме 1 [3] это неравенство показывает нехватку

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

На первом этапе определяются число вершин затравки n = Щ и число L - ранг

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

Сразу отметим, что предфрактальный граф будем строить таким образом, чтобы улучшить покрытие x могли лишь специально подобранные звезды, состоящие из одного старого ребра и имеющие, соответственно, ранговый тип один. Кроме того, все затравки Hi = (Щ, Qi), (i = 1,2,..., nL-1), состоящие из новых ребер, попарно изоморфны (по

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

Действительно, предположим противное, то есть покрытия xi = (Щ, Qix ) некоторой

затравки Hi и xj = WJ , Qjx ) какой-либо другой затравки Hj содержат звезды разных

ранговых типов. Но тогда покрытие x, как объединение покрытий затравок, составленных из новых ребер, будет ухудшено по второму критерию. Это связано с тем, что отличные друг от друга покрытия затравок, состоящих из новых ребер, будут увеличивать значение второго критерия покрытия x. В случае, когда покрытия всех затравок изоморфны (например xi = (Щ, Qix )) число ранговых типов F2 (x) будет меньше исходного, ибо x не

будет содержать звезд изоморфных связным компонентам из xj = Щ,QJx ), ранговые

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

Пусть для простоты конструкции покрытия каждой такой затравки состоят из a2 звезд

K1,KL2,...,KLa2 ранговых типов. Учитывая, что для любого s K1 s покрывает s+1 вершину, имеем n = (1 +1)+(2 +1)+... + (a2 +1) = ~- а2. Всего существует nL-1 затравок,

состоящих из новых ребер, на каждую из которых приходится a2 звезд, тогда, если для покрытия предфрактального графа не используются элементы, состоящие из старых ребер, должно выполняться равенство a 1 = a2nL-1, где L - натуральное число. Исходя из этого, приходим к необходимости нахождения натурального числа L так, чтобы выполнялись неравенства a2nL-2 < a1 < a2nL-1, отсюда следует, что L является наименьшим числом удовлетворяющим неравенству L > logn a1 - logn a2 +1. Полученное значение берем в качестве ранга предфрактального графа.

В случае выполнения равенства a2nL-1 = a1 достаточно построить предфрактальный граф GL = (VL, EL) таким образом, чтобы ни одна звезда, состоящая из старых ребер, не могла улучшить покрытие x ни по одному из критериев (это возможно, когда один конец каждого старого ребра, как отмечено выше, совпадает с центральной вершиной какой-либо звезды покрытия x). В противном случае находим разность a2nL-1 - a1 , которая показывает сколько раз необходимо уменьшать число звезд покрытия x введением звезд, составленных из старых ребер, чтобы значение первого критерия было равно a1 .

Действительно, предположим, что GL =(VL, EL) уже построен и Hi, Hj две затравки,

составленные из новых ребер. (Как уже отмечалось, затравки составляются так, что для них существует единственное покрытие звездами.) Для каждой затравки существует по две вершины, покрываемые звездой K11 и только ей. Пусть для Hi такими вершинами

будут ui1,ui2 e Wi, а для Hj - uj1,uj2 e Wj, то есть существуют ребра (ui1,ui2)e Qi и

,j1, Uj2 )e Qj принимающие участие в покрытии как звезды K11 для соответствующих

затравок. При этом следует отметить, что одни концы этих ребер (например ui1, ujX) будут

висячими вершинами. Если эти висячие вершины соединены ребром (ui1,u;1 )e EL-1 /EL-2

ранга L-1, то оно покрывает данные вершины. Если же при этом вершины ui 2, u}- 2 смежны

центрам уже существующих звезд покрытия, то эти вершины могут быть покрыты данными звездами, добавлением к ним соответствующих ребер и увеличением рангового типа на единицу. В этом случае звезды, состоящие из ребер (ui1, ui2 )e Qi и (uj1, uj2 )e Qj

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

Здесь следует заметить, что в случае, когда L=2 мы имеем n затравок, состоящих из новых ребер, тогда при a2nL-1 - a1 > a2 не хватит затравок для осуществления нужного числа замен описанным выше способом. В этом случае алгоритм заканчивает свою работу с нулевым результатом.

На втором этапе алгоритма строится затравка H=(W,Q). Она покрывается звездами K11,K12,...,K1 a2, причем покрытие должно быть точным и единственным. В качестве

начальных значений берем W=0, Q=0.

Сначала строим звезду K1 a2 +1 и нумеруем ее вершины и ребра. Нумерацию начинаем с

центральной вершины, таким образом, имеем: W = {u1, u2,..., ua2+2}, Q = {e1, e2,..., ea2 +1}. Далее

строим звезду K1 a2 с центром в висячей вершине ua2+2 с наибольшим порядковым

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

W = {u1, u2,.-+2, +3 - u2a2 +3 } Q = , +1, ваг +2,.-e2a2 Далее процесс

продолжается аналогичным образом: строим звезду K1 a2-1 так, чтобы ее центром была

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

Процедура построения затравки продолжается тем же способом до звезды K1,3 . В

результате остается построить последнюю звезду K1,1 с центром в висячей вершине только

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

На третьем этапе строим сам предфрактальный граф GL =(VL, EL) (старые ребра которого могут как пересекаться так и не пересекаться), порожденный затравкой H, полученной на втором этапе строящегося алгоритма.

Построение начинается с уже нумерованной затравки H, понимаемой как G1 = (Fj, E1), и происходит в соответствии с определением предфрактального графа с одним дополнительным условием: на L-м этапе построения выбираются a2nL-1 - a1 пар затравок, состоящих из новых ребер и заместивших на предыдущем этапе построения смежные вершины. Их висячие вершины, покрываемые звездами (каждая из них имеет по

построению наибольший порядковый номер среди вершин той затравки, которой эта вершина принадлежит) соединяются ребрами ранга L-1 . Для остальных затравок это условие не выполняется.

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

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

меньше числа старых ребер EL. Действительно, по построению каждая затравка содержит a2 вершин степени выше единицы, а всего затравок, составленных из новых ребер - nL-1 , тогда всего имеем a2nL-1 вершин. В то же время предфрактальный граф по определению содержит nL - 2q + nL-3q +... + nq + q = \EL-1\ старых ребер, где

q = Ql = 1 + 3 + 4 + 5 +... + a2 +1 = (a2 -1) = a2 + a2 -2

(1 +1)+(2 +1) +... + (a2 +1)= a2

a2 + 3

n = (1 +1)+(2 +1) +... + (a2 +1) = ~- a2,

L-2 L-3 nL-2 -1 a22 + a2 - 2 L-1 L-2 a22 + 3a2

\ET A = n q + n q +... + nq + q =--2-2-, а a2n = an --Учитывая,

L 1 n 1 2 2 2

a2 + 3a a2 + a 2 L 2 nL 2 1

что --2 > --2-, nL-2 >- при условии, что a2 > 1. Из всего сказанного

2 2 n -1 2

можно сделать вывод, что количество не висячих вершин затравок, составленных из новых ребер, не меньше числа старых ребер EL- .

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

вершины этих звезд покрываются соседней звездой (таковая всегда существует по построению), увеличивая ее ранговый тип на единицу. Но в случае, когда a2 = 2 покрытие затравки должно состоять из звезд K1,1 и K1,2 и при описанном выше способе уменьшения числа звезд получаются звезды K1,3 за счет прибавления K1,2 по одному новому ребру, соединяющему центры K11 и K12. Это ухудшает покрытие по второму критерию, поэтому в дальнейшем предполагаем, что a2 > 2. Если же a2 > 2, то покрытие состоит из звезд ранговых типов один, два и три, то есть, получая звезды K1,3 за счет использования описанной выше процедуры, число ранговых типов не увеличится, ибо звезды K1,3 и так

присутствуют в покрытии.

На четвертом этапе происходит взвешивание ребер полученного графа, то есть приписывание ребрам весов таким образом, чтобы вес покрытия x был равным a3. Будем взвешивать граф таким образом, что веса ребер одного ранга будут совпадать. Исключение составляют новые ребра, из которых состоят звезды K1L,1 . Их веса должны быть больше

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

ребер, из которых состоят K1L,1 , следует увеличить в два раза по сравнению с весами остальных элементов множества EL \ EL-1.

Далее, для построенного предфрактального графа число вершин равно FL = nL . Тогда суммарное количество ребер всех звезд покрытия x равно nL - a1 (по лемме 1 [3]), причем a2 nL-1 - a1 ребер из них ранга L-1, а остальные ребра ранга L. Кроме того, в каждой из nL-1 затравок, состоящих из новых ребер, одно ребро имеет вес в два раза больший, чем все остальные ребра того же ранга. Тогда, учитывая, что коэффициент пропорциональности

взят равным к=I, получаем интервалы, из которых берутся веса ребер на каждом

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

Действительно, покрытие состоит из nL - a ребер, среди которых a2nL- - a + nL- ребер имеют в два раза больший вес, тогда новое ребро будет иметь вес a3

nL + a2nL 1 - 2a, + nL 1

1,1 -

Соответственно, каждое ребро ранга L-1 и ребра ранга L, из которых состоят звезды K

будут взвешено числами --l-г-3-г-Г . Ребра ранга L-2 взвешиваются числами

nL + a2nL 1 - 2a, + nL 1

3a3 и так далее. Конец алгоритма.

nL + a2nL-1 - 2a1 + nL-1

Теорема 1 . Пусть заданы числа a1 , a2 , a3 , для которых выполняются условия: a1 , a2 -натуральные числа, a2 > 2, a3 - положительное рациональное число. Тогда алгоритм а, если возможно, строит взвешенный предфрактальный граф GL =(VL, EL), старые ребра которого не пересекаются, такой, что существует покрытие x графа GL = (VL, EL) звездами ранговых типов удовлетворяющее условиям: Fi(x) = ai, (i = 1,2,3) и являющееся точным решением. Трудоемкость алгоритма равна т(а1 ) = O(VL ).

Доказательство: Тот факт, что построенный граф GL = (VL, EL) является предфрактальным графом, следует из определения предфрактального графа и конструкции самого алгоритма. Действительно, на втором этапе алгоритма оптимизируется затравка H, после чего строится предфрактальный граф, порожденный этой затравкой, в соответствии с определением, то есть поэтапно строится граф G1 = (V1, E1), затем строится граф G2 = ((2, E2) замещением каждой вершины G1 = (V1, E1) затравкой H, G3 = ((3, E3) и так далее пока не получим граф GL =(VL, EL).

Докажем теперь, что для GL =(VL, EL) существует покрытие x, являющееся точным решением. Сначала найдем покрытие xi = (Wi,Qix) затравки Hi = (Wi,Qi),(i = 1,2,...,nL-1), составленной из новых ребер. Заметим, что по построению затравка состоит из a2 звезд K1L,1,K1L,2,... , K1L,a2 , центры которых соединены ребрами, то есть каждая затравка Hi = (Wi,Qi),(i = 1,2,...,nL-1) состоит из висячих вершин звезд и их центров. Любая висячая вершина Hi = (Wi,Qi), (i = 1,2,... , nL-1 )инцидентна лишь одному новому ребру, поэтому

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

компонента есть одна из звезд K,KL2,...,K1a2 . Следовательно, этот остовный подграф является покрытием xi = (Wi, Qix).

Покрытие xi = (Wi, Qix) - единственное. Предположим, что это не так. Тогда

существует еще одно покрытие xi = (Wi, Qix,) отличное от xi = (Wi, Qix). Но, как мы уже заметили, висячая вершина затравки может быть покрыта лишь одним ребром, то есть

покрытие xi = (Wi,Qix~) должно содержать все ребра, инцидентные висячим вершинам, и будет совпадать с xi = (Wi, Qix). Получили противоречие и xi = (Wi, Qix) является единственным покрытием затравки Hi = (Wi,Qi), (i = 1,2,...,nL-1) звездами.

Далее так как *Wi = EL , то объединение покрытий затравок

Hi = (Щ,Qi),(i = 1,2,...,nL-1) есть покрытие предфрактального графа GL = (VL,EL) звездами, а так как каждая звезда состоит из ребер одного ранга, то покрытие является покрытием звездами ранговых типов. Причем, состоит оно из a2nL-1 звезд. Затем это покрытие улучшается за счет введения a2nL-1 - a1 звезд, состоящих из одного ребра ранга L-1 и

критериев. Каждое из них инцидентно центру некоторой звезды .,(( = 1,2,...,a2)

соединяющего висячие вершины затравок, соответствующие звездам . Действительно, количество звезд покрытия уменьшается на a2nL-1 - a1, число ранговых типов звезд не увеличивается (звезда K-1 допустимого рангового типа), вес покрытия не увеличивается.

Кроме того, ни одно другое старое ребро не может улучшить покрытия ни по одному из

Чя - >УЛ2,

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

Из всего сказанного также следует, что вес покрытия оптимален и по построению равен a3 .

Таким образом, мы получили покрытие x оптимальное по всем трем критериям, значения которых равны a1, a2, a3 соответственно.

Трудоемкость алгоритма не превышает трудоемкости построения предфрактального графа GL =(VL,EL) и равна т(а1 ) = O(VL). Действительно, на первом этапе алгоритма

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

a2 + 3

находим из соотношения n = - a2, а ранг определяем как наименьшее целое число

удовлетворяющее неравенству L > 1 + logn -. В обоих случаях трудоемкость вычислений

много меньше трудоемкости построения предфрактального графа. На втором этапе алгоритма строим затравку, что требует O(n) операций и на трудоемкость алгоритма не влияет. Третий и четвертый этапы имеют одинаковую трудоемкость и, учитывая соотношение Щ\ = Q -1 (затравка является деревом), требуют O(N) действий, где

N = \VL\.

Замечание 1. Терема 1 остается справедливой в случае, когда старые ребра предфрактального графа GL = (VL,EL) пересекаются.

Замечание 2. Для случая a2 = 1 достаточно последовательным перебором (n = 1,2,...,a1,L = 1 + logna1) найти натуральные n и L таким образом, чтобы выполнялось условие a1 = nL-1 (подбор чисел всегда осуществим, ибо при n = a1, L = 2 равенство имеет место). После строится предфрактальный граф с затравкой звезда K1 n-1 [2].

Замечание 3. Если a1 является составным числом, представимым в виде a1 = snL-1, где

s>1, n, L - натуральные числа, - = t - натуральное число большее двух, то в этом случае

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

Замечание 4. Для случая a2 = 2 достаточно применить алгоритм а1 с той лишь разницей, что затравка будет представлять собой совокупность трех звезд K12, K11, K11, центры которых последовательно соединены ребрами.

Литература:

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

2. А.М. Кочкаров Распознавание фрактальных графов: Алгоритмический подход. Нижний Архыз: Издательский центр CYGNUS , 1998.- 170 с.

3. И.З. Батчаев Об одной многокритериальной задаче покрытия предфрактальных графов звездами ранговых типов. Деп. в ВИНИТИ в 2002 г. №724-В2002.

4. И. З. Батчаев Об одной многокритериальной задаче покрытия предфрактальных графов звездами одного рангового типа. Нальчик: Известия КБНЦ РАН №1(8), 2002. С. 1-5.

5. И.З. Батчаев, А.М. Кочкаров Математическая модель задачи размещения центров технического обслуживания автомобильной компании. Международная конференция Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики Тез. докл.- Нальчик, НИИ ПМиА КБНЦ РАН, 2001. С. 14-16.