24. Антисимметричные отношения без контуров, порядковые отношения, порядковые функции нечеткого отношения порядка

Рассмотрим нечеткое отношение ( конечное), которое обладает следующими свойствами: 1) рефлексивностью (согласно (16.7)); 2) антисимметрией (согласно (22.1)); 3) не имеет контура в соответствующем обычном графе, отличного от петель, т. е. контуров длины 1, таких, как .

Такое отношение называется нечетким порядковым отношением.

Пример 1. Нечеткое отношение на рис. 24.1 есть порядковое отношение. По связанному с этим отношением обычному графу (рис. 24.2) можно проверить, что это отношение действительно рефлексивно, антисимметрично и не имеет других контуров, кроме петель.

Рис. 24.1.

Рис. 24.2.

Понятие порядковой функции обычного антисимметричного конечного графа без контуров. Рассмотрим обычный граф без контуров ,  конечное. Через  опять обозначим упорядоченную пару , где  обозначает отображение  в , в общем случае многозначное.

Определим обычные подмножества , такие, что

                        (24.1)

где  - наименьшее целое число, такое, что

.                   (24.2)

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

.              (24.3)

Функция , определенная условием

,                     (24.4)

называется порядковой функцией обычного графа без контуров.

Другими словами, менее точно, но более кратко можно представить себе разложение множества вершин обычного графа  без контуров на обычные подмножества, непересекающиеся и упорядоченные, так, что если одна из этих вершин принадлежит подмножеству, несущему номер , то все вершины, следующие за данной вершиной, должны располагаться в подмножестве с номером, большим, чем .

Обычные подмножества такого разложения называются уровнями.

Пример. Обычный граф без контуров на рис. 24.3 разложен по уровням на рис. 24.4. Если  - вершина графа, то каждому  здесь соответствует  или просто . Функция , представленная на рис. 24.5, есть порядковая функция графа. Нумерация вершин показана на рис. 24.6.

Рис. 24.3.

Рис. 24.4.

Рис. 24.5.

Рис. 24.6.

Порядковая функция графа в общем случае не единственна: она может определяться относительно наибольших элементов упорядоченного множества вместо наименьших; скажем, упорядоченных справа налево вместо слева направо, как мы это сделали в примерах на рис. 24.3 - 24.6.

Понятие порядковой функции играет важную роль во многих теоретических комбинаторных проблемах и практических приложениях.

Распространение понятий порядковой функции на обычные графы с контурами. Для этого достаточно рассмотреть классы эквивалентности (по отношению «существует путь из  в  и обратно») обычного графа.

Эти классы являются максимальными обычными подмножествами для отношения эквивалентности. Они образуют порядок (полный или частичный, в зависимости от случая). Если порядок полный, то имеем порядковую функцию, если порядок частичный, то ищем порядковую функцию обычного графа без контуров, образующую эти классы.

Пример приведен на рис. 24.7-24.10.

Рис. 24.7.

Рис. 24.8.

Рис. 24.9.

Рис. 24.10.

Метод определения уровня графа без контуров. Рассмотрим булеву матрицу обычного графа, изображенного на рис. 24.3; эта матрица приведена на рис. 24.11. В строке  подсчитаны суммы строк этой матрицы. Нули в  дают вершины, которым не предшествует ни одна другая вершина; таким образом, вершины  и  составляют уровень . Исключив из сумм строки  значения, записанные в строках  и , получим строку в которой нули из  заменены знаком  (крестом). Появившиеся в строке  нули дают вершины, которым не предшествует ни одна другая вершина, кроме удаленных  и ; это вершины , , и , которые образуют . Теперь из  вычтем суммы строк ,  и  после замены всех ранее появившихся нулей крестами; новые нули, появившиеся в , дают вершины, для которых не существует других предшествующих вершин, кроме удаленных , , , , . Вершины ,  и  составляют . Этот процесс мы продолжаем до тех пор, пока не переберем все точки. После этого остается только построить обычный граф (рис. 24.4), в котором вершины появляются на соответствующих им уровнях. Произвольная нумерация вершин представлена на рис. 24.6, где изображена порядковая функция.

Рис. 24.11.

Когда граф содержит по крайней мере один контур, найдется строка , в которой невозможно добиться появления нового нуля. Этот факт дает автоматическое средство для выявления контуров в графе.

Чтобы получить порядковую функцию при обратном упорядочении уровней (справа налево), когда выделяются наибольшие элементы данного порядка, можно применить ту же самую процедуру к транспонированной булевой матрице (строки становятся столбцами и наоборот). Пересматривая пример на рис. 24.3 - 24.6, находим порядковую функцию, когда уровни упорядочены справа налево. Результат изображен на рис. 24.12.

Рис. 24.12.

Порядковая функция нечеткого отношения порядка. Отношение порядка - это обычное отношение; оно рефлексивно, антисимметрично, не имеет контуров; кроме того, оно транзитивно. Следовательно, для него можно определить порядковую функцию.

Рассмотрим иллюстративный пример. На рис. 24.13 изображено нечеткое отношение порядка, которое представляет собой частичный порядок. На рис. 24.14 представлена порядковая функция соответствующего обычного графа относительно наименьших элементов. В этом графе мы умышленно опустили петли.

Рис. 24.13.

Рис. 24.14.

Теперь рассмотрим нечеткое отношение порядка, изображенное на рис. 24.15,а. Соответствующий ему обычный граф изображен на рис. 24.15,б. Переставляя элементы так, что порядковая функция, приведенная на рис. 24.14, не меняется (на рис. 24.14,а и 24.15,б представлен один и тот же обычный граф), мы видим, как появляется треугольная матрица. Пересматривая нечеткое отношение порядка в полном порядке его элементов, выбранном таким образом, чтобы не нарушалась порядковая функция, получаем нечеткое отношение порядка, которое будем называть треугольным. Известно, что при любых вычислениях важно знать, как привести матрицу к треугольной форме.

Рис. 24.15.

Полезность понятия порядковой функции для нечетких отношений предпорядка. В § 23 мы видели, что понятие класса подобия индуцирует в нечетком отношении квазипорядка (полный или частичный) порядок классов подобия (если квазипорядок приводимый).

Очевидно, что соответствующий этому порядку обычный граф рефлексивный и антисимметричный, а также и транзитивный. Если предпорядок является порядком, он может быть приведен, как это мы только что видели, к такому виду, что соответствующая ему матрица будет иметь треугольную форму. Если предпорядок не является порядком, то его матрицу всегда можно привести к блочно-треугольному виду. Такая блочно-треугольная форма уже была представлена в примере на рис. 23.10, который мы воспроизводим здесь вместе с соответствующей булевой матрицей (рис. 24.16), чтобы показать, что она действительно блочно-треугольного вида.

Рис. 24.16.

К тому же построение порядковой функции позволяет автоматически получать диаграмму Хассе, соответствующую отношению порядка, и определять уровни этой диаграммы.