Билет №7. 1. Структура ВС типа “бинарное дерево”, “мультидерево глубины n и ширины ”

1. Структура ВС типа “бинарное дерево”, “мультидерево глубины n и ширины ”.

Бинарное дерево T_o(n). Структура ВС типа «бинарное дерево» обозначается T_o(n) глубины n описывается графом GS=(M, S*), где M={m_i}, i=0, …, N-1, N=2ⁿ-1; Содержит n рангов r (r={0, …,n-1}), причем в каждом ранге размещается ровно 2^r вершин так, что каждая вершина ранга r (0<r<n-2) соединяется с парой вершин ранга r+1.

Мультидерево глубины n и ширины k T₁(n, k). Структура ВС типа «Мультидерево глубины n и ширины k» T₁(n, k), число вычислителей N=k*2ⁿ описывается графом GS=(M, S*), где M={m_i}, i=0, …, N-1, а сеть S* содержит k двоичных деревьев, объединенных с помощью колец R₀ и _1.Корневая вершина j={1, …,k} каждого из k деревьев соединена ребром с вершиной и они образуют кольцо R₀ (, , …, ). Второе кольцо R₁ образованно вершинами листьев и содержит k*2^n-1 элементов.