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



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


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

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

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

:

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

  • и

    , то

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

  • и

    , то

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

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

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

    . Если

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

    меньше, чем

    ,

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

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

    , такого что

    , то

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

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

    ).

    Если

    и

    , то пишут

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

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

    .

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

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

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

    , если

    и

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

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

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

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

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

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

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

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

    , то

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

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

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

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

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

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

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

    , такой что

    для всех

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

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

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

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

    такая, что

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

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

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

    на

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

    .

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

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

    и любых

    :

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

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

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

    .

    Для

    и

    мы пишем

    вместо

    . Если

    , то

    .

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

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

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

    .

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

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

    и

    на

    (

    ):

        и

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




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