2014-02-24
1438
1. Обращение отношений — это изменение порядка первой и второй компоненты пар. Если пара (a, b) 
, то пара (b, a) 
. Графически операция обращения отражается изменением направления стрелки:
Таблично обращение означает замену строки столбцом, а столбца строкой. Обращение соответствует операции транспонирования булевой матрицы отношений.
2. Умножение отношений.
Две пары называются примыкающими, если вторая компонента первой пары равна первой компоненте второй пары. Пусть пары (a, b), (b, c) — примыкающие. Тогда произведение примыкающих пар определяется следующим образом: (a, b)*(b, c)=(a, c)
Произведением отношений 
и 
называется новое отношение 
, состоящее из произведений всех примыкающих пар, первая из которых принадлежит отношению , а вторая пара принадлежит отношению . Если пары (a, b) , пары (b, c) 
,, то пары (a, c) 
Пример Пусть — отношение “быть женой”, пусть — отношение “быть отцом”, тогда 
означает, что существует такое z, с которым x и y образуют примыкающие пары, то есть что
. В принятом смысле отношений это означает, что x — жена z, z — отец y, следовательно, означает, что x — мать y
|
|
|
Графически, принадлежность пары (a, c) произведению отношения 
означает, что из a в с можно попасть за два шага; первый шаг по дуге с отношением , а второй — с отношением :
Если отношения заданы своими графами, то произведение этих отношений можно получить, перемножая матричные представления их графов.
Пример. Пусть заданы графы отношений
Запишем матричные представления этих графов
Матрица графа :
| a | b | c | |
| a | |||
| b | |||
| c |
Матрица графа :
| a | b | c | |
| a | |||
| b | |||
| c |
Перемножим эти матрицы. Получим матрицу произведения отношений.
| a | b | c | |
| a | |||
| b | |||
| c |
Этой матрице соответствует граф произведения отношений
Связь (с, а) образовалась от примыкающих пар (с, b) из графа отношения и (b, a) из графа отношения , а кольцевая связь (с, с) – от примыкающих пар (с, b) из графа отношения , и (b, с) из графа отношения.
