Сложность информационного графа

Прежде чем вычислять сложность ИГ [/*, докажем одно вспомогательное утверждение.

Пусть 0 некоторая вершина некоторого ИГ U. Скажем что подграф U' графа U является зависимым от /?, если он содержит вершину /?, является связным, состоит только из таких вершин а ИГ ?/, что любая цепь, ведущая из корня ИГ U в вершину а, проходит через вершину 0 и содержит все ребра ИГ С/, исходящие из вершин V.

Так, например, если вершина 0 является корнем связного ИГ V, то ИГ U будет зависимым от 0. А для произвольной вершины 0 любой зависимый от 0 граф по крайней мере содержит все ребра, исходящие из вершины 0.

Договоримся через Р (АВ) обозначать условную вероятность события А при условии осуществления события В.

= Р (В|Х').

Пусть X — множество запросов с заданным на нем вероятностным пространством (X, сг, Р). Пусть X' € о. Вероятностным пространством, порожденным множеством X', назовем вероятностно* пространство (Ха Р'), где а' = {В 6 <�г. В С X'}, Р' — такая вероятностная мера на что для любого В € <�т' имеем Р'(В) =.

Лемма 51. Пусть Р некоторая вершина некоторого ИГ U над базовым множеством, функции которого определены на множестве запросов X. Пусть (X, а, Р) — вероятностное пространство над X. Пусть X' = N_ip$. Пусть (Х <�т Р') — вероятностное пространство, порожденное множеством X'. Пусть U' — зависимый от Р подграф ИГ U. Пусть Т' — сложность ИГ U' (как отдельного ИГ с корнем в вершине Iв) для вероятностного пространства (Х а Р'). Тогда сложность U' как подграфа ИГ U для вероятностного пространства (X, а, Р) равна T (U') = Р (Х') • Г.

Доказательство. Рассмотрим произвольную вершину а подграфа U'. Из определения зависимого подграфа следует, что N С С N (p₀ = XСледовательно,

Откуда сразу следует утверждение леммы.

Вычислим сложность ИГ U*.

Пусть Р — некоторая вершина ИГ U*. Чтобы сократить этажность формул договоримся обозначать JV (/?) = N_V6.

Введем следующие множества вершин ИГ U*:

Обозначим через T_q (g = 1,2,…, М) суммарную сложность ребер ИГ U_q за исключением ребер, исходящих из вершин из множества В4. Через T_q(x) (q = 1,2, …, М) обозначим сложность ИГ U_q на запросе х минус количество вычисленных переключателей, приписанных вершинам из множества В4.

Покажем по индукции, что.

%ЛЯ Любого X G Xi_nt2- Базис индукции: q = 1.

Из соотношений (4.67), (4.78) и (4.79) легко следуют следующие /тверждения.

Поскольку из корня ИГ U* растет ИГ Uj^i ₀ i, сложность которого оценивается соотношением (4.68), вершинам приписаны переключатели <$, из вершин 0″ исходят ИГ р _v зависимые от в" и сложность которых оценивается соотношением (4.69), а из вершин Оу исходят ребра с предикатом тождественная 1, то с учетом (4.97) согласно лемме 51 имеем.

и для любого х € Xi_nt2

Индуктивный переход. Пусть q € {2,…, М} и утверждение индукции выполняется для q — 1. Обозначим.

Из соотношений (4.72)-(4.74), (4.80), (4.81), (4.83) и (4.84) легко следуют следующие утверждения.

Поскольку из вершин т?^-1 и 7?^-1 исходят ИГ U_fq ,_i ,_j, слож;

ность которых оценивается соотношением (4.68) и зависимые от этих вершин, из вершин $~¹ исходят ИГ U_f4 ,_i ,_i, а из вершин —.

ИГ Ul₉j _/9 сложность которых оценивается соотноше;

нием (4.69) и которые зависимы от своих корневых вершин, из каждой вершины из множества исходит ребро с предикатом тождественная 1, ведущее в вершины i9?, а из каждой вершины из множества исходит ребро с предикатом тождественная 1, ведущее в вершины /??, то с учетом (4.98) согласно лемме 51 имеем.

и для любого х Е Xint2 выполняется.

При q = М нам надо делать на одно вычисление меньше, так как в ИГ Um нет вершин типа tff*, т. е.

для любого х Е Xi_nt2- Обозначим.

Из (4.73), (4.75)-(4.77), (4.82) непосредственно проверяется справедливость следующих утверждений.

Пусть Iв Е #13, тогда для некоторых q, 5, г, j из вершины (3 исходит ИГ U_q, зависимый от вершины В. Обозначим ^A«ij

Учитывая, что при попадании в вершину из В2 мы вычисляем один предикат, приписанный ребру, исходящему из этой вершины, а при попадании в вершину из В мы вычисляем один переключатель, приписанный этой вершине, имеем.

Согласно лемме 51 и (4.70) для данной вершины р

Согласно (4.99) для любого запроса мы можем попасть не более чем в одну вершину из #gU#i2, следовательно при этом мы в худшем случае выполним 2 + log₂ к вычислений плюс перечисление ответа. Согласно (4.100) для каждого q = 2,…, М и любого запроса мы можем попасть не более чем в одну вершину из В4 U Вт и не более чем в одну вершину из Вц ив каждом из этих случаев мы выполним не более чем 2 + log₂ к вычислений плюс перечисление ответа. Тем самым для любого запроса х € X{_nt2

Тем самым, теорема 52 полностью доказана.

Понятно, что данный метод может быть обобщен для п-мерной задачи интервального поиска для произвольного п.