Методы и средства защиты информации



              

Определение 18.3 - часть 3


Очевидно, что независимые множества (и только они) задаются условием r(A) = |A|. Ранговая функция матроида обладает свойствами

r(A) ÎZ; r(Æ) = 0;                                                                               (18.6.1)

r(A) £ r(A È b) £ r(A) + 1;                                                                  (18.6.2)

Если r(A È b) = r (A È c) = r(A), то r (A È b È c) = r(A).               (18.6.3)

Обратно, пусть некоторая функция r(A) обладает свойствами (18.6). Назовем независимыми те множества А, для которых r(A) = |A|. Тогда эти множества задают матроид, а функция r является его ранговой функцией. Возможно также определить матроид через минимальные зависимые множества, называемые циклами. Матроид называется связным, если для любых двух его точек существует содержащий их цикл.

Теперь мы можем сформулировать основной результат.

Теорема. Для любой БД-совершенной идеальной СРС, реализующей структуру доступа Г, независимые множества, определяемые условием

log|S0| ||VA|| = |A|, задают связный матроид на множестве {0, 1,…, n}. Все циклы этого матроида, содержащие точку 0, имеют вид 0 È А, где А Î Гmin.

Доказательство теоремы приведено в соответствующей литературе и выходит за рамки данной книги. Главным в доказательстве теоремы является “проверка” целочисленности функции h(A). В самом деле, h(A) очевидно обладает остальными свойствами (6) и, следовательно, при условии целочисленности является ранговой функцией и задает матроид.

Отметим, что из второй части утверждения теоремы следует, что разным идеальным СРС, реализующим данную структуру доступа Г, всегда соответствует один и тот же матроид, поскольку матроид однозначно определяется всеми циклами, проходящими через фиксированную точку. Тем самым, каждой идеальной реализуемой структуре доступа соответствует однозначно определенный матроид.

В связи с теоремой возникает несколько естественных вопросов. Прежде всего, не порождают ли идеальные СРС все матроиды? Нет, например, матроид Вамоса не может быть получен как матроид идеальной СРС.С другой стороны линейные матроиды есть ни что иное, как рассмотренные идеальные одномерные линейные СРС. В связи с этим возникает вопрос о существовании структуры доступа Г, которую невозможно реализовать в виде идеальной одномерной линейной СРС, но можно в виде идеальной многомерной линейной СРС. Такие примеры имеются, и, значит, мы можем говорить о многомерных линейных матроидах как классе матроидов более общем, чем линейные.

Итак, идеальных СРС больше, чем линейных матроидов, но меньше, чем всех матроидов. Уточнить, насколько больше, представляется довольно сложной задачей. В частности, существует ли идеально реализуемая структура доступа Г, которую невозможно реализовать как идеальную линейную многомерную СРС?




Содержание  Назад  Вперед