Случай оптимальности перебора

Теорема 5. Если I = (X, V, р) — ЗИП и Т = (F, 0) — измеримое базовое множество, такие, что для любой записи у € V выполня-

етсяху, р € F иО{у, р)( U N_f)^9,mo

VeFx_v.p ⁷

Доказательство. Пусть V = {уьУ2>• • • >У*}- Каждому г 6 {l, fc}.

сопоставим некоторый запрос Xi € 0(у, р) ([J N/) — Легко.

_ VeFx_v.p ^У

видеть, что для любых таких i, j G {1, А:}, что i ф j, справедливо Ф %j'

Понятно, что U 6 U^T) Ф 0, так как ИГ, изображенный на рис. 1.5, соответствующий алгоритму перебора, разрешает ЗИП I. Обозначим этот ИГ через Uq.

Возьмем произвольный ИГ U € U{I, F). Так как U разрешает ЗИП J, то для каждого i € {1, А:} существуют лист а", которому приписана запись у*, и цепочка ребер С", ведущая из корня в лист а*, которая проводит запрос Х{. Нетрудно заметить, что для любых таких i, j 6 {!,&}, что i ф j, цепочки С{ и Cj не пересекаются по ребрам, поскольку, если бы существовало ребро, принадлежащее и С", и С, то нагрузка этого ребра принимала бы значение 1 одновременно и на х, — и на Xj, но, по определению х* и Xj таких функций в множестве F не существует. Отсюда сразу следует, что из корня ИГ U исходит по крайней мере к ребер, и, следовательно, для любого х 6 X T (U, x) ^ А, откуда T (U) ^ к и T (U) ^ fc, а в силу произвольности ИГ U имеем ^ к и Т (1,Т) ^ к. Но так как для ИГ Uo справедливо T (Uo) = = T (Uq) = А, то Т (/, Т) = Т (/, Т) — к, что и требовалось доказать.