Математические методы в библиотечной работе. Елизаров А.М - 43 стр.

   Определение 2. Отношение строгого поряд-
на R называется совершенным строгим порядком,
если для всякой пары несовпадающих элементов
х и у из М выполняется либо xRy, либо yRx.
   По доказанной выше теореме оба эти свойства не
могут выполняться одновременно, поэтому все пары
из М М разбиваются на три класса: класс пар (х, x);
класс пар (х, у) таких, что xRy; класс пар (х, у) таких, что
yRx.
   Примерами совершенного строгого порядка могут
служить отношения „больше", лексикографического
порядка на множестве словарных статей в энцикло-
педии и т. д.
   Пример 1. Алфавитный каталог представляет
собой картотеку библиографических описаний, рас-
ставленную по алфавитному принципу: сначала фами-
лии, начинающиеся на А, затем на Б и т. д. С нашей
точки зрения, алфавитный каталог — это множество
фамилий авторов, на котором задано отношение лек-
сикографического порядка.
    Однако далеко не во всяком множестве можно
задать естественное отношение совершенного строгого
порядка. Например, на множестве всех подмножеств
из М отношение включения не является совершенным
строгим порядком, т. к. существуют подмножества
из М, которые не включаются одно в другое. Наибо-
лее интересный случай такого частичного строгого
порядка — так называемый древесный порядок.
    Определение 3. Отношение строгого порядка
R на М называется древесным порядком, если:
   1) из того, что xRy и xRz, следует, что либо
yRz, либо zRy;
   2) в М существует максимальный элемент x0 та
кой, что для любого x М выполнено xRx 0 .
    Первое условие этого определения означает, что
для всех элементов, предшествующих х, исходный
древесный порядок превращается в совершенный по-
рядок. Второе условие означает наличие элемента,
которому все подчинены.
   Граф отношения древесного порядка является
деревом (рис. 25).
    Пример 2. Рассмотрим множество рубрик Уни-
версальной десятичной классификации (УДК) и зада-
дим на нем древесный порядок: xRy, если рубрика х
                                     (д. п.)
                                                          43