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

то

9.2. Алгоритм Лоулера — Ири — Томидзавы построения мак­симального общего независимого множества двух матроидов. Пусть М1 и М2 — матроиды на Е. Задача состоит в отыска­нии максимального множества А*, независимого как в М1, так и в М2, т. е. А* = M1∩ М2 и В 4.3 показано, как она сводится к задаче построения базы суммы двух матроидов. Поэтому ее можно решить алгоритмами, описанными в разд. 1.9.8. Существует другой алгоритм для этой задачи. Он состоит в следующем. Если на

k-м шаге уже построено общее независимое множество Аk, то на

(k + 1)-м шаге на основе Аk либо строится общее независимое множество Ak+1 большей, чем |Аk|, мощности, либо устанавливается, что Ak =А* — максимальное общее независимое множество матроидов M1 и М2. Опишем (k + 1)-й шаг алгоритма. По множеству А=Аk строится вспомогательный ориентированный граф GA с мно­жеством вершин Е и с дугами двух типов для х А и у Е\А:

(al) (у, х) есть дуга графа GA, если хС(М1, А + у);

(а2) (х, у) есть дуга в GA, если хС(М2, А + у).

В орграфе GA ищется путь из вершины множества Е\с12А (источники) в вершины множества Е\с11 А (стоки). Здесь с11 — оператор замыкания в матроиде Мі. Если такого пути не суще­ствует, то работа алгоритма заканчивается и можно доказать, что Ak есть максимальное общее независимое множество матрои­дов М1 и М2. В противном случае находят кратчайший такой путь Р. Затем из А удаляются те элементы, которые принадле­жат Р, и добавляются элементы из Р, нe принадлежащие А; т. е. Ak+1 = Ak + P\(Ak∩P). Тогда, очевидно,

|Ak+1 | = |Ak| + 1.

Cравним данный алгоритм с алгоритмом в 3.6. Пусть В*2 — база матроида М*2, а В есть база матроида M1\B*2 ипусть λ = (B*2, В). Орграфы GB и Гλ имеют одно и то же множество вершин Е. Все дуги типа (al) из орграфа GB присутствуют и в графе Гλ. Однако дуга типа (а2) из орграфа GB находится в графе Гλ, если только у В*2, так как Е\В*2 есть база мат­роида М2. Других дуг в орграфе Гλ нет, поэтому Гλ есть просто подграф орграфа GB.

В алгоритме, описанном в 3.6, в орграфе Гλ ищут активные пути из элементов множества Е\В*2\В. Элемент х Е\В*2\В активен, если в орграфе Гλ есть путь с началом в х и концом в у с11В (т. е. у есть сток в орграфе GB). Очевидно, х с12В, так как Е\В*2— база матроида

М2 и Е\В2 (В+х).Таким образом, х — источник в орграфе GB.

Из леммы 5.8 следует, что алгоритм строит множество

.

2. Нечеткие графы и нечеткие отношения

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

2.1. Нечеткие графы

Рассмотрим два множества Е1 и Е2; пусть х обозначает элемент Е1, у — элемент Е2. Множество упорядоченных пар (х, у) определяет прямое произведение Е1 × Е2.

Нечеткое подмножествотакое, что

(1.1)

где М — множество принадлежностей элементов множества Е1 × Е2, называется нечетким графом.

Пример 1. Пусть

и (1.2)

(1.3)

(1.4)

Для упрощения обозначений положим

(1.5)

Этот элемент множества М будем называть значением упорядоченной пары (хi, уj).

Рассмотрим, например,

(1.6)

Эта функция определяет нечеткое подмножество

(1.7)

Это же нечеткое подмножество можно представить в виде матрицы (рис. 1.1).

Pис. 1.1

Граф

(1.8)

— нечеткий граф.

Граф

(1.9)

— обычный граф, рассматриваемый в теории множеств (рис. 1.2).

Pис. 1.2

Пример 2. Пусть Е1 = Е2 = R+,

где R+ — множество неотрица­тельных действительных чисел. Пусть

х R+, у R+. Рассмотрим прямое произведение R+×R+. Тогда отношение у х опреде­ляет нечеткий граф в R+2.

Предположим, что используется функция

(1.10)

Где

На рис. 1.3 наглядно представлено это нечеткое подмножество для точек у = kx, k ≥ 1.

Рис. 1.3

Пример 3. (Графы Бержа). Графом в смысле Бержа называется такой граф, что

Е1= Е2 == Е счетные, (1.11)

и граф представляет собой подмножество упорядоченных пар

такое, что

и (1.12), (1.13)

Для таких графов, представляющих лишь частный слу­чай графов, изучаемых в теории множеств, можно определить обобщение на нечеткие графы. Например, на рис. 1.4, 1.6, 1.8 и 1.10 изо­бражен один и тот же нечеткий граф Бержа, тогда как на рис. 1.5, 1.7, 1.9 и 1.11 показан один и тот же обычный граф Бержа.

Рис. 1.4 Рис. 1.5

Рис. 1.6 Рис. 1.7

Рис. 1.8 Рис. 1.9

Рис. 1.10 Рис. 1.11

Используя обозначения Бержа для обычного графа на рис. 1.5, 1.7, 1.9 и 1.11, положим

(1.14)

где Г называется многозначным отображением элемента X в элементы универсального множества Е.

Пользуясь этим обозначением, не­четкие графы, представленные различ­ным образом на рис. 1.4, 1.6, 1.8 и 1.10, запишем в виде

(1.15)

(1.15)

Пример 4. На рис. 1.12 и 1.13 изображены нечеткий и обычный графы.