Композиция отношений

Пусть даны три множества X, Y, Z и два отношения и . Композиция отноше­ний А и В есть отношение С=А ° В, состоящее из всех тех пар , для которых существует такое у Î Y, что (х, у) Î А и (у, z) Î В.

Сечение отношения С=А ° В по х совпадает с сечением отношения В по подмножеству А(х)Î Y, т. е. С(х) = В (А(х)).

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

Матрица композиции отношений является произведением матриц исходных отношений, взятых в обратном порядке, с заменой всех ненулевых элементов на 1.

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

Тогда

Граф композиции этих отношений приведен на рис. 2.3.

Рис. 2.3. Граф композиции С=А ° В

;