2. Теоретическое введение

2.1. Общие понятия бинарных отношений

Бинарные отношения – это отношения, которые могут выполняться или не выполняться между элементами одного множества. Если –– множество решений (альтернатив), тогда отношение на множестве - это подмножество , т.е. - множество пар , определённые на декартовом произведении ( ), для которых выполняется определённое (заданное) свойство.

Обозначение для отношения .

Если пара , то ( находится в отношении с ). Множество – область задания отношений (отношения ).

Способы задания отношений:

1. Задание матрицей. Если множество состоит из элементов, то элементы могут быть проидентифицированы индексами такими, что ; тогда для решений может быть введена в рассмотрение матрица размерности .

При этом если , то, a_ij=1; если не является верным (т.е. ), то a_ij=0, тогда общее правило определения элементов матрицы следующее ( ):

при этом ; .

Пример 1. Задание вида матрицы ( при ).

Заметим, что a_ii=0, (т.е. в данном (общем) рассматриваемом случае ).

2. Задание графом. Графом называется пара , где – конечное множество вершин, (гамма) – конечное подмножество произведения , множество дуг, соединяющих вершины; дугу, соединяющую вершину с вершиной , обозначим как .

Если множество решений (альтернатив) однозначно соответствует множеству вершин графа , тогда дуга соединяет две вершины и в том случае, если выполнено отношение .

Если задан граф с n вершинами (где ), нумерация вершин соответствует нумерации решений (альтернатив) из , тогда на графе (для элементов множества ) задаётся отношение такое, что при на графе определяется дуга (формируется дуга) .

Пример 2. Задание графа отношения (Рисунок 1).

а)

б)

Рисунок 1 – Виды графов отношений

3. Задание сечением. Верхнее сечение множества (отношения) обозначается как (т.е. определяется для каждого элемента множества ) и формируется в соответствии с выражением вида:

.

Если – отношение предпочтения (доминирования), то для элемента верхнее сечение отношения – это те решения , которые предпочтительнее, чем рассматриваемое решение . Нижнее сечение отношения определяется аналогичным образом:

Таким образом, – те элементы (решения) , которые находятся с элементом в отношении ; – те элементы (решения ), с которыми фиксированный элемент находится в отношении .

Отношения специального вида.

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

2. Полное отношение. Отношение называется полным, если оно выполняется для всех пар . Полное отношение обозначается Р. Тогда такая, что для всех индексов , ; граф такой, что дуги соединяют любую пару вершин; для любого .

Операции над отношениями.

1. Вложение отношений. Отношение вложено или включено в отношение (обозначается ), если множество пар , для которых выполнено отношение , содержится в множестве пар, для которых выполнено отношение . Если , то либо , либо .

2. Дополнение отношения . Отношение называется дополнением отношения , если оно выполняется для тех пар , для которых не выполняется отношение . Таким образом, если , то (т.е. ). Тогда , граф содержит те дуги, которые отсутствуют в графе .

3. Обратное отношение. Обратным к отношению называется отношение , определяемое условием:

.

Если – отношение «меньше» на множестве действительных чисел, то обратное отношение – «больше». Для обратного отношения справедливо:

1) при , ;

2) граф получается из графа изменением направления дуг.

Свойства отношений

1. Рефлексивность. Отношение называется рефлексивным, если . Тогда:

а) в матрице рефлексивного отношения на главной диагонали заданы 1;

б) в графе при каждой вершине имеется петля.

Соответственно, если отношение антирефлексивно, то выражение вида не является верным, в этом случае диагональные элементы матрицы равны 0.

2. Симметричность. Отношение - симметрично, если из вытекает . Тогда:

а) матрица отношения симметрична, т.е. .

б) каждая вершина графа имеет исходящую дугу и входящую дугу .

3. Асимметричность. Для пары выполняется либо , либо , т.е. если выполняется, то нет. В этом случае граф не может содержать одновременно дуги и (содержит одну из этих дуг).

4. Антисимметричность. Для антисимметричного отношения выражения и справедливы тогда, когда . Для антисимметричного отношения граф не может одновременно содержать дуги и при .

5. Транзитивность. Из и следует .

6. Ацикличность. Из , ,…, следует, что (т.е. путь на графе не является циклом).

Виды отношений, используемых в ТПР

1. Отношение эквивалентности ~ (вид отношения, связывающего пару решений – ~ . Свойства отношения: рефлексивно ~ ), симметрично ~ и ~ , транзитивно ~ , ~ , ~ . Отношение эквивалентности ~ определяет, что два решения и эквивалентны.

2. Отношение нестрогого (частичного) порядка определяет, что решение не хуже, чем решение (т.е. лучше или эквивалентно). Таким образом для пары решений выполняется либо либо ~ . Свойства отношения: рефлексивность ( ), антисимметричность (если и , то ~ ), транзитивность (если и , то ). Таким образом, отношение позволяет реализовывать упорядоченность решений при возможной их эквивалентности.

3. Отношение строгого порядка (т.е. решение строго лучше, чем ). Свойства отношения: антирефлексивность ( не является верным), антисимметричность (если верно , то - не верно и наоборот). Отношение также соответствует отношению строгого предпочтения (доминирования). Т.е. при решение строго предпочтительнее решения , решение доминирует решение .

Тогда с использованием отношений и ~ может быть определён порядок (предпочтительность, доминирование) решений.

Пример 3. Задание вида порядка решений.

~