Основные свойства графа

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

Традиционное задание отношений аналогично тому, как это принято в теории множеств, что не всегда удобно. Поэтому, наряду с таким заданием, применяются другие способы.

1. Матричное задание. Оно используется когда А – конечное или счетное множество А = {x_i}. Тогда бинарное отношение R можно задавать с помощью матрицы R = {x_ij}, элементы которой определяются соотношением:

2. Табличное задание. Этим способом можно задавать произвольное n-арное отношение. Он используется, когда А_i – конечные или счетные множества А_i = {x_ij}. Строки таблицы соответствуют различным n-мерным элементам отношения, столбцы – наборам элементов из множеств А_i.

3. Задание с помощью графа. Для конечного или счетного множества А бинарное отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф – фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x_i, а наличие дуги, соединяющей вершины x_i и x_j, означает, что (x_i, x_j)ÎR. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка.

1) Г(R^–1) получается из Г(R) изменением направления стрелок на противоположные.

2) Граф Г(А´А) содержит дуги, соединяющие любую пару (x_i, x_j). Такой граф называется полным.

4. Задание верхними и нижними срезами. Этот способ может быть использован для любых множеств и бинарных отношений. Пусть на множестве А задано отношение R. Верхний срез G_R(x) отношения R в точке x ÎА – это множество элементов yÎА таких, что (y, x)ÎR, т.е.

G_R(x) = { yÎA | (y, x)ÎR }.

Если рассматривать R как отношение предпочтения, то G_R (x) – это множество элементов, лучших, чем х.

Нижний срез H_R(x) отношения R в точке xÎА – это множество элементов yÎА, таких, что (x, y)ÎR, т.е.

H_R(x) = { yÎA | (x, y)ÎR }.

Свойства нижних и верхних срезов. Для любого хÎA и любого отношения R_i Í A´A выполняются соотношения.

1. а) G_RÇR(x) = G_R(x) Ç G_R(x); б) H_RÇR(x) = H_R(x) Ç H_R(x)

2. a) G_{`R</sub>(x) = A \ G<sub>R</sub>(x); б) H<sub>`R}(x) = A \ H_R(x).

3. a) G_R^–1(x) = H_R(x); б) H_R^–1(x) = H_R(x).

4. G_A´A(x) = H_A´A(x) = A.