Методы бикластеризации для анализа интернет-данных

       

Частично упорядоченные множества и решётки


Определение 2.1   Бинарное отношение

на некотором множестве

называется отношением (нестрогого) частичного порядка, если для

:

  • (рефлексивность);

  • и

    , то

    (антисимметричность);

  • и

    , то



    (транзитивность).

  • Множество S с определённым на нем отношением частичного порядка

    (частично упорядоченное множество) обозначается

    . Если

    , то говорят, что элемент

    меньше, чем

    ,

    или равен ему. Если для

    не существует

    , такого что

    , то

    называют максимальным элементом

    (относительно

    ).

    Если

    и

    , то пишут

    и говорят, что

    строго меньше, чем

    .

    Определение 2.2   Пусть

    — частично упорядоченное множество. Элемент

    называется соседом снизу элемента

    , если

    и

    . В этом случае

    называется соседом сверху

    (обозначается

    ). Направленный граф отношения

    называется графом покрытия.

    Конечное частично упорядоченное множество

    может быть графически представлено с помощью диаграммы Хассе (или просто диаграммы [1]). Элементы

    изображаются в виде точек. Если

    , то

    размещается "над"

    (вертикальная координата

    больше вертикальной координаты

    ), и две точки соединяются линией.

    Определение 2.3   Верхней гранью подмножества

    в упорядоченном множестве

    называется элемент

    , такой что

    для всех

    . Точная верхняя грань множества

    (называемая также наименьшей верхней гранью или супремумом) множества

    (обозначается sup

    ) есть верхняя грань

    такая, что

    для любой верхней грани

    подмножества

    . Двойственным образом (с заменой

    на

    ) определяется понятие точной (наибольшей) нижней грани или инфимума inf

    .

    Определение 2.4   Бинарная операция

    называется полурешёточной, если для некоторого

    и любых

    :

    (идемпотентность);

    (коммутативность);

    (ассоциативность);

    .

    Для

    и

    мы пишем

    вместо

    . Если

    , то

    .

    Определение 2.5   Множество

    с определённой на нем полурешёточной операцией

    называется полурешёткой

    .

    Полурешёточная операция

    задает два частичных порядка

    и

    на

    (

    ):

        и

    Тогда множество с определённой на нем полурешёточной операцией


    будем называть нижней полурешёткой (относительно частичного порядка


    ) и верхней полурешёткой (относительно частичного порядка


    ).

    Определение 2.6   Пусть


    — полурешётка. Множество


    называется системой замыканий [33] или семейством Мура [1] (относительно


    ), если


    .

    Очевидно, что система замыканий (относительно


    )


    с определённой на ней операцией,


    и


    , образует полурешётку.

    Определение 2.7   Упорядоченное множество


    с определёнными на нем полурешёточными операциями


    и


    называется решёткой, если


    и


    являются, соответственно, нижней и верхней полурешётками (относительно


    ).

    Операции


    и


    называют операциями взятия точной нижней и верхней грани в решётке, или инфимума и супремума соответственно.

    Определение 2.8   Подрешёткой решётки


    называется подмножество


    такое, что если


    ,


    , то


    и


    .

    Полурешёточные операции


    и


    удовлетворяют в решётках следующему условию:


    (поглощение).

    Из любой конечной полурешётки можно получить решётку добавлением одного (максимального или минимального в зависимости от типа полурешетки) элемента.

    Решётка называется полной, если у каждого подмножества его элементов есть супремум и инфимум (всякая конечная решётка является полной).

    Определение 2.9   Интервал


    состоит из всех элементов
    , которые удовлетворяют неравенствам


    . Порядковым фильтром (идеалом) решётки


    называется подмножество


    такое, что если


    ,


    и


    , то


    (соответственно,


    ,


    и


    , то


    ).

    Элемент


    решётки называется инфимум-неразложимым или


    -неразложимым (или неразложимым в пересечение), если для любых


    и


    , не выполняется


    . Элемент


    решётки называется супремум-неразложимым или


    -неразложимым (или неразложимым в объединение), если для любых


    и


    не выполняется


    .

    Подмножество


    полной решётки


    называется инфимум-плотным, если


    , и супремум-плотным, если


    ).

    Определение 2.10   Пусть


    и


    — частично упорядоченные множества. Пара отображений


    и


    называется соответствием Галуа между частично упорядоченными множествами


    и


    , если для любых




    и


    :



    ;



    ;



    и


    .

    Приведённые условия эквивалентны одному:


     [1,33,28].

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


    Содержание раздела