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

О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей.

В этом разделе рассматриваются так называемые бесповторные графы.

Под беспооторпьши графами будем понимать ПИГ над базовым множеством (АСП, 0) или над базовым множеством п, 0), в которых для любой цепи нагрузки любых двух различных ребер этой цепи не пересекаются по переменным.

Мы покажем, что в классе бесповторных графов оптимальные графы древовидны.

Предварительно докажем два вспомогательных утверждения.

Лемма 15. Если ПИГ U над одним из трех базовых множеств (Мп, 0), (АСП, 0), п, 0) является оптимальным для некоторой ЗИП типа Sbooit то в графе U в любую вершину, функция фильтра которой есть элементарная монотонная конъюнкция, входит не более одного ребра.

Доказательство. Доказательство будем вести от противного. Предположим, что в графе U существует вершина /3, функция фильтра которой есть элементарная монотонная конъюнкция и в когорую входит несколько ребер. Так как функция фильтра вершины /3 является элементарной монотонной конъюнкцией, то вершина /3 образует характерное подмножество, и, следовательно, согласно теореме 21 существует главная цепь (обозначим ее Ср) этой вершины. Пусть через вершину /3 проходит несколько главных цепей записей, которые обозначим Ci,..., Cm- Понятно, что т > 0, так как иначе вершину 0 вместе с входящими в нее и исходящими из нее ребрами можно было бы удалить, а в силу оптимальности графа U из него нельзя удалить ни одного ребра.

Пусть Ci = C}Ci = 1,...,m), где С} — часть цепи С{ от корня до вершины /3, а С — часть цепи С{ после вершины 0 до соответствующей записи.

Поскольку функция фильтра <рр вершины /3 равна проводимости цепи Ср, то, следовательно, <рр не зависит от проводимости цепей С{, г = 1,...,т. Отсюда мы можем объявить вместо цепей Ci в качестве главных цепей цепи С[ = СрС? (t = 1,..., ш) после чего, удалив ребра, не принадлежащие новым главным цепям (в частности, удаляются все ребра, входящие в вершину (3, за исключением ребра, принадлежащего цепи Ср)у получим ПИГ U, который разрешает исходную ЗИП, и в соответствии с леммой б имеем T(U) < T(U), что противоречит оптимальности графа U и тем самым доказывает лемму.

Лемма 16. Если ПИГ U над одним из двух базовых множеств (Кп, 0), (Хп, 0) является оптимальным в классе бесповторных графов для некоторой ЗИП типа Sbool, то функция фильтра любой вершины графа U является элементарной монотонной конъюнкцией.

Доказательство. Доказательство будем вести от противного. Пусть Р — вершина, функция фильтра которой не есть элементарная монотонная конъюнкция. В силу оптимальности графа существует лист а такой, что существует ребро (или цепь ребер), соединяющее а и Р (если существует цепь ребер, то без ограничения общности считаем, что Р — ближайшая к а вершина, функция фильтра которой не является элементарной монотонной конъюнкцией).

Обозначим функцию проводимости от р к а через К. Пусть ipp = = K.'i V • • • V Кт. Так как а является элементарной монотонной конъюнкцией, то в силу леммы 15 и определения вершины р

Но Ki2 V • • • V Кт) не может быть элементарной монотонной конъюнкцией, так как в силу бесповторности графа конъюнкция К не может содержать переменных, принадлежащих конъюнкциям

к2,...,кт.

Полученное противоречие и доказывают лемму.

Справедлива следующая теорема.

Теорема 24. Пусть Т одно из двух базовых множеств (АСП, 0) или (Л"п, 0), тогда для любой ЗИП I типа Sbool граф над базовым множеством Т, являющийся оптимальным в классе бесповторных графов для задачи I, имеет вид дерева.

Доказательство. Пусть U — оптимальный бесповторный граф над базовым множеством Т для задачи I. Согласно лемме 16 функция фильтра любой вершины графа U является элементарной монотонной конъюнкцией, следовательно, в соответствии с леммой 15 в каждую вершину ПИГ U входит не более одного ребра, что означает, что граф U имеет вид дерева.

Что и требовалось доказать.

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