Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

Объем информационного графа.

Для вычисления объема информационного графа U* вычислим сначала объем ИГ U.

ИГ U содержит ИГ 0 v объем которого согласно (4.68) равен

Из каждой вершины Т{ (i = l,...,&ai) исходит два ребра, что суммарно дает 2ках ребер.

Из каждой вершины т" (г = 1,..., kai 1) исходит ИГ U%ltl ti г, объем которого согласно (4.69) равен Q((/|lti х) = (2 + c)(kai — t) + l.

В каждую вершину (j = 1 ,...,fcai) из каждой вершины Tjj,

г = 1,... ,j, ведет ребро, т. е. суммарное число ребер, ведущих в вершины /?j, равно

Подсчитаем объем ИГ Uq при 2 ^ q ^ М.

ИГ Uq содержит в себе ИГ Uq-.

Из каждой вершины 0?“ (i = 2,..., fca,+ *«“1) исходит ИГ

иГя ,ч-1 »«-!> объем которого согласно (4.68) равен (2-f с)(A;Q« —1)4-1.

Из каждой вершины (3q~ , (г = 1,...,Дгв1+"*«”1) исходит ИГ , объем которого согласно (4.69) равен (2 4- с)(ка« -1)4-1.

'*«• »**+1

Из каждой вершины 7?”1, (г = 2,... ,&ai+ **”1 4- 1) исходит ИГ иГя 19-1 ц-1* Его объем равен (2 + с)(А;а* —1)4-1. Из каждой вершины

Oqij (j = 1,..., — 1) исходит по 2 ребра. Из каждой вершины

(j = 1,..., кая — 2) исходит ИГ rLj , ,_i, объем которого

равен (2 4- с)(ка* — j — 1) 4-1. Таким образом, объем ИГ, растущего из 0—1

вершины 7* , равен

Если q < М, то в вершины tiqt (t = 2,...,&ai+"’+e*) из каждой вершины i = 2,..., +*••+««-1 4- 1, у = 1,..., A;Q« — 1, и каждой

вершины rqij, г = 2,..., A;al+''","a«“,, j = 1,...,&а«, ведет по одному ребру. Следовательно суммарное число ребер, ведущих в вершины равно

В вершины 0J (5 = 1,..., +?•?+««) из каждой вершины г =

= 2,...,fca,+"«“1 4-1, j = — 1, t = у4-1,...,А:а«, и каждой

вершины Tqij, г = 1,...,fcttl+"'•+*«-!, j = l,...,fca«, ведет по одному ребру. Следовательно суммарное число ребер, ведущих в вершины /3J, равно

Тем самым, при 2 ^ q < М

Учитывая, что суммарное число ребер, ведущих в вершины dqt, равно 0(kQl+'«), и есть еще другие слагаемые имеющие тот же порядок, получаем, что

Вычислим объем информационного графа U*.

Из (4.85) легко видеть, что

Из каждой вершины q = 1,..., М, 5 = 1,..., kai+‘"+a*-1, { = = 2,..., ka* — 1, j = i + 1,..., к°ч (при q = 1 индексы меняются как s = 1, i = 1,..., kai 1, j = i -4-1,..., kQl) исходит ИГ U^q , объем

которого согласно (4.70) и (4.87) равен

Суммируя по всем q, s, г, j, получаем, что объем ИГ, растущих из вершин Sjjj, (обозначим его Qi) не превышает

Суммируя по всем g, t, j, получаем, что объем ИГ, растущих из вершин т;?., (обозначим его Q2) не превышает

Из каждой вершины Я = 2, t = 1,... ,fcQt,+"+a«“1,

j = 2,исходит ИГ С/д, , объем которого согласно (4.70) и (4.87) равен

Q(^?j .) $ 4(j - l)fc!-(“‘+'•+“-) - 1 + 6c[l0g2((j - l)fcl-(a,+- +a,))]

Суммируя по всем <7, г, j, получаем, что объем ИГ, растущих из вершин ???, (обозначим его <Эз) не превышает

Из каждой вершины /3^, j = l,...,fcai+"+Q:M, исходит по одному ребру, следовательно, суммарное число ребер, исходящих из вершин равно

Исходя из (4.89), положим

Согласно (4.86) и (4.94)

Поскольку

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы