Бинарные отношения и графы

Бинарное отношение 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.

До каз а тельст во. Достаточность. Предположим, что отображение ϕ обладает указанным свойством. Тогда для любого цикла v 0, v 1, …, vn, v 0 = vn, в графе G (R) имеем:

ϕ(v 0) < ϕ(v 1) <…< ϕ(vn) = ϕ(v 0),

что невозможно при n > 0.

Необходимость. Пусть n = | V | – число элементов множества V. Для произвольного x ∈ V рассмотрим множество всевозможных простых цепей в графе G (R), заканчивающихся в вершине x. Ни одна из этих цепей не содержит более чем n вершин, так что их длины ограничены в совокупности. Положим ϕ(x) = k, где k – максимальная из длин простых цепей, заканчивающихся в вершине x. Если нет ни одной цепи, ведущей в x, то есть ни одна дуга не заканчивается в x, полагаем ϕ(x)=0. Покажем, что так определенное отображение ϕ обладает нужным свойством. Предположим, что xRy. Пусть ϕ(x)= k. Тогда в графе G (R) имеется простая цепь v 0, v 1, …, vk = x. Добавив к этой цепи дугу из x в y, мы получим маршрут v 0, v 1, …, vk = x, y (длины k +1). Этот маршрут является простой цепью. В самом деле, так как цепь v 0, v 1, …, vk простая, все вершины в ней различны. Если y совпадает с одной из вершин этой цепи, скажем y = vi, получается цикл y = vi, v 1, …, 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).

С другой стороны, в соответствии с определением функции

выбора CR имеем:

Следовательно,

x ∈ CR (X)⇔ ∀ y ∈ X (yRx)}.

x ∈ C (X) ⇒ x ∈ CR (X),

то есть C (X) ⊂ CR (X).

Деревья

Не нашли, что искали? Воспользуйтесь поиском: