Дискретно-непрерывная математика (стр. 40 )

и сильнейший путь (не единственный) имеет значение 0,5. Таким же об­разом находим, что не единственный сильнейший путь от К3 к K1 име­ет значение 0,2.

Аналогично находим, что для К2 → К3 это значение равно 0,4; для

К3 → К2 — 0,2, причем определение значений тривиально, посколь­ку каждый класс состоит только из одного элемента. Таким образом, мы получили, то, что изображено на рис. 13.9.

В более общем случае процедура для построения нечеткого отно­шения порядка между классами состоит в следующем.

В приводимом нечетком предпорядке находим классы подобия Kі. Для этого рассматриваем упорядоченные пары (х, у), для которых

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

2. Для каждой упорядоченной пары (Kі, Kj), i ≠ j рассматриваем нечеткое подотношение между Kі и Kj (строки Kі и столбцы Kj). Определяем глобальную проекцию подотношения [см. (2.13)];

таким образом,

3. Приписываем значение функции принадлежности пары

(Kі, Kj).

Пример 2. Пример на рис. 13.10 более сложный.

Рис. 13.10

В этом приводимом нечетком предпорядке можно заметить несколько особенностей, отсут­ствовавших в предыдущих примерах. Из рис. 13.11 очевидно, что меж­ду классами существует частичный порядок.

Рис. 13.11

В предыдущем же приме­ре порядок был полный (см. рис. 13.8).

Пример 3. Нечеткое отношение, представленное на рис. 13.12, есть приводимое отношение нечеткого предпорядка, если принять, что

Рис. 13.12

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

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

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

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

Пример 1. Нечеткое отношение на рис. 14.1 естьпорядковое отно - шение.

Рис. 14.1 Рис. 14.2

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

Понятие порядковой функции обычного антисимметричного конеч­ного графа без контуров. Рассмотрим обычный граф без контуров GE×E, Е конечное. Через G опять обозначим упорядоченную пару (Е, Г), гдеобозначает отображение Е в Е, в общем случае многозначное.

Определим обычные подмножества N1, N1,....., Nr, такие, что (Некоторые авторы предпочитают определять порядковую функцию обыч­ного графа, заменяя в формуле (14.1) обратное отображение Г-1 прямым Г. В результате такой замены в конце концов получается другой порядок уровней.)

(14.1)

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

(14.2)

Можно легко показать, что обычные подмножества Nk, k = 0,1,2,... ..., r, образуют разбиение Е и полностью и строго упорядочены отно­шением

(14.3)

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

(14.4)

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

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

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

(Некоторые авторы эти обычные подмножества называют рангами (разря­дами, категориями, классами).)

Рис. 14.3 Рис, 14.4

Пример. Обычный граф без контуров на рис. 14.3 разложен по уровням на рис. 14.4. Если Хі — вершина графа, то каждому Хі здесь соответствует Nk или просто k{0,1, ..., 5}. Функция

представленная на рис. 14.5, есть порядковая функция графа. Нумера­ция вершин показана на рис. 14.6.

Рис. 14.5 Рис. 14.6

Порядковая функция графа в общем случае не единственна: она может определяться относительно наибольших элементов (в смысле, придаваемом наибольшим и наименьшим элементам в теории обычных упорядоченных множеств) упорядоченного множества вместо наименьших; скажем, упорядоченных спра­ва налево вместо слева направо, как мы это сделали в примерах на рис. 14.3 — 14.6.

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

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

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

Пример приведен на рис. 14.7—14.10.

Рис. 14.7 Рис. 14.8

Рис. 14.9 Рис. 14.10

Метод определения уровня графа без контуров. Рассмотрим булеву матрицу обычного графа, изображенного на рис. 14.3; эта мат­рица приведена на рис. 14.11.

Рис. 14.11

В строке о подсчитаны суммы строк этой матрицы, т. е. суммы элементов в соответствующих столбцах. Нули в о дают вершины, которым не предшествует ни одна другая вершина; таким образом, вершины Е и Н составляют уровень No. Исключив из сумм строки 0 значения, записанные в стро­ках Е и Н, получим строку 1, в которой нули из о заменены знаком × (крестом). Появившиеся в строке 2 нули дают вершины, которым не предшествует ни одна другая вершина, кроме удаленных Е и Н; это вершины В, I, и J, которые образуют N1. Теперь из 1 вычтем сум­мы строк В, I и J после замены всех ранее появившихся нулей крес­тами; новые нули, появившиеся в 2, дают вершины, для которых не существует других предшествующих вершин, кроме удаленных Е, Н, В, I, J. Вершины A, G и N составляют N2. Этот процесс мы продолжаем до тех пор, пока не переберем все точки. После этого остается только построить обычный граф (рис. 14.4), в ко­тором вершины появляются на соответст­вующих им уровнях. Произвольная нумерация вершин представлена на рис. 14.6, где изображена порядковая функция.