Compact graphs and the deterministic algorithm for their synthesis.pdf Проблема анализа и синтеза структур вычислительных систем (ВС) традицион-но решается методами теории графов. При этом между множествами модулей ВС ивершин V графа G( V, E) и между множествами линий связи и ребер E графа уста-навливают биективные соответствия; задержки при этом оценивают метрическими ха-рактеристиками соответствующих графов - их диаметром d или радиусом. В рамкахрешения проблемы синтеза структур ВС рассматривается синтез s-регулярного графапорядка n = | V | с минимально возможным при значениях n и s диаметром d. Такиеграфы далее называем n(s)-компактными.Решение задачи основано на предложенном в [1] описании графа проекциями. Про-екция P(vj) графа G(V, E) является многоуровневой конструкцией, на нулевом уровнекоторой расположена ракурсная вершина vj из V. Порожденное ею подмножество вер-шин первого уровня Vcj содержит все вершины ее окружения N( v j ) , а i-й уровень(i ^ 1) представляет собой совокупность подмножеств вершин, каждое из которых по-рождено вершиной (i - 1)-го уровня и является окружением этой вершины без вершин,предшествующих ей в проекции. Вершине vj k-уровневой проекции Pk(vo) соответству-ет упорядоченное множество вершин W(vj) = (v0, v c 0 , . . . , vj), представляющее собойпростую цепь из ракурсной вершины v0 нулевого уровня этой проекции в вершину vji-го уровня (i ^ k); длина этой цепи L(v0, v j ) = i. В общем случае некоторые вершиныпроекции Pk (v0) могут быть mj-кратными (1 ^ mj). Значение кратности mj соответ-ствует числу простых цепей из ракурсной вершины v0 в вершину vj. Номер i уровняв проекции P (v0) определяет удаленность вершин этого уровня от ракурсной верши-ны v0, а уровень k, впервые доопределяющий множество вершин всех нижерасполо-женных уровней проекции графа G(V, E) до V, соответствует эксцентриситету e(v0)ракурсной вершины v0 в проекции P(v0) и вершинной полноте этой проекции. Приk = e(vo) проекция Pk(v0) графа G( V, E) становится вершинно-полной, и каждая вер-шина графа G(V, E) хотя бы однажды появляется на уровне i ^ e(v0) проекции Pk(v0).Если при этом e(u) = e = const для всех u G V, то диаметр d графа G равен значению e(напомним, что d(G) = maxe(u)), и число уровней в каждой вершинно-полной проек-uGVции графа также будет равным этому значению и диаметру графа. Таким образом,задача построения п(з)-компактного графа порядка n и степени s трансформируетсяв задачу построения такой системы проекций графа, в которой каждая проекция явля-ется вершинно-полной, а число уровней - минимально достаточным для размещениявсех n вершин.Нетрудно увидеть, что максимально возможное число вершин ni+1, которое спо-собен вместить (i + 1)-й уровень проекции s-регулярного графа, определяется рекур-сивно: ni+1 = n^(s - 1), причем первые два члена этой последовательности - n0 = 1 иn1 = s. Тогда максимально возможное для k-уровневой проекции Pk (v0) число вершинkс единичной кратностью составит N (s) = 1 + s . (s - 1)i - i . Этот предел являетсяi=1верхним для порядка s-регулярного графа при заданном числе k уровней в его про-екциях; ограничение снизу определяется (k - 1)-м уровнем: Nk-1(s) < n. Справедливои обратное: минимальное число уровней в проекции графа определяется, исходя иззначений порядка графа и его степени. Таким образом, для n(s)-компактного гра-фа его диаметр d (равный эксцентриситету любой ракурсной вершины) находится изнеравенстваd-1 d1 + s . (s - 1)i - i < n ^ 1 + s. (s - 1)i - i.i=1 i=1Приведём модифицированный в сравнении с [2] детерминированный алгоритм син-теза компактных графов.1. Из условия компактности и заданных значений порядка и степени/диаметраполучим значение диаметра/степени графа.2. Введем разметку вершин графа, произвольно выберем ракурсную вершинуv0 G V и построим для нее базовую d-уровневую проекцию Pd(v0) остовного подгра-фа искомого n(s)-компактного графа G( V, E). Размещение n вершин на d уровняхd dэтой проекции может быть произвольным, но таким, что (J V = V, или У] |Vj| = |V|.i=0 i=0Вершины Vl 1-го уровня проекции Pd(v0) составляют окружение N (v0) ракурсной вер-шины v0, |Vl| = s; на последующих 2 < i ^ d уровнях |Vj + 1| ^ |Vj| (s - 1).3. Окружения N' ( v j ) вершин из базовой проекции Pd(v0) сведем в список N'(G) == (N'(vj) : Vj G V). Вершины vj G V, окружения которых пока не определены полно-стью, включим в множество V' = {vj G V : |N'(vj)| < s}. Окружения N (vj) этихвершин vj дополним потенциальными подмножествами NP (vj)x = V \ W(v0, vj), ниж-ний индекс x при которых равен числу недостающих в этом окружении вершин (x == s - |N' (vj)|): N (vj) = N' (vj) UNP (vj)x. Здесь W(v0,vj) -множество всех пред-шественниц вершины vj в проекции Pd(v0), составляющих простую цепь из v0 в vj.При необходимости обусловим синтез n(s)-компактного графа его обхватом g. В этомслучае потенциальные подмножества вершин NP (vj), входящие в состав N (vj), долж-ны быть скорректированы: Np (vj) := Np (vj) \ {vj G Np (vj) : i, j G {1,..., d} , i + j < g}.Здесь индексы при вершинах vj, vj G V соответствуют номерам уровней проек-ции Pd(v0), на которых эти вершины располагаются.4. Исходя из списка N (G) и заданного обхвата, поочередно выстраиваем остальныепроекции Pd(vj), vj G V, уточняя при этом потенциальные подмножества Np (vj) ивнося изменения в список N' (G) графа и в выстроенные ранее проекции.5. Задача синтеза графа решена, когда список N' (G) определен полностью, т. е.для всех vj G V имеет место |N(vj)| = s, NP(vj) = 0. Если это условие не выполнено,то в одном из потенциальных окружений следует выбрать вершину и перейти к п. 4.При этом мощность некоторых потенциальных подмножеств в списке N' (G) вершинможет стать меньше их индекса, т.е. |Np(vj)x| < x. Тогда следует вернуться к пред-шествующей подстановке с запретом таковой и выбрать альтернативный в данномпотенциальном подмножестве вариант.В работе приведены примеры 13(4)-компактных графов с обхватами g = 3 и g = 4,а также 16(3)- и 16(5)-компактных графов с обхватами g = 5 и g = 4 соответственно,сгенерированных в соответствии с описанным выше алгоритмом.

Скачать электронную версию публикации