Федоров В.Н. - Введение в теорию множеств (1023557), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

– "быть не больше".

Матрицы отношений R₁, , , R₁² , R₁°, приведены на рис. 3.8.

Эти матрицы получены по известной матрице отношения R следующим образом .

• Матрица дополнения — в матрице исходного отношения R заменены единицы нулями, а нули — единицами.

• Матрица обратного отношения R^–1 — в ней проставлены единицы, симметричные (относительно главной диагонали) соответствующим единицам исходной матрицы. Очевидно, что матрица симметричного отношения совпадает с матрицей его обратного отношения.

• Матрица составного отношения R² – в ней для каждой единицы исходной матрицы отношения R, принадлежащей i–ой строке, например единицы в j–ой компоненте, т.е. для с_ij = 1, в i–й строке вычисляемой матрицы проставлены единицы в тех к–х компонентах, в которых имеются единицы в j–ой строке исходной матрицы (см. поясняющий рис. 2.6).

• Матрица транзитивного замыкания R^о нетранзитивного отношения R — здесь необходимо выполнить серию (одну или более) итераций, заключающихся в следующем:

а) для каждой единицы исходной матрицы отношения R, принадлежащей i–ой строке, например единицы в j–ой компоненте, т.е. для с_ij = 1, в i–ой строке вычисляемой матрицы проставляются единицы в тех к–х компонентах, в которых имеются единицы в i–ой строке, а также в j–ой строке исходной матрицы (см. поясняющий рис. 3.4);

R1	1	2	3	4	5	6				1	2	3	4	5	6				1	2	3	4	5	6
1	0	1	1	1	1	1			1	1	0	0	0	0	0			1	0	0	0	0	0	0
2	0	0	1	1	1	1			2	1	1	0	0	0	0			2	1	0	0	0	0	0
3	0	0	0	1	1	1			3	1	1	1	0	0	0			3	1	1	0	0	0	0
4	0	0	0	0	1	1			4	1	1	1	1	0	0			4	1	1	1	0	0	0
5	0	0	0	0	0	1			5	1	1	1	1	1	0			5	1	1	1	1	0	0
6	0	0	0	0	0	0			6	1	1	1	1	1	1			6	1	1	1	1	1	0
a)								б)									в)
R12	1	2	3	4	5	6			R1°	1	2	3	4	5	6				1	2	3	4	5	6
1	0	0	1	1	1	1			1	0	1	1	1	1	1			1	1	1	1	1	1	1
2	0	0	0	1	1	1			2	0	0	1	1	1	1			2	0	1	1	1	1	1
3	0	0	0	0	1	1			3	0	0	0	1	1	1			3	0	0	1	1	1	1
4	0	0	0	0	0	1			4	0	0	0	0	1	1			4	0	0	0	1	1	1
5	0	0	0	0	0	0			5	0	0	0	0	0	1			5	0	0	0	0	1	1
6	0	0	0	0	0	0			6	0	0	0	0	0	0			6	0	0	0	0	0	1
г)								д)									е)

Рисунок 3.8

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

Очевидно, что матрица транзитивного замыкания R° совпадает с матрицей исходного отношения R, если отношение R транзитивно.

Характеристики

Список файлов книги