Бинарное отношение R на конечном множестве V может быть представлено ориентированным графом G(R), называемым графом отношения R. Вершинами графа служат элементы множества V; вершины x и y соединены направленной дугой с началом x и концом y, если (x,y)∈R. Обратно, всякий ориентированный граф без параллельных дуг G задает бинарное отношение R(G) на множестве своих вершин, чьим графом он и
является: вершины x и y связаны отношением R(G), если они соединены направленной дугой с началом x и концом y. Если R
– бинарное отношение на конечном множестве V = {1, 2, …, n}, а G – граф c вершинами V = {1, 2, …, n}, то матрица смежности графа G совпадает с характеристической матрицей отношения R в том и только том случае, когда G = G(R) или, что равносильно, R = R(G).
Рассмотрим, как связаны свойства отношения R и соответствующего ему графа G = G(R).
Отношение R симметрично, если для любых x, y∈V из xRy следует yRx. Иными словами, если на ориентированном графе G имеется дуга из x в y, то имеется также и дуга из y в x. В этом случае матрица смежности графа G симметрична. По существу, граф G оказывается неориентированным. Можно считать, что симметричным отношениям отвечают неориентированные графы. Антисимметричность отношения R означает, что xRy и yRx влечет x = y и равносильна тому, что две различные вершины графа G могут быть связаны дугой лишь в одном направлении. Если отношение R асимметрично, то есть xRy влечет yRx, то, кроме того, граф G не должен иметь петель.
Если R – рефлексивное отношение, то есть xRx для любого
x∈V, то граф G имеет петлю в каждой вершине, а диагональ матрицы смежности состоит из одних единиц. Соответственно отношение R антирефлексивно тогда и только тогда, когда граф G не имеет петель.
Отношение R транзитивно, если из xRy и yRz следует xRz. Для графа G это означает, что если G содержит дуги из x в y и из y в z, то он содержит и дугу из x в z. Более того, если существует путь из вершины x в вершину y, то имеется и дуга из x в y.
В терминах графа G = G(R) простую интерпретацию получает понятие транзитивного замыкания отношения R. На множестве вершин графа G определим отношение достижимости R^, полагая xR^y тогда и только тогда, когда вершина y достижима из вершины x (в графе G имеется путь из x в y). Отношение достижимости R^ является транзитивным замыканием отношения R, то есть R^ – это наименьшее транзитивное отношение, содержащее R. Матрицей отношения R^ служит матрица E ∨ A ∨ A[k] ∨…∨ A[n–1], где A – матрица
смежности графа G.
Отношение R называется ацикличным, если граф G(R) не содержит нетривиальных циклов. Если вершины x и y на графе ацикличного отношения R соединены некоторым путем, то в этом графе нет дуги из y в x.
Теорема.Отношение R на конечном множестве V ациклично тогда и только тогда, когда существует отображение ϕ:V→N такое, что xRy влечет ϕ(x) < ϕ(y) для любых x,y∈V.
До каз а тельст во . Достаточность. Предположим, что отображение ϕ обладает указанным свойством. Тогда для любого цикла v0, v1, …,vn, v0 = vn, в графе G(R) имеем:
ϕ(v0) < ϕ(v1) <…< ϕ(vn) = ϕ(v0),
что невозможно при n > 0.
Необходимость. Пусть n = |V| – число элементов множества V. Для произвольного x∈V рассмотрим множество всевозможных простых цепей в графе G(R), заканчивающихся в вершине x. Ни одна из этих цепей не содержит более чем n вершин, так что их длины ограничены в совокупности. Положим ϕ(x) = k, где k – максимальная из длин простых цепей, заканчивающихся в вершине x. Если нет ни одной цепи, ведущей в x, то есть ни одна дуга не заканчивается в x, полагаем ϕ(x)=0. Покажем, что так определенное отображение ϕ обладает нужным свойством. Предположим, что xRy. Пусть ϕ(x)=k. Тогда в графе G(R) имеется простая цепь v0, v1, …,vk = x. Добавив к этой цепи дугу из x в y, мы получим маршрут v0, v1, …,vk = x, y (длины k+1). Этот маршрут является простой цепью. В самом деле, так как цепь v0, v1, …, vk простая, все вершины в ней различны. Если y совпадает с одной из вершин этой цепи, скажем y = vi, получается цикл y = vi, v1, …,vk = x, y, что противоречит ацикличности отношения R. Следовательно, имеется простая цепь длины k+1, заканчивающаяся в y. Значит, ϕ(y) ≥ k+1 и потому ϕ(y) > ϕ(x).
Пример.Рассмотрим бинарное отношение R, граф которого
G(R) представлен на рис 9.
1 2
4 3
Рис. 9
В соответствии с определением отображения ϕ находим:
ϕ(1) = 0; ϕ(2) = 1; ϕ(3) = 2; ϕ(4) = 3.
Из предыдущей теоремы следует, что функция выбора CR (блокировка), построенная по ацикличному отношению R, является расширением некоторой функции выбора по скалярному критерию. В самом деле, пусть Ω = {1, 2, …, n} – множество альтернатив, а R – ацикличное бинарное отношение на Ω. Тогда, по предыдущей теореме, на множестве Ω существует числовая функция ϕ :{1, 2, …, n}→N такая, что iRj влечет ϕ(i) < ϕ(j). Зададим функцию f (скалярный критерий), полагая f(i) = n – ϕ(i). Ясно, что iRj влечет f(i) > f(j). Следовательно, f(i) ≤ f(j) влечет iRj. Обозначим через C функцию выбора по скалярному критерию f. Тогда
x∈C(X) ⇔ ∀y∈X f(x) ≥ f(y).
С другой стороны, в соответствии с определением функции
4 3