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



              

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


Естественный вопрос состоит в том, для каких структур доступа Г существуют реализующие их идеальные (вероятностные или комбинаторные) СРС. Как уже отмечалось, наилучший на сегодняшний день ответ использует слово матроид. Напомним определение матроидов и некоторые их основные свойства.

Матроидом называется конечное множество Х и семейство I его подмножеств, называемых независимыми (остальные множества называются зависимыми), если выполнены следующие свойства:

Æ Î I;                                                                                                   (18.5.1)

Если A Î I и B Ì A, то B Î I;                                                             (18.5.2)

Если A, B Î I и |A| = |B| + 1,                                                                           

то существует a ÎA\B такое, что a È B Î I.                                     (18.5.3)

Пример 18.4. Множество Х — это множество векторов в некотором линейном векторном пространстве, а независимые подмножества — это линейно независимые подмножества векторов.

Собственно с этого примера и началась теория матроидов, вначале как попытка дать аксиоматическое определение линейной независимости векторов через “внутренние свойства”, т.е. не апеллируя к понятию вектора. К счастью, попытка не удалась, так как нашлись матроиды, не представимые как линейные (т.е. как системы векторов), а сама теория матроидов разрослась далеко за пределы линейной алгебры.

Пример 18.5. (матроид Вамоса). Рассмотрим следующее множество: Х = {1, 2, 3, 4, 5, 6, 7, 8} и положим a = {1, 2}, b = {3, 4}, c = {5, 6} и d = {7, 8}. Матроид Вамоса определяется как матроид, в котором множества a È c, a È d, b È c, b È d, c È d, а также все подмножества из пяти или более элементов являются зависимыми. Известно, что этот матроид не является линейным.

Матроид также можно определить через так называемую ранговую функцию r(A) матроида, определяемую как максимальная мощность независимого подмножества В Í А.


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